双链表——“数据结构与算法”-阿里云开发者社区

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

这八种结构分别为：单向带头循环链表、单向带头非循环链表、单向不带头循环链表、单向不带头非循环链表、双向带头循环链表、双向带头非循环链表、双向不带头循环链表、双向不带头非循环链表

虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：

单向不带头非循环链表和双向带头循环链表

无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。

下面，我们开始用代码和图来实现一下双向带头循环链表！！！

在后续函数中，有很多函数都需要这样一个功能：创建一个新节点

那么，我们把此功能单独封装成一个函数：

//创建一个新节点
LTNode* BuyLTNode(LTDataType x)
{
  LTNode* newnode = ((LTNode*)malloc(sizeof(LTNode)));
  if (newnode == NULL)
  {
    printf("malloc fail");
    return NULL;
  }
  newnode->data = x;
  newnode->next = NULL;
  newnode->prev = NULL;
  return newnode;
}

双链表的初始化：

//双链表的初始化
LTNode* LTInit()
{
  //哨兵位的头节点
  LTNode* phead = BuyLTNode(-1);
  phead->next = phead;
  phead->prev = phead;
  return phead;
}

尾插：

//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
  assert(phead);
  LTNode* tail = phead->prev;
  //malloc一个新节点
  LTNode* newnode = BuyLTNode(x);
  //让tail的下一个结点指向newnode，链接起来
  tail->next = newnode;
  //newnode的前一个结点指向tail
  newnode->prev = tail;
  //newnode的下一个结点指向头，形成循环
  newnode->next = phead;
  //phead的上一个结点指向newnode
  phead->prev = newnode;
}

头插：

//头插
//插在哨兵位的头节点的后面
void LTPushFront(LTNode* phead, LTDataType x)
{
  assert(phead);
  LTNode* newnode = BuyLTNode(x);
  LTNode* first = phead->next;
  phead->next = newnode;
  newnode->prev = phead;
  newnode->next = first;
  first->prev = newnode;
}

当然，这样的代码可读性是非常高的，可是，有些人就不喜欢定义那么多指针，然后就还有另外一种写法：

//头插
//插在哨兵位的头节点的后面
void LTPushFront(LTNode* phead, LTDataType x)
{
  assert(phead);
  LTNode* newnode = BuyLTNode(x);
  newnode->next = phead->next;
  phead->next->prev = newnode;
  phead->next = newnode;
  newnode->prev = phead;
}

但是这样的代码，可读性就显得不是那么的高，所以尽量不要使用这种写法

不是说你写代码多定义了几个指针就说你写的代码没有那些没有定义什么指针的代码差，关键得看可读性！！！

双链表的打印：

//双链表的打印
void LTPrint(LTNode* phead)
{
  assert(phead);
  printf("guard<--->");
  LTNode* cur = phead->next;
  while (cur != phead)
  {
    printf("%d<--->", cur->data);
    cur = cur->next;
  }
  printf("\n");
}

下面，让我们来验证一下头插和尾插的功能：

void TestDoubleList1()
{
  LTNode* plist = LTInit();
  LTPushBack(plist, 1);
  LTPushBack(plist, 2);
  LTPushBack(plist, 3);
  LTPushBack(plist, 4);
  LTPushBack(plist, 5);
  LTPrint(plist);
  LTPushFront(plist, 6);
  LTPushFront(plist, 7);
  LTPushFront(plist, 8);
  LTPushFront(plist, 9);
  LTPushFront(plist, 10);
  LTPrint(plist);
}
int main()
{
  TestDoubleList1();
  return 0;
}

尾删：

首先要判断此链表是否为空：

bool LTEmpty(LTNode* phead)
{
  assert(phead);
  return phead->next == phead;
}

//尾删
void LTPopBack(LTNode* phead)
{
  assert(phead);
  assert(!LTEmpty(phead));
  LTNode* tail = phead->prev;
  LTNode* tailPrev = tail->prev;
  free(tail);
  tailPrev->next = phead;
  phead->prev = tailPrev;
}

头删：

bool LTEmpty(LTNode* phead)
{
  assert(phead);
  return phead->next == phead;
}
//头删
void LTPopFront(LTNode* phead)
{
  assert(phead);
  assert(!LTEmpty(phead));
  LTNode* first = phead->next;
  LTNode* second = first->next;
  phead->next = second;
  second->prev = phead;
  free(first);
 
}

头删也有另外一种写法，和上面阐述的一样，也是可以不用定义这么多指针，但是代码的可读性差一些

bool LTEmpty(LTNode* phead)
{
  assert(phead);
  return phead->next == phead;
}
//头删
void LTPopFront(LTNode* phead)
{
  assert(phead);
  assert(!LTEmpty(phead));
  LTNode* next = phead->next;
  phead->next = next->next;
  next->next->prev = phead;
  free(next);
}

下面，让我们来验证一下头删和尾删的功能：

void TestDoubleList2()
{
  LTNode* plist = LTInit();
  LTPushBack(plist, 1);
  LTPushBack(plist, 2);
  LTPushBack(plist, 3);
  LTPushBack(plist, 4);
  LTPushBack(plist, 5);
  LTPrint(plist);
  LTPushFront(plist, 6);
  LTPushFront(plist, 7);
  LTPushFront(plist, 8);
  LTPushFront(plist, 9);
  LTPushFront(plist, 10);
  LTPrint(plist);
  LTPopBack(plist);
  LTPopBack(plist);
  LTPrint(plist);
  LTPopFront(plist);
  LTPopFront(plist);
  LTPrint(plist);
}
int main()
{
  TestDoubleList2();
  return 0;
}

在双链表里面查找：

//在双链表里面查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{
  assert(phead);
  LTNode* cur = phead->next;
  while (cur != phead)
  {
    if (cur->data == x)
    {
      return cur;
    }
    cur = cur->next;
  }
}

在pos位置之前插入值：

//在pos位置之前插入
void LTInsert(LTNode* pos, LTDataType x)
{
  assert(pos);
  LTNode* prev = pos->prev;
  LTNode* newnode = BuyLTNode(x);
  prev->next = newnode;
  newnode->prev = prev;
  newnode->next = pos;
  pos->prev = newnode;
}

一般查找和在pos位置之前插入值是搭配使用的！！！

下面，让我们来测试一下此功能：

void TestDoubleList3()
{
  LTNode* plist = LTInit();
  LTPushBack(plist, 1);
  LTPushBack(plist, 2);
  LTPushBack(plist, 3);
  LTPushBack(plist, 4);
  LTPushBack(plist, 5);
  LTPrint(plist);
  LTPushFront(plist, 6);
  LTPushFront(plist, 7);
  LTPushFront(plist, 8);
  LTPushFront(plist, 9);
  LTPushFront(plist, 10);
  LTPrint(plist);
  LTPopBack(plist);
  LTPopBack(plist);
  LTPrint(plist);
  LTPopFront(plist);
  LTPopFront(plist);
  LTPrint(plist);
  LTNode* pos = LTFind(plist, 3);
  if (pos != NULL)
  {
    LTInsert(pos, 30);
  }
  LTPrint(plist);
 
}
int main()
{
  TestDoubleList3();
  return 0;
}

在pos位置之前插入值这个功能，可以很好地解决之前头插和尾插的功能，头插和尾插可以直接复用此代码：

//头插
void LTPushFront(LTNode* phead, LTDataType x)
{
  LTInsert(phead->next, x);
}
//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
  assert(phead);
  LTInsert(phead, x);
}

删除pos位置的值：

//删除pos位置的值
void LTErase(LTNode* pos)
{
  assert(pos);
  LTNode* posPrev = pos->prev;
  LTNode* posNext = pos->next;
  posPrev->next = posNext;
  posNext->prev = posPrev;
  free(pos);
}

验证一下该删除功能：

void TestDoubleList4()
{
  LTNode* plist = LTInit();
  LTPushBack(plist, 1);
  LTPushBack(plist, 2);
  LTPushBack(plist, 3);
  LTPushBack(plist, 4);
  LTPushBack(plist, 5);
  LTPrint(plist);
  LTPushFront(plist, 6);
  LTPushFront(plist, 7);
  LTPushFront(plist, 8);
  LTPushFront(plist, 9);
  LTPushFront(plist, 10);
  LTPrint(plist);
  LTPopBack(plist);
  LTPopBack(plist);
  LTPrint(plist);
  LTPopFront(plist);
  LTPopFront(plist);
  LTPrint(plist);
  LTNode* pos = LTFind(plist, 3);
  if (pos != NULL)
  {
    LTInsert(pos, 30);
  }
  LTPrint(plist);
  pos = LTFind(plist, 1);
  if (pos != NULL)
  {
    LTErase(pos);
  }
  LTPrint(plist);
}
int main()
{
  TestDoubleList4();
  return 0;
}

这个功能也很神奇，删除pos位置的值，之前我们写的头删和尾删一样可以复用此代码的功能

//尾删
void LTPopBack(LTNode* phead)
{
  assert(phead);
  assert(!LTEmpty(phead));
  LTErase(phead->prev);
}
//头删
void LTPopFront(LTNode* phead)
{
  assert(phead);
  assert(!LTEmpty(phead));
  LTErase(phead->next);
}

双链表的销毁：

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

如果不销毁双链表，就会有内存泄漏的问题！！！

源代码如下：

List.h的内容：

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int LTDataType;
typedef struct ListNode
{
  struct ListNode* prev;
  struct ListNode* next;
  LTDataType data;
}LTNode;
//双链表的初始化
LTNode* LTInit();
//双链表的打印
void LTPrint(LTNode* phead);
//尾插
void LTPushBack(LTNode* phead, LTDataType x);
//头插
void LTPushFront(LTNode* phead, LTDataType x);
//尾删
void LTPopBack(LTNode* phead);
//头删
void LTPopFront(LTNode* phead);
//在双链表里面查找
LTNode* LTFind(LTNode* phead, LTDataType x);
//在pos位置之前插入
void LTInsert(LTNode* pos, LTDataType x);
//删除pos位置的值
void LTErase(LTNode* pos);
//双链表的销毁
void LTDestroy(LTNode* phead);

List.c的内容：

#include"List.h"
//创建一个新节点
LTNode* BuyLTNode(LTDataType x)
{
  LTNode* newnode = ((LTNode*)malloc(sizeof(LTNode)));
  if (newnode == NULL)
  {
    printf("malloc fail");
    return NULL;
  }
  newnode->data = x;
  newnode->next = NULL;
  newnode->prev = NULL;
  return newnode;
}
//双链表的初始化
LTNode* LTInit()
{
  //哨兵位的头节点
  LTNode* phead = BuyLTNode(-1);
  phead->next = phead;
  phead->prev = phead;
  return phead;
}
//双链表的打印
void LTPrint(LTNode* phead)
{
  assert(phead);
  printf("guard<--->");
  LTNode* cur = phead->next;
  while (cur != phead)
  {
    printf("%d<--->", cur->data);
    cur = cur->next;
  }
  printf("\n");
}
//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
  assert(phead);
  LTNode* tail = phead->prev;
  //malloc一个新节点
  LTNode* newnode = BuyLTNode(x);
  //让tail的下一个结点指向newnode，链接起来
  tail->next = newnode;
  //newnode的前一个结点指向tail
  newnode->prev = tail;
  //newnode的下一个结点指向头，形成循环
  newnode->next = phead;
  //phead的上一个结点指向newnode
  phead->prev = newnode;
}
//头插
//插在哨兵位的头节点的后面
void LTPushFront(LTNode* phead, LTDataType x)
{
  assert(phead);
  LTNode* newnode = BuyLTNode(x);
  LTNode* first = phead->next;
  phead->next = newnode;
  newnode->prev = phead;
  newnode->next = first;
  first->prev = newnode;
}
头插
插在哨兵位的头节点的后面
//void LTPushFront(LTNode* phead, LTDataType x)
//{
//  assert(phead);
//  LTNode* newnode = BuyLTNode(x);
//  newnode->next = phead->next;
//  phead->next->prev = newnode;
//  phead->next = newnode;
//  newnode->prev = phead;
//}
头插
//void LTPushFront(LTNode* phead, LTDataType x)
//{
//  LTInsert(phead->next, x);
//}
尾插
//void LTPushBack(LTNode* phead, LTDataType x)
//{
//  assert(phead);
//  LTInsert(phead, x);
//}
bool LTEmpty(LTNode* phead)
{
  assert(phead);
  return phead->next == phead;
}
//尾删
void LTPopBack(LTNode* phead)
{
  assert(phead);
  assert(!LTEmpty(phead));
  LTNode* tail = phead->prev;
  LTNode* tailPrev = tail->prev;
  free(tail);
  tailPrev->next = phead;
  phead->prev = tailPrev;
}
头删
//void LTPopFront(LTNode* phead)
//{
//  assert(phead);
//  assert(!LTEmpty(phead));
//  LTNode* next = phead->next;
//  phead->next = next->next;
//  next->next->prev = phead;
//  free(next);
//}
//头删
void LTPopFront(LTNode* phead)
{
  assert(phead);
  assert(!LTEmpty(phead));
  LTNode* first = phead->next;
  LTNode* second = first->next;
  phead->next = second;
  second->prev = phead;
  free(first);
}
尾删
//void LTPopBack(LTNode* phead)
//{
//  assert(phead);
//  assert(!LTEmpty(phead));
//  LTErase(phead->prev);
//}
头删
//void LTPopFront(LTNode* phead)
//{
//  assert(phead);
//  assert(!LTEmpty(phead));
//  LTErase(phead->next);
//}
//在双链表里面查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{
  assert(phead);
  LTNode* cur = phead->next;
  while (cur != phead)
  {
    if (cur->data == x)
    {
      return cur;
    }
    cur = cur->next;
  }
}
//在pos位置之前插入
void LTInsert(LTNode* pos, LTDataType x)
{
  assert(pos);
  LTNode* prev = pos->prev;
  LTNode* newnode = BuyLTNode(x);
  prev->next = newnode;
  newnode->prev = prev;
  newnode->next = pos;
  pos->prev = newnode;
}
//删除pos位置的值
void LTErase(LTNode* pos)
{
  assert(pos);
  LTNode* posPrev = pos->prev;
  LTNode* posNext = pos->next;
  posPrev->next = posNext;
  posNext->prev = posPrev;
  free(pos);
}
//双链表的销毁
void LTDestroy(LTNode* phead)
{
  assert(phead);
  LTNode* cur = phead->next;
  while (cur != phead)
  {
    LTNode* next = cur->next;
    free(cur);
    cur = next;
  }
  free(phead);
}

好啦，小雅兰今天的学习内容就到这里啦，还要继续加油噢！！！

双链表——“数据结构与算法”

热门文章

最新文章

相关课程

相关电子书

相关实验场景