在数组中，您有权限在O(1)时间内访问任何元素。所以它适用于二进制搜索、快速排序等操作。链表则适合于插入删除，因为它在O(1)时间内。两者都有优点和缺点，选择一种而不是另一种归结为您想要实现什么。

—更大的问题是，我们能有一个两者的混合体吗?类似于python和perl实现的列表。

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

除了插入到列表中间更容易之外——从链表中间删除也比从数组中删除容易得多。

但坦率地说，我从未使用过链表。每当我需要快速插入和删除时，我也需要快速查找，所以我使用HashSet或Dictionary。

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

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

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

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

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

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

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