LinkedList源码分析

前面分析了ArrayList的源码,今天来分析一下jdk中对LinkedList的实现。

首先,还是看一下LinkedList的声明。

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

LinkedList继承了List接口,同时继承了Deque接口,这表明了LinkedList是一个双向队列,可以从队列的两端来执行新增和删除操作。

首先来看LinkedList中的节点类,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;
    }
}

可以看到构造一个新的Node,需要三个元素:前驱节点、后驱节点和当前节点的值。

代码中定义了first和last,来分别标识队首元素和队尾元素。

transient Node<E> first;
transient Node<E> last;

定义了size变量,用来表示链表的长度。

int size;

关于first节点,隐含着如下的不变性:

(first == null && last == null) || (first.prev == null && first.item != null)

关于last节点,同样隐含着不变性:

(first == null && last == null) || (last.next == null && last.item != null)

LinkedList提供了两个构造函数,如下所示

public LinkedList() {}

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

可以看出,使用Collection对象来构造LinkedList的逻辑在addAll函数中,addAll函数的逻辑后面再说。

先来看几个重要的辅助函数。

  1. linkFirst

    linkFirst函数的作用是将新元素插入到链表的首部。实现如下

    private void linkFirst(E e) {
       final Node<E> f = first;
       final Node<E> newNode = new Node<>(null, e, f);
       first = newNode;
       if (f == null) {
           last = newNode;
       } else {
           f.prev = newNode;
       }
       size++;
       modCount++;
    }
    

    函数的逻辑很简单。通过在构造Node的时候完成了如下的操作

    eNode.next = f;
    eNode.prev = null;
    

    当插入之前,链表为空的情况下,还需要将last节点指向新的节点。

    last = newNode;
    

    当插入之前,链表不为空的情况下,还需要将原来头节点的prev节点指向新的节点。

    f.prev = newNode;
    
  2. linkLast

    linkLast函数的作用是将新元素插入到链表的尾部。实现如下

    private void linkLast(E e) {
       final Node<E> f = last;
       final Node<E> newNode = new Node<>(last, e, null);
       last = newNode;
       if (f == null) {
           first = newNode;
       } else {
           f.next = newNode;
       }
       size++;
       modeCount++;
    }
    

    同linkFirst函数类似,在构造Node的时候,完成了如下的操作

    eNode.prev = last;
    eNode.next = null;
    

    当插入之前,链表为空的情况下,还需要将first节点指向新的节点。

    first = newNode;
    

    当插入之前,链表不为空的情况下,需要将原来尾节点last的next指向新的节点。

    f.next = newNode;
    
  3. linkBefore

    linkBefore函数的作用是在给定节点之前插入一个节点。

    void linkBefore(E e, Node<E> succ) {
       final Node<E> pred = succ.prev;
       final Node<E> newNode = new Node<>(pred, e, succ);
       if (pred == null) {
           first = newNode;
       } else {
           pred.next = newNode;
       }
       size++;
       modCount++;
    }
    

    在构造了新的节点之后,需要考虑succ节点原来的前驱节点是否为空,为空的情况表示新插入的节点为头节点。

  4. unlinkFirst

    unlinkFirst节点的作用是从链表中删除头节点。

    private E unlinkFirst(Node<E> f) {
       final E element = f.item;
       final Node<E> next = f.next;
       f.item = null;
       f.next = null;
       first = next;
       if (next == null) {
           last = null;
       } else {
           next.prev = null;
       }
       size--;
       modeCount++;
       return element;
    }
    

    以上的函数逻辑同样很简单,需要注意的是如下的两步操作是用于加快垃圾回收,对功能的正确性没有实际影响。

    f.item = null;
    f.next = null;
    
  5. unlinkLast

    unlinkLast函数的作用为删除链表尾部的元素。

    private unlinkLast(Node<E> l) {
       E element = l.item;
       Node<E> pred = l.prev;
       l.item = null;
       l.prev = null;
       if (pred == null) {
           first = null;
       } else {
           prev.next = null;
       }
       size--;
       modCount++;
       return element;
    }
    

    逻辑同unlinkFirst一致,不再具体说明。

  6. unlink

    unlink函数的作用为从链表中删除给定的元素。具体实现如下

    E unlink(Node<E> x) {
       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;
       }
       size--;
       modCount++;
       return element;
    }
    

    在以上辅助函数的帮助下,LinkedList中大多的插入和删除操作都可以简介的实现,比如addFirst、addLast、removeFirst、removeLast。而getFirst和getLast更是简直的直接返回first和last节点即可。

    在以上这些对链表进行结构性修改的方法中,同样对modCount变量进行了操作。在ArrayList中我们已经提到过,这个变量是用于实现fail-fast机制,这一点在LinkedList中同样适用。

    上面提到过,LinkedList有个构造函数,需要一个Collection类型的参数,而在这个函数中,主要的逻辑是在addAll函数中,下面我们就来看一下addAll函数的具体实现。

    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) {
           E e = (E) o;
           Node<E> newNode = newNode<>(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++;
       modCount++;
       return true;
    }
    

    在checkPositionIndex中首先判断给定的index是否合法,合法的index应该满足 index >= 0 && index <= size。index等于0,表示将第一个节点插入到首节点的前面,index 等于size的时候,表示将第一个节点插入到尾节点的后面。而如下的node辅助函数,可以用于获取第index个节点。

    Node<E> node(int index) {
       if (index < (size >> 1)) {
           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;
       }
    }
    

    如下的操作,用于获取当前插入位置的节点,以及当前节点的前驱节点。

    if (index == size) {
       succ = null;
       pred = last;
    } else {
       succ = node(index);
       pred = succ.prev;
    }
    

    获取了当前节点的位置之后,就可以将Collection中的数据依次的插入,在循环的时候,将pred节点的值依次替换为newNode,然后将新节点插入进来即可,最后再将最后一个插入的节点和上个步骤中保存的succ节点串起来就完成了整个插入。

    LinkedList是一个双向队列,可以选择从头开始进行遍历或是从尾开始遍历。在上面的node函数中,就使用了这个特性,根据index和size、0之间的关系,选择从头进行遍历或是从尾进行遍历,带来更好的性能。

    在前面分析ArrayList的时候,ArrayList内部是使用一个数组来存储数据,内存分配上是一个连续的内存单元,它实现了RandomAccess接口,可以带来快速的随机访问。对于get(index),set(index, e)等操作,在不考虑数据扩容的情况下,时间复杂度是O(1)。而对于LinkedList来说,无法在常量时间内找到对应的节点,时间复杂度变为O(size)。但相比较而已,LinkedList的add操作和remove操作会更加高效,因为不会涉及到数组的复制新增和数据元素的移动,只是单纯的通过修改节点的prev和next指向即可完成。

    除了常规的List接口中定义的方法,LinkedList还是一个队列,因此peek、offer、poll等方法也是提供了的。同时还是一个双向的队列,因此offerFirst、offerLast、peekFirst、peekLast、pollFirst、pollLast同样也都具备。

    同时,LinkedList还提供了push和pop方法,可以当作Stack来使用。

    迭代器方法,LinkedList提供了listIterator方法,实现了ListIterator接口,可以在给定index的情况下,向前或是向后进行遍历。除此之外,还提供了descendingIterator函数,可以用于从尾节点向头节点来进行遍历。

Comments
Write a Comment