数据结构——双向链表

一、链表的分类

(1)单向或双向编辑

（2）带头或不带头编辑

（3）循环或不循环编辑

（4）补充

二、实现双向链表

（1）List.h

(2)List.c

(3)注意

三、顺序表和链表的比较

四、写在最后

一、链表的分类

链表的结构多种多样，包括：带头或不带头、单向或双向、循环或不循环，组合起来有8种情况（2x2x2）:

(1)单向或双向

（2）带头或不带头

（3）循环或不循环

（4）补充

①虽然链表有多种结构，但是最常用的是单链表（不带头单向不循环链表）、双向链表（带头双向循环链表）；

②带头指的是头结点，这里的头结点和我们之前说的是两个概念，实际上在前面的称呼并不严谨。头结点实际为“哨兵位”，哨兵位不存储有效数据，作用为“放哨的”；

③双向链表的结构

二、实现双向链表

（1）List.h

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>//定义双向链表的结点的结构
typedef int LTDatatype;
typedef struct ListNode
{LTDatatype data;struct ListNode* next;struct ListNode* prev;
}LTNode;//初始化
void LTInit1(LTNode** pphead);
LTNode* LTInit2();//打印
void LTPrint(LTNode* phead);//插入
void LTPushFront(LTNode* phead, LTDatatype x);
void LTPushBack(LTNode* phead, LTDatatype x);//判断链表是否为空
bool LTEmpty(LTNode* phead);//删除
void LTPopFront(LTNode* phead);
void LTPopBack(LTNode* phead);//查找数据位置
LTNode* LTFind(LTNode* phead, LTDatatype x);//在指定位置之后插入数据
void LTInit(LTNode* pos, LTDatatype x);//删除指定位置的数据
void LTErase(LTNode* pos);//销毁
void LTDestroy(LTNode** pphead);
void LTDestroy2(LTNode* phead);//需要手动将plist置为空

(2)List.c

#include "List.h"LTNode* LTBuyNode(LTDatatype x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));//如果申请不成功if (newnode == NULL){perror("malloc fail!\n");exit(1);//退出}newnode->data = x;newnode->next = newnode->prev = newnode;//由于双向链表是循环的，所以指向自身而非NULLreturn newnode;//注意返回新结点
}//初始化
void LTInit1(LTNode** pphead)
{//创建哨兵位*pphead = LTBuyNode(-1);
}LTNode* LTInit2()
{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");
}//插入
void LTPushFront(LTNode* phead, LTDatatype x)
{assert(phead);LTNode* newnode = LTBuyNode(x);newnode->next = phead->next;newnode->prev = phead;phead->next->prev = newnode;phead->next = newnode;
}void LTPushBack(LTNode* phead, LTDatatype x)
{assert(phead);LTNode* newnode = LTBuyNode(x);newnode->next = phead;newnode->prev = phead->prev;phead->prev->next = newnode;phead->prev = newnode;
}//判断链表是否为空
bool LTEmpty(LTNode* phead)
{assert(phead);return phead->next == phead;
}//删除
void LTPopFront(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));//判断链表不为空LTNode* del = phead->next;phead->next = del->next;del->next->prev = phead;free(del);del = NULL;
}
void LTPopBack(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));//判断链表不为空LTNode* del = phead->prev;del->prev->next = phead;phead->prev = del->prev;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;
}//在指定位置之后插入数据
void LTInit(LTNode* pos, LTDatatype x)
{assert(pos);LTNode* newnode = LTBuyNode(x);newnode->next = pos->next;newnode->prev = pos;pos->next->prev = newnode;pos->next = newnode;
}//删除指定位置的数据
void LTErase(LTNode* pos)
{assert(pos);pos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);pos = NULL;
}//销毁
void LTDestroy(LTNode** pphead)
{assert(pphead && *pphead);LTNode* pcur = (*pphead)->next;while (pcur != *pphead){LTNode* Next = pcur->next;free(pcur);pcur = Next;}free(*pphead);*pphead = NULL;pcur = NULL;//记得将pcur置为空，否则如果后续使用，它为野指针
}void LTDestroy2(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){LTNode* Next = pcur->next;free(pcur);pcur = Next;}free(phead);phead = NULL;pcur = NULL;
}

(3)注意

1.双向链表是循环的，在创建新结点时，新结点的next、prev指针要指向自身。因为如果链表为空，此时链表只有头节点，要想构成循环，其next、prev指针必须指向自身；

2.除初始化和销毁的函数传入的是二级指针外，其他函数的形参均为一级指针，为了保持接口的一致性，给它们传入一级指针作为优化。但美中不足的是，对于链表的销毁，还需在调用函数后将实参置为空；

3.插入时需要创建新结点，删除时需要判断链表是否为空。

三、顺序表和链表的比较

不同点	顺序表	链表（单链表）
存储空间上	物理上一定连续	逻辑上连续，但物理上不一定连续
随机访问	支持，复杂度为O（1）	不支持，复杂度为O（N）
任意位置插入或删除元素	可能需要搬运元素，效率低，复杂度为O（N）	只需要修改指针的指向
插入时的空间	动态顺序表，空间不够时需要扩容，还可能造成空间浪费	没有容量的概念，按需申请和释放，不存在空间浪费的情况
应用场景	高效存储元素+频繁访问	任意位置高效插入和删除