「Linux链表实现」——学习样例代码如何用C语言实现一个简单的链表结构 (linux 链表实现)
Linux链表实现——学习样例代码如何用C语言实现一个简单的链表结构
链表是一种常见的线性数据结构，用于存储数据。它可以动态地增加或删除元素，不需要提前分配固定的内存空间。
在Linux内核中，链表也被广泛使用。内核维护了许多链表结构，例如进程链表、文件描述符链表等等。在了解内核源代码之前，我们可以先来看一下如何用C语言实现一个简单的链表结构。
1. 链表的定义
我们可以用结构体来定义链表节点：
“`
struct node {
int data;
struct node *next;
};
“`
其中，data表示节点中存储的数据，next表示指向下一个节点的指针。
2. 初始化链表
为了让链表起始为空，我们需要定义一个head指向NULL：
“`
struct node *head = NULL;
“`
3. 插入节点
我们可以定义一个函数来向链表中插入一个节点：
“`
void insert(int data) {
struct node *new_node = (struct node*) malloc(sizeof(struct node));
new_node->data = data;
new_node->next = head;
head = new_node;
}
“`
我们要创建一个新节点并分配内存。然后，将数据存储到新节点中，并将其next指针指向head。我们将head指针指向新节点，以便新节点成为链表的之一个元素。
4. 删除节点
同样地，我们可以定义一个函数来从链表中删除一个节点：
“`
void delete(int data) {
struct node *current = head;
struct node *previous = NULL;
while (current != NULL && current->data != data) {
previous = current;
current = current->next;
}
if (current == NULL) {
return; // 数据没找到
}
if (previous == NULL) {
head = current->next; // 删除之一个节点
} else {
previous->next = current->next; // 删除中间节点
}
free(current); // 释放内存
}
“`
我们通过遍历链表来找到要删除的节点。如果找不到相应的节点，我们就返回。如果相应的节点存在，我们就把previous指向当前节点的前一个节点，并把current指向当前节点。
然后，我们检查是否要删除之一个节点，如果是，则更新head指针。否则，我们就更新previous节点的next指针，将其指向current节点的next指针。
我们释放current节点的内存。
5. 遍历链表
我们可以用一个循环来遍历链表并打印其中的每个元素：
“`
void traverse() {
struct node *current = head;
while (current != NULL) {
printf(“%d “, current->data);
current = current->next;
}
printf(“\n”);
}
“`
6. 完整代码
最终，我们可以得到以下完整的链表实现代码：
“`
#include
#include
struct node {
int data;
struct node *next;
};
struct node *head = NULL;
void insert(int data) {
struct node *new_node = (struct node*) malloc(sizeof(struct node));
new_node->data = data;
new_node->next = head;
head = new_node;
}
void delete(int data) {
struct node *current = head;
struct node *previous = NULL;
while (current != NULL && current->data != data) {
previous = current;
current = current->next;
}
if (current == NULL) {
return;
}
if (previous == NULL) {
head = current->next;
} else {
previous->next = current->next;
}
free(current);
}
void traverse() {
struct node *current = head;
while (current != NULL) {
printf(“%d “, current->data);
current = current->next;
}
printf(“\n”);
}
int mn() {
insert(1);
insert(2);
insert(3);
traverse();
delete(2);
traverse();
return 0;
}
“`
在本样例中，我们定义了一个链表并在其中插入了三个节点。然后，我们遍历链表并打印其中的每个元素。接下来，我们删除了第二个节点，并再次遍历链表以确认节点已被删除。
