网站导航
> 技术文档 > 重生之“我打数据结构，真的假的？”--2.单链表（无习题）

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

网友: 技术文档 2025-07-30 11:54:15

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

C语言中的单链表总结

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

一、单链表的基本结构

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

  • 数据部分：存储实际数据。
  • 指针部分：指向下一个节点的指针。
    重生之“我打数据结构，真的假的？”--2.单链表（无习题）

节点的定义

在C语言中，我们可以使用结构体来定义单链表的节点。
重生之“我打数据结构，真的假的？”--2.单链表（无习题）

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; // 新节点的下一个指针为NULL if (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和current current = next; } return prev; // 返回新的头节点}

三、单链表的应用

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

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

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

四、完整示例

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

#include #include 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

网络标签：

相关问题