转载

从零开始的Java容器学习（三）：LinkedList

基于双向链表机制，在插入元素时，须创建一个新的Node对象，并切换相应元素的前后元素的引用；在查找元素时须遍历链表；在删除链表时，找到要删除的元素然后在链表上删除即可。

此图由IDEA生成，由图可得出其继承关系分别是继承自AbstractSequentialList，实现了Cloneable、List、Deque、Serializable接口。

因为LinkedList实现了Deque(Queue)的接口，所有一些队列的操作也可以直接使用，但是应该把重点放在链表的特性上。

从源码分析LinkedList

成员变量

transient int size = 0;
transient Node<E> first;
transient Node<E> last;

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是LinkedList的基本节点，prev、item、next分别指的是前一元素、节点存的值、后一元素。

构造方法

public LinkedList() {
}

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

有两个构造方法，一个是无参，一个是传入一个容器，然后先调用空参构造方法再调用addAll方法添加所有元素到链表里。

添加

//add有很多方法，实际使用到的操作是下面三个：linkFirst、linkLast、linkBefore
private void linkFirst(E e) {
    final Node<E> f = first;//先存一下原链表的头节点为f
    final Node<E> newNode = new Node<>(null, e, f);//用一个新节点newNode存传进来的值，可以看到它的prev是null，next是f
    first = newNode;//然后将链表的First转为newNode
    if (f == null)//这里判断一下f是否为null，即是否为空链表
        last = newNode;//如果是空链表，则Last也是newNode
    else
        f.prev = newNode;//不是的话说明f不为空，原来的f.prev是null，所以要连接上newNode
    size++;
    modCount++;
}
//linkLast跟linkFirst差不多就不多说了
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++;
}
void linkBefore(E e, Node<E> succ) {//在一个非空节点succ前插入一个节点
    // assert succ != null;
    final Node<E> pred = succ.prev;//succ原来的前一节点为pred
    final Node<E> newNode = new Node<>(pred, e, succ);//new一个新节点，前为pred，后为succ
    succ.prev = newNode;//然后将succ的prev指向新节点
    if (pred == null)//判断pred是否为null
        first = newNode;//是null说明succ是头节点，此时新的头节点就变成newNode了
    else
        pred.next = newNode;//前节点不为空，所以要将前节点的next更新为newNode
    size++;
    modCount++;
}
复制代码

当然还有其他一些添加方法，但底层都是这三个方法，列举一下：

boolean add(E e);//将指定的元素追加到此列表的末尾。
void add(int index, E element);//在此列表中的指定位置插入指定的元素。
boolean addAll(Collection<? extends E> c);//按照指定集合的迭代器返回的顺序将指定集合中的所有元素追加到此列表的末尾。
boolean addAll(int index, Collection<? extends E> c);//将指定集合中的所有元素插入到此列表中，从指定的位置开始。
void addFirst(E e);//在该列表开头插入指定的元素。
void addLast(E e);//将指定的元素追加到此列表的末尾。
复制代码

删除

//同理我们来看unlikFirst
private E unlinkFirst(Node<E> f) {//f不为null
    // assert f == first && f != null;
    final E element = f.item;//方法返回的是删除的头节点的值，所以要存一下
    final Node<E> next = f.next;//定义头节点的下一个节点是next
    f.item = null;//释放头节点的值
    f.next = null; // help GC //f的next（原来是next节点）设置为null
    first = next;//链表的first设置为next节点
    if (next == null)//判定next是否为null
        last = null;//next为空说明原链表只有一个头节点，删除之后，直接将last设置为null
    else
        next.prev = null;//next不为空，则next成为新的头节点，将next的prev从first设置成null
    size--;
    modCount++;
    return element;
}
//unlinkLast跟上面的unlinkFirst差不多不细讲了
private E unlinkLast(Node<E> l) {
    // assert l == last && l != null;
    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;
}
E unlink(Node<E> x) {
    // assert x != null;//x不为null，然后存一下x的值和前、后节点
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;

    if (prev == null) {
        first = next;//如果x的前节点为空，说明x是头节点，头节点删掉，要将first设置为next节点
    } else {
        prev.next = next;//前节点不为空，因为x被删除，所以前节点的next要指向后节点
        x.prev = null;//释放x的prev
    }

    if (next == null) {
        last = prev;//如果后节点为空，说明x是最后一个节点，删除最后一个节点要将last设置为prev节点
    } else {
        next.prev = prev;//后节点不为空，因为x被删除，所以要将后节点的prev指向前节点
        x.next = null;//然后释放x的next
    }
        x.item = null;
        size--;
        modCount++;
        return element;
    }
复制代码

更添加元素同理，删除元素的方法都是调用的以上的三种方法，下面列举一些remove方法的功能

E remove();//检索并删除此列表的头（第一个元素）。 
E remove(int index);//删除该列表中指定位置的元素。 
boolean remove(Object o);//从列表中删除指定元素的第一个出现（如果存在）。 
E removeFirst();//从此列表中删除并返回第一个元素。 
boolean removeFirstOccurrence(Object o);//删除此列表中指定元素的第一个出现（从头到尾遍历列表时）。 
E removeLast();//从此列表中删除并返回最后一个元素。 
boolean removeLastOccurrence(Object o);//删除此列表中指定元素的最后一次出现（从头到尾遍历列表时）。
复制代码

更新和查询

//set和get就比较简单了
public E set(int index, E element) {
    checkElementIndex(index);
    Node<E> x = node(index);
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}
public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}
复制代码

遍历

因为以上啰嗦了很多，所以遍历这里就不多写了，遍历主要的三种方法可以参考ArrayList的遍历方法。还有可以根据其他的一些方法poll、remove来遍历，但会删除原链表。

其他的一些注意点

前面也提到了LinkedList实现了Deque的接口，所以一些队列的操作是可以使用的，如下所示：

boolean offer(E e);//将指定的元素添加为此列表的尾部（最后一个元素）。 
boolean offerFirst(E e);//在此列表的前面插入指定的元素。
boolean offerLast(E e);//在该列表的末尾插入指定的元素。 
E peek();//检索但不删除此列表的头（第一个元素）。 
E peekFirst();//检索但不删除此列表的第一个元素，如果此列表为空，则返回 null 。 
E peekLast();//检索但不删除此列表的最后一个元素，如果此列表为空，则返回 null 。 
E poll();//检索并删除此列表的头（第一个元素）。 
E pollFirst();//检索并删除此列表的第一个元素，如果此列表为空，则返回 null 。 
E pollLast();//检索并删除此列表的最后一个元素，如果此列表为空，则返回 null 。 
E pop();//从此列表表示的堆栈中弹出一个元素。 
void push(E e);//将元素推送到由此列表表示的堆栈上。 
复制代码