【链表】双向循环带头链表-增-删-查(C语言)-摩杜云开发者社区

单链表存在的缺陷：

不能从后往前走,

找不到他的前驱,

指定位置删除增加尾删都要找前一个，时间复杂度都是O(n)

针对上面的这些缺陷的解决方案——双向链表。

带头双向循环链表

结构体创建
创建结点
初始化
销毁
打印
尾插
头插
头删
尾删
查找位置
删除pos位置的值
在pos前插入x
返回链表的结点数量
判断链表是否为空
优化
总结
全部代码

实际中要实现的链表的结构非常多样，以下情况组合起来就有8种链表结构：

单向、双向
带头、不带头——带哨兵位的头结点，这个结点不存储有效数据，好处是什么？尾插的判断更方便简单，带头就不需要二级指针了，（带头结点，不需要改变穿过来的指针，也就是意味着不需要传二级指针了。）
循环、非循环

无头单向非循环：结构简单，一般不会单独用来存数据，实际中更多是作为其他数据结构的子结构，如哈希桶，图的邻接表等，另外这种数据结构在笔试面试中出现很多。
带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头循环双向链表，另外，这个结构虽然复杂，但是使用代码代码实现的以后会发现结构带来许多优势，实现反而简单了。

带头双向循环链表

【链表】双向循环带头链表-增-删-查(C语言)

结构体创建

typedef int LSTNodeData;
typedef struct ListNode
{
  LSTNodeData data;
  struct ListNode* next;
  struct ListNode* prev;
}LSTNode;

创建结点

DBLSTNode* DBLSTCreat(DoubleListDataType x)
{
  DBLSTNode* newnode = (DBLSTNode*)malloc(sizeof(DBLSTNode));
  newnode->data = x;
  newnode->next = NULL;
  newnode->prev = NULL;
  return newnode;
}

初始化

有个小哨兵位的头结点，并且是一个循环状态。

DBLSTNode* DBLSTInit()
{
  //用一个返回值可以 替代二级指针
  DBLSTNode* phead = DBLSTCreat(0);
  //循环
  phead->next = phead;
  phead->prev = phead;
  return phead;
}

销毁

void DBLSTDestory(DBLSTNode* phead)
{
  //找到第一个结点
  DBLSTNode* cur = phead->next;
  while (cur !=phead)
  {
    //保存下一个结点
    DBLSTNode* curNext = cur->next;
    free(cur);
    cur = curNext;
  }
  free(phead);
}

画图有利于双向链表的理解。

【链表】双向循环带头链表-增-删-查(C语言)

打印

void DBLSTPrint(DBLSTNode* phead)
{
  //如果链表是空的会发生错误吗?
  //不会。因为phead->next还是自己。
  DBLSTNode* cur = phead->next;//这里我容易忘记指向next
  while (cur != phead)
  {
    printf("%d ", cur->data);
    cur = cur->next;
  }
  printf("\n");
}

尾插

双向带头循环链表，结构虽然复杂了，但是更容易操作了。

这就是结构设计的优势。

void DBLSTPushBack(DBLSTNode* phead, DoubleListDataType x)
{
  //创建新结点
  DBLSTNode* newnode = DBLSTCreat(x);
  //找到尾结点
  DBLSTNode* tail = phead->prev;
  //插入-链接
  tail->next = newnode;
  newnode->prev = tail;
  newnode->next = phead;
  phead->prev = newnode;
}

头插

如果插入的时候链表是空的同样不会有影响。

有first这几个指针先动谁都行，没有first也可以，就是会有顺序要求。

示例：

【链表】双向循环带头链表-增-删-查(C语言)

newnode->next = phead->next;
phead->next->prev = newnode;
phead->next = newnode;
newnode->prev = phead;

void DBLSTPushFront(DBLSTNode* phead,DoubleListDataType x)
{
  //创建新结点
  DBLSTNode* newnode = DBLSTCreat(x);
  //拿到第一个结点
  DBLSTNode* first = phead->next;
  //插入-链接
  phead->next = newnode;
  newnode->prev = phead;
  newnode->next = first;
  first->prev = newnode;
}

头删

void DBLSTPopFront(DBLSTNode* phead)
{
  //保存第一个和第二个结点
  DBLSTNode* first = phead->next;
  DBLSTNode* second = first->next;
  phead->next = second;
  second->prev = phead;
  free(first);
  first = NULL;
}

尾删

void DBLSTPopBack(DBLSTNode* phead)
{
  //找到最后的一个结点
  DBLSTNode* tail = phead->prev;
  //找到最后一个结点的前一个结点
  DBLSTNode* tailPrev = tail->prev;
  tailPrev->next = phead;
  phead->prev = tailPrev;
  free(tail);
  tail = NULL;
}

查找位置

DBLSTNode* DBLSTFind(DBLSTNode* phead,DoubleListDataType x)
{
  //从第一个结点开始往下寻找，找到返回结点
  DBLSTNode* cur = phead->next;
  while (cur != phead)
  {
    if (cur->data == x)
    {
      return cur;
    }
    cur = cur->next;
  }
  return NULL;
}

使用：

DBLSTNode* pos = DBLSTFind(phead,x);
if(pos)
{
  printf("找到了");
}
else
{
  printf("没找到");
}

删除pos位置的值

void DBLSTErase(DBLSTNode* pos)
{
  //找到pos的前一个
  DBLSTNode* posPrev = pos->prev;
  //找到pos的后一个
  DBLSTNode* posNext = pos->next;
  //链接pos的前一个和pos的后一个
  posPrev->next = posNext;
  posNext->prev = posPrev;
  //释放pos
  free(pos);
  pos = NULL;
}

在pos前插入x

void DBLSTInsert(DBLSTNode* pos, DoubleListDataType x)
{
  //知道pos前的一个结点
  DBLSTNode* posPrev = pos->prev;
  //创建新的结点
  DBLSTNode* newnode = DBLSTCreat(x);
  //将新的结点插入
  newnode->data = x;
  newnode->prev = posPrev;
  posPrev->next = newnode;
  newnode->next = pos;
  pos->prev = newnode;
}

返回链表的结点数量

int DBLSTSize(DBLSTNode* phead)
{
  //其实就是遍历一遍，找一个计数的
  int count = 0;
  DBLSTNode* cur = phead->next;
  while (cur != phead)
  {
    count++;
    cur = cur->next;
  }
  return count;
}

判断链表是否为空

bool DBLSTEmpty(DBLSTNode* phead)
{
  //定义一个cur指向第一个结点，如果第一个结点就是phead,说明链表为空
  DBLSTNode* cur = phead->next;
  if (phead == cur)
  {
    //空
    return true;
  }
  else
  {
    //不为空
    return false;
  }
}

优化

为了更快的实现一个双向循环的带头链表，我们可以直接利用Insert和Erase。

如果Erase的pos位置是第一个结点，那就代表着头删，如图：

【链表】双向循环带头链表-增-删-查(C语言)

所以头删还可以这样写：

void DBLSTPopFront(DBLSTNode* phead)
{
    DBLSTErase(phead->next);
}

尾删同理：

void DBLSTPopBack(DBLSTNode* phead)
{
  DBLSTErase(phead->prev);
}

头插：

void DBLSTPushFront(DBLSTNode* phead,DoubleListDataType x)
{
  DBLSTInsert(phead->next,x);
}

尾插：

其实就是插到头结点phead的前面。

【链表】双向循环带头链表-增-删-查(C语言)

void DBLSTPushBack(DBLSTNode* phead, DoubleListDataType x)
{
  DBLSTInsert(phead, x);
}

总结

带头双向循环链表，任意位置插入和删除数据，时间复杂度都是O(1)。

查找最优的结构不是这个，查找就得遍历，时间复杂度还是O(N)。

查找的最优结构有三种：

平衡搜索树（AVL树和红黑树）
哈希表
B树 & B+树系列 (数据库底层核心引擎)

全部代码

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int DoubleListDataType;
typedef struct DoubleListNode
{
  DoubleListDataType data;
  struct DoubleListNode* next;
  struct DoubleListNode* prev;
}DBLSTNode;
//创建结点
DBLSTNode* DBLSTCreat(DoubleListDataType x)
{
  DBLSTNode* newnode = (DBLSTNode*)malloc(sizeof(DBLSTNode));
  newnode->data = x;
  newnode->next = NULL;
  newnode->prev = NULL;
  return newnode;
}
//初始化
DBLSTNode* DBLSTInit()
{
  //用一个返回值可以 替代二级指针
  DBLSTNode* phead = DBLSTCreat(0);
  //循环
  phead->next = phead;
  phead->prev = phead;
  return phead;
}
//销毁链表
void DBLSTDestory(DBLSTNode* phead)
{
  //找到第一个结点
  DBLSTNode* cur = phead->next;
  while (cur !=phead)
  {
    //保存下一个结点
    DBLSTNode* curNext = cur->next;
    free(cur);
    cur = curNext;
  }
  free(phead);
}
//打印结点
void DBLSTPrint(DBLSTNode* phead)
{
  //如果链表是空的会发生错误吗?
  //不会。因为phead->next还是自己。
  DBLSTNode* cur = phead->next;//这里我容易忘记指向next
  while (cur != phead)
  {
    printf("%d ", cur->data);
    cur = cur->next;
  }
  printf("\n");
}
//尾插
void DBLSTPushBack(DBLSTNode* phead, DoubleListDataType x)
{
  //创建新结点
  DBLSTNode* newnode = DBLSTCreat(x);
  //找到尾结点
  DBLSTNode* tail = phead->prev;
  //插入-链接
  tail->next = newnode;
  newnode->prev = tail;
  newnode->next = phead;
  phead->prev = newnode;
  //或者
  //DBLSTInsert(phead, x);
}
//头插
void DBLSTPushFront(DBLSTNode* phead,DoubleListDataType x)
{
  //创建新结点
  DBLSTNode* newnode = DBLSTCreat(x);
  //拿到第一个结点
  DBLSTNode* first = phead->next;
  //插入-链接
  phead->next = newnode;
  newnode->prev = phead;
  newnode->next = first;
  first->prev = newnode;
  //或者
  //DBLSTInsert(phead->next,x);
}
//头删
void DBLSTPopFront(DBLSTNode* phead)
{
  //保存第一个和第二个结点
  DBLSTNode* first = phead->next;
  DBLSTNode* second = first->next;
  phead->next = second;
  second->prev = phead;
  free(first);
  first = NULL;
  /或者
  //DBLSTErase(phead->next);
}
//尾删
void DBLSTPopBack(DBLSTNode* phead)
{
  //找到最后的一个结点
  DBLSTNode* tail = phead->prev;
  //找到最后一个结点的前一个结点
  DBLSTNode* tailPrev = tail->prev;
  tailPrev->next = phead;
  phead->prev = tailPrev;
  free(tail);
  tail = NULL;
  //或者
  //DBLSTErase(phead->prev);
}
//查找位置
DBLSTNode* DBLSTFind(DBLSTNode* phead,DoubleListDataType x)
{
  //从第一个结点开始往下寻找，找到返回结点
  DBLSTNode* cur = phead->next;
  while (cur != phead)
  {
    if (cur->data == x)
    {
      return cur;
    }
    cur = cur->next;
  }
  return NULL;
}
//删除pos位置的值
void DBLSTErase(DBLSTNode* pos)
{
  //找到pos的前一个
  DBLSTNode* posPrev = pos->prev;
  //找到pos的后一个
  DBLSTNode* posNext = pos->next;
  //链接pos的前一个和pos的后一个
  posPrev->next = posNext;
  posNext->prev = posPrev;
  //释放pos
  free(pos);
  pos = NULL;
}
//在pos前插入x
void DBLSTInsert(DBLSTNode* pos, DoubleListDataType x)
{
  //知道pos前的一个结点
  DBLSTNode* posPrev = pos->prev;
  //创建新的结点
  DBLSTNode* newnode = DBLSTCreat(x);
  //将新的结点插入
  newnode->data = x;
  newnode->prev = posPrev;
  posPrev->next = newnode;
  newnode->next = pos;
  pos->prev = newnode;
}
//返回链表的结点数量
int DBLSTSize(DBLSTNode* phead)
{
  //其实就是遍历一遍，找一个计数的
  int count = 0;
  DBLSTNode* cur = phead->next;
  while (cur != phead)
  {
    count++;
    cur = cur->next;
  }
  return count;
}
//判断链表是否为空
bool DBLSTEmpty(DBLSTNode* phead)
{
  //定义一个cur指向第一个结点，如果第一个结点就是phead,说明链表为空
  DBLSTNode* cur = phead->next;
  if (phead == cur)
  {
    //空
    return true;
  }
  else
  {
    //不为空
    return false;
  }
}
void Test1()
{
  DBLSTNode* phead = DBLSTInit();
  DBLSTPushBack(phead, 1);
  DBLSTPushBack(phead, 2);
  DBLSTPushBack(phead, 3);
  DBLSTPushBack(phead, 4);
  DBLSTPushFront(phead, 0);
  DBLSTPrint(phead);
  //DBLSTNode* pos = DBLSTFind(phead, 3);
  //if (pos)
  //{
  //  DBLSTErase(pos);
  //}
  DBLSTPrint(phead);
  int Count = DBLSTSize(phead);
  printf("%d", Count);
  DBLSTEmpty(phead);
  if (DBLSTEmpty(phead) == 0)
  {
    printf("不为空\n");
  }
}

int main(void)
{
  Test1();
  return 0;
}