基于索引,随机访问和顺序访问之间的区别？

Question

据我说:

基于索引:可以通过传递索引来访问.现在内部它正在进行随机或顺序迭代并不重要.

随机访问:您可以随机访问一个位置.

顺序访问:从其他位置开始依次逐个访问所需位置.

但是在采访中我说LinkedList是基于java的索引,因为它提供了所有方法add(int index,obj),get(int index),remove(int index).人们不接受.然后我说基于索引和随机访问是两个不同的概念.我对吗？

Answer 1

因此,这个问题比看起来有点棘手,因为这些术语的适当性确实取决于上下文,正如JB Nizet在下面的评论中强调的那样,这实际上归结为一个术语问题,而不是实现或实际概念的问题,所以这个答案主要是关于措辞的迂腐.首先,您的定义是:

• 基于索引:可以通过传递索引来访问.现在内部它正在进行随机或顺序迭代并不重要.
• 随机访问:您可以随机访问一个位置.
• 顺序访问:从其他位置开始依次逐个访问所需位置.

首先照顾这一部分:"基于索引的"并不属于那里.术语"基于索引"并不真正识别访问类型或任何东西,它只是意味着......"基于索引".它只是一个可以形容某事的任意形容词.在谈论一般访问类型时,我们只讨论随机和顺序.通常,"基于索引的访问"意味着/是"随机访问"的同义词.如果存在"随机访问"样式界面,也许它使用索引,也许它使用其他东西,谁知道,它并不重要.所以,让我们从那里的术语列表中"基于索引".

如果这没有多大意义,可以这样想:你的列表"基于索引","随机访问","顺序访问",类似于"磁性","金属椅","木椅" , 分别.第一个只是一个形容词,而不是一种类型的椅子,如果你谈论的是椅子那么它就意味着"金属椅子"而对"木椅"没有意义.

现在,至于LinkedList表达几个点作为列表更容易,没有特别的顺序:

• LinkedList实现List接口,从而支持随机访问(通过get(int)和朋友).
• LinkedList还支持iterator()从Collection接口(List扩展)的顺序访问(via ).
• 由此可见,所有 List S IN的Java(可能是LinkedList,ArrayList等),支持 随机和顺序访问.

所以说LinkedList 支持(或"允许"或任何你喜欢的词)随机访问是正确的,并且它支持顺序访问.

另一方面,您可以谈谈复杂性 /实现细节:

• LinkedList 由于链表的性质,它是顺序访问的理想选择.
• LinkedList随机访问是O(n)最坏的情况,因为它必须通过顺序迭代来实现.你不能跳转到特定的索引,而是必须从头开始并迭代.

所以:

但是在采访中我说LinkedList是基于java的索引,因为它提供了所有方法add(int index,obj),get(int index),remove(int index).人们不接受.然后我说基于索引和随机访问是两个不同的概念.我对吗？

不完全是.如上所述,"基于索引的访问"通常是"随机访问"的同义词,或者至少暗示它,但"基于索引的"本身并不是一件事.这里只有"随机"和"顺序".

你能说的LinkedList是:

• 它支持基于索引的随机访问.
• 与之相比,它没有良好的随机访问性能ArrayList.
• 它是顺序访问的理想选择.

你不能说是一个LinkedList" 是基于索引的".虽然List随机访问接口是基于索引的,但是说"链接列表的实现是基于索引的"或者"链表是基于索引的"并没有多大意义,因为链接列表不是这基于索引,这与Java的实现恰好提供随机和顺序访问接口这一事实无关.

此外,您并没有真正说"链表是随机访问"或"链表是顺序访问".在语义上,这些短语没有多大意义.链表是一个链表,它具有较差的随机访问性能,Java为它提供了随机和顺序访问接口,但列表本身通常不会被称为"其中之一".

因此,您的面试答案可能是"嗯,LinkedList通过List界面支持基于索引的随机访问,但其性能不如一般ArrayList,顺序访问更理想."

希望有所帮助.