1. 双向链表的结构

注意：这里的“带头”跟前面我们说的“头结点”是两个概念，为了更好的理解直接称为单链表的头结点

带头链表里的头结点，实际为“哨兵位”，哨兵位节点不存储任何有效数字，知识站在这里“放哨”

“哨兵位”存在的意义：
遍历循环链表避免死循环

2. 实现双向链表

预先的准备

typedef int LTDataType;
typedef struct ListNode
{LTDataType data;struct ListNode* prev;struct ListNode* next;
}LTNode;

初始化

注意，双向链表是带有哨兵位的，插入数据之前链表中必须要先初始化一个哨兵位

void LTInit(LTNode** pphead)
{*pphead = (LTNode*)malloc(sizeof(LTNode));if (*pphead == NULL){perror("malloc");exit(1);}(*pphead)->data = -1;(*pphead)->next = (*pphead)->prev = *pphead;
}

当链表中只有哨兵位节点的时候，我们称该链为空链表
即哨兵位是不能删除也不能修改的，即不能对哨兵位进行任何操作

尾插、头插

//不需要改变哨兵位，则不需要传二级指针
//如果需要修稿哨兵位的话，则传二级指针
//尾插
LTNode* LTBuyNode(LTDataType  x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("malloc");exit(1);}newnode->data = x;newnode->next = newnode->prev = 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;
}//头插
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;
}

单链表中涉及到二级指针：单链表中的phead（第一个节点）可能为空
双向链表中不需要二级指针：双向链表中的phead（哨兵位）不可能为空

尾删、头删

//头删、尾删
void LTPopBack(LTNode* phead)
{assert(phead);//链表为空：只有一个哨兵位assert(phead->next != phead);/*phead->prev->prev->next = phead;phead->prev = phead -> prev->prev*/LTNode* del = phead->prev;LTNode* prev = del->prev;prev->next = phead;phead->prev = prev;free(del);del = NULL;
}
//头删
void LTPopFront(LTNode* phead)
{assert(phead);assert(phead->next != phead);LTNode* del = phead->next;LTNode* next = del->next;next->prev = phead;phead->next = next;free(del);del = NULL;
}

查找

LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}

在pos位置之后插⼊数据

/在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)
{assert(pos);pos->next->prev = pos->prev;pos->prev->next = pos->next;free(pos);pos = NULL;
}

3. 顺序表和双向链表的分析

不同点	顺序表	链表（单链表）
存储空间上	物理上一定连续	逻辑上连续，但物理上不一定连续
随机访问	支持O（1）	不支持 O（N）
任意插入或者删除元素	可能需要搬移元素，效率低	只需要修改指针指向
插入	动态顺序表，空间不够时需要扩展	没有容量的概念
应用场景	元素高效存储+频繁访问	任意位置插入和删除频繁