JDK源码阅读——LinkedList实现

时间:2022-12-15 15:24:31

1 继承结构图

JDK源码阅读——LinkedList实现 

LinkedList是List的另一种实现。继承自AbstractSequentialList

2 数据结构

LinkedList与ArrayList不同的是LinkedList底层使用双向链表进行存储,其主要数据结构如下

  // 记录List长度
  transient int size = 0;

  // 指向LinkedList第一个节点
  transient Node<E> first;

  // 指向LinkedList最后一个节点
  transient Node<E> last;

  // Node Class如下
    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的一个节点是一个Node对象,可以看到node.item记录值,并且分别有指向前一个节点和后一个节点的指针prev和next

 

3 构造方法

    public LinkedList() {}

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

LinkedList也支持两种构造方式,无参构造和传入一个集合构造LinkedList,addAll的具体实现如下

    public boolean addAll(Collection<? extends E> c) {
        return addAll(size, c);
    }  

    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;
            pred = last;
        } else {
            succ = node(index);
            pred = succ.prev;
        }

        for (Object o : a) {
            @SuppressWarnings("unchecked") E e = (E) o;
            Node<E> newNode = new Node<>(pred, e, null);
            if (pred == null)
                first = newNode;
            else
                pred.next = newNode;
            pred = newNode;
        }

        if (succ == null) {
            last = pred;
        } else {
            pred.next = succ;
            succ.prev = pred;
        }

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

 

初始化是size=0,可见就是利用Collection的toArray方法把c转为对象数组,然后遍历新建Node,并逐个连起来,基本的链表操作。

4 一些方法介绍

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

linkBefore方法是在succ节点之前插入一个新的节点,其执行过程大致如下图

JDK源码阅读——LinkedList实现

其他方法类似也都可以通过画图的形式了解大致执行步骤,涉及链表操作,画图能更好的理解执行过程,在此不再赘述。

5 与ArrayList的异同

ArrayList和LinkedList是List的两种实现,不同的ArrayList是基于动态数组的数据结构,而LinkedList是基于双向链表的数据结构。

他们的优缺点也正是由于他们所依赖的数据结构决定的

  • 对于随机存取,因为ArrayList是基于数组实现的,所以随机存取的时间复杂度为O(1),直接根据数据下标即可get或set,而LinkedList由于是使用双向链表实现,随机存取需要移动指针,时间复杂度为O(n);
  • 但是对于元素的删除和增加,如果不是在List尾部操作,ArrayList中元素的删除会涉及数组元素的移动,所以复杂度O(n)会比只单纯操作几个指针的复杂度O(1)要高。

所以在日常使用中,需要根据应用场景灵活选择,对于不需要随机存取而是只进行平凡的增加和删除的场景,使用LinkedList是较好的选择。

 

本文来自我的个人博客:http://blog.duchangchun.com/2018/12/29/jdk_linkedlist/