数据结构是噩梦？想要通过面试，你必须掌握它

本文转载自公众号“读芯术”(ID：AI_Discovery)

就当是一场梦，醒了还是很悲痛，还是难以忘记被数据结构折磨的惨痛。当你打开一本数据结构和算法的教科书时，里面总是充满复杂的数学，令人望而生畏。对于那些不太喜欢这门学科的人来说，这就是一场噩梦。

然而现实是，想要通过编程面试，必须求解算法，这就离不开数据结构。别害怕，一旦了解了数据结构，就会发现它们其实没有看上去那么难了。

本文将会简化和总结这些最基本的数据结构，帮你搞定数据结构。

什么是数据结构?

数据结构是一种在计算机中组织数据以便高效使用的特殊方式：

“在计算机科学中，数据结构是一种数据组织、管理和存储的格式，其允许高效地访问和修改。更准确地说，数据结构是数据值，数据值之间的关系，以及可应用于数据的函数或操作的集合。”

我们必须将数据存储到某种数据结构中，选择正确的数据结构至关重要。

值得注意的是，数据结构没有好坏之分，每种数据结构都有其优缺点。有很多方法可以用来衡量一种数据结构，这些也被称为大O符号，这是衡量操作可伸缩性的一个指标。

现在来讨论一下不同类型的数据结构。

链表

链表的单位被称为“节点”，一个节点包含一个值和一个指针(Pointer)。值只是一个数字，如12，而指针将该值链接到链中的下一个节点。这就是链表的连接部分，链表中的第一个节点被称为头，最后一个没有指针的节点被称为尾。

• 优点：添加删除节点很方便，只需要更改指针指向的地址即可。
• 缺点：不擅长检索节点，尽管有索引或搜索功能。因为每个节点只知道相邻节点的信息。

散列表(哈希表)

哈希映射或哈希表，也是一种关键的数据结构。它类似于JavaScript中的对象和Python中的字典，在这种类型的数据结构中，用户为散列表提供一个单词或者键，它将检索定义或值。

其工作原理很像一个数组，该键通过名为“散列函数(哈希函数)”的函数运行，该函数会找出键对应的内存地址。

不同之处在于，这些位置在内存中不需要相邻，而是可以在任意位置。因此，大小的增加不会存在问题。

但是，存在一个不同问题——根据使用的散列函数，两个键可能会指向同一个内存地址。这就是所谓的“冲突”，有很多种办法可以解决这个问题，但是这一切都隐藏在函数内。

• 优点：正如已提及的，散列函数(哈希函数)非常适合添加和读取。
• 缺点：可能会导致键值冲突。

栈和队列

这两种结构彼此非常相似，都是在数组的基础上构建了一些附加功能。

栈是后进先出的数据结构。这类似于堆叠在一起的托盘，顶部的托盘在放入时是最后一个，在取出时是第一个。

将一个元素添加到栈顶称为入栈，而从栈顶取出一个元素称为出栈。每种语言都通过称为调用堆栈的方式跟踪已调用的函数。栈对于称为深度优先搜索(DFS)的算法非常重要。

另一方面，队列是一种先进先出的结构，就像公共汽车站的排队，最后一个排队的人最后上车。在末尾添加元素的操作称为入队，从队首删除元素称为出队。队列被用于称为广度优先搜索(BFS)的重要算法中。

• 优点：两种结构在添加和删除元素时都非常有效。
• 缺点：与其他的数据结构相比，它们的用例数量有限。

数组

数组在所有的编程语言中都很常见，它是计算机内存中连续的单元块。

下面的示例表示了一个具有12个元素的整数数组。数组的索引从0开始，因此包含12个元素的数组具有从0到11的索引。

• 优点：数组擅于检索项，但前提是数组较小。
• 缺点：随着数组规模不断增大，会占用内存中的其他项来运行。因此，数组的添加操作效率很低，因为可能需要将数组移动到内存中的一个新位置以适应其长度。

幸运的是，这种情况出现在高级语言中，比如JavaScript和Python。若在底层语言中，必须要事先声明数组的大小。

图和树

计算机语言中有一个专门的部分叫做“图论”，图类似于链表有着指向其它节点的节点，只是这些指针被称为“边”，边可以有权重或者被赋予编号。

有一种特殊的层图称为“树”，其中的数据向一个方向拓展。它们可以用于指代很多事物，例如“家谱”，或者用于表示网络。与数组、链表、栈和队列这样的线性数据结构不同，树是分层数据结构。

• 优点：树提供了高效的插入和搜索能力，而且树的数据格式非常灵活，允许以最小的工作量来移动子树。
• 缺点：缺点在于，修改列表和检索的时间长度为O(log n)。

入门算法求解离不开这些数据结构，关键在于不要畏难。搏一搏，噩梦变美梦。祝你早日掌数据结构。

【责任编辑：赵宁宁 TEL：（010）68476606】