关于arraylist:源码分析ArrayList和LinkedList如何实现的我看你还有机会

文章曾经收录在 Github.com/niumoo/JavaNotes，更有 Java 程序员所须要把握的外围常识，欢送 Star 和指教。
欢送关注我的公众号，文章每周更新。

前言

说真的，在 Java 应用最多的汇合类中，List 相对占有一席之地的，它和 Map 一样实用于很多场景，十分不便咱们的日常开发，毕竟存储一个列表的需要随处可见。尽管如此，还是有很多同学没有弄明确 List 中 ArrayList 和 LinkedList 有什么区别，这几乎太遗憾了，这两者其实都是数据结构中的 根底内容 ，这篇文章会从 根底概念 开始，剖析两者在 Java 中的 具体源码实现，寻找两者的不同之处，最初思考它们应用时的注意事项。

这篇文章会蕴含以下内容。

1. 介绍线性表的概念，具体介绍线性表中 数组 和链表 的数据结构。
2. 进行 ArrayList 的源码剖析，比方存储构造、扩容机制、数据新增、数据获取等。
3. 进行 LinkedList 的源码剖析，比方它的存储构造、数据插入、数据查问、数据删除和 LinkedList 作为队列的应用形式等。
4. 进行 ArrayList 和 LinkedList 的总结。

线性表

要钻研 ArrayList 和 LinkedList，首先要弄明确什么是 线性表，这里援用百度百科的一段文字。

线性表是最根本、最简略、也是最罕用的一种数据结构。线性表（linear list）是数据结构的一种，一个线性表是 n 个具备雷同个性的数据元素的无限序列。

你必定看到了，线性表在数据结构中是一种 最根本、最简略、最罕用 的数据结构。它将数据一个接一个的排成一条线（可能逻辑上），也因而线性表上的每个数据只有前后两个方向，而在数据结构中，数组、链表、栈、队列 都是线性表。你能够设想一下整整齐齐排队的样子。

看到这里你可能有疑难了，有线性表，那么必定有 非线性表 喽？没错。二叉树 和图 就是典型的非线性构造了。不要被这些花里胡哨的图吓到，其实这篇文章非常简单，心愿同学急躁看完 点个赞。

数组

既然晓得了什么是线性表，那么了解数组也就很容易了，首先数组是线性表的一种实现。数组是由 雷同类型 元素组成的一种数据结构，数组须要调配 一段间断的内存 用来存储。留神关键词，雷同类型 ， 间断内存，像这样。

不好意思放错图了，像这样。

下面的图能够很直观的体现数组的存储构造，因为数组内存地址间断，元素类型固定，所有具备 疾速查找 某个地位的元素的个性；同时也因为数组须要一段间断内存，所以长度在初始化 长度曾经固定，且不能更改。Java 中的 ArrayList 实质上就是一个数组的封装。

链表

链表也是一种线性表，和数组不同的是链表 不须要间断的内存 进行数据存储，而是在每个节点里同时 存储下一个节点 的指针，又要留神关键词了，每个节点都有一个指针指向下一个节点。那么这个链表应该是什么样子呢？看图。

哦不，放错图了，是这样。

上图很好的展现了链表的存储构造，图中每个节点都有一个指针指向下一个节点地位，这种咱们称为 单向链表 ；还有一种链表在每个节点上还有一个指针指向上一个节点，这种链表咱们称为 双向链表。图我就不画了，像上面这样。

能够发现链表不用间断内存存储了，因为链表是通过节点指针进行下一个或者上一个节点的，只有找到头节点，就能够以此找到前面一串的节点。不过也因而，链表在 查找或者拜访某个地位的节点 时，须要 O(n) 的工夫复杂度。然而插入数据时能够达到 O(1) 的复杂度，因为只须要批改节点指针指向。

ArratList

下面介绍了线性表的概念，并举出了两个线性表的理论实现例子，既数组和链表。在 Java 的汇合类 ArrayList 里，实际上应用的就是数组存储构造，ArrayList 对 Array 进行了封装，并减少了不便的插入、获取、扩容等操作。因为 ArrayList 的底层是数组，所以存取十分迅速，然而增删时，因为要挪动前面的元素地位，所以增删效率绝对较低。那么它具体是怎么实现的呢？无妨深刻源码一探到底。

ArrayList 存储构造

查看 ArrayList 的源码能够看到它就是一个简略的数组，用来数据存储。

/**
 * The array buffer into which the elements of the ArrayList are stored.
 * The capacity of the ArrayList is the length of this array buffer. Any
 * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
 * will be expanded to DEFAULT_CAPACITY when the first element is added.
 */
transient Object[] elementData; // non-private to simplify nested class access

/**
 * Shared empty array instance used for default sized empty instances. We
 * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
 * first element is added.
 */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/**
 * Default initial capacity.
 */
private static final int DEFAULT_CAPACITY = 10;

通过下面的正文理解到，ArrayList 无参结构时是会共享一个长度为 0 的数组 DEFAULTCAPACITY_EMPTY_ELEMENTDATA. 只有当第一个元素增加时才会第一次扩容，这样也避免了创建对象时更多的内存节约。

ArrayList 扩容机制

咱们都晓得数组的大小一但确定是不能扭转的，那么 ArrayList 显著能够一直的增加元素，它的底层又是数组，它是怎么实现的呢？从下面的 ArrayList 存储构造以及正文中理解到，ArrayList 在初始化时，是共享一个长度为 0 的数组的，当第一个元素增加进来时会进行第一次扩容，咱们能够想像出 ArrayList 每当空间不够应用时就会进行一次扩容，那么扩容的机制是什么样子的呢?

仍旧从源码开始，追踪 add() 办法的外部实现。

/**
 * 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;
}
// 开始查看以后插入地位时数组容量是否足够
private void ensureCapacityInternal(int minCapacity) {
    // ArrayList 是否未初始化，未初始化是则初始化 ArrayList，容量给 10.
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}
// 比拟插入 index 是否大于以后数组长度，大于就 grow 进行扩容
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

/**
 * Increases the capacity to ensure that it can hold at least the
 * number of elements specified by the minimum capacity argument.
 *
 * @param minCapacity the desired minimum capacity
 */
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    // 扩容规定是以后容量 + 以后容量右移 1 位。也就是 1.5 倍。int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 是否大于 Int 最大值，也就是容量最大值
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    // 拷贝元素到裁减后的新的 ArrayList
    elementData = Arrays.copyOf(elementData, newCapacity);
}

通过源码发现扩容逻辑还是比较简单的，整顿下具体的扩容流程如下：

1. 开始查看以后插入地位时数组容量是否足够
2. ArrayList 是否未初始化，未初始化是则初始化 ArrayList，容量给 10.

3. 判断以后要插入的下标是否大于容量

   1. 不大于，插入新增元素，新增流程结束。

4. 如果所需的容量大于以后容量，开始裁减。

   1. 扩容规定是以后容量 + 以后容量右移 1 位。也就是 1.5 倍。

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

   2. 如果裁减之后还是小于须要的最小容量，则把所需最小容量作为容量。
   3. 如果容量大于默认最大容量，则应用 最大值 Integer 作为容量。
   4. 拷贝老数组元素到裁减后的新数组
5. 插入新增元素，新增流程结束。

ArrayList 数据新增

下面剖析扩容时候曾经看到了新增一个元素的具体逻辑，因为底层是数组，所以间接指定下标赋值即可，非常简单。

public boolean add(E e) {ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e; // 间接赋值
    return true;
}

然而还有一种新增数据得状况，就是新增时指定了要退出的下标地位。这时逻辑有什么不同呢？

/**
 * Inserts the specified element at the specified position in this
 * list. Shifts the element currently at that position (if any) and
 * any subsequent elements to the right (adds one to their indices).
 *
 * @param index index at which the specified element is to be inserted
 * @param element element to be inserted
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public void add(int index, E element) {rangeCheckForAdd(index);
    ensureCapacityInternal(size + 1);  // Increments modCount!!
     // 指定下标开始所有元素后移一位
    System.arraycopy(elementData, index, elementData, index + 1,size - index);
    elementData[index] = element;
    size++;
}

能够发现这种新增多了要害的一行，它的作用是把从要插入的坐标开始的元素都向后挪动一位，这样能力给指定下标腾出空间，才能够放入新增的元素。

比方你要在下标为 3 的地位新增数据 100，那么下标为 3 开始的所有元素都须要后移一位。

由此也能够看到 ArrayList 的一个毛病，随机插入新数据时效率不高。

ArrayList 数据获取

数据下标获取元素值，一步到位，不用多言。

public E get(int index) {rangeCheck(index);
    return elementData(index);
}
E elementData(int index) {return (E) elementData[index];
}

LinkedList

LinkedList 的底层就是一个链表线性构造了，链表除了要有一个节点对象外，依据单向链表和双向链表的不同，还有一个或者两个指针。那么 LinkedList 是单链表还是双向链表呢？

LinkedList 存储构造

仍旧深刻 LinkedList 源码一探到底，能够看到 LinkedList 无参结构里没有任何操作，不过咱们通过查看变量 first、last 能够发现它们就是存储链表第一个和最初 一个的节点。

transient int size = 0;
/**
 * Pointer to first node.
 * Invariant: (first == null && last == null) ||
 *            (first.prev == null && first.item != null)
 */
transient Node<E> first;

/**
 * Pointer to last node.
 * Invariant: (first == null && last == null) ||
 *            (last.next == null && last.item != null)
 */
transient Node<E> last;

/**
 * Constructs an empty list.
 */
public LinkedList() {}

变量 first 和 last 都是 Node 类型，继而查看 Node 源码。

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

能够看到这就是一个典型的 双向链表 构造，item 用来寄存元素值；next 指向下一个 node 节点，prev 指向上一个 node 节点。

LinkedList 数据获取

链表不像数组是间断的内存地址，链表是通过 next 和 prev 指向记录链接门路的，所以查找指定地位的 node 只能遍历查找，查看源码也是如此。

public E get(int index) {checkElementIndex(index);
    return node(index).item;
}
/**
 * Returns the (non-null) Node at the specified element index.
 */
// 遍历查找 index 地位的节点信息
Node<E> node(int index) {// assert isElementIndex(index);
    // 这里判断 index 是在以后链表的前半部分还是后半局部，而后决定是从
    // first 向后查找还是从 last 向前查找。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;
    }
}

查找指定地位的 node 对象，这个局部要留神的是，查找会首先判断 index 是在以后链表的前半部分还是后半局部，而后决定是从 first 向后查找还是从 last 向前查找。这样能够减少查找速度。从这里也能够看出链表在查找指定地位元素时，效率不高。

LinkedList 数据新增

因为 LinkedList 是链表，所以 LinkedList 的新增也就是链表的数据新增了，这时候要依据要插入的地位的辨别操作。

1. 尾部插入

   public boolean add(E e) {linkLast(e);
       return true;
   }
   void linkLast(E e) {
       final Node<E> l = last;
       // 新节点，prev 为以后尾部节点，e 为元素值，next 为 null，final Node<E> newNode = new Node<>(l, e, null);
       last = newNode;
       if (l == null)
           first = newNode;
       else
            // 目前的尾部节点 next 指向新的节点
           l.next = newNode;
       size++;
       modCount++;
   }

   默认的 add 形式就是尾部新增了，尾部新增的逻辑很简略，只须要创立一个新的节点，新节点的 prev 设置现有的开端节点，现有的开端 Node 指向新节点 Node，新节点的 next 设为 null 即可。

2. 两头新增

   上面是在指定地位新增元素，波及到的源码局部。

   public void add(int index, E element) {checkPositionIndex(index);
       if (index == size)
           // 如果地位就是以后链表尾部，间接尾插
           linkLast(element);
       else
           // 获取 index 地位的节点，插入新的元素
           linkBefore(element, node(index));
   }
   
   /**

*/

// 在指定节点处新增元素，批改指定元素的下一个节点为新增元素，新增元素的下一个节点是查找到得 node 的 next 节点指向，
// 新增元素的上一个节点为查找到的 node 节点，查找到的 node 节点的 next 指向 node 的 prev 批改为新 Node
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++;

}

能够看到指定地位插入元素次要分为两个局部，第一个局部是查找 node 节点局部，这部分就是下面介绍的 LinkedList 数据获取局部，第二个局部是在查找到得 node 对象后插入元素。次要就是批改 node 的 next 指向为新节点，新节点的 prev 指向为查找到的 node 节点，新节点的 next 指向为查找到的 node 节点的 next 指向。查找到的 node 节点的 next 指向的 node 节点的 prev 批改为新节点。![LinkedLst 插入元素](https://cdn.jsdelivr.net/gh/niumoo/cdn-assets/2020/image-20200809145942634.png)

### LinkedList 数据删除

仍旧查看源码进行剖析，源码中看到如果节点是头结点或者尾节点，删除比较简单。咱们次要看删除两头一个节点时的操作

public E remove(int index) {

checkElementIndex(index);
return unlink(node(index));

}
/**

• Unlinks non-null node x.

*/
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;

}

node(index) 办法仍旧是二分查找指标地位，而后进行删除操作。比方要删除的节点叫做 X，删除操作次要是批改 X 节点的 prev 节点的 next 指向为 X 节点的 next 指向，批改 X 节点的 next 节点的 prev 指向为 X 节点的 prev 指向，最初把 X 节点的 prev 和 next 指向清空。如果了解起来有点吃力，能够看上面这个图，可能会比拟明确。![LinkedList 删除数据](https://cdn.jsdelivr.net/gh/niumoo/cdn-assets/2020/image-20200810222445628.png)

### 扩大

你认为 LinkedList 只是一个 List，其余它不仅实现了 List 接口，还实现了 Deque，所以它外表上是一个 List，其实它还是一个队列。

public class LinkedList<E> extends AbstractSequentialList<E>

implements List<E>, Deque<E>, Cloneable, java.io.Serializable

体验一下先进先出的队列。

Queue<String> queue = new LinkedList<>();
queue.add(“a”);
queue.add(“b”);
queue.add(“c”);
queue.add(“d”);
System.out.println(queue.poll());
System.out.println(queue.poll());
System.out.println(queue.poll());
System.out.println(queue.poll());
// result：
// a
// b
// c
// d

同学能够思考一下这个队列是怎么实现的，其实很简略对不对，就是先进先出嘛，`poll` 时删除 first 节点不就完事了嘛。## 总结

不论是 ArrayList 还是 LinkedList 都是开发中罕用的汇合类，这篇文章剖析了两者的底层实现，通过对底层实现的剖析咱们能够总结出两者的次要优缺点。1. 遍历，ArrayList 每次都是 ** 间接定位 **，LinkedList 通过 **next 节点定位 **，并驾齐驱。这里要留神的是 LinkedList  只有应用 ** 迭代器 ** 的形式遍历才会应用 next 节点。如果应用 `get`，则因为遍历查找效率低下。2. 新增，ArrayList 可能会须要 ** 扩容 **，两头插入时，ArrayList 须要 ** 后移 ** 插入地位之后的所有元素。LinkedList ** 间接批改 ** node 的 prev, next 指向，LinkedList 胜出。3. 删除，同 2.
4. ** 随机拜访 ** 指定地位，ArrayList 间接定位，LinkedList 从头会尾开始查找，** 数组胜出 **。综上所述，ArrayList 适宜存储和拜访数据，LinkedList 则更适宜数据的解决，心愿你当前在应用时能够正当的抉择 List 构造。** 最初的话 **
> 我把我所有文章都开源在 [Github.com/niumoo/JavaNotes](https://github.com/niumoo/JavaNotes)，欢送 **Star** 和欠缺，心愿咱们一起变得优良。文章有帮忙能够点个「** 赞 **」或「** 分享 **」，都是反对，我都喜爱！文章每周继续更新，要实时关注我更新的文章以及分享的干货，能够关注「** 未读代码 **」公众号或者[我的博客](https://www.wdbyte.com/)。![](https://p1-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/6023eaa2464044668e006df71de87b19~tplv-k3u1fbpfcp-zoom-1.image)