乐趣区

关于java:面试老被问LinkedList源码看看阿里技术官是怎么深度剖析的吧

前言

 LinkedList 底层是基于双向链表,链表在内存中不是间断的,而是通过援用来关联所有的元素,所以链表的长处在于增加和删除元素比拟快,因为只是挪动指针,并且不须要判断是否须要扩容,毛病是查问和遍历效率比拟低。上面会给大家具体的分析一下底层源码!

构造

LinkedList 继承关系,核心成员变量,次要构造函数:

    public class LinkedList<E>
        extends AbstractSequentialList<E>
        implements List<E>, Deque<E>, Cloneable, java.io.Serializable {

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

        //------------------------ 成员变量 -------------------------------------

        transient int size = 0;

        // 记录头结点,它的前一个结点 =null
        transient Node<E> first;

        // 记录尾结点,它的后一个结点 =null
        // 当 first = last = null 时示意链表为空
        // 当 first = last != null 时示意只有一个节点
        transient Node<E> last;

        //-------------------------- 构造方法 -------------------------------------

        public LinkedList() {}

         public LinkedList(Collection<? extends E> c) {this();
            addAll(c);
        }

        // ........
    }

办法解析 &api

追加

追加节点时,咱们能够抉择追加到链表头部,还是追加到链表尾部,add 办法默认是从尾部开始追加,addFirst 办法是从头部开始追加,咱们别离来看下两种不同的追加形式:

-add()

    public boolean add(E e) {linkLast(e);
            return true;
    }

--linkLast()

    /**
     * 尾插
     * newNode.pre = last
     * last.next = newNode   注:思考 last=null 状况(链表为空,这时仅更新头结点即可)* last = newNode
    */
    void linkLast(E e) {
        // 把尾节点数据暂存,为 last.next 做筹备,其实扭转一下程序就能够不要这个 l 了
        final Node<E> l = last;

        final Node<E> newNode = new Node<>(l, e, null); // 1
        last = newNode; // 2

        // 空链表,l=null,l.next 报空指针
        if (l == null)
            first = newNode;
        else
            l.next = newNode; // 3

        // size 和版本更改
        size++;
        modCount++;
    }

-addFirst()

    public void addFirst(E e) {linkFirst(e);
    }

--linkFirst()

    /**
    * 头插
    * newNode.next = first;
    * first.prev = newNode;  注:思考 first=null(链表为空,只用更新 last 即可)* first = newNode;
    */
    private void linkFirst(E e) {
        // 头节点赋值给长期变量
        final Node<E> f = first;

        final Node<E> newNode = new Node<>(null, e, f); // 1

        first = newNode;  // 2

        // 链表为空,f=null, f.prev 报空指针
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;  // 3

        // 更新 size 和版本号
        size++;
        modCount++;
    }

删除

节点删除的形式和追加相似,咱们能够删除指定元素,或者从头部(尾部)删除,删除操作会把节点的值,前后指向节点都置为 null,帮忙 GC 进行回收

-remove()

    /**
    * 删除指定元素;找到要删除的节点
    * 注:只有链表有这个节点且胜利删除才返回 true
    */
    public boolean remove(Object o) {if (o == null) {for (Node<E> x = first; x != null; x = x.next) {
                    // null 用 == 判断
                    if (x.item == null) {unlink(x);
                        return true;
                    }
                }
            } else {for (Node<E> x = first; x != null; x = x.next) {
                    // 调用 equals 判断,若传入的类无 equals 须要重写
                    if (o.equals(x.item)) {unlink(x);
                        return true;
                    }
                }
            }
            return false;  // 链表无要删除元素,或链表为空
    }

注:remove 还能够依据索引删除

    public E remove(int index) {checkElementIndex(index); // 链表为空,抛出异样
            return unlink(node(index));
    }

--unlink()

    /**
    * 执行删除
    * x.prev.next = x.next        注:思考 x.prev=null(x 是 first,间接更新 first)* x.next.prev = x.prev.prev   注:思考 x.next=null(x 是 last,间接更新 last)*/
    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;

             // 如果 prev=null, 则以后节点为头结点
            if (prev == null) {
                // 间接将头结点赋成 next
                first = next;
            } else {
                prev.next = next; // 1
                x.prev = null; // 帮忙 GC 回收该节点
            }

             // 如果 next=null,则以后节点为尾结点
            if (next == null) {last = prev;} else {
                next.prev = prev; // 2
                x.next = null; // 帮忙 GC 回收该节点
            }

            x.item = null; // 帮忙 GC 回收该节点

             // 批改 size 及版本
            size--;
            modCount++;

            return element;
        }

-remove()

    /**
    * 删除头节点,队列为空时抛出异样
    */
    public E remove() {return removeFirst();
    }

-removeFirst()

    /**
    * 删除头节点
    */
    public E removeFirst() {
            final Node<E> f = first;
            if (f == null)
                throw new NoSuchElementException();
            return unlinkFirst(f);
     }

--unLinkFirst()

    /**
    * 执行删除头节点
    * first.next.pre = null;  注:思考 first=null(链表为空),first.next=null(尾结点,即链表仅一个节点)* first = first.next;
    */
    private E unlinkFirst(Node<E> f) {

        final E element = f.item; // 拿出头节点的值,作为办法的返回值
        final Node<E> next = f.next; // 拿出头节点的下一个节点

        // 帮忙 GC 回收头节点
        f.item = null;
        f.next = null;

        first = next;  // 1

        // next 为空示意链表只有一个节点
        if (next == null)
            last = null;
        else
            next.prev = null; // 2

        // 批改链表大小和版本
        size--;
        modCount++;
        return element;
    }

从源码中咱们能够理解到,链表构造的节点新增、删除都非常简单,仅仅把前后节点的指向批改下就好了,所以 LinkedList 新增和删除速度很快。

查问

链表查问某一个节点是比较慢的,须要挨个循环查找才行,咱们看看 LinkedList 的源码是如何寻找节点的

-get()

    /**
    * 依据索引进行查找
    */
    public E get(int index) {checkElementIndex(index);
            return node(index).item;
    }

--node()

    Node<E> node(int index) {
        // 如果 index 处于队列的前半部分,从头开始找,size >> 1 是 size 除以 2 的意思。if (index < (size >> 1)) {
            // 取头节点
            Node<E> x = first;
            // 直到 for 循环到 index 的前一个 node 进行
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {// 如果 index 处于队列的后半局部,从尾开始找
            // 取尾结点
            Node<E> x = last;
            // 直到 for 循环到 index 的后一个 node 进行
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

从源码中咱们能够发现,LinkedList 并没有采纳从头循环到尾的做法,而是采取了简略二分法,首先看看 index 是在链表的前半部分,还是后半局部。如果是前半部分,就从头开始寻找,反之亦然。通过这种形式,使循环的次数至多升高了一半,进步了查找的性能,这种思维值得咱们借鉴

迭代器

因为 LinkedList 要实现双向的迭代拜访,所以应用 Iterator 接口必定不行了,因为 Iterator 只反对从头到尾的拜访。Java 新增了一个迭代接口,叫做:ListIterator,这个接口提供了向前和向后的迭代办法,如下所示:

迭代程序 办法
从尾到头迭代办法 hasPrevious、previous、previousIndex
从头到尾迭代办法 hasNext、next、nextIndex

-listIterator()

    /**
    * 从指定节点开始迭代,可前可后
    */
    public ListIterator<E> listIterator(int index) {checkPositionIndex(index);
        return new ListItr(index);
    }

    /**
    *ListItr, 双向迭代器
    */
    private class ListItr implements ListIterator<E> {private Node<E> lastReturned;// 上一次执行 next() 或者 previos() 办法时的节点地位
        private Node<E> next;// 下一个节点
        private int nextIndex;// 下一个节点的地位
        //expectedModCount:冀望版本号;modCount:目前最新版本号
        private int expectedModCount = modCount;

        ListItr(int index) {// assert isPositionIndex(index);
              next = (index == size) ? null : node(index);
              nextIndex = index;
        }
    }

--hasNext()

从前向后迭代

    // 判断还有没有下一个元素,还是通过 index 和 size 管制
    public boolean hasNext() {return nextIndex < size;// 下一个节点的索引小于链表的大小,就有}

---next()

    // 取下一个元素,并后移
    public E next() {
        // 查看冀望版本号有无发生变化
        checkForComodification();
        if (!hasNext())// 再次查看
            throw new NoSuchElementException();
        // next 是以后节点,在上一次执行 next() 办法时被赋值的。// 第一次执行时,是在初始化迭代器的时候,next 被赋值的
        lastReturned = next;
        // next 是下一个节点了,为下次迭代做筹备
        next = next.next;
        nextIndex++;
        return lastReturned.item;
    }

--hasPrevious()

从后向前迭代

    // 如果上次节点索引地位大于 0,就还有节点能够迭代
    public boolean hasPrevious() {return nextIndex > 0;}

---previous()

    public E previous() {checkForComodification();
        if (!hasPrevious())
            throw new NoSuchElementException();
        // next 为空场景:1: 阐明是第一次迭代,取尾节点 (last);2: 上一次操作把尾节点删除掉了
        // next 不为空场景:阐明曾经产生过迭代了,间接取前一个节点即可 (next.prev)
        lastReturned = next = (next == null) ? last : next.prev;
        // 索引地位变动
        nextIndex--;
        return lastReturned.item;
    }

----remove()

    /**
    * 迭代时,删除以后元素
    */
    public void remove() {checkForComodification();
        // lastReturned 是本次迭代须要删除的值,分以下空和非空两种状况:// lastReturned 为空,阐明调用者没有被动执行过 next() 或者 previos(),间接报错
        // lastReturned 不为空,是在上次执行 next() 或者 previos() 办法时赋的值
        if (lastReturned == null)
            throw new IllegalStateException();
        Node<E> lastNext = lastReturned.next;
        // 删除以后节点
        unlink(lastReturned);
        // next == lastReturned 的场景剖析:从尾到头递归程序,并且是第一次迭代,并且要删除最初一个元素的状况
        // 这种状况下,previous() 办法外面设置了 lastReturned=next=last, 所以 next 和 l astReturned 会相等
        if (next == lastReturned)
            // 这时候 lastReturned 是尾节点,lastNext 是 null,所以 next 也是 null,这样在 previous() 执行         // 时,发现 next 是 null,就会把尾节点赋值给 next
            next = lastNext;
        else
            nextIndex--;
        lastReturned = null;
        expectedModCount++;
    }

Queue 的实现

LinkedList 实现了 Queue 接口,在新增、删除、查问等方面减少了很多新的办法,这些办法在平时特地容易混同,在链表为空的状况下,返回值也不太一样,上面列一个表格,不便大家记录:

PS:Queue 接口正文倡议 add 办法操作失败时抛出异样,但 LinkedList 实现的 add 办法始终返回 true。
LinkedList 也实现了 Deque 接口,对新增、删除和查找都提供从头开始,还是从尾开始两种方向的办法,比方 remove 办法,Deque 提供了 removeFirst 和 removeLast 两种方向的应用形式,但当链表为空时的体现都和 remove 办法一样,都会抛出异样。

最初

感激你看到这里,文章有什么有余还请斧正,感觉文章对你有帮忙的话记得给我点个赞,每天都会分享 java 相干技术文章或行业资讯,欢送大家关注和转发文章!

退出移动版