维基百科上有很好的章节介绍了它们的区别。

Linked lists have several advantages over arrays. Elements can be inserted into linked lists indefinitely, while an array will eventually either fill up or need to be resized, an expensive operation that may not even be possible if memory is fragmented. Similarly, an array from which many elements are removed may become wastefully empty or need to be made smaller. On the other hand, arrays allow random access, while linked lists allow only sequential access to elements. Singly-linked lists, in fact, can only be traversed in one direction. This makes linked lists unsuitable for applications where it's useful to look up an element by its index quickly, such as heapsort. Sequential access on arrays is also faster than on linked lists on many machines due to locality of reference and data caches. Linked lists receive almost no benefit from the cache. Another disadvantage of linked lists is the extra storage needed for references, which often makes them impractical for lists of small data items such as characters or boolean values. It can also be slow, and with a naïve allocator, wasteful, to allocate memory separately for each new element, a problem generally solved using memory pools.

http://en.wikipedia.org/wiki/Linked_list

首先，在c++中，使用链表应该不会比使用数组更麻烦。对于链表，可以使用std::list或boost指针列表。链表与数组的关键问题是指针需要额外的空间和糟糕的随机访问。你应该使用链表，如果你

你不需要随机访问数据 您将添加/删除元素，特别是列表中间的元素

对我来说是这样的，

Access Linked Lists allow only sequential access to elements. Thus the algorithmic complexities is order of O(n) Arrays allow random access to its elements and thus the complexity is order of O(1) Storage Linked lists require an extra storage for references. This makes them impractical for lists of small data items such as characters or boolean values. Arrays do not need an extra storage to point to next data item. Each element can be accessed via indexes. Size The size of Linked lists are dynamic by nature. The size of array is restricted to declaration. Insertion/Deletion Elements can be inserted and deleted in linked lists indefinitely. Insertion/Deletion of values in arrays are very expensive. It requires memory reallocation.

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

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

您的第一个问题，正如您自己所注意到的，是插入链表允许插入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.

两件事:

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

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

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

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

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

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

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