目录
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咯,版权归原作者所有。