介绍 LinkedList 集合

一、历史LinkedList

Java还有一个集合类Java继承自C++语言。这是LinkedList实现“链表”的类。

从表面上看，aLinkedList似乎与 an 相同ArrayList。该类LinkedList具有与该类相同的所有方法ArrayList。原则上，您始终可以使用 aLinkedList而不是 an ArrayList，一切都会正常进行。

那么为什么我们需要另一个列表类呢？

答案与类的内部结构息息相关LinkedList。它不使用数组，而是使用双向链表。我们稍后会解释那是什么。

该类LinkedList不同的内部结构使其在列表中间插入元素的速度最快。

在网上经常可以找到类ArrayList和LinkedList类的对比：

add(value)

add(index, value)

get(index)

set(index, value)

remove(index)

一切似乎都很清楚：如果您需要经常向列表中插入元素，请使用LinkedList; 如果很少，则使用 ArrayList。但现实有点不同。

2. 没人用LinkedList

没有人使用LinkedList。

就连该课程的作者LinkedList最近也在推特上写道：“真的有人用吗LinkedList？我写的，我从来没用过。”

那有什么关系呢？

首先，该类ArrayList开始能够非常快速地将元素插入到列表的中间。在列表中间插入一个元素时，必须将插入点之后的所有元素向列表末尾移动 1。这过去需要时间。

但现在一切都变了。数组的所有元素在同一块内存中彼此靠近，因此移动元素的操作由一个非常快速的低级命令执行：。System.arraycopy()

此外，今天的处理器有一个大缓存，通常可以容纳整个数组，这允许数组元素在缓存内而不是在内存中移动。一百万个元素可以在一毫秒内轻松移动。

其次，如果您使用迭代器插入元素，该类可以快速插入元素。LinkedList如果使用迭代器遍历 aLinkedList并不断插入新元素（或删除现有元素），操作速度非常快。

LinkedList如果您只是在循环内向对象添加元素，那么每个快速插入操作都伴随着一个缓慢的“获取元素”操作。

现实更接近于此：

add(value)

add(index, value)

get(index)

set(index, value)

remove(index)

it.add(value)

it.remove()

为什么从如此缓慢的操作中获取元素LinkedList？

你可以在稍微了解一下它的LinkedList结构后回答这个问题。

3.LinkedList结构如何

LinkedList与 . 具有不同的内部结构ArrayList。它没有用于存储元素的内部数组。相反，它使用一种称为双墨列表的数据结构。

双向链表的每个元素都存储对前一个元素和下一个元素的引用。这有点像在商店排队，每个人都记得站在他们前面的人以及站在他们后面的人。

这是这样一个列表在内存中的样子：

头部和尾部（灰色背景的单元格）是first和last变量，它们存储对Node对象的引用。

在中间，你有一个Node对象链（对象，不是变量）。它们每个都包含三个字段：

• prev— 存储对前一个对象（黄色背景的单元格）的引用（链接）。Node
• value— 存储列表中该元素的值（绿色背景的单元格）。
• next— 存储对下一个对象（蓝色背景的单元格）的引用（链接）Node

第二个对象（地址 F24）是next第一个对象的下一个 ( ) 和prev第三个对象的前一个 ( )。第三个对象的黄色字段包含地址 F24，第一个对象的蓝色字段包含地址 F24。

第一个和第三个对象的箭头指向同一个第二个对象。所以这样画箭头会更正确。

4. 向链表中插入一个元素

要像这样添加某人，您只需要获得并排站着的两个人的许可即可。第一个人记得新人是“我身后的人”，第二个人记得他们是“我前面的人”。

您需要做的就是更改两个相邻对象的引用：

我们通过更改第二个和第三个对象的引用向我们的列表中添加了一个新项目。新对象是旧的第二个对象的下一个，旧的第三个对象的前一个。当然，新对象本身需要存储正确的引用：它的前一个对象是旧的第二个对象，它的下一个对象是旧的第三个对象。

删除一个元素更容易：如果我们想删除，比方说，列表中的第 100 个对象，我们只需要更改第 99 个对象的字段，使其next指向第 101 个对象，并更改第prev101 个对象的字段对象，使其指向第 99 个。就是这样。

但是获得第 100 个对象并不是那么容易。

5. 从列表中删除一个元素

要获取链表的第 100 个元素，您需要：

获取第一个对象：您使用对象first中的变量来执行此操作LinkedList。第一个对象的字段next存储对第二个对象的引用。这就是我们获得第二个对象的方式。第二个对象引用了第三个，依此类推。

如果我们需要获取第 100 个对象的引用，我们需要依次遍历从第 1 个到第 100 个的所有对象。如果我们需要列表中的第 100 万个元素，我们需要一个接一个地迭代一百万个对象！

并且如果这些对象在不同的​​时间被添加到列表中，它们将位于内存的不同部分并且不太可能同时在处理器的缓存中结束。这意味着迭代链表的元素不仅慢，而且非常慢。

这就是我们正在处理的。

那么我们为什么要教你这个慢是如何LinkedList工作的呢？

那么，在求职面试中，您将被问到与 . 有何LinkedList不同ArrayList。确实。