目录

一.链表的分类

二.双向链表的结构

 三.双向链表的实现

1.初始化

2.尾插与头插

3.尾删与头删

4.在指定位置之后插入数据

查找函数

5.删除指定节点

6，销毁链表

 四.完整代码

List.h

List.c

---

一.链表的分类

前面的单链表应该叫不带头单向不循环链表，前面的单链表章节提到的头节点只是为了方便理解，并不是真正的头节点。数据结构--链表-CSDN博客

1. ⽆头单向⾮循环链表：结构简单，⼀般不会单独⽤来存数据。实际中更多是作为其他数据结构的⼦结构，如哈希桶、图的邻接表等等。

2. 带头双向循环链表：结构最复杂，⼀般⽤在单独存储数据。实际中使⽤的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使⽤代码实现以后会发现结构会带来很多优势，实现反⽽简单了

二.双向链表的结构

带头链表⾥的头节点，实际为“哨兵位”，哨兵位节点不存储任何有效元素，只是站在这⾥“放哨的”

“哨兵位”存在的意义：

遍历循环链表避免死循环。

 三.双向链表的实现

test.c//测试文件

List.c//实现双向链表的方法

List.h//双向链表声明

1.初始化

 双向链表由节点组成

• 数据
• 指向下一个节点的指针
• 指向前应该节点的指针

typedef int LTDataType;
//定义双向链表节点的结构
typedef struct ListNode
{LTDataType data;struct ListNode* next;struct ListNode* prev;
}LTNode;

插入数据之前，链表必须初始化到只有一个头结点的情况

//申请节点
LTNode* LTBuyNode(LTDataType x)
{LTNode* node = (LTNode*)malloc(sizeof(LTNode));if (node == NULL){perror("malloc fail!");exit(1);}node->data = x;node->next = node->prev = node;return node;
}

//初始化
LTNode* LTInit()
{//给双向链表创建一个哨兵位LTNode* phead = LTBuyNode(-1);return phead;
}

//打印链表
void LTPrint(LTNode* phead)
{LTNode* pcur = phead->next;while (pcur != phead){printf("%d->", pcur->data);pcur = pcur->next;}printf("\n");
}

2.尾插与头插

//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);//phead phead->prev newnodenewnode->prev = phead->prev;newnode->next = phead;phead->prev->next = newnode;phead->prev = newnode;
}

//头插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);//phead newnode phead->nextnewnode->next = phead->next;newnode->prev = phead;phead->next->prev = newnode;phead->next = newnode;
}

3.尾删与头删

void LTPopBack(LTNode* phead)
{//链表必须有效且链表不能为空（只有一个哨兵位）assert(phead && phead->next != phead);LTNode* del = phead->prev;//phead del->prev deldel->prev->next = phead;phead->prev = del->prev;//删除del节点free(del);del = NULL;
}

//头删
void LTPopFront(LTNode* phead)
{assert(phead && phead->next != phead);LTNode* del = phead->next;//phead del del->nextphead->next = del->next;del->next->prev = phead;//删除del节点free(del);del = NULL;
}

4.在指定位置之后插入数据

• 查找函数

LTNode* LTFind(LTNode* phead, LTDataType x)
{LTNode* pcur = phead->next;while (pcur != phead){if (pcur->data == x){return pcur;}pcur = pcur->next;}//没有找到return NULL;
}

//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = LTBuyNode(x);//pos newnode pos->nextnewnode->next = pos->next;newnode->prev = pos;pos->next->prev = newnode;pos->next = newnode;
}

5.删除指定节点

//删除pos节点
void LTErase(LTNode* pos)
{//pos理论上来说不能为phead，但是没有参数phead，无法增加校验assert(pos);//pos->prev pos pos->nextpos->next->prev = pos->prev;pos->prev->next = pos->next;free(pos);pos = NULL;
}

6，销毁链表

void LTDesTroy(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}//此时pcur指向phead，而phead还没有被销毁free(phead);phead = NULL;
}

 四.完整代码

List.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int LTDataType;
//定义双向链表节点的结构
typedef struct ListNode
{LTDataType data;struct ListNode* next;struct ListNode* prev;
}LTNode;//声明双向链表中提供的方法//初始化
//void LTInit(LTNode** pphead);
LTNode* LTInit();
void LTDesTroy(LTNode* phead);void LTPrint(LTNode* phead);//插入数据之前，链表必须初始化到只有一个头结点的情况
//不改变哨兵位的地址，因此传一级即可
//尾插
void LTPushBack(LTNode* phead, LTDataType x); 
//头插
void LTPushFront(LTNode* phead, LTDataType x); //尾删
void LTPopBack(LTNode* phead);
//头删
void LTPopFront(LTNode* phead);//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x);
//删除pos节点
void LTErase(LTNode* pos);
LTNode* LTFind(LTNode* phead, LTDataType x);

List.c

#include"List.h"void LTPrint(LTNode* phead)
{LTNode* pcur = phead->next;while (pcur != phead){printf("%d->", pcur->data);pcur = pcur->next;}printf("\n");
}//申请节点
LTNode* LTBuyNode(LTDataType x)
{LTNode* node = (LTNode*)malloc(sizeof(LTNode));if (node == NULL){perror("malloc fail!");exit(1);}node->data = x;node->next = node->prev = node;return node;
}
//初始化
//void LTInit(LTNode** pphead)
//{
//	//给双向链表创建一个哨兵位
//	*pphead = LTBuyNode(-1);
//}
LTNode* LTInit()
{LTNode* phead = LTBuyNode(-1);return phead;
}//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);//phead phead->prev newnodenewnode->prev = phead->prev;newnode->next = phead;phead->prev->next = newnode;phead->prev = newnode;
}
//头插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);//phead newnode phead->nextnewnode->next = phead->next;newnode->prev = phead;phead->next->prev = newnode;phead->next = newnode;
}//尾删
void LTPopBack(LTNode* phead)
{//链表必须有效且链表不能为空（只有一个哨兵位）assert(phead && phead->next != phead);LTNode* del = phead->prev;//phead del->prev deldel->prev->next = phead;phead->prev = del->prev;//删除del节点free(del);del = NULL;
}
//头删
void LTPopFront(LTNode* phead)
{assert(phead && phead->next != phead);LTNode* del = phead->next;//phead del del->nextphead->next = del->next;del->next->prev = phead;//删除del节点free(del);del = NULL;
}LTNode* LTFind(LTNode* phead, LTDataType x)
{LTNode* pcur = phead->next;while (pcur != phead){if (pcur->data == x){return pcur;}pcur = pcur->next;}//没有找到return NULL;
}
//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = LTBuyNode(x);//pos newnode pos->nextnewnode->next = pos->next;newnode->prev = pos;pos->next->prev = newnode;pos->next = newnode;
}
//删除pos节点
void LTErase(LTNode* pos)
{//pos理论上来说不能为phead，但是没有参数phead，无法增加校验assert(pos);//pos->prev pos pos->nextpos->next->prev = pos->prev;pos->prev->next = pos->next;free(pos);pos = NULL;
}
void LTDesTroy(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}//此时pcur指向phead，而phead还没有被销毁free(phead);phead = NULL;
}