1. 介绍
LinkedList是一个双向链表, 实现了List和Deque接口。它实现所有可选的list操作,并且存储对象可以为null。
2. 特点
LinkedList具有以下特点:
- 查到列表中的元素,需要从头至尾的遍历列表
- 没有同步
- 它的Iterator和ListIterator迭代器是快速失败的(这意味着在迭代器创建之后,如果修改了列表,将抛出一个ConcurrentModificationException)
- 每个元素都是一个节点,它保留对下一个和前一个节点的引用
- 维护了插入顺序
虽然LinkedList没有同步,但是我们可以通过调用Collections.synchronizedList方法创建它的同步版本,如:
List list = Collections.synchronizedList(new LinkedList(...));
3. 与ArrayList比较
虽然它们都实现了List接口,但它们具有不同的语义,这将影响我们使用哪一个。
3.1 结构体
ArrayList是基于索引的数据结构,它提供了对其元素的随机访问,其性能为O(1)。
LinkedList将数据存储为元素列表,并且每个元素都链接到上一个和下一个元素。在这样情况下,其元素搜索的复发度为O(n)。
3.2 操作
对LinkedList中的元素进行插入,删除操作更快,因为当元素添加到集合内的某个位置时,不需要调整数组的大小或更新索引,只需更改前后元素的pre和next指针即可。
3.3 内存的使用情况
LinkedList的内存占用比ArrayList更多,因为在每一个接口都需要存储两个引用,一个用于记录前一个元素,一个用于记录后一个元素。而ArrayList中仅需要保持数据和它的索引。
4. 用法
以下是一些代码示例,展示了如何使用LinkedList:
4.1 创建
LinkedList<Object> linkedList = new LinkedList<>();
4.2 添加元素
LinkedList实现了List和Deque接口,除了标准的add()和addAll(),还提供了addFirst()和addLast(),它们分别在开头或结尾添加一个元素。
4.3 删除元素
与元素添加类似,LinkedList还提供了removeFirst()和removeLast()。
此外,还有方便的方法removeFirstOccurence()和removeLastOccurence()返回boolean。如果collection中包含了指定的元素,则返回true。
4.4 队列操作
Deque接口提供类似队列的行为(实际上Deque扩展了Queue接口):
linkedList.poll();
linkedList.pop();
这些方法检索第一个元素并将其从列表中删除。poll()和pop()的区别是当列表为空时,pop就会抛出NoSuchElementException()异常,而poll则会返回null。
linkedList.push(Object o);
push将在列表头添加一个元素。
LinkedList还有许多其他操作,使用方式与List和Deque一样。
5. 结论
ArrayList通常是默认的List实现。
但是,在某些使用情况下,使用LinkedList会是更好的选择。例如需要频繁的插入,删除,更新列表元素时。