前言

这篇文章主要讲的就是带头+双向+循环链表增删查改的实现

一、带头双向循环链表的初始化

1.1带头双向循环链表的结构体定义

我们应该知道为什么他叫双向循环链表，因为他有两个指针，一个指向自己的next（也就是下一个），一个是prev（也就是自己的上一个），这样是不是就很方便了呢？对比单链表，单链表的删除就需要定义两个指针来删除，还得从头来删除，而带头双向循环链表就不用那么的麻烦啦。下面是结构体的代码描述

typedef int LTDatatype;
typedef struct ListNode
{
  struct ListNode* next;
  struct ListNode* prev;
  LTDatatype data;
}LNode;

1.2初始化代码的实现

首先带头双向循环链表的初始化首先是有一个next，一个prev,这是什么呢？这是一个头指针，一个尾指针，初始化的话可以都先指向自己，如下图所示这就是初始化代码的由来啦。

LNode* LTInit()
{
  LNode* phead = BuyLTNode(-1);
  phead->next = phead;
  phead->prev = phead;
  return phead;
}

我们会发现这里有一个BuyLTNode函数，这个函数是用来干什么的呢？这个函数是用来开辟一个新的节点的，那么具体是怎么实现的呢？这里我们用到了malloc函数用来动态开辟一个节点。

LNode* BuyLTNode(LTDatatype x)
{
  LNode* newnode = (LNode*)malloc(sizeof(LNode));
  if (newnode == NULL)
  {
    perror("malloc fail");
    return NULL;
  }
  newnode->data = x;
  newnode->next = NULL;
  newnode->prev = NULL;
  return newnode;
}

二、带头+双向+循环链表的增功能实现

2.1头插代码的实现

void LTPustFront(LNode* phead, LTDatatype x)
{
  assert(phead);
  LNode* newnode = BuyLTNode(x);
  LNode* first = phead->next;
  phead->next = newnode;
  newnode->prev = phead;
  newnode->next = first;
  first->prev = newnode;
}

我们要进行带头双向循环链表的头插，那么我们应该怎么样头插呢？很多人会认为是在phead那一个指针进行头插，实则并不然，应该是在phead与p之间才是对的，那么我们应该怎么操作才能把我们newnode的节点头插进去呢？首先我们应该找到first，也就是phead->next,我们为什么要找到这一个节点呢？因为我们要在phead和p之间头插所以first这个节点我们必须得是知道的，而且找到这个节点也是有好处的，有什么好处呢？找到这个节点我们就能知道这个节点的位置，之后的操作也会方便很多。

先将cur定义出来，也就是LNode* cur = phead->next;,其次在链接就行啦，phead->next = newnode,newnode->prev = phead,newnode->next = cur,cur->next = newnode;这里的p指针要根据图来链接哦！

2.2尾插代码的实现

void LTPustBack(LNode* phead, LTDatatype x)
{
  assert(phead);
  LNode* tail = phead->prev;
  LNode* newnode = BuyLTNode(x);
  tail->next = newnode;
  newnode->prev = tail;
  newnode->next = phead;
  phead->prev = newnode;
}

尾插：顾名思义就是在尾部插入，那么双向带头循环链表有啥优势呢？我们可以直接从头就可以找到尾，就不像单链表需要从头开始找了。如下图所示

这是未插入之前：

这是插入之后：

该图把尾指针的next链接到newnode上，再把头指针的链接链到新开的newnode的节点上。这里我们还需要找到未插入之前的尾节点，那么我们应该怎么找到尾节点呢？LNode* tail = phead->prev;这样我们是不是就能找到尾节点了呢？

三、带头+双向+循环链表的打印功能实现

3.1打印代码的实现

void LTPrint(LNode* phead)
{
  assert(phead);
  LNode* cur = phead->next;
  printf("phead<==>");
  while (cur != phead)
  {
    printf("%d<==>", cur->data);
    cur = cur->next;
  }
  printf("\n");
}

因为我们是带有双向循环链表，我们的最后一个节点，会重新指向头结点，我们只需要把遍历的继续条件设为cur!=phead时就行啦。

四、带头+双向+循环链表删功能实现

4.1头删功能的实现

首先，我们应该怎么样进行头删呢？既然遇到解决不了的事情，我们选择画图来进行理解吧

void LTPopFront(LNode* phead)
{
  assert(phead);
  LNode* first = phead->next;
  LNode* second = first->next;
  phead->next = second;
  second->prev = phead;
  free(first);
}

4.2尾删功能的实现

void LTPopBack(LNode* phead)
{
  assert(phead);
  LNode* tail = phead->prev;
  LNode* tailprev = tail->prev;
  free(tail);
  phead->prev = tailprev;
  tailprev->next = phead;
}

五、带头+双向+循环链表查功能实现

5.1查功能代码实现

其实查找功能也就是遍历一遍所有的节点，找到我们想要的值，然后返回就行啦。

LNode* LTFind(LNode* phead, LTDatatype x)
{
  assert(phead);
  LNode* cur = phead->next;
  while (cur != phead)
  {
    if (cur->data == x)
    {
      return cur;
    }
    cur = cur->next;
  }
  return NULL;
}

六、最后的代码全过程实现

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "List.h"
void TestList1()
{
  LNode* plist = LTInit();
  LTPustBack(plist, 1);
  LTPustBack(plist, 2);
  LTPustBack(plist, 3);
  LTPustBack(plist, 4);
  LTPrint(plist);
  LTPopBack(plist);
  LTPrint(plist);
}
void TestList2()
{
  LNode* plist = LTInit();
  LTPustFront(plist, 1);
  LTPustFront(plist, 2);
  LTPustFront(plist, 3);
  LTPustFront(plist, 4);
  LTPrint(plist);
  LTPopFront(plist);
  LTPrint(plist);
  LNode* pos = LTFind(plist, 3);
  //LTInsert(pos, 4);
  LTErase(pos);
  LTPrint(plist);
}
int main()
{
  TestList2();
  return 0;
}

list.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int LTDatatype;
typedef struct ListNode
{
  struct ListNode* next;
  struct ListNode* prev;
  LTDatatype data;
}LNode;
LNode* LTInit();
void LTPustBack(LNode* phead, LTDatatype x);
void LTPustFront(LNode* phead, LTDatatype x);
void LTPopBack(LNode* phead);
void LTPopFront(LNode* phead);
void LTPrint(LNode* phead);
void LTInsert(LNode* pos, LTDatatype x);
LNode* LTFind(LNode* phead, LTDatatype x);
void LTErase(LNode* pos);

list.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "List.h"
LNode* BuyLTNode(LTDatatype x)
{
  LNode* newnode = (LNode*)malloc(sizeof(LNode));
  if (newnode == NULL)
  {
    perror("malloc fail");
    return NULL;
  }
  newnode->data = x;
  newnode->next = NULL;
  newnode->prev = NULL;
  return newnode;
}
LNode* LTInit()
{
  LNode* phead = BuyLTNode(-1);
  phead->next = phead;
  phead->prev = phead;
  return phead;
}
void LTPustBack(LNode* phead, LTDatatype x)
{
  assert(phead);
  LNode* tail = phead->prev;
  LNode* newnode = BuyLTNode(x);
  tail->next = newnode;
  newnode->prev = tail;
  newnode->next = phead;
  phead->prev = newnode;
}
void LTPrint(LNode* phead)
{
  assert(phead);
  LNode* cur = phead->next;
  printf("phead<==>");
  while (cur != phead)
  {
    printf("%d<==>", cur->data);
    cur = cur->next;
  }
  printf("\n");
}
//void LTPustFront(LNode* phead, LTDatatype x)
//{
//  assert(phead);
//  LNode* newnode = BuyLTNode(x);
//  newnode->next = phead->next;
//  phead->next->prev = newnode;
//  phead->next = newnode;
//  newnode->prev = phead;
//
//}
void LTPustFront(LNode* phead, LTDatatype x)
{
  assert(phead);
  LNode* newnode = BuyLTNode(x);
  LNode* first = phead->next;
  phead->next = newnode;
  newnode->prev = phead;
  newnode->next = first;
  first->prev = newnode;
}
void LTPopBack(LNode* phead)
{
  assert(phead);
  LNode* tail = phead->prev;
  LNode* tailprev = tail->prev;
  free(tail);
  phead->prev = tailprev;
  tailprev->next = phead;
}
void LTPopFront(LNode* phead)
{
  assert(phead);
  LNode* first = phead->next;
  LNode* second = first->next;
  phead->next = second;
  second->prev = phead;
  free(first);
}
LNode* LTFind(LNode* phead, LTDatatype x)
{
  assert(phead);
  LNode* cur = phead->next;
  while (cur != phead)
  {
    if (cur->data == x)
    {
      return cur;
    }
    cur = cur->next;
  }
  return NULL;
}
void LTInsert(LNode* pos, LTDatatype x)
{
  assert(pos);
  LNode* prev = pos->prev;
  LNode* newnode = BuyLTNode(x);
  prev->next = newnode;
  newnode->prev = prev;
  newnode->next = pos;
  pos->prev = newnode;
}
void LTErase(LNode* pos)
{
  assert(pos);
  LNode* tail = pos->next;
  LNode* prev = pos->prev;
  prev->next = tail;
  tail->prev = prev;
}

总结

今天带大家了解了数据结构的带头双向循环链表的增删查，其中该数据结构还有随机插入和随机删除我没讲解，大家有不懂的可以评论区留言啦！

初阶数据结构之带头+双向+循环链表增删查实现（三）

前言