LinkedList详解

概述

LinkedList是实现List接口的类，主要有以下特点：

• LinkedList是用双向链表实现的列表。
• LinkedList插入、删除较快，查询较慢。
• LinkedList可以存放包含null对象的任何元素。
• LinkedList是线程不安全的。

LinkedList类图如下：

详解

字段

transient Node<E> first;  // 双向链表的头结点
transient Node<E> last;  // 双向链表的尾节点
transient int size = 0;  // 双向链表中元素个数

private static class Node{
    E item;
    Node next;
    Node prev;
    Node(Node prev, E element, Node next){
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

部分API的实现

/**
 * 把Collection中的元素依次插入到索引位置之前
 * @param index 索引
 */
private 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;  // 定义Node的前驱与后继
    if(index == size){   // 如果在尾部插入
        succ = last;     // 后继为尾部 
        pred = null;     // 前驱为空
    }else{               // 如果不在尾部
        succ = node(index);  // 后继就是该索引所在Node
        pred = succ.prev;    // 前驱指向前一个位置
    }
    for(Object o : a){
        @SuppressWarning("unchecked") E e = (E) o;
        Node<E> newNode = new Node<>(pred, e, null);  // 创建newNode，指定前驱,后继为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;
}
/**
 * 该方法是返回索引所在位置的节点：index与size/2比较，若小于则从first开始查找,若大于则从last开始查找
 */
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;
    }
}

实现

自己模拟写的LinkedList，由于实现List、Deque等接口需要实现太多的方法，我就没有实现这些接口，仅仅写点代码表示LinkedList的基本思路。

class LinkedList<E> {
    // LinkedList包含元素的数目
    private int size;
    // 头结点
    private Node<E> first;
    // 尾节点
    private Node<E> last;

    /**
     * 插入头部
     */
    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++;
    }

    /**
     * 插入尾部
     */
    private 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++;
    }

    /**
     * 插入到某个非空结点succ之前
     */
    private 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){
            last = newNode;
        } else {
            pred.next = newNode;
        }
        size++;
    }

    /**
     * 删除不为空的头结点f
     */
    private E unlinkFirst(Node<E> f){
        final E element = f.item;
        final Node<E> next = f.next;
        f.next = null;
        f.item = null;  // help GC
        first = next;
        if(next == null){
            last = null;
        } else {
            next.prev = null;
        }
        size--;
        return element;
    }

    /**
     *  删除不为空的尾节点l
     */
    private E unlinkLast(Node<E> l){
        final E element = l.item;
        final Node<E> prev = l.prev;
        l.prev = null;
        l.item = null;  // help GC
        last = prev;
        if(prev == null){
            first = null;
        } else {
            prev.next = null;
        }
        size--;
        return element;
    }

    /**
     * 删除不为空的节点x
     */
    private E unlink(Node<E> x){
        final E element = x.item;
        final Node<E> prev = x.prev;
        final Node<E> next = x.next;
        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
            x.prev = null;
        }
        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            x.next = null;
        }
        x.item = null; //help GC
        size--;
        return element;
    }
    private static class Node<E>{
        Node<E> prev;
        E item;
        Node<E> next;
        Node(Node<E> prev, E element, Node<E> next){
            this.prev = prev;
            this.item = element;
            this.next = next;
        }
    }
}