为什么Java中的LinkedList不是真正的链表? [英] Why LinkedList in Java is not a real Linked List?
问题描述
按定义,链表是一个列表,其中的每个元素都指向下一个元素(如果我们要讨论双链表,则指向上一个元素.) http://en.wikipedia.org/wiki/Linked_list
By definition Linked List is a list that each element of it refers to the next element (and previous element if we are talkin about double 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
However, in Java LinkedList is implementing List, Queue, Deque and more. http://docs.oracle.com/javase/6/docs/api/java/util/LinkedList.html
在LinkedList中找不到可以在列表中提供下一个或上一个对象的方法,最好的办法是获取Iterator并获取对象.我的问题是,为什么Java将此数据结构称为LinkedList,而不是真正的链表?链表可以用Java来实现,如下所示:
You can not find a method in LinkedList that gives you next or previous object in the list, the best you can do is to get an Iterator and get objects. My question is why Java has called this data structure LinkedList, while it is not truly a linked list? A linked list can be implemented in Java like this:
Public class MyLinkedList{
public int value;
public MyLinkedList next;
}
推荐答案
我的问题是,为什么Java称这种数据结构为LinkedList,而不是真正的链表?
My question is why Java has called this data structure LinkedList, while it is not truly a linked list?
因为它的实现是一个链表.来自文档:
Because the implementation of it is a linked list. From the documentation:
List
和Deque
接口的双链列表实现.实现所有可选的列表操作,并允许所有元素(包括
null
).
LinkedList
是通过链表实现的 List
, ArrayList
是使用数组实现的 List
等等.就运行时特性而言,选择哪一个可能很重要.例如,来自 LinkedList
文档:
LinkedList
is a List
implemented via a linked-list, ArrayList
is a List
implemented using an array, etc. Which one you choose can matter in terms of runtime characteristics. For instance, from the LinkedList
docs:
所有操作均按双向链接列表的预期执行.索引到列表中的操作将从列表的开头或结尾开始遍历列表,以更接近指定索引的位置为准.
All of the operations perform as could be expected for a doubly-linked list. Operations that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index.
例如,您知道从 iterator
或 listIterator
获得的 Iterator
上的 next
效率很高,但是按索引获取 get
会涉及遍历.
So you know, for instance, that next
on the Iterator
you get from iterator
or listIterator
will be quite efficient, but that get
by index will involve traversal.
这篇关于为什么Java中的LinkedList不是真正的链表?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!