重生之“我打数据结构，真的假的？”--2.单链表（无习题）

C语言中的单链表总结

单链表是一种基础的数据结构，广泛应用于C语言编程中。它由节点组成，每个节点包含数据和指向下一个节点的指针。单链表的优点在于动态内存分配和高效的插入与删除操作。本文将详细探讨单链表的定义、基本操作、应用场景以及相关示例代码。

一、单链表的基本结构

单链表由多个节点组成，每个节点包含两部分：

• 数据部分：存储实际数据。
• 指针部分：指向下一个节点的指针。
  

节点的定义

在C语言中，我们可以使用结构体来定义单链表的节点。

typedef struct Node {int data;               // 数据部分struct Node* next;      // 指向下一个节点的指针
} Node;

二、单链表的基本操作

1. 创建单链表

创建单链表通常需要一个头指针，用于指向链表的第一个节点。若链表为空，头指针为NULL。

Node* createList() {return NULL;  // 返回空链表
}

2. 插入节点

2.1 在头部插入

在链表的头部插入新节点是最简单的操作。我们需要创建一个新节点，并将其指向当前的头节点。

Node* insertAtHead(Node* head, int newData) {Node* newNode = (Node*)malloc(sizeof(Node)); // 动态分配内存newNode->data = newData;    // 设置新节点的数据newNode->next = head;       // 新节点指向原头节点return newNode;             // 返回新的头节点
}

2.2 在尾部插入

在尾部插入节点需要遍历链表找到最后一个节点，然后将其指针指向新节点。

Node* insertAtTail(Node* head, int newData) {Node* newNode = (Node*)malloc(sizeof(Node));newNode->data = newData;newNode->next = NULL; // 新节点的下一个指针为NULLif (head == NULL) {return newNode; // 如果链表为空，返回新节点}Node* temp = head;while (temp->next != NULL) {temp = temp->next; // 遍历到最后一个节点}temp->next = newNode; // 将最后一个节点的next指针指向新节点return head;
}

3. 删除节点

删除节点通常需要指定要删除的节点值，遍历链表找到该节点并进行删除。

Node* deleteNode(Node* head, int key) {Node* temp = head;Node* prev = NULL;// 如果头节点包含要删除的值if (temp != NULL && temp->data == key) {head = temp->next; // 更新头节点free(temp);        // 释放内存return head;}// 遍历链表查找要删除的节点while (temp != NULL && temp->data != key) {prev = temp;temp = temp->next;}// 如果未找到要删除的节点if (temp == NULL) {return head;}// 解除节点的链接并释放内存prev->next = temp->next;free(temp);return head;
}

4. 查找节点

查找节点根据值查找节点的位置。

Node* search(Node* head, int key) {Node* current = head;while (current != NULL) {if (current->data == key) {return current; // 返回找到的节点}current = current->next; // 继续遍历}return NULL; // 未找到
}

5. 遍历链表

遍历链表通常用于显示链表中的所有数据。

void traverseList(Node* head) {Node* temp = head;while (temp != NULL) {printf("%d -> ", temp->data);temp = temp->next;}printf("NULL\n"); // 显示链表结束
}

6. 反转链表

反转链表操作是将链表的指向反转，使最后一个节点变为第一个节点。

Node* reverseList(Node* head) {Node* prev = NULL;Node* current = head;Node* next = NULL;while (current != NULL) {next = current->next; // 保存下一个节点current->next = prev; // 反转指针prev = current;       // 移动prev和currentcurrent = next;}return prev; // 返回新的头节点
}

三、单链表的应用

单链表在许多场景中都有应用，包括：

1. 动态数据存储：当数据量不固定时，链表能有效利用内存。
2. 实现栈和队列：单链表可以轻松实现栈和队列的操作。
3. 缓存管理：可以用于实现LRU缓存。
4. 图的邻接表表示：链表可以表示图中节点之间的连接关系。

四、完整示例

下面是一个完整的单链表示例，演示了所有基本操作。

#include <stdio.h>
#include <stdlib.h>typedef struct Node {int data;struct Node* next;
} Node;Node* createList() {return NULL;
}Node* insertAtHead(Node* head, int newData) {Node* newNode = (Node*)malloc(sizeof(Node));newNode->data = newData;newNode->next = head;return newNode;
}Node* insertAtTail(Node* head, int newData) {Node* newNode = (Node*)malloc(sizeof(Node));newNode->data = newData;newNode->next = NULL;if (head == NULL) {return newNode;}Node* temp = head;while (temp->next != NULL) {temp = temp->next;}temp->next = newNode;return head;
}Node* deleteNode(Node* head, int key) {Node* temp = head;Node* prev = NULL;if (temp != NULL && temp->data == key) {head = temp->next;free(temp);return head;}while (temp != NULL && temp->data != key) {prev = temp;temp = temp->next;}if (temp == NULL) {return head;}prev->next = temp->next;free(temp);return head;
}Node* search(Node* head, int key) {Node* current = head;while (current != NULL) {if (current->data == key) {return current;}current = current->next;}return NULL;
}void traverseList(Node* head) {Node* temp = head;while (temp != NULL) {printf("%d -> ", temp->data);temp = temp->next;}printf("NULL\n");
}Node* reverseList(Node* head) {Node* prev = NULL;Node* current = head;Node* next = NULL;while (current != NULL) {next = current->next;current->next = prev;prev = current;current = next;}return prev;
}int main() {Node* head = createList();head = insertAtHead(head, 1);head = insertAtTail(head, 2);head = insertAtTail(head, 3);head = insertAtHead(head, 0);printf("Current List: ");traverseList(head);head = deleteNode(head, 2);printf("After Deleting 2: ");traverseList(head);Node* foundNode = search(head, 1);if (foundNode) {printf("Found Node with data: %d\n", foundNode->data);} else {printf("Node not found.\n");}head = reverseList(head);printf("Reversed List: ");traverseList(head);return 0;
}

五、总结

单链表是一种灵活且实用的数据结构，通过动态内存分配和简单的插入、删除操作，使得它在许多实际应用中都能发挥重要作用。掌握单链表的基本操作，为深入学习其他数据结构奠定了基础。希望本总结对理解和使用单链表有所帮助。

小习题：

习题1

习题2

习题3