【数据结构】双向带头循环链表的实现-阿里云开发者社区

前言：在前面我们学习了顺序表、单向链表，今天我们在单链表的基础上进一步来模拟实现一个带头双向链表。

双向链表

带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表(如下图所示)。通常我们会使用一个头节点head其并不存储数据只是作为一个哨兵位的作用负责指向下一个元素。

双向链表的基本功能:

双向链表的初始化
双链表的销毁
创建一个新的节点
打印链表中的元素
双向链表尾插
双向链表尾删
双向链表头插
双向链表的头删
双链表元素查找
双向链表在pos的前面进行插入
双向链表删除pos位置的节点

双向链表的定义

//双向链表的定义
typedef int LTDatatype;

typedef struct ListNode
{
  struct ListNode* next;
  struct ListNode* prev;
  LTDatatype val;
}LTNode;

双向链表-创建新的节点

因为我们是动态开辟的链表，因此我们在对链表进行操作的时候，每插入一个节点时都要开辟一个节点，因此我们一样写一个接口函数来实现。

代码思路:我们只需要直接和前面单链表一样开辟思路即可，无非我们需要多管理一个prev指针，这里我们让其置为空即可。

代码实现：

LTNode* ListCreate(LTDatatype x)//创建一个新的节点
{
  LTNode* newnode = malloc(sizeof(LTNode));
  if (newnode == NULL)
  {
    perror("malloc fail");
    return;
  }
  newnode->next = NULL;
  newnode->val = x;
  newnode->prev = NULL;
  return newnode;
}

双向链表-初始化

代码思路：因为双向链表中，我们需要一个哨兵位(头节点)来管理，因此我们在初始化的时候，需要开辟一个节点作为哨兵位，然后将其的pre和next指针置为空即可。

代码实现:

LTNode* ListInit()//双链表的初始化
{
  LTNode* phead = ListCreate(-1);
  phead->next = phead;
  phead->prev = phead;
  return phead;
}

双向链表-打印链表中的元素

代码思路：由于我们是一个循环双向链表，在前面的图可以知道，我们不能够直接通过判断尾指针是否为空指针来判定是否是链表中的尾部元素，但是我们可以知道的是：链表中的最后一个节点的下一个节点，是该链表的头部，所以我们通过判定链表中当前节点的下一个节点是不是头节点，就可以知道是否是链表的尾部了。

代码实现:

void ListPrint(LTNode* pHead)//打印链表中的元素
{
  assert(pHead);
  LTNode* cur = pHead;
  printf("哨兵位-> ");
  while (pHead != cur->next)
  {
    printf("%d->", cur->next->val);
    cur = cur->next;
  }
  printf("\n");

双向链表-尾插

代码思路:由于双向循环链表的特性，我们可以知道哨兵位的pre指向的是尾部节点，因此我们在尾插的时候不用特意的去寻找尾节点，我们只需要，用哨兵位的前驱指针找到尾部节点，让其指向新开辟的空间。因此：

通过哨兵位的前驱指针找到尾部节点
让尾部节点指向新开辟的空间。
让新开辟的空间的前驱指针指向原理的尾部节点，再让其尾指针指向头节点，即可完成双向链表的尾插。(如下图所示)

函数实现：

void ListPushBack(LTNode* pHead, LTDatatype x)//双向链表尾插
{
  assert(pHead);
  LTNode* newnode = ListCreate(x);
  LTNode* cur = pHead->prev;//尾结点
  pHead->prev = newnode;
  newnode->next = pHead;
  newnode->prev = cur;
  cur->next = newnode;
}

函数测试:

void Test_ListPushBack()
{
  LTNode* sl = ListInit();
  ListPushBack(sl, 5);
  ListPushBack(sl, 2);
  ListPushBack(sl, 1);
  ListPushBack(sl, 8);
  ListPrint(sl);
}

运行结果:

双向链表-尾删

代码思路:这里我们依然要重复利用刚刚说到的循环双链表的性质，我们直接通过哨兵位的前驱指针来找到尾结点，来帮助我们进行尾删。

通过哨兵位前驱指针找到尾节点
找到尾结点的前驱指针，即倒数第二个节点，让其指向头节的前驱指针指向倒数第二个节点。
此时在将倒数第二个节点的尾部节点指向头节点，即可完成尾删，此时在释放掉原本的尾部节点即可。(如下图所示)

代码实现:

void ListPopBack(LTNode* pHead)//双向链表尾删
{
  assert(pHead);
  assert(pHead->next);
  LTNode* tail = pHead->prev;//尾部节点
  pHead->prev = tail->prev;//让头节点指向倒数第二个节点
  tail->prev->next = pHead;//尾部节点指向头节点
  free(tail);
  tail = NULL;
}

函数测试:


void Test_ListPopBack()//双向链表尾删
{
  LTNode* sl = ListInit();
  ListPushBack(sl, 5);
  ListPushBack(sl, 2);
  ListPushBack(sl, 1);
  ListPushBack(sl, 8);
  printf("删除前\n");
  ListPrint(sl);
  ListPopBack(sl);
  printf("删除后\n");
  ListPrint(sl);
}

运行结果:

双向链表-头插

代码思路:

我们将哨兵位的next指针指向新开辟的节点。
将新节点的前驱指针指向原本的哨兵位
将新节点的next指向原本的第二个节点
将原本的第二个节点的前驱指针指向新节点，即可完成头插。(如下图)

代码实现:

void ListPushFront(LTNode* pHead, LTDatatype x)//双向链表头插
{
  assert(pHead);
  LTNode* newnode = ListCreate(x);
  LTNode* tail = pHead->next;//记录头节点的下一个节点的位置
  pHead->next = newnode;//让头节点的下一个节点指向新节点
  newnode->prev = pHead;//让新节点的前驱指针指向头节点
  tail->prev = newnode;//让原本的第二个节点的前驱指针指向newnode
  newnode->next = tail;//新节点的尾部节点指针原本的第二个节点
}

函数测试:

void Test_ListPushFront()//双向链表头插
{
  LTNode* sl = ListInit();
  ListPushBack(sl, 5);
  ListPushBack(sl, 2);
  ListPushBack(sl, 1);
  ListPushBack(sl, 8);
  printf("头插前\n");
  ListPrint(sl);
  printf("头插后\n");
  ListPushFront(sl, 10);
  ListPrint(sl);
}

运行结果：

双向链表-头删

代码思路:

我们直接通过哨兵位找到头节点，然后将哨兵位的后驱指针指向头节点的下一个节点。
将头节点的下一个节点的前驱指针指向哨兵位
在将原本的头节点释放掉即可完成头删（如下图）

代码实现:

void ListPopFront(LTNode* pHead)//双向链表的头删
{
  assert(pHead);
  assert(pHead->next);
  LTNode* tail = pHead->next;
  pHead->next = tail->next;//找到第二个节点指向哨兵位后驱指针
  tail->next->prev = pHead;//让次节点指向哨兵位
  free(tail);
  tail = NULL;
}

函数测试:

void Test_ListPopFront()//双向链表的头删
{
  LTNode* sl = ListInit();
  ListPushBack(sl, 5);
  ListPushBack(sl, 2);
  ListPushBack(sl, 1);
  ListPushBack(sl, 8);
  printf("头删前\n");
  ListPrint(sl);
  printf("头删后\n");
  ListPopFront(sl);
  ListPrint(sl);
}

运行结果:

双向链表-元素查找

代码思路:

这里我们依然通过双向链表的性质来帮助我们判断是否走到了链表尾部。
我们定义一个cur指针去帮助我们查找
当cur碰到了尾部的时候说明查找完了，如果此时还没找到就返回空即可
在查找的过程中碰到了要查找的值直接返回此时cur的地址即可。(如下图)

代码实现:

LTNode* ListFind(LTNode* pHead, LTDatatype x)//双链表查找
{
  assert(pHead);
  LTNode* cur = pHead->next;
  while (cur != pHead)
  {
    if (cur->val == x)
    {
      return cur;
    }
    cur = cur->next;
  }
  return NULL;
}

函数测试：


void Test_ListFind()//双向链表的查找
{
  LTNode* sl = ListInit();
  ListPushBack(sl, 5);
  ListPushBack(sl, 2);
  ListPushBack(sl, 1);
  ListPushBack(sl, 8);
  printf("%p\n", ListFind(sl, 2));
  printf("%p\n", ListFind(sl, 999));
}

运行结果:

双向链表-在pos的前面进行插入

代码思路:

我们找到要插入的pos的前一个节点，让其的next指向新开辟的节点
在让此时pos前驱指针所在的位置指向新开辟的节点
再让原本插入的节点的next指向新开辟的节点
再让新开辟的节点的前驱指针和next分别指向原本pos的前一个节点和指向pos。（如下图）

代码实现:

void ListInsert(LTNode* pos, LTDatatype x)// 双向链表在pos的前面进行插入
{
  LTNode* newnode = ListCreate(x);
  LTNode* cur = pos->prev;//找到pos前的一个节点
  pos->prev = newnode;//让其前一个结点指向新结点
  cur->next = newnode;
  newnode->prev = cur;
  newnode->next = pos;
}

函数测试:

void Test_ListInsert()
{
  LTNode* sl = ListInit();
  ListPushBack(sl, 5);
  ListPushBack(sl, 2);
  ListPushBack(sl, 1);
  ListPushBack(sl, 8);
  printf("插入前\n");
  ListPrint(sl);
  ListInsert(ListFind(sl, 2), 99);
  printf("插入后\n");
  ListPrint(sl);
}

运行结果:

双向链表-删除pos所在的位置

代码思路:

我们找到pos所在位置的下个一个节点让其指向pos所在位置的前一个结点
此时在释放掉pos所在的位置即可完成删除

代码实现:

void ListErase(LTNode* pos)// 双向链表删除pos位置的节点
{
  assert(pos);
  LTNode* tail = pos->next;
  tail->prev = pos->prev;
  pos->prev->next = tail;
  free(pos);
  pos = NULL;
}

函数测试:

void Test_ListErase()
{
  LTNode* sl = ListInit();
  ListPushBack(sl, 5);
  ListPushBack(sl, 2);
  ListPushBack(sl, 1);
  ListPushBack(sl, 8);
  printf("删除前\n");
  ListPrint(sl);
  printf("删除后\n");
  ListErase(ListFind(sl, 2));
  ListPrint(sl);
}

运行结果:

双向链表-链表的销毁

关于双向链表的销毁这里就不做过多的总结了，这个和前面的打印元素有比较像，因此不懂的可以参考一下即可。

代码实现:

void ListDestory(LTNode* pHead)//双链表的销毁
{
  assert(pHead);
  LTNode* cur = pHead->next;
  
  while (pHead != cur)
  {
    LTNode* tail = cur->next;
    free(cur);
    cur = tail;
  }
  free(pHead);

}

总结

到这里我们可以发现，当我们写了一个插入之后会发现，那双向链表的头插和尾插，我们可以直接用我们刚刚写的插入的函数直接来实现，就完全没必要单独写尾插和头插了，至于为什么放在最后才说，是因为作者想和大家一起锻炼一下自己的思维能力，这里直接放代码就不演示了。

void ListPushBack(LTNode* pHead, LTDatatype x)//双向链表尾插
{
  assert(pHead);
  ListInsert(pHead,x);//直接再phead之前插入即可
}

void ListPushFront(LTNode* pHead, LTDatatype x)//双向链表头插
{
  assert(pHead);
  ListInsert(pHead->next, x);
}

结语：今天的内容就到这里吧，谢谢各位的观看，如果有讲的不好的地方也请各位多多指出，作者每一条评论都会读的，谢谢各位。

【数据结构】双向带头循环链表的实现

双向链表

双向链表-创建新的节点

双向链表-初始化

双向链表-尾插

双向链表-尾删

双向链表-头插

双向链表-头删

双向链表-元素查找

双向链表-在pos的前面进行插入

双向链表-删除pos所在的位置

双向链表-链表的销毁

总结

热门文章

最新文章

相关课程

相关电子书