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

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

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

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


当前回答

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

其他回答

链表

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

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()

希望有帮助!:)

While many of you have touched upon major adv./dis of linked list vs array, most of the comparisons are how one is better/ worse than the other.Eg. you can do random access in array but not possible in linked list and others. However, this is assuming link lists and array are going to be applied in a similar application. However a correct answer should be how link list would be preferred over array and vice-versa in a particular application deployment. Suppose you want to implement a dictionary application, what would you use ? Array : mmm it would allow easy retrieval through binary search and other search algo .. but lets think how link list can be better..Say you want to search "Blob" in dictionary. Would it make sense to have a link list of A->B->C->D---->Z and then each list element also pointing to an array or another list of all words starting with that letter ..

A -> B -> C -> ...Z
|    |    |
|    |    [Cat, Cave]
|    [Banana, Blob]
[Adam, Apple]

Now is the above approach better or a flat array of [Adam,Apple,Banana,Blob,Cat,Cave] ? Would it even be possible with array ? So a major advantage of link list is you can have an element not just pointing to the next element but also to some other link list/array/ heap/ or any other memory location. Array is a one flat contigous memory sliced into blocks size of the element it is going to store.. Link list on the other hand is a chunks of non-contigous memory units (can be any size and can store anything) and pointing to each other the way you want. Similarly lets say you are making a USB drive. Now would you like files to be saved as any array or as a link list ? I think you get the idea what I am pointing to :)

另一个很好的原因是链表非常适合高效的多线程实现。这样做的原因是,更改往往是局部的——只影响数据结构局部部分的插入和删除的一两个指针。所以,你可以让多个线程在同一个链表上工作。更重要的是,可以使用cas类型的操作创建无锁版本,并完全避免沉重的锁。

使用链表,迭代器还可以在进行修改时遍历列表。在修改没有冲突的乐观情况下,迭代器可以在没有争用的情况下继续。

对于数组,任何修改数组大小的更改都可能需要锁定数组的很大一部分,事实上,这是在整个数组上没有全局锁的情况下完成的,因此修改会停止全局事务。

我也认为链表比数组更好。 因为我们在链表中做遍历,而不是在数组中

数组Vs链表:

由于内存碎片,阵列内存分配有时会失败。 在数组中缓存更好,因为所有元素都分配了连续的内存空间。 编码比数组更复杂。 与数组不同,在链表上没有大小限制 在链表中插入/删除更快,在数组中访问更快。 从多线程的角度来看,链表更好。