目录

关于链表的分类

 双向链表结构体

初始化

尾插

头插

打印

判断是否为空

尾删

头删

查找

指定位置之后的插入

指定位置的删除

销毁

---

关于链表的分类

根据链表的三大特性，单向or双向、带头or不带头、循环or不循环，可将链表分为2*2*2，8种链表，前面我们已经实现了单链表，即：不带头单向非循环链表，它的结构简单，不常用于单独存储数据，而是作为其他数据结构的子结构。

实际运用中，只有单链表（不带头单向非循环链表）和双向链表（带头双向循环链表）运用最多，带头双向循环链表，结构最复杂，常常运用于单独存储数据，使用的链表结构也几乎都是双向带头链表。

附上一张bit课件的图：

---

 双向链表结构体

放一张bi课件的图片很形象：

<code>//重定义一下类型，方便统一修改

typedef int LNDataType;

typedef struct ListNode {

LNDataType data;//数据

struct ListNode* prev;//前一个结点

struct ListNode* next;//后一个结点

}LN;

---

初始化

双向链表的初始化，应创建一个哨兵结点（也称头结点），它存放的数据是无效数据（假定-1），

所以我们先实现一个创建单节点的函数：

//创建新节点

LN* LNBuyNode(LNDataType x) {

LN* node = (LN*)malloc(sizeof(LN));//开辟空间

if (!node) {//判断为空

perror("malloc fail!");

exit(1);

}

node->;data = x;//传入数据

node->next = node->prev = node;

//双向循环链表单节点也应满足循环，不能初始化为NULL;

return node;

}

接着我们就可方便地调用，创建一个哨兵结点：

//初始化

void LNInit(LN** pphead) {

assert(pphead);

*pphead=LNBuynode(-1);

}

---

尾插

//尾插

void LNPushBack(LN* phead, LNDataType x) {

assert(phead);

LN* node = LNBuyNode(x);//创建新结点

node->next = phead;//先对新申请的结点参数进行操作，防止对原链表造成改变

node->prev = phead->prev;

phead->prev->next = node;//更改尾结点的next参数的指向

phead->prev = node;//更改头结点prev结点的指向

}

运行测试一下：

---

头插

注意头插的操作是在哨兵位后插入，双向链表为空的情况也是只剩下哨兵位，因为哨兵位并没有存储有效数据。

<code>//头插

void LNPushFront(LN* phead, LNDataType x) {

assert(phead);

LN* node = LNBuyNode(x);//创建新结点

node->;next = phead->next;//先对新申请的结点参数进行操作，防止对原链表造成改变

node->prev = phead;

phead->next->prev = node;//更改头结点的下一个结点的prev指向

phead->next = node;//更改头结点的next指向

}

运行测试一下：

---

打印

<code>//打印

void LNPrint(LN* phead) {

assert(phead);

LN* pcur = phead->;next;

//因为头结点内存储的是无效数据，所以我们让它指向下一个结点

while (pcur!=phead) {//与头结点相遇说明我们已经遍历完整个链表了

printf("%d->", pcur->data);

pcur = pcur->next;

}

printf("\n");

}

---

判断是否为空

双向链表为空的情况是只有一个哨兵结点而不是NULL

//判断是否为空

bool LNEmpty(LN* phead) {

assert(phead);

return phead->next == phead;

}

---

尾删

//尾删

void LNPopBack(LN* phead) {

assert(phead);

assert(!LNEmpty(phead));//删除操作至少有一个有效数据

//LNEmptys是空返回true,取反保证不为空

LN* del = phead->prev;//保存要删除的结点

phead->prev = del->prev;//对要受影响的结点的参数进行更改

phead->prev->next = phead;

free(del);//释放掉该地址

del = NULL;

}

运行测试一下：

---

头删

<code>//头删

void LNPopFront(LN* phead) {

assert(phead);

assert(!LNEmpty(phead));

LN* del = phead->;next;//保存要删除的结点

phead->next = del->next;//对要受影响的结点的参数进行更改

phead->next->prev = phead;

free(del);//释放掉该地址

del = NULL;

}

运行测试一下：

---

查找

因为后面涉及到任意位置的操作，所以这里要写一个查找方法：

<code>//查找

LN* LNFind(LN* phead, LNDataType x) {

assert(phead);

assert(!LNEmpty(phead));

LN* pcur = phead->;next;

while (pcur!=phead) {

//判断条件为!=phead,遇到哨兵位说明已经遍历完

if (pcur->data == x) {

return pcur;

}

pcur = pcur->next;

}

return NULL;

}

运行测试一下：

---

指定位置之后的插入

<code>//指定位置之后的插入

void LNInsert(LN* pos, LNDataType x) {

assert(pos);

LN* node = LNBuyNode(x);

node->;next = pos->next;//先对要受影响的结点的参数进行更改

node->prev = pos;

pos->next->prev = node;//更改pos结点的后一个结点的prev参数

pos->next = node;//更改pos结点的next参数

}

运行测试一下：

---

指定位置的删除

<code>//任意位置的删除

void LNErase(LN* pos) {

assert(pos);

pos->;next->prev = pos->prev;

pos->prev->next = pos->next;

free(pos);

pos = NULL;

}

运行测试一下：

---

销毁

<code>//销毁

void LNDestory(LN** phead) {

assert(phead && *phead);

LN* pcur = (*phead)->;next;

while (pcur != *phead) {

LN* next = pcur->next;

free(pcur);

pcur = next;

}

free(*phead);

*phead =pcur= NULL;

}