首页 Java

LinkedList 类继承了 AbstractSequentialList 抽象类，实现了 List、Deque、Cloneable、Serializable 接口。由此可以看出，LinkedList 也是一种双端队列。

LinkedList 是基于链表实现的，每个元素是一个结点。

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;
    }
}
LinkedList 类有三个属性，size 表示大小，first 表示链表的第一个元素，last 表示链表的最后一个元素。
transient int size = 0;
transient Node<E> first;
transient Node<E> last;
LinkedList 类有两个构造方法，有参和无参构造。无参构造就创建一个空的 list，有参构造先创建一个空的 list，然后将参数添加到 list 中。
public LinkedList() {
}
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}
getFirst 方法获取第一个元素的值。
public E getFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return f.item;
}
getLast 方法获取最后一个元素的值。
public E getLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return l.item;
}
removeFirst 方法移除第一个元素。unlinkFirst 方法断言参数就是 list 中的第一个元素且不为 null。
public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}
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--;
    modCount++;
    return element;
}
removeLast 方法移除 list 的最后一个元素。unlinkLast 方法断言参数是最后一个元素且不为 null。
public E removeLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return unlinkLast(l);
}
private E unlinkLast(Node<E> l) {
    final E element = l.item;
    final Node<E> prev = l.prev;
    l.item = null;
    l.prev = null; 
    last = prev;
    if (prev == null)
        first = null;
    else
        prev.next = null;
    size--;
    modCount++;
    return element;
}
addFirst 方法将制定元素添加到第一个元素。
public void addFirst(E e) {
    linkFirst(e);
}
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++;
}
addLast 方法将制定元素添加到最后一个元素。
public void addLast(E e) {
    linkLast(e);
}
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++;
}
contains 方法判断 list 是否包含指定元素。
public boolean contains(Object o) {
    return indexOf(o) != -1;
}
size 方法返回 list 的大小。
public int size() {
    return size;
}
add 方法向 list 末尾添加一个元素。与 addLast 方法类似，只是这个方法返回的是布尔值。
public boolean add(E e) {
    linkLast(e);
    return true;
}
remove 方法移除指定元素，unlink 方法断言参数不为 null。
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;
}
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;
    }
    x.item = null;
    size--;
    modCount++;
    return element;
}
addAll 方法向 list 中添加一个集合。
public boolean addAll(Collection<? extends E> c) {
    return addAll(size, 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;
}
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;
    }
}
indexOf 方法返回指定元素的位置。
public int indexOf(Object o) {
    int index = 0;
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null)
                return index;
            index++;
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item))
                return index;
            index++;
        }
    }
    return -1;
}
lastIndexOf 方法从后向前遍历返回 list 中指定元素的位置。
public int lastIndexOf(Object o) {
    int index = size;
    if (o == null) {
        for (Node<E> x = last; x != null; x = x.prev) {
            index--;
            if (x.item == null)
                return index;
        }
    } else {
        for (Node<E> x = last; x != null; x = x.prev) {
            index--;
            if (o.equals(x.item))
                return index;
        }
    }
    return -1;
}
peek 方法返回第一个元素的值。与 getFirst 方法区别是，此方法当第一个元素为空时返回 null，getFirst 方法当第一个元素为空时会抛出异常。
public E peek() {
    final Node<E> f = first;
    return (f == null) ? null : f.item;
}
element 方法返回第一个元素的值。
public E element() {
    return getFirst();
}
poll 方法返回并移除第一个元素。
public E poll() {
    final Node<E> f = first;
    return (f == null) ? null : unlinkFirst(f);
}
remove 方法移除第一个元素。
public E remove() {
    return removeFirst();
}
offer 方法将元素添加到 list 中。
public boolean offer(E e) {
    return add(e);
}
offerFirst 方法将元素添加到 list 中的最前面，最后返回布尔值。
public boolean offerFirst(E e) {
    addFirst(e);
    return true;
}
offerLast 方法将元素添加到 list 中的末尾，最互返回布尔值。
public boolean offerLast(E e) {
    addLast(e);
    return true;
}
peekFirst 方法返回 list 的第一个元素的值。
public E peekFirst() {
    final Node<E> f = first;
    return (f == null) ? null : f.item;
 }
peekLast 方法返回 list 的最后一个元素的值。
public E peekLast() {
    final Node<E> l = last;
    return (l == null) ? null : l.item;
}
pollFirst 方法返回并移除第一个元素。
public E pollFirst() {
    final Node<E> f = first;
    return (f == null) ? null : unlinkFirst(f);
}
pollLast 方法返回并移除最后一个元素。
public E pollLast() {
    final Node<E> l = last;
    return (l == null) ? null : unlinkLast(l);
}
push 方法在 list 最前面添加一个元素。
public void push(E e) {
    addFirst(e);
}
pop 方法移除掉最后一个元素。
public E pop() {
    return removeFirst();
}
removeFirstOccurrence 方法从前向后遍历移除指定元素。
public boolean removeFirstOccurrence(Object o) {
    return remove(o);
}
removeLastOccurrence 方法从后向前遍历移除指定元素。
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;
}