专栏首页Java系列学习与数据结构算法数据结构与算法系列2 线性表 使用java实现动态数组+ArrayList源码详解

数据结构与算法系列2 线性表 使用java实现动态数组+ArrayList源码详解

数据结构与算法系列2 线性表 使用java实现动态数组+ArrayList源码详解

对数组有不了解的可以先看看我的另一篇文章,那篇文章对数组有很多详细的解析,而本篇文章则着重讲动态数组,另一篇文章链接如下,可点击跳转: 链接:https://blog.csdn.net/pjh88/article/details/107166950

什么是数组与动态数组?

数组

数组是相同数据类型的元素按照一定的顺序排列的集合,若将有限个类型相同的变量的集合命名,那么这个名称称为数组名,组成数组的各个变量称为数组的分量,也称为数组的元素,有时爷称为下标变量,用于区分数组的各个元素的数组编号称为下标。数是程序设计中,为了处理方便把具有相同类型的若干变量按有序的形式组织起来的一种形式,这些按序排序的同类元素的集合称为数组

动态数组

顾名思义,动态数组即可以动态扩容的数组,一般的数组是不能扩容的,及在创建数组对象的时候就规定了数组的大小,规定数组是多大就是多大,后期不可以存储多余的元素 动态数组的好处也显而易见: 1.动态的增加和减少元素 2.实现collection和list接口 3.灵活设置数组的大小

java中已经给我们封装好了一个动态数组Arraylist的类,我们可以直接使用,其内部有许多方法,我们先来看看有什么方法,下面仅仅讲我们经常使用到的方法那些不怎么使用的我们在这就不讲了:

int size();元素的数量
boolean isEmpty();是否为空
boolean contains(E element); 判断是否包含某个元素
void add(E element) ;添加元素到最后
E get(int index);返回index对应位置的元素
E set(int index,E element);往index位置添加元素
void add(int index,E element);往index位置添加元素
E remove(int index); 删除index位置对应的元素
int indexOf(E element); 查看元素的位置
void clear();清除所有元素

接下来我们逐一讲解这些方法

定义的变量

    //元素的数量
    private int size;
    //存储元素
    private E[] elements;
    //初始化大小
    private static  final int DEFAULT_CAPACITY=16;
    //元素没有找到时的放回值
    private static  final int ELEMENT_NOT_FOUND=-1;

构造方法

 //自定义大小
    public ArrayList(int capacity){
        //如果传入的大小小于默认数组的大小,则使用默认的大下
        capacity= (capacity<DEFAULT_CAPACITY)?DEFAULT_CAPACITY:capacity;
        elements=(E[])new Object[capacity];
    }


    //默认大小的构造方法
    public  ArrayList(){
        this(DEFAULT_CAPACITY);
    }

判断index的范围有没有越界

public void rangeCheak(int index){
        if (index<0||index>size){
            outofBounds(index);
        }
    }

获取指定位置的元素

public E get(int index){
        rangeCheak(index);
        return  elements[index];
    }

重新设定指定位置的元素

 public E set(int index,E element){
        //检查插入位置是否合法
        rangeCheak(index);
        //返回原来的元素
        E oldelement1 = elements[index];
        //插入新的元素
        elements[index]=element;
        return oldelement1;
    }

判断是否为空

 public boolean isEmpty(){
        return size==0;
    }

返回元素的数量

 public int size(){
        return  size;
    }

判断是否包含某个指定元素

public boolean contains(E element){
        return indexOf(element)!=ELEMENT_NOT_FOUND;
    }

返回指定元素的位置

public int indexOf(E element){
     if (element==null){
         for (int i = 0; i < size; i++) {
             if (elements[i]==null){
                 return  i;
             }
         }
     }else{
         for (int i = 0; i < size; i++) {
             if (element.equals(elements[i])){
                 return i;
             }
         }
     }
     return  ELEMENT_NOT_FOUND;
    }

在末尾插入元素

public void add(E element){
        add(size,element);}

在指定位置插入元素

public void   add(int index,E element){
        //检查范围
        rangeCheakForadd(index);
        //判断容量是否足够
        ensureCapacity(size+1);
        for (int i = size; i > index; i--) {
            elements[i]=elements[i-1];
        }
        elements[index]=element;
        size++;
    }

检查插入范围

public void rangeCheakForadd(int index){
        if (index<0||index>size){
            outofBounds(index);
        }
    }

移除指定位置的元素

 public  E remove(int index){
        //检查范围
        rangeCheak(index);
        E removeElement = elements[index];
        for (int i=index+1;i<size;i++) {
            elements[i-1]=elements[i];
        }
        elements[--size]=null;
        return removeElement;
    }

清除所有元素

public void clear(){ for (int i = 0; i < size; i++) { elements[i]=null; } }

其实动态数组最重要的一个方法就是扩容,下面来重点讲解

public void ensureCapacity(int capacity){
        int oldcapacity = elements.length;
        //如果比原来小则不做改变
        if (oldcapacity>= capacity){
            return;
        }
        //使用位运算,速度更快
        //我这里用的是二倍扩容,这里的扩容大小可以自己来设置,以达到最高的使用率
        int newCapacity=oldcapacity+(oldcapacity>>1);
        E[] newElements = (E[]) new Object[newCapacity];
        for (int i = 0; i < size; i++) {
            newElements[i]=elements[i];
        }
        //将elements的地址赋值新的地址
        elements=newElements;
        System.out.println(oldcapacity+"扩容为:"+newCapacity);
    }

复写toString()方法

@Override
    public String toString(){
        //使用StringBuilder
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append('[');
        for (int i = 0; i < size; i++) {
            if (i!=0){
                stringBuilder.append(",");
            }
            stringBuilder.append(elements[i]);
        }
        stringBuilder.append(']');
        return  stringBuilder.toString();
    }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • java数组详解

    一只胡说八道的猴子
  • 数据结构与算法系列2 线性表 链表的分类+使用java实现链表+链表源码详解

    链表是一种物理存储单元上非连续,非顺序的存储结构,数据元素的逻辑顺序是通过链表的链接次序实现的一系列节点组成,节点可以在运行时动态生成,每个节点包括两个部分,一...

    一只胡说八道的猴子
  • Maven是什么? Maven的概念+作用+仓库的介绍+常用命令

    Maven是一个项目管理工具,它包含了一个对象模型。一组标准集合,一个依赖管理系统。和用来运行定义在生命周期阶段中插件目标和逻辑。 核心功能 Maven的核...

    一只胡说八道的猴子
  • 精解四大集合框架:List核心知识总结

    Java集合框架早也是个老话题了,今天主要是总结一下关于Java中的集合框架List的核心知识点。肯定有人会问,这篇写的是List那接下来就还有三篇?是的,ja...

    田维常
  • 封装Python列表实现多下标访问

    class MyArray(object): def __init__(self, values): #values can be of...

    Python小屋屋主
  • LintCode 合并排序数组 II题目代码

    合并两个排序的整数数组A和B变成一个新的数组。 注意事项 你可以假设A具有足够的空间(A数组的大小大于或等于m+n)去添加B中的元素。

    desperate633
  • 【算法】堆排序

    堆是一种树形结构,在排序的过程中,把元素看成是一颗完全二叉树。用数组来表示一颗完全二叉树的话,对于每个节点 i 存在以下关系: 1)父节点 = (i - 1)...

    MapleYe
  • ES运维实战之系统性能调优

    文件句柄 Linux中,每个进程默认打开的最大文件句柄数是1000,对于服务器进程来说,显然太小,通过修改/etc/security/limits.conf来增...

    暴走大数据
  • 看得见的数据结构Android版之表的数组实现(数据结构篇)

    张风捷特烈
  • [算法题] 使用数组实现栈和队列

    CoderJed

扫码关注云+社区

领取腾讯云代金券