ArrayList源码分析

后端开发

ArrayList源码分析和队列（数组为基础的数据结构）

数组是一个经常使用的数组结构，存储形式一般分为顺序存储和链式存储，区别在于顺序存储占用一块连续内存空间，而链表是由一个个点组成。

这里我们详细分析一下ArrayList，及List的一个实现类，也是实际过程中使用较多。

ArrayList采用数组来存储数据。

存储本身：ArrayList采用 Object[] 的方式存储，因为Object是一切类的父类。

这里需要提到一下泛型和Object的区别

泛型：把运行时期提前到编译
Object: 需要进行强制类型转化

1 ArrayList

1.1 初始化

List<String> list = new ArrayList<String>(10);

private static final Object[] EMPTY_ELEMENTDATA = {}

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

 /**
  * Constructs an empty list with the specified initial capacity.
  *
  * @param  initialCapacity  the initial capacity of the list
  * @throws IllegalArgumentException if the specified initial capacity
  *         is negative
  */
 public ArrayList(int initialCapacity) {
     if (initialCapacity > 0) {
         this.elementData = new Object[initialCapacity];
     } else if (initialCapacity == 0) {
         this.elementData = EMPTY_ELEMENTDATA;
     } else {
         throw new IllegalArgumentException("Illegal Capacity: "+
                                            initialCapacity);
     }
 }

1.2 插入

/**
 * Appends the specified element to the end of this list.
 *
 * @param e element to be appended to this list
 * @return <tt>true</tt> (as specified by {@link Collection#add})
 */
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

1.2 .1数组扩容

数组是定长的，如果超过原来定长长度，扩容则需要申请新的数组长度，并把原数组元素拷贝到新数组中。

判断长度是否充足
```
ensureCapacityInternal(size + 1);
```
当判断长度不足时，则通过扩大函数，进行扩容
```
grow(int minCapacity);
```
扩容的长度计算

int newCapacity = oldCapacity + (oldCapacity >> 1);

当扩容完以后，就需要进行把数组中的数据拷贝到新数组中
```
Arrays.copyOf(elementData, newCapacity);
//底层是System.arraycopy
```

1.2.2 指定位置插入

容量验证

public void add(int index, E element) {
    rangeCheckForAdd(index);
    
    ...
}

private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

添加到指定位置之前要先进行容量验证，每插入一个元素，size++.

插入指定位置时，别的元素会发生迁移

public void add(int index, E element) {
	...
	// 判断是否需要扩容以及扩容操作
	ensureCapacityInternal(size + 1);
    // 数据拷贝迁移，把待插入位置空出来
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    // 数据插入操作                  
    elementData[index] = element;
    size++;
}

判断size，是否可以插入。
判断插入后是否需要扩容；ensureCapacityInternal(size + 1);。
数据元素迁移，把从待插入位置后的元素，顺序往后迁移。
给数组的指定位置赋值，也就是把待插入元素插入进来。

1.3 删除

public E remove(int index) {
    rangeCheck(index);
    modCount++;
    E oldValue = 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;
}

校验是否越界；rangeCheck(index);
计算删除元素的移动长度numMoved，并通过System.arraycopy自己把元素复制给自己。
把结尾元素清空，null。

2. LinkedList

Linked + List = 链表 + 列表 = LinkedList = 链表列表, LinkedList，是基于链表实现，由双向链条next、prev组成的双向链表。

2.1 初始化

直接进行初始化，并不需要创建数组。

2.2 插入

2.2.1 头插法

private void linkFirst(E e) {
    final Node<E> f = first;
    final Node<E> newNode = new Node<>(null, e, f);
    first = newNode;
    if (f == null)
        last = newNode;
    else
        f.prev = newNode;
    size++;
    modCount++;
}

2.2.2 尾插法

void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

2.2.3 指定位置插入

public void add(int index, E element) {
    checkPositionIndex(index);
    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}

//定位
Node<E> node(int index) {
    // assert isElementIndex(index);
    //size >> 1 判断元素位置在左还是有，二分
    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}
// 具体插入
void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}

2.3 删除

// 定位
public boolean remove(Object o) {
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}
// 删除元素
 E unlink(Node<E> x) {
    // assert x != null;
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;
    
    if (prev == null) {
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }
    
    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }
    
    x.item = null;
    size--;
    modCount++;
    return element;
}

3.Stack

java的Stack类继承于Vector ，但是不被推荐使用，原因在于Stack实现类有方法锁。

public class Stack<E> extends Vector<E> 

public synchronized void addElement(E obj) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = obj;
}

synchronized 进行方法锁粒度太粗

如果觉得文章对你有用，请随意赞赏

ArrayList源码分析

http://101.132.42.116:8090/archives/arraylistyuan-ma-fen-xi-he-dui-lie

作者

MirrorML

发布于

2025-01-07

更新于

2025-02-10

许可协议

CC BY 4.0

ArrayList源码分析

ArrayList源码分析和队列（数组为基础的数据结构）

1 ArrayList

1.1 初始化

1.2 插入

1.2 .1数组扩容

1.2.2 指定位置插入

1.3 删除

2. LinkedList

2.1 初始化

2.2 插入

2.2.1 头插法

2.2.2 尾插法

2.2.3 指定位置插入

2.3 删除

3.Stack

作者

发布于

更新于

许可协议

评论