为什么有人想要使用链表而不是数组?

毫无疑问,编码一个链表比使用数组要多一些工作,人们可能会想知道如何才能证明这些额外的工作是合理的。

我认为在链表中插入新元素是微不足道的,但在数组中这是一个主要的任务。与将数据存储在数组中相比,使用链表存储一组数据还有其他优点吗?

这个问题不是这个问题的重复,因为另一个问题是专门问一个特定的Java类,而这个问题是关于一般数据结构的。


当前回答

Arrays make sense where the exact number of items will be known, and where searching by index makes sense. For example, if I wanted to store the exact state of my video output at a given moment without compression I would probably use an array of size [1024][768]. This will provide me with exactly what I need, and a list would be much, much slower to get the value of a given pixel. In places where an array does not make sense there are generally better data types than a list to deal with data effectively.

其他回答

当集合不断增加和减少时,链表尤其有用。例如,很难想象尝试使用数组实现一个Queue(添加到末尾,从前面删除)—您将花费所有时间向下移动内容。另一方面,对于链表来说,这是微不足道的。

这里有一个快速的方法:移除物品更快。

数组和链表之间的区别在于,数组是基于索引的数据结构,每个元素都与一个索引相关联,而链表是使用引用的数据结构,每个节点都被引用到另一个节点。在数组大小是固定的,而在链表大小是不固定的。

假设您有一个有序集,您还想通过添加和删除元素来修改它。此外,您需要能够以这样的方式保留对元素的引用,以便稍后可以获得前一个或下一个元素。例如,一本书中的待办事项列表或一组段落。

首先,我们应该注意到,如果您想在集合本身之外保留对对象的引用,那么您可能最终会将指针存储在数组中,而不是存储对象本身。否则你将无法插入到数组中-如果对象嵌入到数组中,它们将在插入期间移动,并且任何指向它们的指针都将无效。数组下标也是如此。

您的第一个问题,正如您自己所注意到的,是插入链表允许插入O(1),但数组通常需要O(n)。这个问题可以部分克服——可以创建一种数据结构,提供类似数组的按顺序访问接口,其中读和写在最坏的情况下都是对数的。

Your second, and more severe problem is that given an element finding next element is O(n). If the set was not modified you could retain the index of the element as the reference instead of the pointer thus making find-next an O(1) operation, but as it is all you have is a pointer to the object itself and no way to determine its current index in the array other than by scanning the entire "array". This is an insurmountable problem for arrays - even if you can optimized insertions, there is nothing you can do to optimize find-next type operation.

链表

它更可取的时候,它涉及到插入!基本上它所做的就是处理指针

1 -> 3 -> 4

插入(2)

1... 3... 4 ... 2

最后

1 -> 2 -> 3 -> 4

一个箭头指向3点,另一个箭头指向2点

简单!

但是来自Array

| | 1 | 3 | 4

插入(2) | 1 | 3 | | 4 | | 1 | | 3 | 4 | | 1 | 2 | 3 | 4 |

任何人都可以想象出其中的不同! 对于4个索引,我们执行3个步骤

如果数组长度是一百万呢?数组有效吗? 答案是否定的!:)

删除也是一样! 在链表中,我们可以简单地使用指针并将对象类中的元素和next置空! 但对于数组,我们需要执行shiftLeft()

希望有帮助!:)