当前位置：首页 > news >正文

单链表（C语言版）

news 2025/7/15 4:54:26

单链表：理解、实现与应用

单链表（Singly Linked List）是一种常见的数据结构，用于存储一系列具有相同类型的元素，并通过节点之间的链接建立起它们的关系。每个节点包含一个数据元素和一个指向下一个节点的指针。相比于数组，单链表具有动态性能，可以在运行时轻松地插入、删除元素，但也因此在访问特定元素时可能需要更多的时间。

单链表的结构

单链表由一系列节点组成，每个节点拥有两个部分：数据域和指针域。数据域存储节点的值，指针域存储指向下一个节点的指针。

单链表的优点和缺点

优点：

动态性能： 单链表可以在运行时进行插入和删除操作，而无需移动其他元素。这使得它适用于需要频繁插入、删除操作的场景。
内存分配灵活： 单链表的节点可以在不连续的内存位置上分配，这使得它更适合动态内存管理。
节省空间： 每个节点只需要存储数据和一个指向下一个节点的指针，相比之下，数组可能需要更多的内存。

缺点：

访问效率低： 访问单链表中的特定元素通常需要从头节点开始遍历，直到找到目标节点，因此访问效率较低。
占用额外空间： 每个节点都需要额外的指针来指向下一个节点，这会占用一些额外的内存空间。

单链表的基本操作

插入操作： 在特定位置插入一个新节点，需要更新前一个节点的指针以指向新节点，同时新节点的指针指向原来前一个节点指向的节点。
删除操作： 删除特定位置的节点，需要更新前一个节点的指针，使其指向被删除节点的下一个节点。
查找操作： 从头节点开始遍历，直到找到目标节点。

示例代码（C语言版本）

下面是一个简单的单链表的C语言实现，包括插入、删除和打印操作：

#include <stdio.h>
#include <stdlib.h>// 定义单链表节点结构
typedef struct Node {int data;struct Node* next;
} Node;// 在链表末尾插入新节点
void insertEnd(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;}
}// 在链表中删除指定值的节点
void 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 != NULL && current->next->data != data) {current = current->next;}if (current->next != NULL) {Node* temp = current->next;current->next = temp->next;free(temp);}
}// 在链表中查找指定值的节点
Node* searchNode(Node* head, int data) {Node* current = head;while (current != NULL) {if (current->data == data) {return current;}current = current->next;}return NULL;
}// 修改链表中指定值的节点的数据
void updateNode(Node* head, int oldData, int newData) {Node* target = searchNode(head, oldData);if (target != NULL) {target->data = newData;} else {printf("Node with old data %d not found.\n", oldData);}
}// 打印链表元素
void printList(Node* head) {Node* current = head;while (current != NULL) {printf("%d ", current->data);current = current->next;}printf("\n");
}int main() {Node* head = NULL;insertEnd(&head, 1);insertEnd(&head, 2);insertEnd(&head, 3);printf("Initial List: ");printList(head);deleteNode(&head, 2);printf("List after deleting 2: ");printList(head);updateNode(head, 1, 4);printf("List after updating 1 to 4: ");printList(head);return 0;
}