您所在的位置：首页 - 生活 - 正文生活

使用C语言实现双向链表

骏旭 2024-04-14 【生活】 189人已围观

摘要双向链表是一种常见的数据结构，它由一系列节点组成，每个节点包含数据和两个指针，分别指向前一个节点和后一个节点。在C语言中，我们可以通过结构体和指针来实现双向链表。定义双向链表节点结构体```c#inc

双向链表是一种常见的数据结构，它由一系列节点组成，每个节点包含数据和两个指针，分别指向前一个节点和后一个节点。在C语言中，我们可以通过结构体和指针来实现双向链表。

定义双向链表节点结构体

```c #include #include typedef struct Node { int data; struct Node* prev; struct Node* next; } Node; ```

在上面的代码中，我们定义了一个结构体Node，包含一个整型数据data，以及两个指向前一个节点和后一个节点的指针prev和next。

初始化双向链表

```c Node* head = NULL; void init() { head = NULL; } ```

在初始化函数init中，我们将头指针head初始化为NULL，表示链表为空。

插入节点到双向链表

```c void insert(int data) { Node* newNode = (Node*)malloc(sizeof(Node)); newNode->data = data; newNode->prev = NULL; newNode->next = head; if (head != NULL) { head->prev = newNode; } head = newNode; } ```

在插入函数insert中，我们首先动态分配一个新节点newNode，并将数据赋值给它。然后将newNode的prev指针指向NULL，next指针指向当前头节点head。如果链表不为空，将当前头节点的prev指针指向newNode，最后将newNode设为新的头节点。

遍历双向链表

```c void display() { Node* current = head; if (current == NULL) { printf("List is empty.\n"); return; } printf("Nodes in the list: "); while (current != NULL) { printf("%d ", current->data); current = current->next; } printf("\n"); } ```

在遍历函数display中，我们从头节点开始遍历链表，依次输出每个节点的数据。如果链表为空，则输出提示信息。

删除双向链表节点

```c void delete(int data) { Node* current = head; while (current != NULL) { if (current->data == data) { if (current->prev != NULL) { current->prev->next = current->next; } else { head = current->next; } if (current->next != NULL) { current->next->prev = current->prev; } free(current); return; } current = current->next; } printf("Node with data %d not found.\n", data); } ```

在删除函数delete中，我们首先遍历链表找到要删除的节点，然后将该节点的前一个节点的next指针指向该节点的下一个节点，将该节点的下一个节点的prev指针指向该节点的前一个节点。最后释放该节点的内存。