List源码

发表于 | 分类于

ArrayList

ArryList 的底层实现是数组队列。与 Java 中数组不同的是，它的容量能够动态的增长。

继承自 AbstractList, 实现了 List，RandomAccess，Cloneable，Serializable 这些接口。

在 ArrayList 中，很多地方使用了 System.arraycopy() 和 Arrays.copyOf() 这两个方法来复制数组。

比如在 add(int index, E element) 在指定位置插入元素的方法中就巧妙的使用了 arraycopy() 这个方法来复制数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
* arraycopy() 的五个参数依次是:被复制的数组，被复制的坐标，复制到的数组，复制的坐标，复制多少个
*/
public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //arraycopy()方法实现数组自己复制自己
        //elementData:源数组;index:源数组中的起始位置;elementData：目标数组；index + 1：目标数组中的起始位置； size - index：要复制的数组元素的数量；
        System.arraycopy(elementData, index, elementData, index + 1, size - index);
        elementData[index] = element;
        size++;
    }

在 toArray() 方法中又使用了 copyOf() 方法

1
2
3
4
5
6
7
/**
* copyOf() 方法的参数:被复制的数组，复制多少个
*/
public Object[] toArray() {
    //elementData：要复制的数组；size：要复制的长度
    return Arrays.copyOf(elementData, size);
}

copyOf() 实际上是调用了 arraycopy() 方法的

  • arraycopy() 方法是需要实现创建一个目标数组，再将原数组拷贝至目标数组

  • copyOf() 方法不需要实现创建一个目标数组，在方法内部自动创建一个数组，并返回该数组.

另外需要注意的是：

  1. Java 中的length 属性是针对数组说的,比如说你声明了一个数组,想知道这个数组的长度则用到了 length 这个属性.
  2. Java 中的length()方法是针对字 符串String说的,如果想看这个字符串的长度则用到 length()这个方法.
  3. Java 中的size()方法是针对泛型集合说的,如果想看这个泛型有多少个元素,就调用此方法来查看!

LinkedList

LinkedList 是一个实现了 List 接口和 Deque 的双端接口。底层实现是双向链表，支持高效的插入删除操作。

LinkedList 不是线程安全的

add方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public boolean add(E e) {
    linkLast(e);
    return true;
}

/**
* 链接使e作为最后一个元素。
*/
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++;
}

根据索引位置得到数据的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public E get(int index) {
    //检查index范围是否在size之内
    checkElementIndex(index);
    //调用Node(index)去找到index对应的node然后返回它的值
    return node(index).item;
}

Node<E> node(int index) {
    // assert isElementIndex(index);
	// 判断 当前位置是更靠近左边还是右边
    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;
    }
}