【数据结构与算法】单向链表

**数据结构与算法**

**单向链表**

单向链表是一种线性数据结构，具有一个方向的指针（即只可以从头部开始遍历），每个结点包含一个值和一个指向下一个结点的指针。这种数据结构在实际应用中非常常见，例如数据库中的索引、缓存等。

**单向链表的定义**

ctypedef struct Node {
 int data; // 结点的值 struct Node* next; // 指向下一个结点的指针} Node;

**单向链表的基本操作**

1. **创建链表**: 创建一个新的链表，包含一个头结点。

cNode* createList() {
 Node* head = (Node*)malloc(sizeof(Node));
 if (!head) return NULL; // 内存分配失败 head->data =0;
 head->next = NULL;
 return head;
}

2. **插入结点**: 将一个新结点插入到链表的指定位置。

cvoid insertNode(Node* head, int data, int position) {
 Node* newNode = (Node*)malloc(sizeof(Node));
 if (!newNode) return; // 内存分配失败 newNode->data = data;
 newNode->next = NULL;

 if (position ==0) { // 插入到头结点 newNode->next = head;
 head = newNode;
 } else {
 Node* current = head;
 for (int i =0; i < position -1; i++) {
 if (!current->next) break; // 到达链表末尾 current = current->next;
 }
 if (current->next) { // 插入到指定位置 newNode->next = current->next;
 current->next = newNode;
 } else { // 插入到链表末尾 current->next = newNode;
 }
 }
}

3. **删除结点**: 删除链表中的一个结点。

cvoid deleteNode(Node* head, int data) {
 if (head == NULL) return; // 链表为空 if (head->data == data) { // 删除头结点 Node* temp = head;
 head = head->next;
 free(temp);
 return;
 }

 Node* current = head;
 while (current->next && current->next->data != data) {
 current = current->next;
 }
 if (current->next) { // 找到要删除的结点 Node* temp = current->next;
 current->next = current->next->next;
 free(temp);
 }
}

4. **打印链表**: 打印链表中的所有结点。

cvoid printList(Node* head) {
 while (head) {
 printf("%d ", head->data);
 head = head->next;
 }
 printf("
");
}

**单向链表的应用**

1. **数据库索引**: 单向链表可以用来实现数据库索引，快速定位数据。
2. **缓存**: 单向链表可以用来实现缓存机制，快速访问最近使用过的数据。
3. **浏览器历史记录**: 单向链表可以用来实现浏览器历史记录功能，快速回溯之前的页面。

**总结**

单向链表是一种线性数据结构，具有一个方向的指针，每个结点包含一个值和一个指向下一个结点的指针。这种数据结构在实际应用中非常常见，例如数据库中的索引、缓存等。通过创建链表、插入结点、删除结点和打印链表等基本操作，可以实现单向链表的各种功能。