LinkedList不提供基于索引的访问,那为什么它有get(index)方法呢？

Question

我理解ArrayList是基于索引的数据结构,它允许你使用索引访问它的元素但是LinkedList不是基于索引的,所以为什么它有get(index)方法允许直接访问元素？

Answer 1

按索引从链表中检索项目可能效率不高，但链表确实有索引，有时您只需要在某个索引处检索项目。当这种情况发生时，拥有一个get方法比强迫用户获取迭代器并迭代到所需位置要好得多。只要你不叫它太多或列表很小，就可以了。

Answer 2

这实际上只是一个实施决定。如果您不能按索引查找元素，则数组可能是一个相当无用的数据结构，但向链表实现添加按索引查找不会造成任何伤害（好吧，除非用户认为它很快 - 请参阅下面），它有时会派上用场。

可以为每个元素分配一个数字，如下所示：

      0               1           2           3           4
Head (Element0) -> Element1 -> Element2 -> Element3 -> Element4 -> NULL

从这里开始，编写一个函数来返回某个给定索引处的元素是微不足道的。

请注意，链接列表上的按索引查找会很慢 - 如果您正在寻找中间的元素，则需要遍历列表的一半才能到达那里。