关于java:LinkedList剖析

LinkedList是List家族除ArrayList之外最为罕用的另一成员，明天一文彻底搞懂LinkedList。

底层数据结构

LinkedList底层是一个双向链表：

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对象的item中，并保留指向上一节点、下一节点的对象。

再为整个LinkedList定义首节点first，尾结点last，不便对LinkedList的正向或逆向拜访。

LinkedList的容量

不应用数组存储数据，所以不存在容量的概念，能够有限存入。

数据存入

add（E e）/addlast(E e)：追加数据到链表尾部。
addfirst(E e):追加数据到链表头部。
push(E e)：压栈，等同于addfirst。
add(int index, E element)：追加数据到链表指定地位。
addAll(Collection<? extends E> c)：追加汇合c中的所有数据到链表尾部。
addAll(int index,Collection<? extends E> c)：追加汇合c中的所有数据到链表指定地位。

获取数据

contains(Object o)：判断链表是否蕴含指标对象。
peek()：获取链表第一个对象，并且不从链表中一处对象（不出栈）。
get(int index):获取指定地位对象。
pop()：获取链表第一个数据并出栈。
removeFirst():等同于pop。

因为LinkedList是双向链表构造，实现了Deque接口，提供了一系列十分不便的队列操作方法，所以，如果有相似比方先进先出、先进后出等队列操作需要的场景，LinkedList是首选。