---

前言

数据结构 (data structure) 是计算机科学最重要的基础知识之一，如果不能很好地理解数据结构的意义，未来在学习各种专业知识的过程中都将举步维艰。

关于数据结构的各种规范定义，各种教材上几乎都会出现，但是个人认为，对一个从未接触过数据结构的概念的人来说，上来就直接被糊一脸的定义并不会有很好的学习体验。因为本文是面向初学者的，所以我会尽可能避免阐述那些无聊的定义和概念，但是一些必要的定义和概念还是无法避免的。

在阅读引言时，可能会有很多令人疑惑的没听说过的东西，事实上你现在不需要去深究，只留个粗浅的印象，跳过看不懂的部分就好，你会在后面的学习中逐渐接触到这些问题的细节。

本知识板块的主要目的是成为本科基础课程的补足，因此，本知识板块内的文章有如下特点：

• 其一，我不会用古板的方式去介绍这些数据结构，而是尽可能引导读者发散思维，举一反三，并在学习的过程中意识到，数据结构的实现也是人们思想的体现，而不是固定不变的。实现是次要的，思想是主要的，我们完全可以根据实际情况去改变我们对这些数据结构的代码实现。

• 其二，各种教材上都有各种各样的封装好的各种数据结构的代码实现，但是个人认为，对一个从未接触过数据结构的概念的人来说，上来就直接看一大段封装类的代码并不能帮助他深入理解数据结构的本质，这毕竟是数据结构课程而不是面向对象程序设计课程。所以在基础数据结构的其他文章中，我会先给出最为精简易懂的代码实现，以便于初学者快速理解其本质特征，而不是花费精力去关注类和对象的封装设计。

• 其三，同样是出于精简的目的，精简的代码实现中将会省去合法性检测等等一些虽然必要、但和核心逻辑无关的代码。但我会在文章的最后附上完整可运行的所有代码，包括面向过程的代码实现和类封装的代码实现两种。

---

基本概念

什么是数据结构？

数据结构就是按照一定的方法去存储和维护计算机数据的一个抽象概念。这可能听起来有些令人头大，但它没那么难，比如说，其实一个普通的数组就是一种数据结构——从存储上讲，它以连续线性空间来存储数据；从维护上讲，它支持简单的随机访问和修改，但却难以在其中部位置进行插入和删除操作（你不得不先移动一大堆数据才能完成插入和删除）。

所以说，对于一种数据结构，其实你只需要关心两个问题：它如何存储数据？它如何维护数据？仅此而已。至于数据结构提供了哪些有用的功能，有什么优缺点，其实都是由这两个问题的答案决定的。

数据结构的存储问题，又可以分为物理结构和逻辑结构这两个问题。物理结构指的是数据在内存中的实际存储方式，亦称为存储结构。而逻辑结构指的是人们从主观上为其赋予的、语义上的存储方式。

物理结构和逻辑结构之间没有任何必然的联系。物理结构取决于实际是如何用代码实现数据结构的，如果不考虑数据结构的效率，设计者甚至可以随意地设计它的物理结构。而逻辑结构是数据结构本身的内涵，对于某一种数据结构而言，其逻辑结构应当是不变的，如果改变了的话就成了另外一种数据结构了。

物理结构可以分为顺序存储、链式存储、索引存储、散列存储四大类。或许你只接触过前两种，不过大多数基础数据结构也就是顺序或链式的，索引和散列相对更常见于操作系统、计算机组成、数据库等高年级课程中。

逻辑结构可以分为线性结构和非线性结构两大类，线性结构自不必说，非线性结构可以是树、可以是图。

至于大类之下还可以再细分，此处不予赘述。

数据结构的维护问题，通常包括它如何支持你对其中存储的数据的增删改查，即插入、删除、修改、查询。此外，对于一些高级数据结构，它还需要在你执行完增删改查操作后对其中存储的数据进行维护，可能包括重排、自适应调整、旋转等。

通常，每一种数据结构都会支持增删改查的操作，关键在于每一种操作在各种情境下的的效率如何，也就是时间复杂度的优劣。例如数组显然不适合需要频繁在表头处增删的情况，而链表显然不适合需要频繁进行随机查找的情况，把它们互换过来就很合适了。

数据结构有什么用？

对于你曾经写过的那些简单程序而言，数据结构的确没什么用，似乎只用数组、结构体和类就能解决一切。因此很难和没有接触过数据结构的人去解释数据结构的用途，你现在只需要记住：它真的很重要。

大部分的教材都是直接把各种基础数据结构挨个灌进你的脑子，却从来没告诉过你，它们究竟是怎么来的。

首先要弄清楚的是，数据结构不是凭空产生的， 一种数据结构之所以会存在、之所以会被发明出来，是因为前人在实际应用中需要它们。 是因为先有了“待解决的问题”，才有了数据结构作为“解决方案”，而不是由数据结构的存在而衍生出各种问题。

以编程语言为例，是因为我们需要处理批量的数据，所以那些早期的编程语言的发明者才会制造出数组来。同样地，是因为我们有时需要动态开辟内存，才会有 malloc/free 和 new/delete 的存在，而不是因为它们存在，我们就可以动态开辟内存。它们的产生是源自于我们的实际需求的。

这些听起来似乎有些啰嗦和缺乏实际意义，但如果你没有理解这一点，多多少少会影响到你对数据结构的进一步学习和掌握。每一个数据结构的产生都是因为前人遇到了需要它们去解决的问题。或许现在的你听着有些懵，希望你在学习了一段时间以后能够理解我为什么会用这么大的篇幅解释这一点——只要你在学习每一个数据结构的时候，着重注意它们是如何被运用来解决实际问题的。

因此你要牢记：数据结构只是一种工具，就像编程语言也只不过是工具一样，编程的核心还是人的思想。你需要掌握并灵活运用这些数据结构，仅仅把它们背下来是没有意义的。

---

阅读指引图

其中：

• 淡黄色方块表示面向初学者的文章。

• 小麦色方块表示面向进阶读者的文章。

• 箭头表示一组前置知识的关系。在阅读一篇文章前，推荐您先阅读其所有前置文章。

• 虚线箭头表示一组建议的前置关系，是可选的，您可以选择忽略此类提示。

• 空心大箭头表示你将进入到进阶区域。

• 淡粉色方块表示来自其他知识板块的文章，因为它们是本板块内某些文章的前置知识，所以被专门标示出来。

---