《链表之美：C语言中的灵活数据结构》

大家好，这里是小编的博客频道
小编的博客：就爱学编程

很高兴在CSDN这个大家庭与大家相识，希望能在这里与大家共同进步，共同收获更好的自己！！！

引言
正文
- 一、节点结构
- 二、基本操作
- - 1. 创建链表
  - 2. 插入节点
  - 3. 删除节点
  - 4. 查找节点
  - 5. 修改节点数据
- 三、应用场景
- 四、源码
- - LT.h
  - LT.c
  - Test.c
- 五、总结
快乐的时光总是短暂，咱们下篇博文再见啦！！！不要忘了，给小编点点赞和收藏支持一下，在此非常感谢！！！

引言

在C语言中，数据结构的掌握对于高效编程至关重要。其中，双链表作为一种基础且常用的数据结构，具有独特的优势和应用场景。下面将对双链表进行详细介绍，并概述其实现方法。一起来看看吧！！！
在这里插入图片描述

那接下来就让我们开始遨游在知识的海洋！

正文

一、节点结构

在C语言中，可以使用结构体来定义一个双向链表的节点。每个节点通常包含以下三个部分：

数据域：用于存储节点的数据。
前驱指针（ prev ）：指向当前节点的前一个节点。
后继指针（ next ）：指向当前节点的下一个节点。

下面是一个常见的定义方式：

 
typedef struct Node {int data;          // 数据域struct Node* prev; // 前驱指针struct Node* next; // 后继指针
} Node;

二、基本操作

1. 创建链表

创建带头双向循环链表需要先创建一个头节点，并初始化它的两个指针。初始时，头节点的前驱和后继都指向自己，表示这是一个空链表。

 
Node* createDoublyLinkedList() {Node* head = (Node*)malloc(sizeof(Node)); // 创建头节点head->prev = head;                       // 初始时头节点的前驱指向自己head->next = head;                       // 初始时头节点的后继也指向自己return head;
}

2. 插入节点

在带头双向循环链表中插入节点需要确定新节点的位置，并调整相关节点的指针。根据插入位置的不同，可以分为以下几种情况：

在头部插入：将新节点作为新的头节点，并更新原头节点的前驱指针和新节点的后继指针。
在中间插入：找到要插入位置的前一个节点，然后将新节点插入到该节点之后，同时更新相关节点的指针。
在尾部插入：找到链表的最后一个节点，然后将新节点添加到其后，同时更新最后一个节点的后继指针和新节点的前驱指针。

以下是相应的代码示例：

 
void insertAtBeginning(Node** head_ref, int data) {Node* new_node = (Node*)malloc(sizeof(Node));new_node->data = data;new_node->prev = NULL;new_node->next = *head_ref;if (*head_ref != NULL) {(*head_ref)->prev = new_node;}*head_ref = new_node;
}void insertAfter(Node* prev_node, int data) {if (prev_node == NULL) {printf("The given previous node cannot be NULL
");return;}Node* new_node = (Node*)malloc(sizeof(Node));new_node->data = data;new_node->prev = prev_node;new_node->next = prev_node->next;prev_node->next = new_node;if (new_node->next != NULL) {new_node->next->prev = new_node;}
}void insertAtEnd(Node** head_ref, int data) {Node* new_node = (Node*)malloc(sizeof(Node));Node* last = *head_ref;new_node->data = data;new_node->next = NULL;if (*head_ref == NULL) {new_node->prev = NULL;*head_ref = new_node;return;}while (last->next != NULL) {last = last->next;}last->next = new_node;new_node->prev = last;
}

3. 删除节点

删除双带头双向循环链表中的节点也需要调整相关节点的指针。根据删除节点的位置，可以分为以下几种情况：

删除头节点：更新头指针为下一个节点，并将新头节点的前驱指针设为NULL。
删除中间节点：找到要删除的节点，将其前一个节点的后继指针指向其后的节点，并将其后一个节点的前驱指针指向其前的节点。
删除尾节点：找到倒数第二个节点，将其后继指针设为NULL，并释放尾节点的内存。

以下是相应的代码示例：

 
void delete(Node* head, Node* del) {if (head == del) { // 如果要删除的是头节点head = del->next;head->prev = NULL;free(del);return;}if (del->next == del) { // 如果要删除的是尾节点del->prev->next = NULL;free(del);return;}if (del->prev == del) { // 如果要删除的是孤立节点（没有前驱和后继）free(del);return;}del->prev->next = del->next; // 把del的前一个节点的next指针指向del的后一个节点del->next->prev = del->prev; // 把del的后一个节点的prev指针指向del的前一个节点free(del); // 释放del的内存
}

4. 查找节点

查找指定元素的节点需要从表头开始依次遍历链表中的节点，直到找到目标节点或到达链表末尾为止。

int selectElem(Node* head, int elem) {Node* t = head;int i = 1;while (t) {if (t->data == elem) {return i;}i++;t = t->next;}// 程序执行至此处，表示查找失败return -1;
}

5. 修改节点数据

修改带头双向循环链表中指定节点的数据需要在查找到该节点的基础上直接更改其数据域的值。

 
void amendElem(Node* p, int oldElem, int newElem) {Node* temp = p;int find = 0; // 找到要修改的目标节点标志while (temp) {if (temp->data == oldElem) {find = 1;break;}temp = temp->next;}// 成功找到，则进行更改操作if (find == 1) {temp->data = newElem;return;}// 查找失败，输出提示信息printf("链表中未找到目标元素，更改失败
");
}

三、应用场景

带头双向循环链表由于其灵活的插入和删除特性，在许多场景中都有广泛的应用，包括但不限于：

浏览器历史记录：使用双向链表存储用户的导航历史记录，方便用户前进和后退浏览页面。
缓存机制：在实现LRU（最近最少使用）缓存策略中非常有用，可以快速找到并移除最久未使用的项目。
音乐播放器的播放列表：用来存储播放列表，允许用户轻松地在歌曲之间前后跳转。
数据库管理系统：某些类型的数据库索引，如B树中的叶节点，可能使用链表来连接，以便于快速查找和遍历。
图形用户界面：可以用来管理窗口堆栈，使应用程序可以轻松地在窗口之间切换。
游戏开发：可以用来管理游戏对象，如敌人、子弹等，以便于快速添加和删除对象。

四、源码

LT.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>// 带头+双向+循环链表增删查改实现
typedef int LTDataType;
typedef struct ListNode
{LTDataType _data;struct ListNode* next;struct ListNode* prev;
}ListNode;// 创建返回链表的头结点.
ListNode* ListCreate();//创造节点
ListNode* Buy_ListNode(LTDataType x);// 双向链表销毁
void ListDestory(ListNode* phead);// 双向链表打印
void ListPrint(ListNode* phead);// 双向链表尾插
void ListPushBack(ListNode* phead, LTDataType x);// 双向链表尾删
void ListPopBack(ListNode* phead);// 双向链表头插
void ListPushFront(ListNode* phead, LTDataType x);// 双向链表头删
void ListPopFront(ListNode* phead);// 双向链表查找
ListNode* ListFind(ListNode* phead, LTDataType x);// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);// 双向链表删除pos位置的节点
void ListErase(ListNode* pos);

LT.c

#include"LT.h"// 创建并返回链表的头结点（哨兵位）.
ListNode* ListCreate() {ListNode* phead = (ListNode*)malloc(sizeof(ListNode));if (phead == NULL) {perror("malloc fail");//return NULL;exit(-1);}phead->_data;phead->next = phead;phead->prev = phead;return phead;
}
//创造节点
ListNode* Buy_ListNode(LTDataType x)
{ListNode* cur = (ListNode*)malloc(sizeof(ListNode));if (cur == NULL) {perror("malloc fail");//return NULL;exit(-1);}cur->next = NULL;cur->prev = NULL;cur->_data = x;return cur;
}// 双向链表查找
ListNode* ListFind(ListNode* phead, LTDataType x) {assert(phead);ListNode* cur = phead->next;while (cur != phead) {if (x == cur->_data) {return cur;}cur = cur->next;}return NULL;
}// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x) {assert(pos);ListNode* cur = Buy_ListNode(x);pos->prev->next = cur;cur->prev = pos->prev;pos->prev = cur;cur->next = pos;
}// 双向链表删除pos位置的节点
void ListErase(ListNode* pos) {assert(pos);pos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);pos = NULL;            //无用，但为了保持习惯
}// 双向链表打印
void ListPrint(ListNode* phead) {assert(phead);printf("<=head=>");ListNode* cur = phead->next;while (cur != phead) {printf("<=%d=>", cur->_data);cur = cur->next;}printf("\n");
}// 双向链表销毁
void ListDestory(ListNode* phead) {assert(phead);ListNode* cur = phead->next;while (cur != phead) {ListNode* next = cur->next;free(cur);cur = next;}
}// 双向链表尾插
void ListPushBack(ListNode* phead, LTDataType x) {ListInsert(phead, x);
}// 双向链表尾删
void ListPopBack(ListNode* phead)
{ListErase(phead->prev);
}// 双向链表头插
void ListPushFront(ListNode* phead, LTDataType x) {ListInsert(phead->next, x);
}// 双向链表头删
void ListPopFront(ListNode* phead) {ListErase(phead->next);
}

Test.c

#include"LT.h"
void test1() {ListNode* phead = ListCreate();/*ListNode* n1 = Buy_ListNode(1);ListNode* n2 = Buy_ListNode(2);ListNode* n3 = Buy_ListNode(3);ListNode* n4 = Buy_ListNode(4);ListNode* n5 = Buy_ListNode(5);*/ListInsert(phead, 1);ListInsert(phead, 2);ListInsert(phead, 3);ListInsert(phead, 4);ListInsert(phead, 5);ListPrint(phead);ListNode* pos = ListFind(phead, 2);if (pos != NULL) {ListErase(pos);pos = NULL;}ListPrint(phead);ListPushBack(phead, 2);ListPrint(phead);ListPopBack(phead);ListPrint(phead);ListPushFront(phead, 6);ListPrint(phead);ListPopFront(phead);ListPrint(phead);ListDestory(phead);
}
int main() {test1();return 0;
}

五、总结

双向链表是一种复杂但功能强大的数据结构，它提供了在两个方向上进行操作的灵活性。通过合理地使用双向链表，可以高效地解决许多实际问题。