为什么Java中的LinkedList不是真正的链表？

Question

根据定义,Linked List是一个列表,它的每个元素引用下一个元素(如果我们正在讨论双链表,那么前面的元素.) 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中找到一个方法,该方法为您提供列表中的下一个或上一个对象,您可以做的最好的方法是获取Iterator并获取对象.我的问题是为什么Java已经调用了这个数据结构LinkedList,而它不是真正的链表？链接列表可以用Java实现,如下所示:

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

Answer 1

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

不,这完全合适."列表中的下一个项目"的想法是没有意义的名单上.它对列表中的节点非常有意义,但这不是Java API公开的内容.它当然是内部存在的 - 只是没有暴露.如果要遍历列表,则使用迭代器.您仍然可以在开头或结尾添加,从开头或结尾删除,以及从迭代器添加/删除.

虽然您当然可以将"节点"和"列表"的概念混淆为建议的示例代码,但我认为这通常不是一个好主意.

换句话说:你想要实现的是什么导致你出现问题？我相信你应该能够使用公共API做你想做的事 - 你可能根本没有注意到这一切.

Answer 2

我的问题是为什么Java已经调用了这个数据结构LinkedList,而它不是真正的链表？

因为它的实现是一个链表.从文档:

双向链表实现List和Deque接口.实现所有可选列表操作,并允许所有元素(包括null).

LinkedList是List通过链表实现的,ArrayList是List使用数组等实现的.您选择哪一个在运行时特性方面很重要.例如,来自LinkedList文档:

对于双向链表,所有操作都可以预期.索引到列表中的操作将从开头或结尾遍历列表,以较接近指定索引为准.

所以,你知道的,比如,这next对Iterator你获得iterator或listIterator将是相当有效的,但get通过指数将涉及遍历.