数据结构到底在学什么

学习目标

本节要回答一个最基础的问题：数据结构到底在学什么。

初学者常常把数据结构理解成“数组、链表、栈、队列这些东西”。这个理解没有错，但还不够完整。真正学习数据结构时，我们不仅要知道有哪些结构，还要理解每种结构为什么出现、如何表示数据关系、能支持哪些操作，以及这些操作的效率如何。

从数据关系开始理解

现实中的数据通常不是孤立存在的，它们之间会有关系。

例如：

一排座位上的乘客有前后顺序。
一个文件夹下面可以有多个文件和子文件夹。
城市之间可以通过道路连接。
用户和用户之间可以存在关注、好友或协作关系。

这些关系并不一样。

一排座位更像线性关系，一个元素前面最多有一个元素，后面最多有一个元素。文件夹更像层级关系，一个目录可以包含多个子项。城市道路更像网状关系，一个城市可以连接多个城市，而且路径可能有很多种。

数据结构首先要做的事，就是用合适的结构表达这些关系。

从操作需求理解结构选择

同样的数据关系，如果操作需求不同，也可能选择不同结构。

假设我们有一批用户数据。可能的需求包括：

按注册顺序遍历所有用户。
根据用户 ID 快速找到某个用户。
按积分从高到低取出排名靠前的用户。
判断两个用户之间是否存在关系链。

这些需求看起来都在处理“用户”，但背后的操作完全不同。按顺序遍历适合线性结构；按 ID 快速查找适合哈希结构；维护排名可能需要堆或平衡树；分析关系链则可能需要图。

所以，数据结构不是只问“我有什么数据”，而是进一步追问“我要怎样使用这些数据”。

从效率理解结构价值

如果不考虑效率，很多问题都可以用最简单的列表解决。但当数据量变大，效率就会成为关键问题。

下面的例子展示了最朴素的顺序查找：从头到尾检查用户 ID。

struct User {
    int id;
    string name;
};

User* findUser(vector<User>& users, int targetId) {
    for (User& user : users) {
        if (user.id == targetId) {
            return &user;
        }
    }

    return nullptr;
}

class User {
    int id;
    String name;

    User(int id, String name) {
        this.id = id;
        this.name = name;
    }
}

User findUser(User[] users, int targetId) {
    for (User user : users) {
        if (user.id == targetId) {
            return user;
        }
    }

    return null;
}

def find_user(users, target_id):
    for user in users:
        if user["id"] == target_id:
            return user

    return None

class User
{
    public int Id { get; set; }
    public string Name { get; set; } = "";
}

User? FindUser(List<User> users, int targetId)
{
    foreach (User user in users)
    {
        if (user.Id == targetId)
        {
            return user;
        }
    }

    return null;
}

这四段代码表达的是同一个思路：逐个检查，直到找到目标用户。

如果用户只有 3 个，这样写没有任何问题。但如果用户有 300 万个，而且系统需要频繁查找用户，这种线性扫描就不合适了。此时，我们可能会把用户 ID 和用户信息建立成映射关系，让查找更直接。

数据结构学习的三条主线

后续学习时，可以始终抓住三条主线。

第一条主线是数据关系。它回答“这些数据之间是什么关系”。线性表表达顺序关系，树表达层级关系，图表达复杂连接关系。

第二条主线是操作集合。它回答“这个结构主要支持什么操作”。例如栈强调入栈和出栈，队列强调入队和出队，哈希表强调根据键查找值。

第三条主线是性能代价。它回答“这些操作快不快，会消耗多少额外空间”。这条主线会和复杂度分析紧密相关。

本节小结

数据结构学习的对象不只是具体容器，而是数据关系、操作需求和效率代价之间的平衡。

当你面对一个问题时，不要急着写代码。先判断数据之间的关系，再分析最常见的操作，最后选择能让关键操作更高效的数据组织方式。