LinkedList集合深度解析

妖狐艹你老母 2021-10-14 21:35 494阅读 0赞

上文讲解了ArrayList的底层实现原理，感兴趣的小伙伴可以去看下，本文重点讨论LinkedList集合。

**首先说下ArrayList和LinkedList的区别**：（相同点都是有序的~）

① ArrayList底层数据结构是动态数组，LinkedList底层数据结构是双向链表。

②  查询或者修改的时候，ArrayList比LinkedList的效率更高，因为LinkedList是线性的基于链表的数据存储方式，所以需要移动指针从前往后依次查找，即使源码中(下面会详细说明)用了二分法，但是效率还是不如ArrayList底层基于数组，直接通过索引定位，效率极快。

③ 增加或者删除的时候，LinkedList比ArrayList的效率更高，因为ArrayList是数组，所以在其中进行增删操作时，会对操作点之后所有数据的下标索引造成影响，需要进行数据的移动，而LinkedList只需要修改prev和next的指针引用即可。

综上所述，Arraylist适用于查询或者修改比较多的场景，LinkeList适用于查询/修改较少，增加和删除较多的场景。

**纯手写****LinkedList源码（白话文分析）：**

package com.example;
    
    public class MyLinkedList<E> implements MyList<E> {
        //E LinkedList 存放的数据类型
        /**
         * 集合的大小
         */
        transient int size = 0;
    
        /**
         * 第一个节点
         */
        transient Node<E> first;
    
        /**
         * 最后一个节点
         */
        transient Node<E> last;
    
        @Override
        public int size() {
            return size;
        }
    
        @Override
        public boolean add(E e) {
            linkLast(e);
            return true;
        }
    
        @Override
        public E get(int index) {
            // 检查我们index是否越界
            checkElementIndex(index);
            // 通过二分法查找具体Node对象/节点的item
            return node(index).item;
        }
    
        /** 【删除原理：改变相互引用的指针】
         * 步骤1:当前要删除Node节点的上一个的next指向当前要删除节点的下一节点
         * 步骤2:当前要删除Node节点的下一个节点的prev指向当前要删除节点的上一个节点
         * 步骤3:当前要删除Node节点/对象，所有属性置为null，等待gc回收
         * @param index
         * @return
         */
        @Override
        public E remove(int index) {
            // 检查我们index是否越界
            checkElementIndex(index);
            // node(index)首先获取到当前删除节点，然后再删除unlink()，即调整指针位置
            return unlink(node(index));
        }
    
        /**
         * 添加我们的节点，作为最后一个元素
         * @param e
         */
        void linkLast(E e) {
            // 获取当前的最后一个节点
            final Node<E> l = last;
            // 封装我们当前自定义元素
            final Node newNode = new Node<E>(l, e, null);
            // 当前新增节点肯定是链表中最后一个节点（当前新增节点赋给last）
            last = newNode;
            if (l == null)  //注意，走到这一步last变了，但l没变
                // 如果我们链表中没有最后一个节点说明当前新增的元素是第一个
                first = newNode;
            else
                // 原来的最后一个节点的下一个节点就是当前新增的节点
                l.next = newNode;
            size++;
        }
    
        /**
         * 链表：其实可以理解为全表扫描（折半查找）
         * 数组：直接通过索引定位，效率极快
         * @param index index小于折半值，从头开始查；index大于折半值，从尾开始查
         * @return
         */
        Node<E> node(int index) {
            /* 举个例子
                现在链表中有1-100节点，如果想查第88个节点，正常情况下从1查到88，即索引从0到87
                写JDK的人比较聪明，运用了折半查找（也成为二分法），查询步骤如下：
                    size / 2 = 50,如果88大于50，那么查50~100就行了（索引49-99）
             */
    
            // size >> 1 → size/2  → if里面的判断解析为 index < size/2
    
            // 假设链表中有1-10节点，查询下标为0，又因为0<10/2,所以在0-4之间找
            if (index < (size >> 1)) {
                // 获取到第一个节点
                Node<E> x = first;
                for (int i = 0; i < index; i++) {
                    // 如果index小于折半值，从头(0)查询到index【基于索引】
                    x = x.next;
                }
                return x;
            } else {
                // 获取到最后一个节点
                Node<E> x = last;
                for (int i = size - 1; i > index; i--) {
                    // 如果index大于折半值，从尾(size-1)查询到index【基于索引】
                    x = x.prev;
                }
                return x;
            }
            // 1-10 | 3 1-3 | 7 10-7
        }
    
        /**
         * 删除节点，重新连接链表
         * @param x 当前删除的Node节点
         * @return
         */
        E unlink(MyLinkedList.Node<E> x) {
            // 获取到当前删除的节点的元素值
            E element = x.item;
            // 获取当前删除元素的下一个节点
            Node<E> next = x.next;
            // 获取当前删除元素的上一个节点
            Node<E> prev = x.prev;
    
            if (prev == null) { /** 判断prev */
                // 如果prev为空，说明当前删除节点是第一个节点，需要把next置为第一个节点（first为全局变量）
                first = next;
            } else {
                // 如果prev不为空， 上一个Node节点的next指向下一个Node节点
                prev.next = next;
                // 当前删除节点的prev变为空，告诉给gc实现回收
                x.prev = null;
            }
    
            if (next == null) { /** 判断next */
                // 如果next为空，说明当前删除节点是最后一个节点，需要把prev置为最后一个节点（last为全局变量）
                last = prev;
            } else {
                // 如果next不为空，下一个Node节点的prev指向上一个Node节点
                next.prev = prev;
                // 当前删除节点的next变为空 告诉给gc实现回收
                x.next = null;
            }
            // 当前删除的节点的元素值置为空
            x.item = null;
            size--;
            return element;
    
        }
    
        /**
         * 链表中的节点
         * @param <E>
         */
        private static class Node<E> {
            // 节点元素值 zhangsan,lisi..
            E item;
            // 当前节点的下一个node（节点/对象）
            MyLinkedList.Node<E> next;
            // 当前节点的上一个node
            MyLinkedList.Node<E> prev;
    
            // 使用构造函数传递参数
            Node(MyLinkedList.Node<E> prev, E element, MyLinkedList.Node<E> next) {
                this.item = element;
                this.next = next;
                this.prev = prev;
            }
    
            Node(E element) {
                this.item = element;
            }
    
            public void setPrev(Node<E> prev) {
                this.prev = prev;
            }
            public void setNext(Node<E> next) {
                this.next = next;
            }
        }
    
        private void checkElementIndex(int index) {
            if (!isElementIndex(index)) {
                throw new IndexOutOfBoundsException("index已经越界啦~~~");
            }
        }
        private boolean isElementIndex(int index) {
            return index >= 0 && index < size;
        }
    
    
        public static void main(String[] args) {
            Node node1 = new Node("第一关游戏");
            Node node2 = new Node("第二关游戏");
            node1.next = node2;
            node2.prev = node1;
            System.out.println("node:" + node1);
        }
    
    }

在上述main方法最后一行打个断点，Debug启动，会发现node1和node2是相互引用的，验证了LinkedList底层是基于双向链表。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FraXJhTmlja3k_size_16_color_FFFFFF_t_70][]

**此时，测试一下我们手写的LinkesList：**

package com.example.test;
    
    import com.example.MyLinkedList;
    
    public class Test001 {
        public static void main(String[] args) {
            MyLinkedList<String> linkedList = new MyLinkedList<>();
            linkedList.add("001");
            linkedList.add("002");
            linkedList.add("003");
            linkedList.remove(1);
            System.out.println(linkedList.get(1));
        }
    }

会发现，当我们删除索引为1的元素，那么003则会替代002的位置，该测试把我们的增，删，查都用上了，改的话无非就是先调用node（即查询指定索引对应的Node节点），然后替换Node的item属性为新元素即可。

![20190814173244267.png][]

**【总结】**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FraXJhTmlja3k_size_16_color_FFFFFF_t_70 1][]

链表数据底层原理实现：双向链表头尾相接

① 在底层中使用静态内部类Node节点存放节点元素

三个属性 prev（关联的上一个节点），item（当前的值） ，next（下一个节点）

② add原理是如何实现？ 答案： 一直在链表之后新增

③ get原理：采用折半查找 范围查询定位node节点

④ remove原理：改变相互引用的指针

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FraXJhTmlja3k_size_16_color_FFFFFF_t_70]: /images/20211015/f6b4d6ff92504ffdb3543f312dd4d4d7.png
[20190814173244267.png]: /images/20211015/3164e3ed5cb843129c5910e09c4bd54d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FraXJhTmlja3k_size_16_color_FFFFFF_t_70 1]: /images/20211015/a0fd06922bfd4d20be206751aba23ba8.png