A widely unappreciated argument for ArrayList and against LinkedList is that LinkedLists are uncomfortable while debugging. The time spent by maintenance developers to understand the program, e.g. to find bugs, increases and IMHO does sometimes not justify the nanoseconds in performance improvements or bytes in memory consumption in enterprise applicatons. Sometimes (well, of course it depends on the type of applications), it's better to waste a few bytes but have an application which is more maintainable or easier to understand.

例如，在Java环境中，使用Eclipse调试器，调试ArrayList将显示一个非常容易理解的结构:

arrayList   ArrayList<String>
  elementData   Object[]
    [0] Object  "Foo"
    [1] Object  "Foo"
    [2] Object  "Foo"
    [3] Object  "Foo"
    [4] Object  "Foo"
    ...

另一方面，查看LinkedList的内容并找到特定的对象变成了一个展开树的噩梦，更不用说过滤LinkedList内部信息所需的认知开销:

linkedList  LinkedList<String>
    header  LinkedList$Entry<E>
        element E
        next    LinkedList$Entry<E>
            element E   "Foo"
            next    LinkedList$Entry<E>
                element E   "Foo"
                next    LinkedList$Entry<E>
                    element E   "Foo"
                    next    LinkedList$Entry<E>
                    previous    LinkedList$Entry<E>
                    ...
                previous    LinkedList$Entry<E>
            previous    LinkedList$Entry<E>
        previous    LinkedList$Entry<E>

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

为什么是链表而不是数组?有些人已经说过，插入和删除的速度更快。

但也许我们不需要生活在两者的限制下，同时获得两者的优点……是吗?

对于数组删除，您可以使用'Deleted'字节来表示一行已被删除的事实，因此不再需要重新组织数组。为了减轻插入或快速更改数据的负担，可以使用链表。然后，在引用它们的时候，让你的逻辑先搜索一个，再搜索另一个。因此，将它们结合使用可以使您获得两者的最佳效果。

If you have a really large array, you could combine it with another, much smaller array or linked list where the smaller one hold thes 20, 50, 100 most recently used items. If the one needed is not in the shorter linked list or array, you go to the large array. If found there, you can then add it to the smaller linked list/array on the presumption that 'things most recently used are most likey to be re-used' ( and yes, possibly bumping the least recently used item from the list ). Which is true in many cases and solved a problem I had to tackle in an .ASP security permissions checking module, with ease, elegance, and impressive speed.

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

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

除了插入和删除方便之外，链表的内存表示方式也不同于数组。对于链表中的元素数量没有限制，而在数组中，您必须指定元素的总数。 看看这篇文章。

两件事:

毫无疑问，编写链表比使用数组要多一些工作，他想知道如何才能证明这些额外的工作是合理的。

使用c++时不要编写链表。使用STL即可。实现的难度不应该成为选择一种数据结构而不是另一种数据结构的理由，因为大多数数据结构都已经实现了。

至于数组和链表之间的实际区别，对我来说最重要的是你计划如何使用这种结构。我将使用术语向量，因为这是c++中可调整大小的数组的术语。

对链表进行索引很慢，因为必须遍历链表才能找到给定的索引，而向量在内存中是连续的，可以使用指针数学方法到达那里。

添加到链表的末尾或开头是很容易的，因为你只需要更新一个链接，而在向量中，你可能需要调整大小并复制内容。

从列表中删除一个项目很容易，因为您只需要断开一对链接，然后将它们重新连接在一起。从向量中移除一个项目可以更快也可以更慢，这取决于您是否关心顺序。在你想要删除的项目上面交换最后一项更快，而移动它之后的所有内容较慢，但保持顺序。