LinkedList源码学习

写一点笔记

发布于 2020-09-01 10:48:38

41900

代码可运行

运行总次数：0

代码可运行

之前学习了ArrayList，了解了其基于数组的本质，那么LinkedList是怎么实现的？显然LinkedList是链表。也就是基于链表实现。链表分为单向链表和多向链表。那么LinnkedList具体是那种类型的链表？我们可能在工作中一直在用但是也许对LinkedList的原理不熟悉。怀着疑问，我们来解析一下吧！

在类的继承关系图中我们看到了Queue的接口，这个接口是操作队列的一些公用的接口。那么放着这里又是为了什么呐？显然LinkedList的基础操作具有和队列相似的地方。总体来说就是说LinkedList具有list和队列的双重属性。

    //链表的长度
    transient int size = 0;
    //头节点地址    
    transient Node<E> first;
    //尾节点地址
    transient Node<E> last;

LinkedList的限制条件和容器就这三个，而却有两个，那么这是为何？因为在我们的固有思维里一个链表应该就可以搞定了。为啥这里要定义两个。是因为要兼容队列的原因吗？


    public LinkedList() {
    }
    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }
    
   //双向链表
   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;
        }
    }

    //将元素添加到链表中
    public boolean addAll(int index, Collection<? extends E> c) {
        //检测下标
        checkPositionIndex(index);
        Object[] a = c.toArray();
        int numNew = a.length;
        //排除空列表
        if (numNew == 0)
            return false;
        Node<E> pred, succ;
        if (index == size) {
           //如果是添加到最后
            succ = null;
            //缓存last指针
            pred = last;
        } else {
            //向指定位置添加元素
            succ = node(index);
            //缓存添加位置的前一节点
            pred = succ.prev;
        }
        for (Object o : a) {
            //声明一个前一节点为last的新节点
            Node<E> newNode = new Node<>(pred, e, null);
            if (pred == null)
                first = newNode;
            else
               //让原来的last指向新节点
                pred.next = newNode;
            //last指针向后移动
            pred = newNode;
        }

        if (succ == null) {
            last = pred;
        } else {
            //将last指针的末尾添加succ
            pred.next = succ;
            succ.prev = pred;
        }

        size += numNew;
        modCount++;
        return true;
    }

    //向头节点添加元素
    private void linkFirst(E e) {
        //缓存头节点的指针
        final Node<E> f = first;
        //声明一个next是头节点的节点
        final Node<E> newNode = new Node<>(null, e, f);
        first = newNode;
        //将新节点添加到链表额头部 
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;
        size++;
        modCount++;
    }

    //向尾节点之后添加新节点
    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++;
    }

  //添加元素
  public boolean add(E e) {
        //向尾节点之后添加
        linkLast(e);
        return true;
    }
  //向指定下标添加
  public void add(int index, E element) {
  //保障添加额元素的位置不是非法值，小于0或大于size 
        checkPositionIndex(index);
        if (index == size)
            linkLast(element);
        else
        //在指定元素之前添加元素
            linkBefore(element, node(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));
    }
    //移除
  E unlink(Node<E> x) {
        final E element = x.item;
        //缓存当前节点额前一节点和后一节点 
        final Node<E> next = x.next;
        final Node<E> prev = x.prev;
        //如果前一节点为null，说明就是头节点了
        if (prev == null) {
            first = next;
        } else {
           //跨过移除的节点
            prev.next = next;
            //标记一下，然后好让GC回收
            x.prev = null;
        }
        //如果next是null，说明是尾节点 
        if (next == null) {
            last = prev;
        } else {
           //绕过移除的节点 
            next.prev = prev;
            x.next = null;
        }
        //帮助gc
        x.item = null;
        //让size--
        size--;
        modCount++;
        return element;
    }

总结：通过上述分析，发现LinkedList也没有什么神秘的地方。很简单的类，但是因为LindedList是链表。所以内存的使用概率是非常好的，但是对元素的寻址是需要进行计算的，通过移动指针去寻找，和数组的统一地址偏移量的所以还是有些差距。显然是数组的寻址快一点。也就是说LinkedList的get和set比较消耗时间。但是LinkedList在删除元素只需要修改相关的前后两个指针，所以效率非常好，而ArrayList则需要进行元素值得覆盖和移动。所以如果一个列表元素增删比较频繁的话就可以采用LinkedList，如果对数据的读操作比较频繁的话可以采用ArrayList。

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2020-08-26，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法