手撕双链表 1

🌟前言回顾

       C语言数据结构（单链表）

       上期我们介绍了数据结构中，单链表的结构和实现，链表的每个结点都只能存储一个地址，用来访问下一个结点的数据，这样的话有很多事情就会显得很不方便，很拘束。那有没有更好的链表呢，本期交给大家带来双向链表

1.双向链表的介绍

       双向链表的节点通常包含两个部分：数据部分和指针部分。数据部分用于存储节点所包含的数据，指针部分包含两个指针，一个指向前一个节点，一个指向后一个节点。

     双向链表的优点是可以在常数时间内在任意位置插入或删除节点，因为只需要修改相邻节点的指针即可。而在单向链表中，如果要在某个位置插入或删除节点，则需要遍历链表找到该位置的前一个节点。

       双向链表相对于单向链表也有一些缺点。首先，双向链表需要额外的指针来存储前一个节点的地址，因此占用的内存空间比单向链表更大。其次，双向链表在插入或删除节点时需要修改两个指针的值，而单向链表只需要修改一个指针的值，因此操作起来更复杂。

到这里，想必大家就对双向链表有了个大概的认识，告诉你个小秘密哦：其实双向链表的实现比单链表要简单上不少，只是在数据的结构上双向链表看起来不让人觉得简单，别怕都是纸老虎，往下看一步步手撕它。

2.带头双向循环链表

       有没有感觉光听名字就觉得它不简单，还是那句话：别怕都是纸老虎。当你学会了这些对链表就会有了基本的掌握，不再害怕它。

主体

准备工作

在链表的实现前，我们先把链表所需要用到的先准备好，这样实现的时候会省心很多。

链表头部节点

       在对链表一系列的操作之前，我们首要需要的就是头节点，有了头节点后续数据的插入删除都会变得简单。

List* ListCreate()
{
  List* newnode = (List*)malloc(sizeof(List));
  if (newnode == NULL)
  {
    perror("malloc fail");
    exit(-1);
  }
  newnode->prev = newnode;
  newnode->next = newnode;
  newnode->val = 0;
  return newnode;
}

因为是循环的双向链表，所以头结点初始化的时候，两个指针都是指向自己。

添加新节点

在插入数据中，必不可少的就是节点的创建，然后再链接到表中

List* BuyListNode(ListDatatype x)
{
  List* newnode = (List*)malloc(sizeof(List));
  if (newnode == NULL)
  {
    perror("malloc fail");
    exit(-1);
  }
  newnode->val = x;
  newnode->prev = NULL;
  newnode->next = NULL;
  return newnode;
}

打印

当链表有了数据以后，为了直观的方便我们对数据增删查改的观察，打印就起到了作用

void ListPrint(List* pead)
{
  assert(pead);
  List* cur = pead->next;
  printf("pead:");
  while (cur != pead)
  {
    printf("《=》%d", cur->val);
    cur = cur->next;
  }
  printf("\n");
}