Java中的LinkedList在内部是如何工作的？

Question

据我所知，链表的概念是一组通过具有“下一个”和有时还有“前一个”属性来连接彼此的对象，以遍历这些对象。

我注意到在Java中，您可以创建LinkedList对象...但使用与数组/列表/序列相同的方法（如.add（）、.get()等）对待它。

那么，LinkedList在内部是类似于数组的序列吗？

- sqram

---

如果您想查看实现，请查找java.util.LinkedList的源代码，您可以在JDK安装目录下的文件src.zip中找到。 - Jesper

请查看源代码：http://www.docjar.com/html/api/java/util/LinkedList.java.html - Matthew Farwell

你可能会对我的 Java中LinkedList的内部实现 教程感兴趣。 - Volodymyr Levytskyi

Answer 1

所以，LinkedList内部是一个类似数组的序列吗？ 不是。它是一个私有嵌套类Entry的一系列实例，该类具有next、previous和element引用。请注意，通过查看随JDK一起提供的源代码，您可以自己找到这个答案。 之所以不暴露这种内部结构是为了防止结构被破坏，例如包含一个循环。同时，通过List和Deque接口的统一访问，允许多态使用。

- Michael Borgwardt

---

名为 ArrayList 的列表内部是类似于数组的序列。;) - Peter Lawrey

我猜这取决于你的编程技能。从维基百科关于链表的文章中可以看到：“它也可能很慢，并且使用天真的分配器为每个新元素单独分配内存会很浪费，这通常是通过使用内存池来解决的。” -- FYI，内存池是专业人士用于内部存储链表的数组。它们也被称为slab分配器。 - Anthony Blake

@Anthony：报复性的负评，嗯？别纠结了。有经验的专业人士不会为了问题应该回答在哪个层次而在互联网上争吵不休。 - Michael Borgwardt

@MichaelBorgwardt 绝对不是。我同意你的回答“不”在大多数应用和实现中是正确的，但并非全部。当性能是一个问题时，你实际上可以使用数组作为底层数据结构来实现链表 - 正如维基百科文章所说的那样。 - Anthony Blake

@Anthony: 当然可以，但问题是关于Java标准API类LinkedList的，它不使用数组。JVM可能会使用，但如果你坚持“更深入”地探讨，你也可以开始谈论数组的“连续内存”实际上并不是因为为了提高性能，它在物理RAM模块之间和个别芯片之间交错。 - Michael Borgwardt

Answer 2

在Java中，LinkedList的工作方式和你期望的一样。如果你使用官方的Collections LinkedList，那么它确实是一个一堆对象通过'下一个'和有时'前一个'相互连接的数据结构。

是的，它有一个get(int index)方法，这令人惊讶，因为这不是LinkedList擅长的操作方式。要查找第index个元素，你需要从开头开始计数，并逐步遍历列表，这并不高效。它存在的原因是LinkedList实现了List接口，所有类型的列表都可以使用该接口。

然而，当你经常通过get(int index)方法访问LinkedList时，你应该尽量避免使用它，因为这会导致效率低下。你可能最好使用ArrayList。

- OldCurmudgeon

Answer 3

LinkedList是一个实体链，每个实体都知道下一个实体， 所以get(index)操作需要使用计数器在这个链上进行迭代。 但是这个列表针对按位置添加和删除进行了优化（在需要将元素放入列表或从中间删除元素的情况下，链表的表现更好）。

- Stanislav Levental

Answer 4

据我所知，链表就像你在第一段所说的那样。每个对象都有两个引用，称为它的前一个和后一个。 与数组不同，数组按顺序工作（在C中它确切地按顺序存储。我认为Java也是这样做的，这就是为什么我们无法调整数组大小的原因），而列表通过引用工作。因此从逻辑上讲，它比数组工作要慢。

- simaremare

Answer 5

可以使用链表来实现像数组一样工作的对象。与数组相比，某些操作将更快，而某些操作将更慢。例如，对于接近末尾的元素调用get()可能会比使用数组慢得多。但是，这仍然是可能的。

另一方面，从链表中间删除一个元素将比使用数组执行相应操作更快。

- Greg Hewgill

Answer 6

不完全是。链表由集合提供，并且通过良好的设计，您可以创建双向链表。现在它不像数组，因为这些对象将没有索引，并且不是容器内的元素，即列表。因此，您需要定义下一个和上一个，并指定下一步操作。它们都具有相同的方法，因为它们再次像我说的那样是集合。

- sys_debug

Answer 7

那么，LinkedList在内部是类似于数组的序列吗？ 不是，它是双向链表实现。

- Nisarg Patil

Answer 8

在内部，它将使用所谓的“slab分配器”--这基本上是一系列小数组的链表。每次添加一个对象时，它会检查slab中是否有空间，如果有，则将对象放在那里。否则，它会分配一个新的slab并将对象放在slab的第一个元素中。

这种技术最小化了内存分配开销--如果您向链接列表添加大量项目，那将是许多小内存分配，这需要很长时间，而slab分配器可以将其最小化。

- Anthony Blake

---

这是完全错误的。Java不是C++。小的分配是快速的。因此，API实现不使用任何技巧来避免它。 - Michael Borgwardt

从IBM JVM文档中得知：“这些部分通常被实现为连续的本地内存块，这些内存块受Java内存管理器（包括垃圾收集器）控制。” - Anthony Blake

@MichaelBorgwardt 哈哈 @“小分配很快”--它们之所以在Java中快，是因为JVM一直在分配本地内存的块。 - Anthony Blake

@Anthony Blake，那为什么不深入解释一下malloc()的工作原理呢？您使用哪个JVM实现作为参考？也存在8 KiB JVMs。这些实现非常简单。在这里回答问题时，您只是深入了解了一些东西。当您说知道大多数常见JVM如何工作是有好处的时，您是正确的，但对于像这样的问题并不感兴趣。 - Fabian Barney

事实仍然是这与Java中链表的实现无关。JVM内部不是问题的一部分。 - Michael Borgwardt