双向链表的实现-阿里云开发者社区

双向链表的概念

双向链表的全称是带头双向循环链表，它可以在任意位置进行时间复杂度为0(1)的插入删除数据，并且可以按照需求申请释放和开辟空间，但他也有复杂的实现方式，这是它如此好用的代价.

节点的定义

对于双向链表的节点构造和单链表有点小区别，它有结点值，前驱指针，后继指针，来看节点的定义：

//结点定义
LTNode* LTBuyNode(LTDatatype x)
{
  LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
  if (newnode == NULL)
  {
    perror("malloc fail");
    return;
  }
  newnode->data = x;
  newnode->next = newnode->prev = newnode;
  return newnode;
}

初始时结点的前驱和后继指针指向自己，然后返回结点的指针.

双向链表的初始化

由于双向链表带哨兵位，所以初始化要创建一个哨兵位，哨兵位的值是-1，因为他的值不需要修改，所以我们让哨兵位初始化为-1，(当然其他值也可以，因为我们不需要哨兵位的值，这个传什么数都不影响）然后返回哨兵位的结点.

//初始化
LTNode* LTInit()
{
  LTNode* phead = LTBuyNode(-1);
  return phead;
}

头插

代码注释很详尽.

//头插
void LTPushFront(LTNode* phead, LTDatatype x)
{
  assert(phead);
  LTNode* newnode = LTBuyNode(x);
 
  newnode->next = phead->next;//改变插入结点的后继指向
  newnode->prev = phead;//改变插入节点的前驱指向
  phead->next->prev = newnode;//改变原来哨兵位的下一个节点的前驱指向
  phead->next = newnode; //改变头结点的后继指向
 
}

如果我们把倒数后两行的代码换一下位置，会发生什么呢？

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

我们先改变头节点的后继指向，但是我们原来头节点的后继指向就找不到了，这个地方就出现问题了，原来插入一个节点需要改变四个指针的指向，但是我们只改变了三个指针，第四个指针找不到了，所以指针的改变顺序也是要注意的，确保当前指针指向的改变不会影响其他指针.

尾插

尾插的顺序也要注意.

//尾插
void LTPushBack(LTNode* phead, LTDatatype x)
{
  assert(phead);
  LTNode* newnode = LTBuyNode(x);
 
  newnode->next = phead; //改变插入结点的后继指向
  newnode->prev = phead->prev; //改变插入节点的前驱指向
  phead->prev->next = newnode; //改变原来尾节点的后继指向
  phead->prev = newnode; //改变头结点的前驱指向
 
}

头删

头删先找到要删除的头节点，然后通过该头节点找到新的头节点，然后改变新头结点的前驱和后继指针的指向，最后free要删除的头节点，记得free后置为空哟.

//头删
void LTPopFront(LTNode* phead)
{
  assert(phead);
  assert(phead->next != phead);
 
  LTNode* del = phead->next;//找到头节点
  LTNode* next = del->next;//找到头结点的下一个，作为新的头结点
  next->prev = phead;//将新头结点的前驱指向哨兵位
  phead->next = next;//将哨兵位的后继指向新的头结点
 
  free(del);
  del = NULL;//释放掉del后记得值空，当然在这个地方del不置空也不影响
               //但是还养成好习惯
}

尾删

//尾删
void LTPopBack(LTNode* phead)
{
  assert(phead);
  assert(phead->next != phead);
 
  LTNode* del = phead->prev;//找到尾节点
  LTNode* prev = del->prev;//找到尾结点的前一个，作为新的尾结点
  prev->next = phead;//将新尾结点的后继指向哨兵位
  phead->prev = prev;//将哨兵位的前驱指向新的尾结点
 
  free(del);
  del = NULL;
 
}

指定位置插入

//在Pos位置之后插入数据
void LTInsert(LTNode* pos, LTDatatype x)
{
  assert(pos);
  LTNode* newnode = LTBuyNode(x);
 
  newnode->next = pos->next;
  newnode->prev = pos;
  pos->next->prev = newnode;
  pos->next = newnode;
 
}

指定位置删除

改变pos下一个结点的前驱指针，然后改变pos上一个结点的后继指针

//删除pos位置的数据
void LTErase(LTNode* pos)
{
  assert(pos);
  pos->next->prev = pos->prev;
  pos->prev->next = pos->next;
  free(pos);
  pos = NULL;
}

查找

查找链表不能为空呀，记得要断言

//查找
LTNode* LTFind(LTNode* phead, LTDatatype x)
{
  assert(phead);
  assert(phead->next != phead);
  LTNode* pcur = phead->next;
  while (pcur != phead)
  {
    if (pcur->data == x)
      return pcur;
    pcur = pcur->next;
  }
  return NULL;
}

链表打印

//打印
void LTPrint(LTNode* phead)
{
  assert(phead);
  LTNode* pcur = phead->next;
  while (pcur != phead)
  {
    printf("%d ", pcur->data);
    pcur = pcur->next;
  }
  printf("\n");
}

销毁链表

//销毁链表
void LTDestory(LTNode* phead)
{
  assert(phead);
  LTNode* pcur = phead->next;
  while (pcur != phead)
  {
    LTNode* next = pcur->next;
    free(pcur);
    pcur = next;
  }
  //销毁哨兵位
  free(phead);
  phead = NULL;
}

总结

双向链表的增删查改比较复杂，要改变四个指针的指向，注意指针改变的先后顺序，代码注释很清楚了，可以配合画图理解，注意细节，理清思路，废话（有bug不要慌，听首歌慢慢找，最重要的是认真仔细，想清楚自己每写一行代码的意思）

一起加油吧！！！

附完整代码

//List.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int LTDatatype;
typedef struct ListNode
{
  LTDatatype data;
  struct ListNode* next;
  struct ListNode* prev;
}LTNode;
//结点定义
LTNode* LTBuyNode(LTDatatype x);
//初始化
LTNode* LTInit();
//尾插
void LTPushBack(LTNode* phead, LTDatatype x);
//头插
void LTPushFront(LTNode* phead, LTDatatype x);
//尾删
void LTPopBack(LTNode* phead);
//头删
void LTPopFront(LTNode* phead);
//在Pos位置之后插入数据
void LTInsert(LTNode* pos, LTDatatype x);
//删除pos位置的数据
void LTErase(LTNode* pos);
//打印
void LTPrint(LTNode* phead);
//查找
LTNode* LTFind(LTNode* phead, LTDatatype x);
//销毁链表
void LTDestory(LTNode* phead);

//List.c
#include"List.h"
//结点定义
LTNode* LTBuyNode(LTDatatype x)
{
  LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
  if (newnode == NULL)
  {
    perror("malloc fail");
    return;
  }
  newnode->data = x;
  newnode->next = newnode->prev = newnode;
  return newnode;
}
//初始化
LTNode* LTInit()
{
  LTNode* phead = LTBuyNode(-1);
  return phead;
}
 
//尾插需要四步
void LTPushBack(LTNode* phead, LTDatatype x)
{
  assert(phead);
  LTNode* newnode = LTBuyNode(x);
 
  newnode->next = phead; //改变插入结点的后继指向
  newnode->prev = phead->prev; //改变插入节点的前驱指向
  phead->prev->next = newnode; //改变原来尾节点的后继指向
  phead->prev = newnode; //改变头结点的前驱指向
 
}
//头插需要四步
void LTPushFront(LTNode* phead, LTDatatype x)
{
  assert(phead);
  LTNode* newnode = LTBuyNode(x);
 
  newnode->next = phead->next;//改变插入结点的后继指向
  newnode->prev = phead;//改变插入节点的前驱指向
  phead->next->prev = newnode;//改变原来哨兵位的下一个节点的前驱指向
  phead->next = newnode; //改变头结点的后继指向
 
}
//尾删
void LTPopBack(LTNode* phead)
{
  assert(phead);
  assert(phead->next != phead);
 
  LTNode* del = phead->prev;//找到尾节点
  LTNode* prev = del->prev;//找到尾结点的前一个，作为新的尾结点
  prev->next = phead;//将新尾结点的后继指向哨兵位
  phead->prev = prev;//将哨兵位的前驱指向新的尾结点
 
  free(del);
  del = NULL;
 
}
//头删
void LTPopFront(LTNode* phead)
{
  assert(phead);
  assert(phead->next != phead);
 
  LTNode* del = phead->next;//找到头节点
  LTNode* next = del->next;//找到头结点的下一个，作为新的头结点
  next->prev = phead;//将新头结点的前驱指向哨兵位
  phead->next = next;//将哨兵位的后继指向新的头结点
 
  free(del);
  del = NULL;
}
//在Pos位置之后插入数据
void LTInsert(LTNode* pos, LTDatatype x)
{
  assert(pos);
  LTNode* newnode = LTBuyNode(x);
 
  newnode->next = pos->next;
  newnode->prev = pos;
  pos->next->prev = newnode;
  pos->next = newnode;
 
}
//删除pos位置的数据
void LTErase(LTNode* pos)
{
  assert(pos);
  pos->next->prev = pos->prev;
  pos->prev->next = pos->next;
  free(pos);
  pos = NULL;
}
//打印
void LTPrint(LTNode* phead)
{
  assert(phead);
  LTNode* pcur = phead->next;
  while (pcur != phead)
  {
    printf("%d ", pcur->data);
    pcur = pcur->next;
  }
  printf("\n");
}
//查找
LTNode* LTFind(LTNode* phead, LTDatatype x)
{
  assert(phead);
  assert(phead->next != phead);
  LTNode* pcur = phead->next;
  while (pcur != phead)
  {
    if (pcur->data == x)
      return pcur;
    pcur = pcur->next;
  }
  return NULL;
}
//销毁链表
void LTDestory(LTNode* phead)
{
  assert(phead);
  LTNode* pcur = phead->next;
  while (pcur != phead)
  {
    LTNode* next = pcur->next;
    free(pcur);
    pcur = next;
  }
  //销毁哨兵位
  free(phead);
  phead = NULL;
}

//Test.c
#include"List.h"
int main()
{
  LTNode* p1= LTInit();
  //LTInit(&p1);
  LTPushBack(p1, 1);
  LTPushBack(p1, 2);
  LTPushBack(p1, 3);
  LTPushBack(p1, 4);
  LTPushBack(p1, 5);
  LTPushFront(p1, 100);
  LTPushFront(p1, 200);
  LTPushFront(p1, 300);
  LTPushFront(p1, 400);
  LTPushFront(p1, 500);
  LTNode* plist = LTFind(p1, 300);
  LTInsert(plist,600);
  LTErase(plist);
  /*LTPopBack(p1);
  LTPopBack(p1);
  LTPopBack(p1);
  LTPopFront(p1);
  LTPopFront(p1);
  LTPopFront(p1);*/
 
  LTPrint(p1);
  LTDestory(p1);
  return 0;
}

双向链表的实现