ArrayList 与 LinkedList 底层实现

亦凉 2022-06-04 09:43 213阅读 0赞

ArrayList 与 LinkedList 都是List 类型的容器，保存数据的同时也维持着它们插入元素的顺序，LinkedList 提供了更多的方法来操作其中的数据，但是这并不意味着要优先使用LinkedList ,因为这两种容器底层实现的数据结构截然不同。

### **ArrayList** ###

ArrayList 底层的数据结构是数组，因为数组有下标索引，所以在查询与设置特定数据的时候会非常快，缺点就是在插入、删除数据时效率很低(数组在是一块连续的内存空间，当你想要删除或者添加元素时都需要移动内存)。

下面就结合底层的源码进行分析：在查找元素时根据传入的下标就可以直接返回对应的元素数据，但是在进行元素删除与添加时会根据下标进行对应的元素拷贝，如果一个集合中有大量数据，想要删除一个特定位置上的元素，那么这个元素后的所有元素都会进行拷贝，这个效率是相当感人的，在添加元素时还会先对原来的数组长度先进行扩容然后再进行拷贝。

//其底层的数据结构是一个Object 类型的数组
     transient Object[] elementData; // non-private to simplify nested class access
    
    
     //根据下标返回在数组中对应的数据，在返回数据之前回先调用rangeCheck(); 方法
     public E get(int index) {
            rangeCheck(index);
    
            return elementData(index);  //当传入的下标小于0 时报的异常会指向这一行代码
        }
        //rangeCheck(); 方法用于对传入的数组下标进行越界检查，这里只检查下标超出数组长度的情况
        private void rangeCheck(int index) {
            if (index >= size)
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));//当传入的下标大于数组的长度时报的异常会指向这一行代码
        }
    
    
        //修改元素的值
         public E set(int index, E element) {
            rangeCheck(index);    //对下标范围进行检查
    
            E oldValue = elementData(index);
            elementData[index] = element;    //改变元素的值
            return oldValue;
        }
    
    
        //在指定的位置添加元素
         public void add(int index, E element) {
            rangeCheckForAdd(index); //先对下标范围检查
    
            ensureCapacityInternal(size + 1);  //对Object 数组进行扩容，这个扩容步骤分很多步就不在这里贴出来了，感兴趣的话可以自己查看源码
            System.arraycopy(elementData, index, elementData, index + 1,
                             size - index);  //将数组中index 之后的元素向后拷贝
            elementData[index] = element;    //将元素插入在固定的位置上
            size++;
        }
    
    
        //删除元素的方法
         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);    //index 之后的元素全部向前拷贝
            elementData[--size] = null; // clear to let GC do its work
    
            return oldValue;
        }

### **LinkedList** ###

LinkedList 底层是一个Node 类型的双向链表，在当前节点中不仅保存了元素值还保存了上一个元素和下一个元素的地址。

transient Node<E> first;
     transient Node<E> last;
    //内部类，保存了当前的元素至值以及上一个元素和下一个元素的地址
     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;
            }
        }

通过下面对LinkedList 的源码分析： 我们发现想要获得元素值会遍历节点，直到找到对应节点的位置然后返回其中保存的元素值(修改操作类似)。对于删除和插入的操作只要找到对应的节点然后改变节点的前一个节点和后一个节点的指向就可以完成任务，不存在大量元素的拷贝，所以在对元素进行删除与插入时要比ArrayList 效率更高。

//获取指定位置的元素值
      public E get(int index) {
            checkElementIndex(index);    //对元素索引检查
            return node(index).item;    //返回对应位置的节点值，下面这个方法是返回值算法的实现
        }
        Node<E> node(int index) {
            // assert isElementIndex(index);
    
            if (index < (size >> 1)) {    //右移一位相当于 size / 2,避免所有节点扫描
                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;
            }
    
    
        // 设置元素值
         public E set(int index, E element) {
            checkElementIndex(index);    //检查元素所以
            Node<E> x = node(index);    //返回元素的节点
            E oldVal = x.item;
            x.item = element;    //设置新的节点值
            return oldVal;
        }
    
    
        //在指定的位置添加元素
         public void add(int index, E element) {
            checkPositionIndex(index);
    
            if (index == size)    //如果插入元素的位置等于集合的大小，那么直接在最后插入
                linkLast(element);
            else
                linkBefore(element, node(index));   //先找到在index 位置上的元素节点，然后进行链接，对应的方法如下
        }
        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++;
        }
    
    
        //删除对应位置上的元素
         public E remove(int index) {
            checkElementIndex(index);
            return unlink(node(index));    //调用unlink() 方法删除节点
        }
         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;
        }

### **总结** ###

ArrayList：内部数据结构是数组，查找与修改元素很快，增删元素速度很慢–>地址空间连续，还有一点要注意的是在删除元素的时候从后面往前删除元素要比从前往后删除效率更高

LinkedList:内部是双向链表形式的数据结构，增删元素的速度很快，但查找元素速度很慢，由于是双向链表所以在对链表中间元素进行操作时效率会很低

PS：在LinkedList 内部，所有的增删改查操作都会先找到对应的节点，所以在对LinkedList 中的元素进行操作时效率都是相当的。之所以说它查询速度慢是指与ArrayList 相比时它没有数组获取元素容易，删除元素和添加元素快是因为只要找到对应的节点然后对节点的指向进行操作就可以将数据插入与删除，在ArrayList 中，会将元素拷贝到新的数组中，拷贝的操作与LinkedList 节点操作相比并不高效。

### **System.arraycopy() 方法** ###

因为ArrayList 源码中用到了这个方法，就在这里简单介绍一下

> public static void (Object src, int srcPos, Object dest, int destPos, int length)  
> src:源数组；  
> srcPos:源数组要复制的起始位置；  
> dest:目的数组；  
> destPos:目的数组放置的起始位置；  
> length:复制的长度。

举个例子如下：如果这个方法复制的是数组对象，那么只是复制了对象的引用并不是对对象本身进行复制，所以也被称为浅复制。

int[] array = {0,1,2,3,4,5,6}; 
    System.arraycopy(array, 0,array,3, 3);
    
    System.out.println(Arrays.toString(array));
    //复制结果为：[0, 1, 2, 0, 1, 2, 6]

可参考文章：[ 模拟实现ArrayList与 LinkedList][_ArrayList_ LinkedList]

[_ArrayList_ LinkedList]: http://blog.csdn.net/codejas/article/details/78926962