12、数据结构基础：单向链表实现、双向链表、栈与队列、哈希表简单实现

数据结构这东西，说白了就是组织数据的方式。我刚开始学C语言那会儿，觉得数组够用了，搞什么链表、哈希表，不是多此一举吗？直到有一次我写一个内存池管理模块，数组的固定大小让我吃尽了苦头。嗯，从那以后，我再也不敢小看数据结构了。

这一章，我们就把几个最常用的数据结构撸一遍。单向链表、双向链表、栈、队列、哈希表，每个我都会给出C语言的实现思路，顺便聊聊我踩过的坑。

12.1 单向链表：最基础的动态结构

单向链表，每个节点只知道自己下一个节点是谁。它不像数组那样需要连续内存，插入和删除也快得多——只要改改指针就行。

先看节点定义：

typedef struct Node {
    int data;
    struct Node *next;
} Node;

就这么简单。一个存数据，一个存指针。

我习惯把链表操作封装成几个函数：创建节点、插入、删除、遍历、销毁。举个例子，插入操作：

void insertAfter(Node *prev, int data) {
    if (prev == NULL) return;
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = prev->next;
    prev->next = newNode;
}

遍历链表也很直观：

void printList(Node *head) {
    Node *cur = head;
    while (cur != NULL) {
        printf("%d -> ", cur->data);
        cur = cur->next;
    }
    printf("NULL\n");
}

单向链表的缺点也很明显——你只能从头往后走，想找前一个节点？没门。这就引出了双向链表。

12.2 双向链表：能前能后

双向链表每个节点多了一个 prev 指针，指向前一个节点。代价是每个节点多占一个指针的内存，但换来的是双向遍历的灵活性。

typedef struct DNode {
    int data;
    struct DNode *prev;
    struct DNode *next;
} DNode;

插入操作比单向链表稍微复杂一点，因为要同时维护 prev 和 next：

void insertAfterD(DNode *prev, int data) {
    if (prev == NULL) return;
    DNode *newNode = (DNode *)malloc(sizeof(DNode));
    newNode->data = data;
    newNode->next = prev->next;
    newNode->prev = prev;
    if (prev->next != NULL) {
        prev->next->prev = newNode;
    }
    prev->next = newNode;
}

删除操作也要注意前后指针的衔接：

void deleteNodeD(DNode *node) {
    if (node == NULL) return;
    if (node->prev != NULL)
        node->prev->next = node->next;
    if (node->next != NULL)
        node->next->prev = node->prev;
    free(node);
}

12.3 栈与队列：两种经典线性结构

栈和队列，说白了就是操作受限的线性表。栈是后进先出（LIFO），队列是先进先出（FIFO）。

栈的实现，可以用数组，也可以用链表。我个人偏爱数组实现，简单高效：

#define MAX_SIZE 100
typedef struct {
    int data[MAX_SIZE];
    int top;
} Stack;

void push(Stack *s, int val) {
    if (s->top == MAX_SIZE - 1) {
        printf("栈满了\n");
        return;
    }
    s->data[++s->top] = val;
}

int pop(Stack *s) {
    if (s->top == -1) {
        printf("栈空了\n");
        return -1;
    }
    return s->data[s->top--];
}

你想想看，栈的应用场景多不多？函数调用、括号匹配、表达式求值，全是栈的活。

队列的实现，我建议用循环数组，避免假溢出：

typedef struct {
    int data[MAX_SIZE];
    int front, rear;
} Queue;

void enqueue(Queue *q, int val) {
    if ((q->rear + 1) % MAX_SIZE == q->front) {
        printf("队列满了\n");
        return;
    }
    q->data[q->rear] = val;
    q->rear = (q->rear + 1) % MAX_SIZE;
}

int dequeue(Queue *q) {
    if (q->front == q->rear) {
        printf("队列空了\n");
        return -1;
    }
    int val = q->data[q->front];
    q->front = (q->front + 1) % MAX_SIZE;
    return val;
}

12.4 哈希表：快速查找的利器

哈希表，说白了就是通过一个哈希函数，把键映射到数组的某个位置。理想情况下，查找是 O(1) 的。

但现实很骨感——哈希冲突是绕不开的。我常用的解决方法是链地址法：每个数组元素挂一个链表。

#define TABLE_SIZE 10

typedef struct HashNode {
    int key;
    int value;
    struct HashNode *next;
} HashNode;

typedef struct {
    HashNode *buckets[TABLE_SIZE];
} HashTable;

哈希函数我一般用取模：

int hash(int key) {
    return key % TABLE_SIZE;
}

插入操作：

void put(HashTable *ht, int key, int value) {
    int idx = hash(key);
    HashNode *newNode = (HashNode *)malloc(sizeof(HashNode));
    newNode->key = key;
    newNode->value = value;
    newNode->next = ht->buckets[idx];
    ht->buckets[idx] = newNode;
}

查找操作：

int get(HashTable *ht, int key) {
    int idx = hash(key);
    HashNode *cur = ht->buckets[idx];
    while (cur != NULL) {
        if (cur->key == key)
            return cur->value;
        cur = cur->next;
    }
    return -1; // 没找到
}

12.5 知识体系总览

下面这张图，把本章的数据结构串起来了。你看一眼，心里就有谱了。

12.6 我的建议

学数据结构，别光看代码。我建议你动手画图，把每个操作在纸上走一遍。指针怎么指，节点怎么连，画清楚了再写代码。

另外，别贪多。单向链表玩熟了，再玩双向。栈和队列搞明白了，再碰哈希表。一步一个脚印，比什么都强。

嗯，这一章就到这里。代码都在上面了，你拿去跑一跑，改一改，试试看。

---