10

根据定义，链接列表是一个列表，它的每个元素都指向下一个元素（如果我们谈论的是双链表，则是前一个元素。） http://en.wikipedia.org/wiki/Linked_list

然而，在 Java LinkedList 中实现了 List、Queue、Deque 等。 http://docs.oracle.com/javase/6/docs/api/java/util/LinkedList.html

您无法在 LinkedList 中找到为您提供列表中的下一个或上一个对象的方法，您能做的最好的事情就是获取一个迭代器并获取对象。我的问题是为什么 Java 将这种数据结构称为 LinkedList，而它并不是真正的链表？链表可以像这样在 Java 中实现：

Public class MyLinkedList{
 public int value;
 public MyLinkedList next;
}
4

7 回答 7

9

您无法在 LinkedList 中找到为您提供列表中下一个或上一个对象的方法

不，这是完全合适的。“列表中的下一项”的想法在列表中没有意义。这对于列表中的节点非常有意义，但这不是 Java API 所公开的。当然，它存在于内部 - 只是没有暴露。如果要遍历列表，请使用迭代器。您仍然可以在开头或结尾添加，从开头或结尾删除，以及从迭代器中添加/删除。

虽然您当然可以像建议的示例代码那样将“节点”和“列表”的概念混为一谈，但我认为这通常不是一个好主意。

换句话说：你想达到什么目的导致你出现问题？我相信你应该能够使用公共 API 做你想做的事——你可能只是没有注意到这一切。

于 2013-02-11T16:59:24.437 回答
6

我的问题是为什么 Java 将这种数据结构称为 LinkedList，而它并不是真正的链表？

因为它的实现是一个链表。从文档中：

List和Deque接口的双向链表实现。实现所有可选列表操作，并允许所有元素（包括null）。

LinkedList是List通过链表实现的，ArrayList是List使用数组实现的，等等。您选择哪一个取决于运行时特性。例如，来自LinkedList文档：

所有操作都按照双向链表的预期执行。索引到列表中的操作将从开头或结尾遍历列表，以更接近指定索引的为准。

所以你知道，例如，next你Iterator从那里得到iterator或listIterator将非常有效，但get按索引将涉及遍历。

于 2013-02-11T16:58:09.783 回答
4

集合是链表还是数组列表与它的契约无关，而与它的实现有关。LinkedList确实是一个实现的链表，一个java.util.List契约的链表。

它展示的不是它的 API，而是它的空间/时间复杂性特征，任何熟悉链表的人都可以很容易地预料到。

作为参考，这是一个LinkedList节点的实际实现，非常符合您的期望：

957  私有 静态 类Node<E> { 
958       E 项；
959      节点<E> 下一个；
960      节点<E> 上一页; 
962      节点（节点<E>上一个，E元素，节点<E>下一个）{ 
963          这个.item =元素；第
964          章 第
965          章 
966       } 
967   }

于 2013-02-11T16:58:27.817 回答
2

当我阅读您的问题时，我感觉您没有很好地区分链表的概念和链表的实现。

您的示例代码很好地展示了链表的概念，但这并不意味着它是实现链表的唯一方法或最佳方法。我相信您可以使用内置类执行标准链表所需的任何操作LinkedList，尽管您可能会在数据结构类或教科书中看到一组不熟悉的 API。

所以基本上就是一个链表，只要能做到及时的插入操作、O(1)及时的删除操作、O(1)及时的搜索操作O(n)等等，对比其他数据结构比如数组的时间复杂度。

内置LinkedList没有next直接提供操作，而是通过它的迭代器。这只是 Java 语言的设计决策，因为您可能会从迭代器模式中受益。

而Java是一种典型的面向对象语言，其主要特点之一就是抽象。

于 2013-02-11T17:48:00.307 回答
1

除了其他人的正确答案外，如果接口的底层实现是一个Linked List，那么实现对象将有一个方法来获取列表中的下一项。该方法只是没有作为合同的一部分公开。

实现是一个链表这一事实会影响 List 合约的各种方法的 Big-O 性能。

于 2013-02-11T17:00:22.660 回答
0

然而，在 Java LinkedList 中实现了 List、Queue、Deque 等。

根据 API，LinkedList 实现了这些接口，因此可以使用任何这些结构。

于 2013-02-11T17:04:15.590 回答
0

所以我不知道@Marko 从哪里读取该实现，但 1.8 jdk 中的实现有很大不同。

首先，声明的第一个变量是：

 transient int size = 0;

每当将节点添加到列表中时，该值就会增加。这意味着列表中存在 Integer.MAX_VALUE (2147483647) 节点的固有限制。在现代世界，这个数字并不像看起来那么大。问题不在于我们没有真正的链表（创建它们很简单），而是对于所有 3rd 方库，他们很可能不会考虑到这一点，然后整个库就会被淘汰.

于 2019-04-12T15:08:26.353 回答