目录
1. 概述2. 特性3. LinkedList vs ArrayList3.1 底层实现结构3.2 基本操作3.3 内存占用4. 基本用法4.1 Create LinkedList(同步和非同步)4.2 添加元素4.3 删除元素4.4 队列操作5. 总结
1. 概述
源码里面的注释说：LinkedList一种双向链表的实现，实现了接口List和Deque（Java零基础手把手系列：Queue最简入门)，它实现了所有链表的操作，可以存储任何元素，包括null。
/**
* Doubly-linked list implementation of the {@code List} and {@code Deque}
* interfaces. Implements all optional list operations, and permits all
* elements (including {@code null}).
...
**/
本文将讲述该数据结构的基本类型和方法，并举例说明其简单的应用。
2. 特性
我们先来看一下LinkedList的一些基本特性：
它的内部数据结构是一个叫Node的节点：
通过index获取元素很慢，因为需要从头到尾的遍历（虽然源码里面有加速实现：如果index < 双向链表长度的1/2，则从前向后查找; 否则，从后向前查找）
/**
* Returns the element at the specified position in this list.
*
* @param index index of the element to return
* @return the element at the specified position in this list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
/**
* Returns the (non-null) Node at the specified element index.
*/
Node<E> node(int index) {
// assert isElementIndex(index);
//如果index < 双向链表长度的1/2，则从前向后查找; 否则，从后向前查
if (index < (size >> 1)) {
//因为头部复制给x
Node<E> x = first;
//所以从0 遍历到 index - 1
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;
}
}
不是同步的，不是线程安全的
它的Iterator和ListIterator迭代器是fail-fast的（什么意思呢，指的是在获取到迭代器之后，如果修改了列表，将抛出一个ConcurrentModificationException)
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
每一个元素都是一个Node节点，该节点保存了前一个元素、后一个元素的引用
LinkedList维持插入的顺序
3. LinkedList vs ArrayList
虽然两者都是List接口的实现类，但是还是有自己的特点，不同的特点决定了什么样的场景该使用哪一个
3.1 底层实现结构
ArrayList查询快
ArrayList的底层数据结构是数组，可以通过index随机获取元素，且时间复杂度是O(1)
LinkedList底层数据结构是链表，也就是每一个元素都会保存他的前一个，后一个元素的引用。因此，在LinkedList上面的查询操作是O(n)
3.2 基本操作
插入、添加、删除操作LinkedList比ArrayList快
LinkedList做上述操作的时候，只需要改变其previous和next指针的引用即可
ArrayList做上述操作，需要resize或者update index
3.3 内存占用
ArrayList更省内存
ArrayList每一个元素只需要保存它的data和index
LinkedList每一个元素除了data，还有previous和next引用
4. 基本用法
本小节展示LinkedList的基本使用
4.1 Create LinkedList(同步和非同步)
默认的创建如下：
LinkedList<String> linkedList = new LinkedList<>();
虽然LinkedList不是线程安全的，但是我们可以通过调用Collections.synchronizedList方法创建它的同步版本：
List list = Collections.synchronizedList(new LinkedList(...));
4.2 添加元素
LinkedList实现了List和Deque，所以：
add：添加元素到链表尾部
addAll：添加指定的一堆元素到链表尾部
addFirst：添加元素到链表头部
addLast：添加元素到链表尾部
4.3 删除元素
和添加一样，提供removeFirst和removeLast，这里不解释了，特别介绍一下：
removeFirstOccurence（Object o）：删除第一次出现的元素o，也就是从头到头的遍历，直到发现第一个。如果操作成功返回true
removeLastOccurence（Object o）：同First的操作，删除最后一次出现的元素o
4.4 队列操作
Deque接口提供Queue的行为（参考文章:4.Java零基础手把手系列：ArrayDeque简洁却不简单入门）：
//检索第一个元素
linkedList.poll();
//出队一个元素
linkedList.pop();
//入队一个元素o
linkedList.push(Object o);
poll()和pop()的区别是当列表为空时，pop就会抛出NoSuchElementException()异常，而poll则会返回null。
push将在列表头添加一个元素。
LinkedList还有许多其他操作，使用方式与List和Deque一样，有不懂的可以讨论。
5. 总结
一般情况下，如果使用到List，都会选择ArrayList
但是在有些使用情况下，使用LinkedList会是更好的选择，比如需要频繁的插入，删除，更新列表元素时。
注释：内容来自微信公众号写bug咯，版权归原作者所有。
