Java 容器总结(二)

Java 容器总结(二) —— LinkedList

1、LinkedList 与 ArrayList 一样，同样实现了 List 接口，而 List 接口扩展了 Collection 接口，Collection 又扩展了 Iterable 接口，所有这些接口的方法都是可以使用的。

1
2
3

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable {}

2、队列 (Queue)
LinkedList 还实现了队列接口 Queue，队列的特点就是先进先出，在尾部添加元素，从头部删除元素。

 public interface Queue<E> extends Collection<E> {
    boolean add(E e);
    boolean offer(E e);
    E remove();
    E poll();
    E element();
    E peek();
}

Queue 扩展了 Collection，它的主要操作有三个：

在尾部添加元素 (add, offer)。

查看头部元素 (element, peek)，返回头部元素，但不改变队列。

删除头部元素 (remove, poll)，返回头部元素，并且从队列中删除。

每种操作都有两种形式，区别在于，对于特殊情况的处理不同。特殊情况是指，队列为空或者队列为满。为满是指队列有长度大小限制，而且已经占满了。LinkedList 的实现中，队列长度没有限制，但别的 Queue 的实现可能有。

在队列为空时，element 和 remove 会抛出异常 NoSuchElementException，而 peek 和 poll 返回特殊值 null，在队列为满时，add 会抛出异常 IllegalStateException，而 offer 只是返回 false。

3、栈
栈也是一种常用的数据结构，与队列相反，它的特点是先进后出、后进先出。Java 中用 Stack 类来表示栈，但这个类已经过时了，就 Stack 而言，在新的设计中，Queue 可以直接取代它。Java 中没有单独的栈接口，栈相关方法包括在了表示双端队列的接口 Deque 中。

// push 表示入栈，在头部添加元素，栈的空间可能是有限的，如果栈满了，push 会抛出异常 IllegalStateException
void push(E e);
// pop 表示出栈，返回头部元素，并且从栈中删除，如果栈为空，会抛出异常 NoSuchElementException
E pop();
// peek 查看栈头部元素，不修改栈，如果栈为空，返回 null
E peek();

4、双端队列 (Deque)
栈和队列都是在两端进行操作，栈只操作头部，队列两端都操作，但尾部只添加、头部只查看和删除，有一个更为通用的操作两端的接口 Deque，Deque 扩展了 Queue，包括了栈的操作方法，此外，它还有更为明确的操作两端的方法。

xxxFirst 操作头部，xxxLast 操作尾部。与队列类似，每种操作有两种形式，区别也是在队列为空或满时，处理不同。为空时，getXXX/removeXXX 会抛出异常，而 peekXXX/pollXXX 会返回 null。队列满时，addXXX 会抛出异常，offerXXX 只是返回 false。

栈和队列只是双端队列的特殊情况，它们的方法都可以使用双端队列的方法替代，不过，使用不同的名称和方法，概念上更为清晰。

5、LinkedList 内部组成
LinkedList 直译就是链表，确切的说，它的内部实现是双向链表，每个元素在内存都是单独存放的，元素之间通过链接连在一起。

为了表示链接关系，需要一个节点的概念，节点包括实际的元素，但同时有两个链接，分别指向前一个节点(前驱)和后一个节点(后继)，节点是一个内部类。

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

LinkedList 内部组成中有三个实例变量：

// size 表示链表长度，默认为 0
transient int size = 0;
transient Node<E> first;
transient Node<E> last;

LinkedList 的所有 public 方法内部操作的都是这三个实例变量。

6、 add() 方法源码解析

public boolean add(E e) {
    linkLast(e);
    return true;
}
---------------------
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++;
}

7、根据索引访问元素 get()

public E get(int index) {
    // 检查索引位置的有效性，如果无效，抛出异常
    checkElementIndex(index);
    return node(index).item;
}
------------------------
private void checkElementIndex(int index) {
    if (!isElementIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
-------------------------
private boolean isElementIndex(int index) {
    return index >= 0 && index < size;
}
-------------------------
Node<E> node(int index) {
    // 根据 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;
    }
}

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

9、指定位置插入元素 add(int index, E element)

public void add(int index, E element) {
    checkPositionIndex(index);

    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}
----------------------------
private void checkPositionIndex(int index) {
    if (!isPositionIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
----------------------------
private boolean isPositionIndex(int index) {
    return index >= 0 && index <= size;
}
-----------------------------
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++;
}
----------------------------
// 参数 succ 表示后继节点。变量 pred 就表示前驱节点。目标就是在 pred 和 succ 中间插入一个节点。
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++;
}

10、删除元素

public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}
--------------------------
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;
}

11、需要注意的是：对于队列、栈和双端队列接口，长度可能有限制，LinkedList 实现了这些接口，不过 LinkedList 对长度并没有限制。使用的时候需要特别留意那些限制。

12、对于 LinkedList 内部是用双向链表实现的，维护了长度、头节点和尾节点，这决定了它有如下特点：

按需分配空间，不需要预先分配很多空间。

不可以随机访问，按照索引位置访问效率比较低，必须从头或尾顺着链接找，效率为 O(N/2)。

不管列表是否已排序，只要是按照内容查找元素，效率都比较低，必须逐个比较，效率为 O(N)。

在两端添加、删除元素的效率很高，为 O(1)。

在中间插入、删除元素，要先定位，效率比较低，为 O(N)，但修改本身的效率很高，效率为 O(1)。

参考博客

Java编程的逻辑 - 剖析 LinkedList