JDK源码之LinkedList

• • 1. 全局变量
  • 2. 构造器
  • 3. 增删用到的双向链表的方法
  • 4. 方法
  • 5. 特性
  • 6. ArrayList和LinkedList不同

1. 全局变量

// 列表容量
transient int size = 0;
// 指向第一个节点的指针
transient Node<E> first;
// 指向最后一个节点的指针
transient Node<E> last;

2. 构造器

// 构建一个空list
public LinkedList() {
}
// 构建一个包含c的list
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

tip:使用this关键字调用重载构造方法，避免相同的初始化代码，只能在构造方法中使用，必须位于构造方法的第一句。

3. 增删用到的双向链表的方法

双向链表是linkedList的基础。

// 将元素e作为linkedList最后一个元素；
void linkLast(E e) {final Node<E> l = last; //取原本的最后一个节点
    final Node<E> newNode = new Node<>(l, e, null); // new一节点
    last = newNode; // 将新节点赋值给last
    if (l == null) // 前一个节点链接上新节点
        first = newNode;
    else
        l.next = newNode;
    size++; //更新size和修改次数
    modCount++;}
// 将元素e作为linkedList第一个元素
private void linkFirst(E e) {final Node<E> f = first; //取原本的第一个节点
    final Node<E> newNode = new Node<>(null, e, f); // new一个节点
    first = newNode; //将新节点赋值给last
    if (f == null)//后一个节点链接上新节点
        last = newNode;
    else
        f.prev = newNode;
    size++; //更新size和修改次数
    modCount++;}
// 去掉链表中首个元素f
private E unlinkFirst(Node<E> f) {
    final E element = f.item; 
    final Node<E> next = f.next;
    f.item = null;
    f.next = null; // help GC
    first = next;
    if (next == null)
        last = null;
    else
        next.prev = null;
    size--;
    modCount++;
    return element;}
// succ节点前插入一个元素e
void linkBefore(E e, Node<E> succ) {
    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++;}
// 去掉非null的最后一个元素
private E unlinkLast(Node<E> l) {
    final E element = l.item;
    final Node<E> prev = l.prev;
    l.item = null;
    l.prev = null; // help GC
    last = prev;
    if (prev == null)
        first = null;
    else
        prev.next = null;
    size--;
    modCount++;
    return element;}
// 去除某个非null元素
E unlink(Node<E> x) {
    final E element = x.item;// 1. 保存x节点的元素，前后元素的指针
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;
    if (prev == null) {    // 2. x前一个元素链接x后一个元素
        first = next;} else {
        prev.next = next;
        x.prev = null;}
    if (next == null) { //3. x后一个元素链接x前一个元素
        last = prev;} else {
        next.prev = prev;
        x.next = null;}
    x.item = null;// 更新元素，容量和变更次数
    size--;
    modCount++;
    return element;}

对于中间位置元素的增删，下面两个图可以很好的表示操作步骤：
插入操作示意图：（在c之前加入c1节点）

删除操作示意图：（删除c节点）

4. 方法

//在index位置插入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;
}

5. 特性

LinkedList继承了Deque接口，具有队列的特性，同时作为双端队列，LinkedList还具有栈的特性。

队列方法：
栈：

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

public E pop() {
    return removeFirst();
}

6. ArrayList和LinkedList不同

1. LinkedList不支持随机访问，因此访问非首尾元素效率较低，时间复杂度为O(n)，访问首尾时间复杂度为O(1)。
2. 相比于ArrayList, LinkedList的优势在于插入、删除操作，只需要改变前后两个元素的指针，不需要移动后面的元素。
3. LinkedList由双向链表实现，具有队列和栈的特性。ArrayList由数组实现。