如果想要提高单向链表或者单项循环链表的访问速度，则可以在链表中的节点中再添加一个指针域，让新添加的指针域指向当前节点的直接前驱的地址，也就意味着一个节点中有两个指针域（prev+next），也被称为双向链表（Double Linked List）
double_linked_list.h
/**
* @file : doublellist.h
* @brief : 实现双链表的创建、添加、删除、遍历
* @author : TingFengLuo@126.com
* @date : 2025-12-16
* @version 1.0 : v1.0
* @note :双向链表节点有两个指针域(前指针和后指针)，
前指针指向前一个节点的地址，后指针指向后一个节点的地址还有，一个数据域，用于存放数据，双向链表包含一个头指针指向首节点，便于管理链表
*/
#ifndef __DOUBLELLIST_H
#define __DOUBLELLIST_H
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
//将int类型改名为Datatype_t，便于后续用户修改
typedef int Datatype_t;
//定义双向链表类型
typedef struct doublelinkedlist{
Datatype_t data;
struct doublelinkedlist *prev;
struct doublelinkedlist *next;
}doublellist_t;
//双链表的创建
doublellist_t * DoubleLList_create(void);
//双链表创建新节点
doublellist_t * Doublellist_NewNode(Datatype_t data);
//双链表的头部插入
bool Doublellist_HeadAdd(doublellist_t *head,Datatype_t data);
//双链表的目标值后面插入
bool Doulellist_DestAdd(doublellist_t *head,Datatype_t dest,Datatype_t data);
//双链表的尾部插入
bool Doublellist_TailAdd(doublellist_t *head,Datatype_t data);
//双向链表头部删除
bool Doublellist_HeadDel(doublellist_t *head);
//双向链表目标值删除
bool Doublellist_DestDel(doublellist_t *head,Datatype_t dest);
//双向链表尾部删除
bool Doublellist_TailDel(doublellist_t *head);
//遍历双向循环链表
void Doublellist_show(doublellist_t *head);
#endif
double_linked_list.c
#include "doublellist.h"
/**
* @name : DoubleLList_create
* @brief : 实现双向链表的创建
* @param : void
* @retval : 链表创建成功返回双链表的地址，创建失败，直接退出程序
* @date : 2025-12-16
* @version 1.0 : v1.0
* @note : 双链表的创建有一个头头节点，头节点的前指针和后指针都指向空，头指针没有数据域
*/
doublellist_t * DoubleLList_create(void)
{
//定义一个头指针，并对头指针创建存储空间
doublellist_t *head = (doublellist_t *)calloc(1,sizeof(doublellist_t));
//判断头节点是否创建成功，如果失败直接退出程序
if(NULL == head){
perror("create memory falied for head");
exit(-1);
}
//初始化头节点的指针域
head->prev = NULL;
head->next = NULL;
//返回头节点的地址
return head;
}
/**
* @name : Doublellist_NewNode
* @brief : 实现双向链表节点的创建
* @param
@data : 要传输的数据
* @retval : 返回新节点的地址
* @date : 2025-12-16
* @version 1.0 : v1.0
* @note : NULL
*/
doublellist_t * Doublellist_NewNode(Datatype_t data)
{
//创建一个新节点
doublellist_t *new_node = (doublellist_t *)calloc(1,sizeof(doublellist_t));
//如果新节点创建失败，返回NULL
if(NULL == new_node){
perror("create memory failed for new_node");
return NULL;
}
new_node->data = data;
//将新节点的前后指针域指向NULL
new_node->prev = NULL;
new_node->next = NULL;
return new_node;
}
/**
* @name : Doublellist_HeadAdd
* @brief : 实现双向链表头节点的插入
* @param
@head :表示哪一个链表
@data : 要传输的数据
* @retval : 插入成功返回true,插入失败返回false
* @date : 2025-12-16
* @version 1.0 : v1.0
* @note : NULL
*/
bool Doublellist_HeadAdd(doublellist_t *head,Datatype_t data)
{
//用于一个指针存储新节点的地址
doublellist_t *new_node = Doublellist_NewNode(data);
//判断新节点是否创建成功，如果new_node的地址为空，说明新节点创建失败，返回false
if(NULL == new_node){
printf("create new node falied\n");
return false;
}
//判断头节点的下一个地址是否为空,如果为空，直接在双向链表后插入
if(NULL == head->next){
new_node->prev = head;
head->next = new_node;
return true;
}
//如果链表不为空,新节点的next指针指向头节点的下一个地址
new_node->next = head->next;
//新节点的prev指针指向头节点
new_node->prev = head;
//之前的首节点的prev指针指向新节点
head->next->prev = new_node;
//头节点的next指针指向新节点
head->next = new_node;
return true;
}
/**
* @name : Doulellist_DestAdd
* @brief : 实现双向链表目标值后面插入新节点
* @param
@head :表示哪一个链表
@dest :需要找到的目标值
@data : 要传输的数据
* @retval : 插入成功返回true,插入失败返回false
* @date : 2025-12-16
* @version 1.0 : v1.0
* @note : NULL
*/
bool Doulellist_DestAdd(doublellist_t *head,Datatype_t dest,Datatype_t data)
{
//定义变量存储新节点的地址
doublellist_t *new_node = Doublellist_NewNode(data);
//判断新节点是否创建出来
if(NULL == new_node){
printf("double linked list create new node failed\n");
return false;
}
//判断head是否存在
if(NULL == head){
printf("double linked list is Empty!!!\n");
return false;
}
//判断链表是否为空,如果为空直接在头节点后面插入
if(NULL == head->next){
new_node->prev = head;
head->next = new_node;
return true;
}
//定义变量用于存储插入节点的前一个地址
doublellist_t *phead = head->next;
//遍历节点找到目标值节点,然后将新节点插入
//判断当前节点是否为空
while(phead != NULL){
//如果当前节点的值与dest相同，在后面插入
if(phead->data == dest)
{
new_node->next = phead->next;
new_node->prev = phead;
//判断当前节点的Next指针是否为空
if(phead->next != NULL){
phead->next->prev = new_node;
}
phead->next = new_node;
//插入成功返回true
return true;
}
//当前指针指向下一个节点
phead = phead->next;
}
//当前节点为空，释放新节点，返回false
printf("double linked list do not dest value = %d\n",dest);
free(new_node);
return false;
}
/**
* @name : Doublellist_TailAdd
* @brief : 实现双向链表尾节点的插入
* @param
@head : 表示哪一个链表
@data : 要传输的数据
* @retval : 尾部插入成功返回true,失败返回false
* @date : 2025-12-16
* @version 1.0 : v1.0
* @note : NULL
*/
bool Doublellist_TailAdd(doublellist_t *head,Datatype_t data)
{
//定义变量存储新节点的地址
doublellist_t *new_node = Doublellist_NewNode(data);
if(NULL == new_node){
printf("double linked list create new node failed\n");
return false;
}
//判断链表是否存在
if(NULL == head){
printf("create double linked list failed\n");
return false;
}
//判断链表是否为空,如果为空直接在头部添加
if(NULL == head->next){
new_node->prev = head;
head->next = new_node;
return true;
}
//创建变量用于遍历链表
doublellist_t *tail = head;
//如果不为空，先找到尾节点
while(NULL != tail->next){
tail = tail->next;
}
new_node->prev = tail;
tail->next = new_node;
return true;
}
/**
* @name : Doublellist_HeadDel
* @brief : 实现双向链表头部删除
* @param
@head : 表示哪一个链表
* @retval : 头部删除成功返回true,失败返回false
* @date : 2025-12-16
* @version 1.0 : v1.0
* @note : NULL
*/
bool Doublellist_HeadDel(doublellist_t *head)
{
//判断头节点是否创建成功
if(NULL == head){
printf("create double linked list failed\n");
return false;
}
//判断链表是否为空
if(NULL == head->next){
printf("current linked list is Empty!!!\n");
return false;
}
//创建变量存储首节点的地址
doublellist_t *phead = head->next;
//判断链表是否只有一个首节点，如果只有一个首节点，直接将head的next指向NULL
if(phead->next == NULL){
head->next = NULL;
}else{
//如果不为空，直接删除首节点
head->next = phead->next;
phead->next->prev = head;
}
//将删除的首节点的前后指针置空，防止野指针
phead->prev = NULL;
phead->next = NULL;
//释放phead的内存
free(phead);
//避免野指针
phead = NULL;
return true;
}
/**
* @name : Doublellist_DestDel
* @brief : 实现双向链表目标值删除
* @param
@head : 表示哪一个链表
@dest : 表示要删除的目标值
* @retval : 目标值删除成功返回true,失败返回false
* @date : 2025-12-16
* @version 1.0 : v1.0
* @note : NULL
*/
bool Doublellist_DestDel(doublellist_t *head,Datatype_t dest)
{
//判断头节点是否创建成功
if(NULL == head){
printf("create double linked list failed\n");
return false;
}
//判断链表是否为空
if(NULL == head->next){
printf("current linked list is Empty!!!\n");
return false;
}
//创建变量存储目标节点前一个节点的地址
doublellist_t *prev_destnode = head;
//创建变量存储目标节点的地址
doublellist_t *dest_node = head->next;
//遍历链表，找到第一个与目标值相同的节点
while(NULL != dest_node){
if(dest == dest_node->data){
prev_destnode->next = dest_node->next;
if(dest_node->next != NULL){
dest_node->next->prev = prev_destnode;
}
dest_node->prev = NULL;
dest_node->next = NULL;
free(dest_node);
dest_node = NULL;
return true;
}
prev_destnode = dest_node;
dest_node = dest_node->next;
}
printf("double linked list do not have dest value = %d!!!\n",dest);
return false;
}
/**
* @name : Doublellist_TailDel
* @brief : 实现双向链表尾部删除
* @param
@head : 表示哪一个链表
* @retval : 头部删除成功返回true,失败返回false
* @date : 2025-12-16
* @version 1.0 : v1.0
* @note : NULL
*/
bool Doublellist_TailDel(doublellist_t *head)
{
//判断头节点是否创建成功
if(NULL == head){
printf("create double linked list failed\n");
return false;
}
//判断链表是否为空
if(NULL == head->next){
printf("current linked list is Empty!!!\n");
return false;
}
//创建变量存储尾节点
doublellist_t *phead = head->next;
//创建变量存储删除节点的前一个节点
doublellist_t *prev_phead = head;
//遍历链表，找到尾节点和尾节点的前一个节点
while(phead->next != NULL){
prev_phead = phead;
phead = phead->next;
}
//置空指针，防止野指针
prev_phead->next = NULL;
phead->prev = NULL;
free(phead);
//防止野指针
phead = NULL;
return true;
}
/**
* @name : Doublellist_show
* @brief : 实现双向链表的遍历
* @param
@head : 表示是哪个链表
* @retval : void
* @date : 2025-12-16
* @version 1.0 : v1.0
* @note : NULL
*/
void Doublellist_show(doublellist_t *head)
{
if(NULL == head){
printf("double linked list do not have head\n");
return;
}
if(head->next == NULL){
printf("double linked list is empty!!!\n");
printf("please Add new node in double linked list!!!!\n");
return;
}
//创建变量用来遍历链表
doublellist_t *phead = head;
//遍历每个节点的值，如果phead的next指针为空则退出循环
while(phead->next != NULL){
phead = phead->next;
printf("current node vlaue = %d\n",phead->data);
}
}
main.c
#include "doublellist.h"
int main(int argc,char const *argv[]){
//定义变量用来存储创建双向链表的地址
doublellist_t *head = DoubleLList_create();
if(head == NULL){
printf("create double linked list falied\n");
return -1;
}
Doublellist_show(head);
printf("-------------------------------------------------------------\n");
Doublellist_HeadAdd(head,34);
Doublellist_HeadAdd(head,68);
Doublellist_HeadAdd(head,29);
Doublellist_HeadAdd(head,76);
Doublellist_HeadAdd(head,17);
Doublellist_show(head);
printf("-------------------------------------------------------------\n");
Doulellist_DestAdd(head,34,20);
Doulellist_DestAdd(head,68,46);
Doublellist_show(head);
printf("-------------------------------------------------------------\n");
Doublellist_TailAdd(head,50);
Doublellist_TailAdd(head,51);
Doublellist_TailAdd(head,52);
Doublellist_show(head);
printf("-------------------------------------------------------------\n");
Doublellist_HeadDel(head);
Doublellist_HeadDel(head);
Doublellist_HeadDel(head);
Doublellist_show(head);
printf("-------------------------------------------------------------\n");
Doublellist_DestDel(head,68);
Doublellist_DestDel(head,20);
Doublellist_DestDel(head,52);
Doublellist_DestDel(head,10);
Doublellist_show(head);
printf("-------------------------------------------------------------\n");
Doublellist_TailDel(head);
Doublellist_show(head);
printf("-------------------------------------------------------------\n");
return 0;
}
发表回复