类结构
成员变量
Node
构造函数
增
删
改
查
- 总结
总结

JDK version- 1.8

类结构

双向链表。在 jdk 1.7之前，是双向循环链表。
LinkedList 实现了 List、Deque 接口，所以它可以表示标准的集合 List，双向链表 Deque，由于 Deque 集成与 Queue 接口，所以它还可以表示队列 Queue。

成员变量

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    //链表长度
    transient int size = 0;
    /**
     * 头结点
     */
    transient Node<E> first;
    /**
     * 尾结点
     */
    transient Node<E> last;
 }

一个头结点，和一个尾结点。以及链表的长度。

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

结构很简单，一个前置节点，一个后续节点。还有一个表示当前节点值的 item 字段。

构造函数

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

增

add(E e)、add(int index, E element)、addAll(Collection<? extends E> c)、addAll(int index, Collection<? extends E> c)、addFirst(E e)、addLast(E e)、offerFirst(E e)、offerLast(E e)、offer(E e)、push(E e)

-------------------------------------------添加节点到尾部-------------------------------------------
//----------》List、Deque、Queue 三个接口都有的方法。有返回值
public boolean add(E e) {
    //插入到最后
    linkLast(e);
    return true;
}
//----------》Deque 接口独有。无返回值
public void addLast(E e) {
    linkLast(e);
}
//----------》Queue 接口所有。有返回值
public boolean offer(E e) {
    return add(e);
}
//----------》Deque 接口独有。有返回值
public boolean offerLast(E e) {
    addLast(e);
    return true;
}
-------------------------------------------添加节点到头部-------------------------------------------
//----------》Deque接口独有。无返回值
public void addFirst(E e) {
    linkFirst(e);
}
//----------》Deque接口独有。有返回值
public boolean offerFirst(E e) {
    addFirst(e);
    return true;
}
//----------》Deque接口独有。无返回值
public void push(E e) {
    addFirst(e);
}
-------------------------------------------其它-------------------------------------------
//----------》 指定位置插入数据，List 接口独有
public void add(int index, E element) {
    //检测 index 是否合法
    checkPositionIndex(index);
    if (index == size)
        //插入到最后
        linkLast(element);
    else
        //插入到 index 所在节点的前面。
        linkBefore(element, node(index));
}
//----------》添加集合，Collection 接口中有这个方法，List 和 Queue 都继承与 Collection。
//所以 List、Deque、Queue 都有这个方法。
public boolean addAll(Collection<? extends E> c) {
    return addAll(size, c);
}
//----------》指定位置添加集合，List接口独有
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 {
        //在中间添加集合，先找到 index 所指向的节点。
        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;
}

总结

末尾添加元素方法

add(E e)(List、Deque、Queue，返回操作是否成功 Boolean) addLast(E e)(Deque，无返回值) offer(E e)(Queue，返回操作是否成功 Boolean) offerLast(E e)(Deque，返回操作是否成功 Boolean)。

头部添加元素方法

addFirst(E e)(Deque，无返回值) offerFirst(E e)(Deque，返回操作是否成功 Boolean) push(E e)(Deque，无返回值)。

其它添加元素方法

add(int index, E element) 添加数据到指定位置，无返回值，(List)； addAll(Collection<? extends E> c) 添加集合，无返回值，(List、Deque、Queue)； addAll(int index, Collection<? extends E> c) 添加集合到指定位置，返回操作是否成功 Boolean，(List)。

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

linkLast

void linkLast(E e) {
    final Node<E> l = last;
    //将最后一个节点设置为要插入节点的前置节点
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        //如果最后一个节点为 null，说明这个链表为空，那么第一个节点就指向要插入的节点。
        first = newNode;
    else
        //不为空，最后一个节点的后续节点指向要插入的节点。
        l.next = newNode;
    size++;
    modCount++;
}

node(int index)

根据下标找到当前下标对应的节点

Node<E> node(int index) {
    // assert isElementIndex(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;
    }
}

linkBefore

添加节点到指定的节点前面

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

删

-------------------------------------------移除头结点-------------------------------------------
//Queue 所有。所以 Queue、Deque 都有
public E remove() {
    return removeFirst();
}
//Deque 独有
public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}
//Deque 独有
public E pop() {
    return removeFirst();
}
//Queue 所有。所以 Queue、Deque 都有
public E poll() {
    final Node<E> f = first;
    return (f == null) ? null : unlinkFirst(f);
}
//Deque 独有
public E pollFirst() {
    final Node<E> f = first;
    return (f == null) ? null : unlinkFirst(f);
}
-------------------------------------------移除尾结点-------------------------------------------
//Deque 独有
public E removeLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return unlinkLast(l);
}
//Deque 独有
public E pollLast() {
    final Node<E> l = last;
    return (l == null) ? null : unlinkLast(l);
}
-------------------------------------------其它移除-------------------------------------------
//移除指定位置对象。List 独有
public E remove(int index) {
    checkElementIndex(index);
    //先找到 index 对应的节点，然后再移除。
    return unlink(node(index));
}
//移除指定对象。 Collection所有，所以Deque、List、Queue 都有。
public boolean remove(Object o) {
    //移除首个相等的对象。
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}
//从头结点开始，移除首次发现的对象，list 中可以多次添加相同对象。Deque 独有
public boolean removeFirstOccurrence(Object o) {
    return remove(o);
}
//从尾结点开始，移除首次发现的对象，list 中可以多次添加相同对象。Deque 独有
public boolean removeLastOccurrence(Object o) {
    if (o == null) {
        for (Node<E> x = last; x != null; x = x.prev) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        for (Node<E> x = last; x != null; x = x.prev) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}
//清除所有数据， Collection所有，所以Deque、List、Queue 都有。
public void clear() {
    //循环遍历，清除所有节点。
    for (Node<E> x = first; x != null; ) {
        Node<E> next = x.next;
        x.item = null;
        x.next = null;
        x.prev = null;
        x = next;
    }
    first = last = null;
    size = 0;
    modCount++;
}

总结

移除头结点

remove() 抛异常，Queue 所有，所以 Queue、Deque 都有。返回移除的元素。 removeFirst() 抛异常，Deque 独有。返回移除的元素。 pop() 抛异常，Deque 独有。返回移除的元素。 poll() 不抛异常，Queue所有，所以 Queue、Deque 都有。返回移除的元素。 pollFirst() 不抛异常，Deque 独有。返回移除的元素。

移除尾结点

removeLast() 不抛异常，Deque 独有。返回移除的元素。 pollLast() 不抛异常，Deque 独有。返回移除的元素。

其它移除方法
以下这几个方法都不抛异常

remove(int index) 移除指定位置对象。List 独有。返回操作是否成功，boolean。 remove(Object o) 移除指定对象。 Collection所有，所以Deque、List、Queue 都有。返回操作是否成功 boolean。 removeFirstOccurrence(Object o) 从头结点开始，移除首次发现的对象。Deque 独有。返回操作是否成功 boolean。 removeLastOccurrence(Object o) 从尾结点开始，移除首次发现的对象。Deque 独有。返回操作是否成功 boolean。 clear() 清除所有数据， Collection所有，所以Deque、List、Queue 都有。无返回值。

unlink

E unlink(Node<E> x) {
    // assert x != null;
    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;
    }
    x.item = null;
    size--;
    modCount++;
    return element;
}

unlinkFirst

private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    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;
}

将要移除节点和这个节点的后续节点断开，并将这个节点的值返回出去。

unlinkLast

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

改

//修改制定位置的数据。List 独有。
public E set(int index, E element) {
    //检测 index 是否合法
    checkElementIndex(index);
    //获取 index 上的节点，并修改上面的值。
    Node<E> x = node(index);
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}

对于 Queue 和 Deque，是不支持直接修改指定位置的值的。

查

-------------------------------------------查询头结点-------------------------------------------
//Queue 所有。
public E peek() {
    final Node<E> f = first;
    return (f == null) ? null : f.item;
}
//Queue 所有。
public E element() {
    return getFirst();
}
//Deque 所有。
public E peekFirst() {
    final Node<E> f = first;
    return (f == null) ? null : f.item;
}
//Deque 所有。
public E getFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return f.item;
}
-------------------------------------------查询尾结点-------------------------------------------
//Deque 独有。
public E getLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return l.item;
}
//Deque 独有。
public E peekLast() {
    final Node<E> l = last;
    return (l == null) ? null : l.item;
}
-------------------------------------------其它查询-------------------------------------------
//获取指定位置的值，List 独有
public E get(int index) {
    //检测 index 是否合法。
    checkElementIndex(index);
    //获取index指向的 Node，返回 node 中的值。
    return node(index).item;
}

总结

查询头结点

peek() 不抛异常，Queue 所有，所以 Queue、Deque 都有。返回查询到的元素。 element() 不抛异常，Queue 所有，所以 Queue、Deque 都有。返回查询到的元素。 peekFirst() 不抛异常，Deque 独有。返回查询到的元素。 getFirst() 抛异常，Deque 独有。返回查询到的元素。

查询尾结点

getLast() 抛异常，Deque 独有。返回查询到的元素。 peekLast() 不抛异常，Deque 独有。返回查询到的元素。

其它

get(int index) 获取指定位置的值，List 独有

总结

Queue 的 offer 添加方法是添加尾结点，poll 是移除头结点。这里也可以看出队列是先进先出的顺序。
Deque 的 push 是添加头结点，pop 是移除头结点。所以这两个方法对应的是先进后出，后进先出的顺序。对应栈的结构。
Deque 的其它方法，如：addFirst，addLast，offerFirst，offerLast，removeFirst，removeLast，pollFirst，pollLast 都是见名知其义了。