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

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

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

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


当前回答

这实际上是一个效率问题,在链表中插入、删除或移动(而不是简单地交换)元素的开销是最小的,即操作本身是O(1),而不是O(n)。如果您大量操作数据列表,这可能会产生显著的差异。您可以根据对数据类型的操作方式选择数据类型,并为所使用的算法选择最有效的数据类型。

其他回答

It's easier to store data of different sizes in a linked list. An array assumes every element is exactly the same size. As you mentioned, it's easier for a linked list to grow organically. An array's size needs to be known ahead of time, or re-created when it needs to grow. Shuffling a linked list is just a matter of changing what points to what. Shuffling an array is more complicated and/or takes more memory. As long as your iterations all happen in a "foreach" context, you don't lose any performance in iteration.

我将添加另一个-列表可以充当纯函数式数据结构。

例如,您可以让完全不同的列表共享相同的结束部分

a = (1 2 3 4, ....)
b = (4 3 2 1 1 2 3 4 ...)
c = (3 4 ...)

例如:

b = 4 -> 3 -> 2 -> 1 -> a
c = a.next.next  

不需要把a指向的数据复制到b和c中。

这就是为什么它们在函数式语言中如此受欢迎的原因,函数式语言使用不可变变量——前置和尾部操作可以自由发生,而无需复制原始数据——当您将数据视为不可变时,这是非常重要的特性。

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

这只是一个原因——如果你需要一个链表数据结构,而你所使用的编程语言不支持指针。

快速插入和删除确实是链表的最佳参数。如果您的结构是动态增长的,并且不需要对任何元素进行固定时间的访问(例如动态堆栈和队列),链表是一个很好的选择。

这实际上是一个效率问题,在链表中插入、删除或移动(而不是简单地交换)元素的开销是最小的,即操作本身是O(1),而不是O(n)。如果您大量操作数据列表,这可能会产生显著的差异。您可以根据对数据类型的操作方式选择数据类型,并为所使用的算法选择最有效的数据类型。