数据结构与算法 --- 双向链表

前言

本次实现的双向链表，全名叫双向带头循环链表，使用C语言实现。
总体结构如下：

所以基于上图本次实现的双向链表成员有三：data数据域，prve指向前一个节点的指针域，next指向下一个节点的指针域。

// 重命名方便存储多种类型的数据
typedef int Datetype;// 实现双向链表，全称双向带头循环链表
typedef struct ListNode
{struct ListNode* next;           // 指向下一个节点的指针struct ListNode* prve;           // 指向前一个节点的指针Datetype data;                   // 存储的数据
}LNnode;

节点的结构就是双向链表的结构，这一点和单链表是一样的。

一、初始化和销毁

1.初始化

对于双向链表的初始化，不和单链表一样初始化为空，由于自带一个头节点，所以初始状态就只有一个头节点，并且也要满足双向而且循环的特点。
如下图：

初始状态直接自己指向自己即可。

// 申请节点
LNnode* LNBuynode(Datetype x)
{// 开一个节点大小的空间LNnode* newnode = (LNnode*)malloc(sizeof(LNnode));if (newnode == NULL){// 提示错误perror("malloc!!");// 强制不正常退出exit(1);}newnode->data = x;newnode->next = newnode->prve = newnode;return newnode;
}

在初始化函数中调用上述函数即可。

初始化函数1：

// 初始化(1)
void LNInit(LNnode** pphead)
{// 传过来的pphead不能为空assert(pphead);*pphead = LNBuynode(-1);
}

初始化函数2：

//初始化(2)
LNnode* LNInit()
{LNnode* phead = LNBuynode(-1);return phead;
}

对比上述两种函数，函数一是传递一个头节点过去，进行初始化；而函数二是直接进行初始化操作，本次使用的是函数二进行初始化。

2.销毁

双向链表的销毁就是对所有的节点进行销毁，头节点也不例外。

// 销毁链表
// 销毁链表是所有节点都销毁，头节点也要销毁
void LNdestroy(LNnode* phead)
{assert(phead);// 标记头节点的下一个节点LNnode* pcur = phead->next;// 销毁除头节点的其他节点while (pcur != phead){LNnode* pnext = pcur->next;free(pcur);pcur = pnext;}// 销毁头节点free(phead);phead = NULL;
}

不过销毁顺序有点不同，首先销毁除开头节点的其他节点，因为在这一步需要将头节点视作遍历条件，待节点销毁完毕之后再销毁头节点即可。

二、增删改查

1.尾插

尾插即在链表的最后一个节点之后再插入新节点，插入示意图如下：

// 尾插
void LNpush_back(LNnode* phead, Datetype x)
{assert(phead);// 首先申请节点LNnode* newnode = LNBuynode(x);// 改变各个节点中指针的指向,需要注意指向的顺序// 优先修改对链表没有影响的指针指向// 三个指针：phead，phead->prve(尾节点)，newnode(尾插节点)newnode->next = phead;newnode->prve = phead->prve;phead->prve->next = newnode;phead->prve = newnode;
}

2.头插

头插是在链表的第一个有效节点之前插入数据，并非是在头节点之前插入数据，插入示意图如下：

// 头插
// 头插是插入到第一个有效节点之前，并非头节点之前
void LNpush_front(LNnode* phead, Datetype x)
{assert(phead);// 申请节点LNnode* newnode = LNBuynode(x);// 改变指针指向// 优先更改对链表整体结构没有影响的指针// 三个指针：phead，phead->next(第一个节点)，newnodenewnode->prve = phead;newnode->next = phead->next;phead->next->prve = newnode;phead->next = newnode;
}

3.尾删

删除示意图如下：

// 尾删
void LNpop_back(LNnode* phead)
{// 首先对List判空// 链表非空才可以删除assert(!LNempty(phead));// 标记将要删除的尾节点LNnode* pdelete = phead->prve;// 改变指针指向// phead，pdelete(删除的尾节点)，pdelete->prve(尾节点的前一个节点)pdelete->prve->next = phead;phead->prve = pdelete->prve;// 销毁节点free(pdelete);pdelete = NULL;
}

4.头删

删除示意图如下：

// 头删
void LNpop_front(LNnode* phead)
{// 首先对List判空// 链表非空才可以删除assert(!LNempty(phead));// 标记将要删除的头节点LNnode* pdelete = phead->next;// 改变指针指向// phead，pdelete(删除的第一个节点)，pdelete->next(第二个节点)pdelete->next->prve = phead;phead->next = pdelete->next;// 销毁节点free(pdelete);pdelete = NULL;
}

5.pos位置之后 / 之前插入

本函数需要配合查找函数使用，pos位置之后插入（pos之前插入与之后插入高度相似）示意图如下：

pos位置之后差插入：

// 指定位置之后插入
void LNinsert_back(LNnode* pos, Datetype x)
{assert(pos);// 创建将要插入的新节点LNnode* newnode = LNBuynode(x);// 改变指针指向// pos，newnode，pos->next(pos的下一个节点)newnode->next = pos->next;newnode->prve = pos;pos->next->prve = newnode;pos->next = newnode;
}

pos位置之前插入：

// 指定位置之前插入
void LNinsert_front(LNnode* pos, Datetype x)
{assert(pos);// 创建将要插入的新节点LNnode* newnode = LNBuynode(x);// 改变指针指向// pos，newnode，pos->prve(pos的前一个节点)newnode->next = pos;newnode->prve = pos->prve;pos->prve->next = newnode;pos->prve = newnode;
}

6.删除pos位置节点

删除示意图如下：

// 删除指定位置的数据
void LNerase(LNnode* pos)
{assert(pos);// 改变指针指向// pos->next，pos->prvepos->next->prve = pos->prve;pos->prve->next = pos->next;
}

7.查找指定数据的节点

// 查找指定元素位置
LNnode* LNfind(LNnode* phead,Datetype x)
{assert(phead);// 标记第一个节点，方便后续遍历操作LNnode* pcur = phead->next;// 遍历// 遍历条件：不等于头节点继续遍历，一旦等于头节点则表示一轮遍历完毕while (pcur != phead){// 找到了if (pcur->data == x){// 找到返回其位置return pcur;}pcur = pcur->next;}// 没找到返回NULLreturn NULL;
}

三、其他

1.打印

// 打印
void lNPrint(LNnode* phead)
{// 首先打印数据只需要从第一个节点（不算头节点）开始，所以标记此节点为pcurLNnode* pcur = phead->next;// 其次打印结束条件等于头节点即可，因为链表本身是一个循环结构，需要规定中止条件while (pcur != phead){// 打印每个节点的数据printf("%d -> ", pcur->data);// 当前节点数据打印完之后使pcur指向下一个节点，继续打印，直到遇见pheadpcur = pcur->next;}printf("\n");
}

2.判空

双向链表为空，即只有一个头节点的情况下。

// 判空
// 若链表为空，则返回true，反之false
bool LNempty(LNnode* phead)
{// 双向链表为空即只剩下一个头节点assert(phead);return phead->next == phead;
}

四、总结

对比单链表，双向链表在实现方面要简单得多，只需要改变指针得指向即可，例如尾节点就直接能表示为phead->prve(这里phead代表头节点)，并且也能完成单链表不能完成得操作，即从尾节点遍历到第一个节点的操作，并且大多数函数的时间复杂度都是为O(1)。