1. 介绍

LinkedListListDeque*接口的双链表实现。它实现了所有可选的列表操作,并允许插入任何元素,包括 null。

2特点

LinkedList 主要特点包括:

  • 查找索引,需要从头到尾遍历
  • synchronized,即非线程安全
  • IteratorListIterator 迭代器具 fail-fast 特性(遍历过程中如果列表结构被修改,将抛出 ConcurrentModificationException 异常)
  • 每个元素都是一个节点,它保存着对下一个和上一个元素的引用
  • 其维护了插入顺序

虽然 LinkedList 非线程安全,但我们可以通过调用 Collections.synchronizedList 方法来获取其线程安全版本,例如

List list = Collections.synchronizedList(new LinkedList(...));

3. 与 ArrayList 相比较

虽然它们都实现了 List 接口,但其底层数据结构和使用场景有所不同。

3.1. 数据结构

ArrayList 基于索引,底层使用数组作为数据结构。它提供对其元素的随机访问的能力,时间复杂度相当于 O(1)。

LinkedList 基于链表实现,每个元素都保存着下一个和上一个元素的引用。查找一个元素的的时间复杂度等于 O(n)。

3.2. 操作

LinkedList 在元素的插入、新增和删除操作速度上更快,因为当一个元素被添加到集合内的任意位置时,无需调整数组的大小或更新索引,只有周围元素的引用会发生变化。

3.3. 内存使用

LinkedListArrayList 消耗更多内存,因为 LinkedList 中的每个节点都存储两个引用,一个是上一个元素的引用,另一个是下一个元素的引用,而 ArrayList 只存储数据及其索引。

4. 用法

下面是一些代码示例,展示了如何使用 LinkedList

4.1. 新建List

LinkedList<Object> linkedList = new LinkedList<>();

4.2. 插入元素

LinkedList 实现了 ListDeque 接口,除了标准的 add()addAll() 方法外,你还可以使用 addFirst()addLast() ,在List起始位置或结尾添加一个元素。

4.3. 删除元素

与元素添加类似,LinkedList实现也提供 removeFirst()removeLast() 功能。

此外,removeFirstOccurence()removeLastOccurence() 方法也很方便,可返回布尔值(如果集合包含指定元素,则返回 true)。

4.4. 队列操作

Deque 接口提供类似队列的行为(实际上 Deque 继承了 Queue 接口):

linkedList.poll();
linkedList.pop();

上面方法会获取第一个元素,并将其从列表中删除。

*poll()pop()*的区别在于, pop 会在空列表中抛出 NoSuchElementException() ,而 poll 则返回空值。此外,还提供了 pollFirst()pollLast() 接口。

下面是 push 的用法:

linkedList.push(Object o);

其将该元素插入到集合的起始位置。

LinkedList 还有许多其他方法,对于已经使用过 Lists 的开发者来说,其中大部分方法应该都不陌生。Deque 提供的其他方法可能是 "标准 "方法的一种方便的替代方法。

完整的文档可在 此处 找到。

5. 总结

ArrayList 通常是默认的 List 实现。

不过,在某些使用情况下,使用 LinkedList 会更合适,例如,频繁插入/删除/更新。

本文中的代码可在 GitHub 上找到。