【C语言】深入理解C语言链表

╰+攻爆jí腚メ 2024-03-17 21:29 100阅读 0赞

> 链表是一种常见的数据结构，广泛应用于计算机科学中。C语言提供了丰富的指针操作，使得链表的实现相对简便。本博客将介绍链表的基本概念，以及使用C语言实现链表的代码示例。

**目录**

一、链表的基本概念

二、链表的分类

三、通俗例子：学生管理系统

--------------------

## 一、链表的基本概念 ##

链表是由节点（Node）组成的数据结构，每个节点包含两个部分：数据域和指针域。数据域用于存储数据，指针域用于指向下一个节点。链表的起点为头节点（Head），尾节点的指针域为NULL。

![链表操作-嗨客网][-]

链表的特点包括：动态性（可以灵活地添加或删除节点）、内存利用率高、插入和删除操作效率高。然而，链表的查询效率较低，需要遍历整个链表才能找到目标节点。

## 二、链表的分类 ##

![看动画理解「链表」实现LRU缓存淘汰算法 － 小专栏][LRU_ _]

1. **单链表（Singly Linked List）**：单链表是最基本的链表类型，每个节点包含一个数据域和一个指向下一个节点的指针。它只能从头节点开始顺序访问，无法回溯到前一个节点。

示例代码：

#include <stdio.h>
    #include <stdlib.h>
    
    typedef struct Node {
        int data;
        struct Node* next;
    } Node;
    
    void printList(Node* head) {
        Node* current = head;
        
        while (current != NULL) {
            printf("%d ", current->data);
            current = current->next;
        }
    }
    
    // 在链表尾部插入新节点
    void insert(Node** head, int data) {
        Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->data = data;
        newNode->next = NULL;
        
        if (*head == NULL) {
            *head = newNode;
        } else {
            Node* current = *head;
            
            while (current->next != NULL) {
                current = current->next;
            }
            
            current->next = newNode;
        }
    }
    
    int main() {
        Node* head = NULL;
    
        insert(&head, 1);
        insert(&head, 2);
        insert(&head, 3);
        
        printList(head);
        
        return 0;
    }

2. **双向链表（Doubly Linked List）**：双向链表中的每个节点都有两个指针，一个指向前一个节点，一个指向后一个节点。相比于单链表，双向链表可以进行双向遍历和删除操作，但在插入和删除节点时需要维护更多的指针关系。

示例代码：

#include <stdio.h>
    #include <stdlib.h>
    
    typedef struct Node {
        int data;
        struct Node* prev;
        struct Node* next;
    } Node;
    
    void printList(Node* head) {
        Node* current = head;
        
        while (current != NULL) {
            printf("%d ", current->data);
            current = current->next;
        }
    }
    
    void insert(Node** head, int data) {
        Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->data = data;
        newNode->prev = NULL;
        newNode->next = NULL;
        
        if (*head == NULL) {
            *head = newNode;
        } else {
            Node* current = *head;
            
            while (current->next != NULL) {
                current = current->next;
            }
            
            newNode->prev = current;
            current->next = newNode;
        }
    }
    
    int main() {
        Node* head = NULL;
    
        insert(&head, 1);
        insert(&head, 2);
        insert(&head, 3);
        
        printList(head);
        
        return 0;
    }

3. **循环链表（Circular Linked List）**：循环链表是一种特殊的链表，最后一个节点的指针指向第一个节点，形成一个闭环。循环链表可以无限循环地遍历，常用于构建循环队列等数据结构。

示例代码：

#include <stdio.h>
    #include <stdlib.h>
    
    typedef struct Node {
        int data;
        struct Node* next;
    } Node;
    
    void printList(Node* head) {
        Node* current = head;
        
        if (head == NULL) {
            return;
        }
        
        do {
            printf("%d ", current->data);
            current = current->next;
        } while (current != head);
    }
    
    void insert(Node** head, int data) {
        Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->data = data;
        newNode->next = NULL;
        
        if (*head == NULL) {
            *head = newNode;
            newNode->next = newNode;
        } else {
            Node* last = *head;
            
            while (last->next != *head) {
                last = last->next;
            }
            
            newNode->next = *head;
            last->next = newNode;
        }
    }
    
    int main() {
        Node* head = NULL;
    
        insert(&head, 1);
        insert(&head, 2);
        insert(&head, 3);
        
        printList(head);
        
        return 0;
    }

4. **静态链表（Static Linked List）**：静态链表是使用数组实现的链表，而不是使用指针。通过数组的下标关系来模拟节点之间的链接关系。静态链表的缺点是大小固定，插入和删除节点不方便，但由于不需要指针的额外存储空间，具有一定的存储效率。

5. **带头结点链表（Head Linked List）**：带头结点的链表在链表开始部分添加了一个额外的头节点，用于简化链表的操作。头节点不存储具体的数据，仅用于指向第一个真正的节点，有助于统一处理链表的边界情况。

6. **带环链表（Cyclic Linked List）**：带环链表是一种特殊的链表，其中某个节点的指针指向链表中的一个前面的节点，形成环状结构。带环链表常用于解决一些与环有关的算法问题，如判断链表中是否存在环、找到环的起点等。

## 三、通俗例子：学生管理系统 ##

假设我们要存储一组人的信息，每个人有姓名和年龄两个属性。如果使用数组来存储这些人的信息，可能会遇到一个问题：数组的大小是固定的，无法动态地添加或删除人员。这时候链表就派上用场了。

我们可以将链表看作是一个班级的人员名册。每个节点表示一个人，其中数据域存储着该人的姓名和年龄，指针域则指向下一个人。

现在，我们以一个简单的链表为例来说明。

假设我们有以下链表：

-> [Alice, 25] -> [Bob, 30] -> [Charlie, 35] -> [Diana, 40] -> NULL

**其中箭头表示指针，指向下一个节点。**

在这个链表中，每个节点都包含两个部分：**数据域**和**指针域**。数据域存储人员的姓名和年龄，指针域则指向下一个人员节点。

我们可以从头节点（最前面的节点）开始，依次遍历整个链表，获取每个人员的信息。

通过链表，我们可以轻松地添加新的人员信息。比如，假设我们要插入一个叫"Eva"、年龄为28岁的人，只需在链表尾部添加一个新节点：

-> [Alice, 25] -> [Bob, 30] -> [Charlie, 35] -> [Diana, 40] -> [Eva, 28] -> NULL

或者，我们也可以在链表中间插入一个新节点，比如将"Bob"后面插入一个叫"Frank"、年龄为32岁的人：

-> [Alice, 25] -> [Bob, 30] -> [Frank, 32] -> [Charlie, 35] -> [Diana, 40] -> NULL

此外，我们还可以轻松地删除链表中的人员信息。比如，我们要删除年龄为35岁的"Charlie"，只需要将指向"Charlie"的指针跳过，让它指向"Charlie"后面的节点：

-> [Alice, 25] -> [Bob, 30] -> [Frank, 32] -> [Diana, 40] -> NULL

通过这个通俗的例子，我们可以更好地理解链表的概念。链表具有动态存储、灵活插入和删除的特性，可以解决一些固定大小的数据结构无法满足的需求。对于需要经常进行插入和删除操作的场景，链表是一个非常有用的数据结构。

[-]: https://haicoder.net/uploads/pic/architecture/datastruct/datastruct-arrays-lists/15_%E9%93%BE%E8%A1%A8%E8%AF%A6%E8%A7%A3.png
[LRU_ _]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/666822599bdf4b258594f5ea559899c6.png