我有兴趣了解人们在编程中会想到哪些最有用的数据结构。我们会一直使用什么数据结构？

这篇文章的答案应该可以帮助有兴趣为其问题找到有用数据结构的新程序员。答案可能应该包括数据结构，有关它的信息或者相关链接，使用它的情况以及为什么它是解决此问题的好选择(例如理想的计算复杂性，简单性和理解性等)。

每个答案应仅关于一个数据结构。

感谢我们分享人们的智慧和经验。

解决方案

这篇文章太含糊了。有无数的数据结构：数组，字典等。每种数据结构都可以用来解决不同的问题。

要求DS解决特定问题会更有效率。

这有点像询问木匠工具箱中的哪些工具最适合学习使用。它们中的每一个都适合于某种特定的工作，并且我们需要同等地学习基本的(地图，列表，箱包，集合等)。

我认为没有一个必须知道的数据结构。每个数据结构都有其自己的属性，因此适合于特定的问题。

我发现自己经常使用关联数组，基本上是使用字符串作为索引的数组。

链表/双链表/其他变体

每个人都应该知道链表的优缺点，并且由于完全缺乏用法，这似乎是许多人似乎忘记的事情。

链接列表的优点是添加/删除节点非常便宜。与在核心使用数组的数组或者数据结构不同，它们不需要在扩展时重新分配更多的内存。

缺点是它们在搜索中根本表现不佳。数组中的O(1)查找是链表的O(n)。

像所有结构一样，链表仅在某些条件下才是理想的。但是在正确的时间使用它们，它们非常强大。

我一直发现堆栈有无数的用途，尽管在面向对象的编程中很少。确实，所有数据结构都有其用途，并且并不复杂。尽你所能。

我认为这里没有一个普遍的答案。它应限于某些用例。
例如，在我作为程序员/经理的10多年职业中，我从未使用过二进制树。我怀疑这意味着二叉树没有用，但是在内核和嵌入式世界中，链表可能更合适。
实际上，当我考虑删除一些异常时，我仅使用简单的链表。
然后，即使是在嵌入式环境中，它可能也不是我生活在底层硬件协议世界中的唯一结构，可能"爬上山"使用了更多数据结构...

我喜欢二叉树。特别是Splay-Tree变体。它在某种程度上类似于自平衡二叉树，但也适应于应用程序的使用模式。我们几乎永远不会遇到最坏的情况O(n)行为。

一个不错的好处是，与其他自平衡二进制树相比，它们还更易于编写并且需要更少的代码。它是我最喜欢的数据结构之一，因为它在实践中表现得非常好。

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

为了获得基本的了解，我们应该了解一些抽象的数据类型(集合，字典，有序列表，队列，堆栈等)，以及几种实现每种方法的相对折衷方法。

这可能需要我们了解数组，链表(单链和双链)，哈希表，二进制搜索树(对简单的平衡启发式算法有所了解)和二进制堆。完全了解这些内容，我们将有一段很长的路要走，以了解更复杂，更有趣的数据结构。另外，如果我们已经实现了所有这些，那么我们将拥有一个对编程项目了解的现成的库(尽管显然有更多经过战斗加固的库，例如Boost或者更适合生产代码的库)。

这提供了非常有用的数据结构词汇，可能对我们编写程序的方式产生重大影响。我们可能会发现自己一直在使用队列的许多部分实现来解决问题，例如，现在可以将其替换为规范的实现。

Hashtable是我使用最多的数据结构之一(当然，向量之外)。
这是唯一的选择，如果我们需要能够在O(1)的时间内搜索大量数据，这意味着搜索时间不会随集合大小的增长而增长。

问题是插入和删除时间比其他数据结构长，并且我们需要某种类型的键来搜索集合。每个元素都必须有一个键。
该算法获取每个元素的密钥，并计算一个哈希码，该哈希码指示哈希表中要在其中搜索的插槽。
然后，根据实现情况，它或者跟随该存储桶中的某个项目列表以找到项目，或者搜索附近的存储桶。
hastable的大小决定了哈希的效率，而哈希的效率很大程度上受键之间哈希码冲突量的影响。

每当我们需要一个映射并且映射的预期元素数超过大约10个时，都可以使用它。与其他结构相比，它占用更多的内存，因为它需要表中大量未使用的插槽以提高效率。

用Dictionary <keytype，valuetype>来实现它的一个很好的实现，甚至有一个HybridDictionary在内部决定何时使用哈希表或者向量。
任何好的编程书籍都可以描述它，但维基百科将为我们提供良好的服务：
http://en.wikipedia.org/wiki/哈希表

我发现自己经常与" foreach"控制结构结合使用数组来遍历项目。过去，我使用带有数字索引和" for(i = 1; i <n; i ++)"的数组。我发现，使用" foreach"而不是显式的数字索引遍历数组提供了一种更通用，更易读的解决方案。

我将不必理会我们对每个帖子一个数据结构的要求，这些是我使用最多的数据结构，而我发现大多数程序在这些程序中大多都需要其中之一，也可能需要组合。

排列最基本的内容并提供最快的访问权限。向量是在简单的旧阵列上的即兴创作，并且是近来常用的事实上的替代品。出队是此主题的另一种变体，再次提供了恒定的时间/随机访问，但针对在开始和结束时的快速插入和删除进行了优化。

链接列表对于维护频繁删除和插入的数据列表非常有用，但是迭代/搜索非常慢。例如，内存页面中的空闲/已用列表

树木是构成更复杂结构基础的基本结构。这种结构有很多形式。提供对树进行排序时的登录搜索时间。对字典等大型数据项很有用。二进制/ AVL和红黑树是最常见的。

maps and hashs并非完全是数据结构，而是结合了巧妙的逻辑和上述数据结构实现的复杂快速查找算法。

这些数据结构及其实现在C ++中的STL库中可用。其他语言也有其本机实现。一旦我们知道了这些基本数据结构及其一些变量(队列，堆栈，优先级队列)以及有关搜索算法的知识，我就会说基本知识将被很好地介绍。

The advantages of linked lists are that they are very cheap to add/remove nodes. Unlike arrays [...] they do not require reallocating more memory upon expanding.

如果我们有一个数组，并且每次填充它时分配的大小都加倍，则将摊销O(1)追加。另外，由于缓存的影响(除非我们将链接分配成大块并且不要过多地弄乱链接)，循环遍历数组的所有元素(在墙上的时间)可能比循环遍历链表的速度更快。 )。

同样，数组更小：我们节省了每个元素的字的开销，加上每个分配的开销(这可能至少是两个字：一个用于大小，一个用于下一个空闲列表指针)。

快速排序

合并排序

泡泡排序

这些对于学习和理解它们的工作原理确实非常有用。排序很有趣，可以应用于很多领域：)

图是一个非常强大的被忽略的数据结构。

通过构造对问题进行建模的图形，然后在图形上使用众所周知的算法，可以解决许多问题。
电子游戏(使用图形确定AI字符的最短路径)和网络拓扑的一些示例包括自然语言处理(连接节点的边缘权重可以表示一个单词跟随另一个单词的可能性)。

我从算法设计手册中了解了图，这是史蒂夫·耶格(Steve Yegge)在博客文章中推荐的。