C语言进阶教程：链表（单向、双向、循环）的实现与操作

链表是一种基础且重要的数据结构，它由一系列节点（Node）组成，这些节点在内存中不必是连续存储的。每个节点包含数据域和指向下一个（或上一个）节点的指针域。链表因其动态性（可以方便地插入和删除元素而无需移动大量数据）而被广泛应用于各种编程场景。

本教程将介绍三种基本类型的链表：单向链表、双向链表和循环链表。

1. 单向链表 (Singly Linked List)

定义

单向链表的每个节点包含两部分：

0. 数据域 (Data)：存储实际数据。
1. 指针域 (Next)：存储指向下一个节点的地址。最后一个节点的指针域通常为 NULL。

   Head
    |    +------+-----+     +------+-----+     +------+-----+ 
    +--->| Data | Next|---->| Data | Next|---->| Data | NULL|
         +------+-----+     +------+-----+     +------+-----+ 
          Node 1              Node 2              Node 3 (Tail)

节点结构定义

 #include <stdio.h>
 #include <stdlib.h>
 
 // 单向链表节点定义
 typedef struct SNode {
     int data;           // 数据域，这里假设为int类型
     struct SNode *next; // 指针域，指向下一个节点
 } SNode, *SLinkedList; // SNode是结构体类型名，SLinkedList是指向SNode的指针类型

基本操作

a. 创建节点

 SNode* create_snode(int value) {
     SNode *new_node = (SNode*)malloc(sizeof(SNode));
     if (new_node == NULL) {
         perror("Failed to allocate memory for new snode");
         return NULL;
     }
     new_node->data = value;
     new_node->next = NULL;
     return new_node;
 }

b. 插入节点

• 头插法 (Insert at Head)：新节点成为新的头节点。
• void insert_snode_at_head(SLinkedList *head_ref, int value) {
  SNode *new_node = create_snode(value);
  if (new_node == NULL) return;
  new_node->next = *head_ref; // 新节点的next指向原来的头节点
  *head_ref = new_node; // 更新头指针指向新节点
  }
• 尾插法 (Insert at Tail)：新节点添加到链表末尾。
• void insert_snode_at_tail(SLinkedList *head_ref, int value) {
  SNode *new_node = create_snode(value);
  if (new_node == NULL) return;
  if (*head_ref == NULL) { // 如果链表为空
  *head_ref = new_node;
  return;
  }
  SNode *current = *head_ref;
  while (current->next != NULL) { // 遍历到最后一个节点
  current = current->next;
  }
  current->next = new_node; // 将最后一个节点的next指向新节点
  }
• 在指定位置后插入 (Insert After a Given Node)：
• void insert_snode_after(SNode *prev_node, int value) {
  if (prev_node == NULL) {
  printf("Previous node cannot be NULL for insertion.\n");
  return;
  }
  SNode *new_node = create_snode(value);
  if (new_node == NULL) return;
  new_node->next = prev_node->next;
  prev_node->next = new_node;
  }

c. 删除节点

• 删除指定值的节点：需要找到该节点及其前驱节点。
• void delete_snode_by_value(SLinkedList *head_ref, int key) {
  SNode *temp = *head_ref, *prev = NULL;
  // 如果头节点就是要删除的节点
  if (temp != NULL && temp->data == key) {
  *head_ref = temp->next; // 改变头指针
  free(temp); // 释放旧头节点
  return;
  }
  // 查找要删除的节点，并记录其前驱
  while (temp != NULL && temp->data != key) {
  prev = temp;
  temp = temp->next;
  }
  // 如果没有找到该节点
  if (temp == NULL) {
  printf("Node with value %d not found.\n", key);
  return;
  }
  // 从链表中移除节点
  prev->next = temp->next;
  free(temp); // 释放内存
  }

d. 遍历链表

 void print_slist(SLinkedList head) {
     SNode *current = head;
     while (current != NULL) {
         printf("%d -> ", current->data);
         current = current->next;
     }
     printf("NULL\n");
 }

e. 查找节点

SNode* find_snode(SLinkedList head, int key) {
    SNode *current = head;
    while (current != NULL) {
        if (current->data == key) {
            return current;
        }
        current = current->next;
    }
    return NULL; // 未找到
}

f. 释放整个链表

void free_slist(SLinkedList *head_ref) {
    SNode *current = *head_ref;
    SNode *next_node;
    while (current != NULL) {
        next_node = current->next;
        free(current);
        current = next_node;
    }
    *head_ref = NULL; // 将头指针置为NULL
}

单向链表示例

int main_singly() { // Renamed to avoid conflict if all examples are in one file
    SLinkedList list_head = NULL;

    insert_snode_at_tail(&list_head, 10);
    insert_snode_at_head(&list_head, 5);
    insert_snode_at_tail(&list_head, 20);
    insert_snode_after(find_snode(list_head, 10), 15);

    printf("Singly Linked List: ");
    print_slist(list_head);

    delete_snode_by_value(&list_head, 10);
    printf("After deleting 10: ");
    print_slist(list_head);

    SNode *found = find_snode(list_head, 15);
    if (found) {
        printf("Found node with value: %d\n", found->data);
    }

    free_slist(&list_head);
    printf("After freeing list: ");
    print_slist(list_head);
    return 0;
}

2. 双向链表 (Doubly Linked List)

定义

双向链表的每个节点包含三部分：

0. 数据域 (Data)。
1. 指向下一个节点的指针域 (Next)。
2. 指向上一个节点的指针域 (Prev)。第一个节点的 prev 指针通常为 NULL，最后一个节点的 next 指针通常为 NULL。

      Head                                        Tail
       |                                            |
       v                                            v
+------+-----+-----+     +------+-----+-----+     +------+-----+-----+
| NULL | Data| Next|---->| Prev | Data| Next|---->| Prev | Data| NULL|
+------+-----+-----+<----|------+-----+-----+<----|------+-----+-----+
       Node 1              Node 2              Node 3

节点结构定义

// 双向链表节点定义
typedef struct DNode {
    int data;
    struct DNode *prev;
    struct DNode *next;
} DNode, *DLinkedList;

基本操作

双向链表的操作比单向链表略复杂，因为插入和删除时需要同时维护 next 和 prev 两个指针。

a. 创建节点

DNode* create_dnode(int value) {
    DNode *new_node = (DNode*)malloc(sizeof(DNode));
    if (new_node == NULL) {
        perror("Failed to allocate memory for new dnode");
        return NULL;
    }
    new_node->data = value;
    new_node->prev = NULL;
    new_node->next = NULL;
    return new_node;
}

b. 插入节点

• 头插法
• void insert_dnode_at_head(DLinkedList *head_ref, int value) {
  DNode *new_node = create_dnode(value);
  if (new_node == NULL) return;
  new_node->next = *head_ref;
  if (*head_ref != NULL) {
  (*head_ref)->prev = new_node;
  }
  *head_ref = new_node;
  }
• 尾插法
• void insert_dnode_at_tail(DLinkedList *head_ref, int value) {
  DNode *new_node = create_dnode(value);
  if (new_node == NULL) return;
  if (*head_ref == NULL) {
  *head_ref = new_node;
  return;
  }
  DNode *last = *head_ref;
  while (last->next != NULL) {
  last = last->next;
  }
  last->next = new_node;
  new_node->prev = last;
  }
• 在指定节点后插入
• void insert_dnode_after(DNode *prev_node, int value) {
  if (prev_node == NULL) {
  printf("Previous node cannot be NULL.\n");
  return;
  }
  DNode *new_node = create_dnode(value);
  if (new_node == NULL) return;
  new_node->next = prev_node->next;
  new_node->prev = prev_node;
  prev_node->next = new_node;
  if (new_node->next != NULL) { // 如果 prev_node 不是尾节点
  new_node->next->prev = new_node;
  }
  }
• 在指定节点前插入
• void insert_dnode_before(DLinkedList *head_ref, DNode *next_node, int value) {
  if (next_node == NULL) {
  printf("Next node cannot be NULL for insertion before.\n");
  // (Could also mean insert at tail if list is not empty, or head if list is empty)
  // For simplicity, we assume next_node is a valid existing node or we are inserting at head.
  if (*head_ref == NULL) { // If list is empty, this is like head insertion
  insert_dnode_at_head(head_ref, value);
  return;
  }
  // If next_node is NULL but list is not, it's ambiguous. Let's disallow for now.
  return;
  }
  DNode *new_node = create_dnode(value);
  if (new_node == NULL) return;
  new_node->prev = next_node->prev;
  new_node->next = next_node;
  next_node->prev = new_node;
  if (new_node->prev != NULL) { // 如果 next_node 不是头节点
  new_node->prev->next = new_node;
  } else { // new_node 成为新的头节点
  *head_ref = new_node;
  }
  }

c. 删除节点

删除节点 del_node 时，需要处理其前驱 del_node->prev 和后继 del_node->next。

void delete_dnode(DLinkedList *head_ref, DNode *del_node) {
    if (*head_ref == NULL || del_node == NULL) {
        return;
    }

    // 如果要删除的是头节点
    if (*head_ref == del_node) {
        *head_ref = del_node->next;
    }

    // 修改 del_node 的后继节点的前驱指针 (如果 del_node 不是尾节点)
    if (del_node->next != NULL) {
        del_node->next->prev = del_node->prev;
    }

    // 修改 del_node 的前驱节点的后继指针 (如果 del_node 不是头节点)
    if (del_node->prev != NULL) {
        del_node->prev->next = del_node->next;
    }

    free(del_node);
}

// 辅助函数：按值查找并删除
void delete_dnode_by_value(DLinkedList *head_ref, int key) {
    DNode *current = *head_ref;
    while (current != NULL) {
        if (current->data == key) {
            delete_dnode(head_ref, current);
            return; // 假设只删除第一个匹配项
        }
        current = current->next;
    }
    printf("Node with value %d not found for deletion.\n", key);
}

d. 遍历链表 (正向和反向)

void print_dlist_forward(DLinkedList head) {
    DNode *current = head;
    printf("Forward: NULL <-> ");
    while (current != NULL) {
        printf("%d <-> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

void print_dlist_backward(DLinkedList head) {
    if (head == NULL) {
        printf("Backward: NULL\n");
        return;
    }
    DNode *last = head;
    while (last->next != NULL) { // 找到尾节点
        last = last->next;
    }
    printf("Backward: NULL <-> ");
    DNode *current = last;
    while (current != NULL) {
        printf("%d <-> ", current->data);
        current = current->prev;
    }
    printf("NULL\n");
}

e. 释放整个链表

与单向链表类似。

void free_dlist(DLinkedList *head_ref) {
    DNode *current = *head_ref;
    DNode *next_node;
    while (current != NULL) {
        next_node = current->next;
        free(current);
        current = next_node;
    }
    *head_ref = NULL;
}

双向链表示例

int main_doubly() { // Renamed
    DLinkedList dlist_head = NULL;
    insert_dnode_at_head(&dlist_head, 10);
    insert_dnode_at_tail(&dlist_head, 20);
    insert_dnode_at_head(&dlist_head, 5);
    // 假设要插在10之后: find 10, then insert_dnode_after
    DNode *node_10 = dlist_head; // 5 -> 10 -> 20, node_10 is 5
    while(node_10 != NULL && node_10->data != 10) node_10 = node_10->next;
    if(node_10) insert_dnode_after(node_10, 15); // 5 -> 10 -> 15 -> 20

    printf("Doubly Linked List (Forward): "); print_dlist_forward(dlist_head);
    printf("Doubly Linked List (Backward): "); print_dlist_backward(dlist_head);

    delete_dnode_by_value(&dlist_head, 10);
    printf("After deleting 10 (Forward): "); print_dlist_forward(dlist_head);

    free_dlist(&dlist_head);
    printf("After freeing list (Forward): "); print_dlist_forward(dlist_head);
    return 0;
}

3. 循环链表 (Circular Linked List)

定义

循环链表可以是单向的也可以是双向的。其特点是链表的最后一个节点的 next 指针（对于单向循环链表）或 next 和 prev 指针（对于双向循环链表）不再指向 NULL，而是指向链表的头节点。

a. 单向循环链表

最后一个节点的 next 指针指向头节点。

  Head
   |    +------+-----+     +------+-----+     +------+-----+ 
   +--->| Data | Next|---->| Data | Next|---->| Data | Next|--+
        +------+-----+     +------+-----+     +------+-----+  |
         Node 1              Node 2              Node 3       |
          ^                                                   |
          |                                                   |
          +---------------------------------------------------+

b. 双向循环链表

最后一个节点的 next 指针指向头节点，头节点的 prev 指针指向尾节点。

          +---------------------------------------------------+ 
          |                                                   | 
          v  Head                                           ^ Tail
   +------+-----+-----+     +------+-----+-----+     +------+-----+-----+
   | Prev | Data| Next|---->| Prev | Data| Next|---->| Prev | Data| Next|--+
   +------+-----+-----+<----|------+-----+-----+<----|------+-----+-----+  |
          Node 1              Node 2              Node 3       |
           ^                                                   |
           |                                                   |
           +---------------------------------------------------+

节点结构定义

与单向或双向链表相同，区别在于指针的连接方式。

基本操作 (以单向循环链表为例)

操作循环链表时，需要特别注意循环的终止条件，以及在修改头尾连接时正确更新指针。 通常，我们会维护一个指向尾节点的指针（tail），这样可以方便地在O(1)时间内访问头节点（tail->next）和尾节点。

a. 创建节点 (同单向链表 create_snode)

b. 插入节点 (假设维护尾指针 tail_ref)

• 在空链表中插入第一个节点
• void insert_scircular_empty(SLinkedList *tail_ref, int value) {
  SNode *new_node = create_snode(value);
  if (new_node == NULL) return;
  *tail_ref = new_node;
  new_node->next = new_node; // 指向自身形成循环
  }
• 头插法 (在 tail->next 前插入)
• void insert_scircular_at_head(SLinkedList *tail_ref, int value) {
  if (*tail_ref == NULL) { // 如果链表为空
  insert_scircular_empty(tail_ref, value);
  return;
  }
  SNode *new_node = create_snode(value);
  if (new_node == NULL) return;
  new_node->next = (*tail_ref)->next; // 新节点的next指向原来的头
  (*tail_ref)->next = new_node; // 尾节点的next指向新头
  }
• 尾插法 (在 tail 后插入，新节点成为新尾)
• void insert_scircular_at_tail(SLinkedList *tail_ref, int value) {
  if (*tail_ref == NULL) {
  insert_scircular_empty(tail_ref, value);
  return;
  }
  SNode *new_node = create_snode(value);
  if (new_node == NULL) return;
  new_node->next = (*tail_ref)->next; // 新节点的next指向原来的头
  (*tail_ref)->next = new_node; // 原尾节点的next指向新节点
  *tail_ref = new_node; // 更新尾指针
  }

c. 删除节点

删除操作比较复杂，需要考虑删除的是头节点、尾节点还是一般节点，以及链表只有一个节点的情况。

// 删除单向循环链表中指定值的节点 (假设 tail_ref 指向尾节点)
void delete_scircular_by_value(SLinkedList *tail_ref, int key) {
    if (*tail_ref == NULL) {
        printf("List is empty.\n");
        return;
    }

    SNode *current = (*tail_ref)->next; // 从头节点开始
    SNode *prev = *tail_ref;            // prev 初始化为尾节点

    // 循环查找，直到回到头节点或找到
    do {
        if (current->data == key) {
            // 情况1: 链表只有一个节点且是目标节点
            if (current == *tail_ref && current->next == current) {
                free(current);
                *tail_ref = NULL;
                return;
            }
            // 情况2: 删除的是头节点 (current == (*tail_ref)->next)
            if (current == (*tail_ref)->next) {
                (*tail_ref)->next = current->next; // 尾节点指向新的头
            }
            // 情况3: 删除的是尾节点 (current == *tail_ref)
            else if (current == *tail_ref) {
                prev->next = current->next; // 前一个节点指向头
                *tail_ref = prev;           // 更新尾指针
            }
            // 情况4: 删除的是中间节点
            else {
                prev->next = current->next;
            }
            free(current);
            return;
        }
        prev = current;
        current = current->next;
    } while (current != (*tail_ref)->next); // 循环条件

    printf("Node with value %d not found.\n", key);
}

d. 遍历链表

void print_scircular_list(SLinkedList tail) {
    if (tail == NULL) {
        printf("Circular List is empty.\n");
        return;
    }
    SNode *current = tail->next; // 从头节点开始
    printf("Head -> ");
    do {
        printf("%d -> ", current->data);
        current = current->next;
    } while (current != tail->next); // 直到再次回到头节点
    printf("(Head)\n");
}

e. 释放整个链表

void free_scircular_list(SLinkedList *tail_ref) {
    if (*tail_ref == NULL) return;

    SNode *current = (*tail_ref)->next; // 头节点
    SNode *head = current;
    SNode *next_node;

    // 断开循环，使其变成一个普通的单向链表，方便释放
    (*tail_ref)->next = NULL; 

    while (current != NULL) {
        next_node = current->next;
        free(current);
        current = next_node;
    }
    *tail_ref = NULL;
}

循环链表示例 (单向)

int main_scircular() { // Renamed
    SLinkedList sc_tail = NULL;

    insert_scircular_at_tail(&sc_tail, 10);
    insert_scircular_at_head(&sc_tail, 5);  // 5 (H) -> 10 (T) -> 5
    insert_scircular_at_tail(&sc_tail, 20); // 5 (H) -> 10 -> 20 (T) -> 5
    insert_scircular_at_head(&sc_tail, 1);  // 1 (H) -> 5 -> 10 -> 20 (T) -> 1

    printf("Singly Circular Linked List: ");
    print_scircular_list(sc_tail);

    delete_scircular_by_value(&sc_tail, 10); // 1 (H) -> 5 -> 20 (T) -> 1
    printf("After deleting 10: ");
    print_scircular_list(sc_tail);

    delete_scircular_by_value(&sc_tail, 1); // 5 (H) -> 20 (T) -> 5
    printf("After deleting 1 (head): ");
    print_scircular_list(sc_tail);

    delete_scircular_by_value(&sc_tail, 20); // 5 (H, T) -> 5
    printf("After deleting 20 (tail): ");
    print_scircular_list(sc_tail);

    delete_scircular_by_value(&sc_tail, 5); // Empty
    printf("After deleting 5 (last element): ");
    print_scircular_list(sc_tail);

    // Re-populate for freeing test
    insert_scircular_at_tail(&sc_tail, 100);
    insert_scircular_at_tail(&sc_tail, 200);
    free_scircular_list(&sc_tail);
    printf("After freeing list: ");
    print_scircular_list(sc_tail);

    return 0;
}

// To run all examples, you might call them from a main function:
/*
int main() {
    printf("--- Singly Linked List Demo ---\n");
    main_singly();
    printf("\n--- Doubly Linked List Demo ---\n");
    main_doubly();
    printf("\n--- Singly Circular Linked List Demo ---\n");
    main_scircular();
    return 0;
}
*/

4. 链表的优缺点与应用

优点

• 动态大小：链表可以在运行时动态增长和缩小，不需要预先知道元素数量。
• 插入和删除高效：一旦定位到要操作的节点，插入和删除操作的时间复杂度通常是 O(1)（不包括查找时间）。这比数组（可能需要移动大量元素）要高效。
• 内存利用率：按需分配内存，不会像静态数组那样可能浪费空间（如果数组未满）。

缺点

• 随机访问慢：要访问链表中的第 i 个元素，必须从头开始遍历，时间复杂度为 O(n)。数组的随机访问是 O(1)。
• 额外内存开销：每个节点都需要额外的空间来存储指针（next，以及双向链表的 prev）。
• 缓存性能：链表节点在内存中可能不连续，这可能导致CPU缓存命中率降低，影响性能，尤其是在遍历大量节点时。

应用场景

• 实现栈和队列。
• 需要频繁插入和删除操作的场景，如音乐播放器的播放列表、任务调度器。
• 当数据元素的数量不确定时。
• 图的邻接表示法。
• 哈希表中的冲突解决（链地址法）。
• 大整数运算。
• 操作系统的内存管理（如空闲块链表）。

总结

链表是理解更复杂数据结构和算法的基础。单向链表是最简单的形式，双向链表提供了更灵活的前后遍历和删除能力（但开销更大），循环链表则适用于需要循环访问或从尾部快速访问头部的场景（如循环队列、时间片轮转调度）。

掌握链表的各种操作（创建、插入、删除、查找、遍历、释放）是C语言程序员必备的技能。在实际应用中，选择哪种链表取决于具体的需求和性能考量。