概述

LinkedListlistDeque接口的双链列表实现。它实现所有可选的列表操作,并允许所有元素(包括null)。

特点

下面你可以找到LinkedList最重要的属性:

  • 索引到列表中的操作将从头到尾遍历列表,以更接近指定索引的操作为准
  • 它不是同步的
  • 它的迭代器和ListIterator迭代器是快速失败的(这意味着在迭代器创建之后,如果列表被修改,将抛出ConcurrentModificationException)
  • 每个元素都是一个节点,它保存对下一个和上一个元素的引用
  • 它保持插入顺序

尽管LinkedList未同步,但我们可以通过调用Collections.SynchronizedList方法检索他的同步版本,如:

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

与ArrayList对比

尽管它们都实现了List接口,但它们具有不同的含义——这肯定会影响使用哪个接口。

结构

ArrayList是由数组支持的基于索引的数据结构。它提供对其性能等于O(1)的元素的随机访问。

另一方面,LinkedList将其数据存储为元素列表,每个元素都链接到它的上一个和下一个元素。在本例中,对元素的搜索操作的执行时间等于O(n)

操作

LinkedList中,元素的插入、添加和删除操作速度更快,因为当元素被添加到集合中的任意位置时,不需要调整数组的大小或更新索引,只需要更改周围元素中的引用。

内存占用

LinkedListArrayList消耗更多的内存,因为LinkedList中的每个节点都存储两个引用,一个用于前一个元素,一个用于下一个元素,而ArrayList只保存数据和索引。

使用

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

创建

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

添加元素

LinkedList实现了ListDeque接口,除了标准的add()addAll()方法之外,您还可以找到addFirst()addLast(),它们分别在开头和结尾添加了一个元素。

删除元素

与元素添加类似,此列表实现提供了removeFirst()removeLast()

此外,还有方便的方法removeFirstOccurence()removelastoccurs(),它们返回布尔值(如果集合包含指定的元素,则为true)。

搜索操作

Deque接口提供了类似队列的行为(实际上Deque扩展了队列接口):

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

这些方法检索第一个元素并将其从列表中删除。

poll()pop()的区别在于,pop将抛出NoSuchElementException()到空列表,而poll返回null。api pollFirst()pollLast()也可用。

linkedList.push(Object o);

它将元素插入集合的头部。

LinkedList还有很多其他的方法,其中大部分对于已经使用过list的用户应该很熟悉。Deque提供的其他方法可能是“标准”方法的一个方便的替代方法。

总结

ArrayList通常是默认的列表实现。

然而,在某些特定的用例中,使用LinkedList会更合适,比如对固定插入/删除时间(例如频繁插入/删除/更新)、固定访问时间和有效内存使用。

【腾讯云】境外1核2G服务器低至2折,半价续费券限量免费领取!
https://cloud.tencent.com/act/cps/redirect?redirect=1068&cps_key=e4b50f6c64a4480367f8a8d16fd07c5a&from=console

标签: java, ArrayList, LinkedList

添加新评论