<数据结构>线性顺序表应用ArrayList源码分析

204 阅读2分钟

数据结构-1-线性表中的顺序存储表(数组)

前面描述了线性表的顺序存储结构顺序表的各种操作,Java中ArrayList的实现就是数组

ArrayList

  • 基于顺序表数组实现,允许空值以及null,可自动扩容
  • 线程不安全
基本操作
List<String> list = new ArrayList();
list.add("data1");
list.add(0,"data2");
list.get(0);
list.remove(0);
list.clear();
构造方法
//默认初始容量
private static final int DEFAULT_CAPACITY = 10;
//
private static final Object[] EMPTY_ELEMENTDATA = {};
//默认占位数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData;
private int size;//当前数据元素个数

public ArrayList() {//一般使用此构造方法
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
添加元素
  1. 尾部添加
    1f17df85759cceba121b9697ea859ef0.png
public boolean add(E e) {
    ensureCapacityInternal(size + 1);//判定并给出可以放置新元素的空间
    elementData[size++] = e;//赋值
    return true;
}
  1. 指定位置插入
    81811f27ccde802be439c808c977f834.png
public void add(int index, E element) {
    //检查index的合法性
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    //判定并给出可以放置新元素的空间
    ensureCapacityInternal(size + 1);
    //将index之后的数据后移一位
    System.arraycopy(elementData, index, elementData, index + 1, size - index);
    elementData[index] = element;//赋值
    size++;
}
  1. 判定并给出可以放置新元素的空间有两种可能
  • 空间足够,直接赋值
  • 空间不够了,需扩容后赋值
//计算最小容量
private void ensureCapacityInternal(int minCapacity) {
    //刚初始化状态下,首次添加数据时默认先给数组DEFAULT_CAPACITY空间
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;//根据api解释,modCount是指操作list多少次
    //当新计算的最小容量比当前数组容量大时,扩容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
private void grow(int minCapacity) {//扩容方法
    int oldCapacity = elementData.length;//原数组长度
    int newCapacity = oldCapacity + (oldCapacity >> 1);//扩容至原数组的1.5倍
    //扩容后的长度仍比最小容量小,直接使用最小容量,一般在空list刚添加第一条数据时触发
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)//数组太大了,一般也不会触发吧
        newCapacity = hugeCapacity(minCapacity);//溢出判定
    //建立一个新的数组,将原数组中的数组复制进来
    elementData = Arrays.copyOf(elementData, newCapacity);
}
获取元素
public E get(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    return (E) elementData[index];
}
删除元素

27c52aec9c7752145c155512834fab33.png

public E remove(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

    modCount++;
    E oldValue = (E) elementData[index];

    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

数据删除后,并没有自动缩容机制,可手动触发

86bb5c2b5cb51931ffc61e9a6e1b3e42.png

public void trimToSize() {
    modCount++;
    if (size < elementData.length) {
        elementData = (size == 0)
          ? EMPTY_ELEMENTDATA
          : Arrays.copyOf(elementData, size);
    }
}
清空
 public void clear() {
    modCount++;
    // clear to let GC do its work
    for (int i = 0; i < size; i++)
        elementData[i] = null;

    size = 0;
}