Skip to main content
 首页 » 编程设计

Java LinkedList 教程

2022年07月19日116mayingbao

本文介绍Java LinkedList数据结构。它常用于实现stack、queue,graph,另外稀疏矩阵的存储,HashMap为了防止hash code冲突也用到。

LinkedList 同时实现了List 和 Deque接口并实现了所有可用的方法,并支持元素为null 。

LinkedList特性

这里列举最常用的一些特性:

  • 访问元素必须从头或尾开始遍历
  • 不是同步的
  • Iterator 和 ListIterator 迭代器是快速失败模式(即迭代器创建之后,如果list被修改了,则会抛出ConcurrentModificationException异常)
  • 每个元素是一个节点,包括前面和后面节点的引用
  • 维护插入顺序

虽然LinkedList 不是同步的,我们可以利用 Collections.synchronizedList 实现同步版本:

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

对比ArrayList

虽然两者都实现了List接口,但语义不同,不同是应用场景不同。

  • 内部结构

    ArrayList底层基于数组按照索引访问的数据结构。提供元素随机访问方式,性能为O(1).

    LinkedList按照链表方式存储数据,每个元素于前后元素进行链接,这时搜索操作时间复杂度为 O(n).

  • 操作性能

    LinkedList的插入、添加、删除操作比较快,因为不需要扩大数组或更新索引(当增加元素至特定位置),仅引用周边元素会改变.

  • 内存使用

    LinkedList消费内存较ArrayList更多,因为其每个节点需要额外存储两个引用(前后节点的引用),ArrayList不需要存储该引用。

使用示例

下面通过一些示例代码展示如何使用LinkedList。

  • 创建

    LinkedList<Object> linkedList = new LinkedList<>(); 
    
  • 增加元素

    LinkedList 实现了List 和 Deque接口,除了标准的add 、addAll 方法,还有addFirst 、addLast分别在开头和结尾增加元素。

  • 删除元素

    与添加类似,list也提供了removeFirst() 和 removeLast() 。另外还提供好的 removeFirstOccurence()removeLastOccurence() 方法,用于删除首次出现或最后出现元素,如果包括该元素则返回true。

  • 队列操作

    Deque接口提供队列方式行为,如出队和入队:

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

​ 这些方法返回第一个元素并从列表中删除。两者的差异是,如果list为空pop方法会抛出NoSuchElementException异常,而poll返回null。 pollFirst()pollLast() 也可用。这里示例push方法:

linkedList.push(Object o); 

在list的开头插入元素。LinkedList 还有其他方法,大多数与list或与Deque的方法类似。

总结

ArrayList是List的缺省实现,但有时LinkedList 更合适,如在频繁的插入、删除、更新操作时,我们需要这些操作时间为常量。


本文参考链接:https://blog.csdn.net/neweastsun/article/details/120508469
阅读延展