探索数据结构：便捷的双向链表-阿里云开发者社区

前言

前面我们学习了单链表，它解决了顺序表中插入删除需要挪动大量数据的缺点，使单链表解决顺序表缺陷时，我们发现作为另一种形态出现的单链表似乎也有明显的缺陷。

在部分功能实现时因为头结点的改变需要引进二级指针（或者采用返回等更为复杂的方法）导致代码更加复杂。

寻找某个节点的前一个节点，对于单链表而言只能遍历，这样就可能造成大量时间的浪费。

尾部以及指定位置插入、删除数据的时间复杂度为O(N) ，效率低下。

为了解决这个问题，我们就要学习今天的主角——双向链表。

一、带头双向循环链表的介绍

实际中链表的结构非常多样，以下情况组合起来就有8种链表结构，虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：无头单向不循环链表，带头双向循环链表。

对比单链表来了解，带头双向循环链表：结构复杂，一般单独存储数据。凭着其复杂的结构我们可以做到快速管理数据，实现对数据的操作。

带头双向循环链表具有以下特点：

1.头节点：带头双向循环链表包含一个头节点，它位于链表的起始位置，并且不存储实际数据。头节点的前指针指向尾节点，头节点的后指针指向第一个实际数据节点。

2.循环连接：尾节点的后指针指向头节点，而头节点的前指针指向尾节点，将链表形成一个循环连接的闭环。这样可以使链表在遍历时可以无限循环，方便实现循环操作。

3.双向连接：每个节点都有一个前指针和一个后指针，使得节点可以向前和向后遍历。前驱指针指向前一个节点，后继指针指向后一个节点。

总结:带头双向循环链表可以支持在链表的任意位置进行插入和删除操作，并且可以实现正向和反向的循环遍历。通过循环连接的特性，链表可以在连续的循环中遍历所有节点，使得链表的操作更加灵活和高效。

二、带头双向循环双链表的实现

2.1 创建链表

双向链表的定义结构体需要包含三个成员，一个成员存储数值，一个成员存储前一个节点的地址，最后一个成员存储下一个节点的地址。

typedef int LTDataType;
typedef struct ListNode
{
  LTDataType val;
  struct ListNode* next;
  struct ListNode* prev;
}LTN;

2.2 初始化链表

在初始化双向链表时，我们需要创建一个头节点，也就是我们常说的哨兵位头节点。

这里需要注意一下：创建头结点的时候，因为链表中没有其它的数据，我们在初始化的时候让guard的next和prev都要指向自己，这样才是一个循环链表（如下图所示 ↓↓↓ ）

LTN* LTinit()
{
  LTN* phead = CreateLTNode(-1);
  phead->next = phead;
  phead->prev = phead;
 
  return phead;
}

2.3 创建新结点

跟之前的一样就不过多介绍了

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

2.4 打印链表

这个链表中的结点是没有NULL的，因此在判断循环是否要结束的条件应该是判断tail是否等于phead

void LTprint(LTN* phead)
{
  assert(phead);
 
  printf("哨兵位 <--> ");
  LTN* tail = phead->next;
  while (tail != phead)
  {
    printf("%d <--> ",tail->val);
    tail = tail->next;
  }
  printf("哨兵位\n");
}

2.5 双向链表的查找

和单链表一样，我们也可以对双向链表进行查找。如果找到就返回该节点的地址，否则返回NULL。

LTN* LTFind(LTN* phead, LTDataType x)
{
  assert(phead);
 
  LTN* cur = phead->next;
  while (cur != phead)
  {
    if (cur->val == x)
    {
      return cur;
    }
    else
    {
      cur = cur->next;
    }
  }
  return NULL;
}

2.6 双向链表的插入

2.5.1 尾插

单链表尾插结点需要遍历全链表，当指针走到链表最后一个结点的时候，判断tail->next是否为NULL，若为NULL，则跳出遍历的循环，尾插新结点。然而带头双向循环链表不需要遍历链表，只需要对哨兵位的头节点的prev域解引用，直接找到带头双向循环链表的尾节点，尾插新节点。

头指针的区别:带头双向循环链表不需要判断头指针是否指向NULL，因为哨兵位的头节点也是有它的地址的,添加新节点时只需要直接在尾节点尾插。然而单链表却需要判断头指针是否指向NULL，而且需要用到二级指针，比较棘手。

void LTpushback(LTN* phead, LTDataType x)
{
  assert(phead);
  //带哨兵位头结点，只改变了结构体成员，不需要二级指针
  LTN* tail = phead->prev;
  LTN* newnode = CreateLTNode(x);
 
  tail->next = newnode;
  newnode->prev = tail;
  newnode->next = phead;
  phead->prev = newnode;
}

2.5.2 头插

void LTpushfront(LTN* phead, LTDataType x)
{
  assert(phead);
  LTN* tail = phead->next;
  LTN* newnode = CreateLTNode(x);
 
  tail->prev = newnode;
  newnode->next = tail;
  newnode->prev = phead;
  phead->next = newnode;
}

2.5.3 任意位置插入

void LTInsert(LTN* pos, LTDataType x)
{
  assert(pos);
  LTN* newnode = CreateLTNode(x);
  LTN* tail = pos->prev;
 
  pos->prev = newnode;
  newnode->next = pos;
  newnode->prev = tail;
  tail->next = newnode;
}

和单链表不同，双向链表头尾操作完全可以用任意位置操作替代。

LTInsert实现尾插：

LTInsert(phead, x);

LTInsert实现头插:

LTInsert(phead->next, x);

2.7 双向链表的删除

2.6.1 尾删

当链表只有一个节点（哨兵位不算）时:

若链表为NULL(只剩哨兵位就是链表为NULL)时，再尾删就被assert会出错：

void LTpopback(LTN* phead)
{
  assert(phead);
  assert(phead->next != phead);
 
  LTN* tail = phead->prev;
  LTN* tailprev = tail->prev;
  
  tailprev->next = phead;
  phead->prev = tailprev;
  free(tail);
  tail = NULL;
}

2.6.2 头删

链表不止一个结点时:

链表为一个结点时:

代码示例如下：

void LTpopfront(LTN* phead)
{
  assert(phead);
  assert(phead->next != phead);
 
  LTN* tail = phead->next;
  LTN* tailnext = tail->next;
 
  tailnext->prev = phead;
  phead->next = tailnext;
  free(tail);
  tail = NULL;
}

2.6.3 任意位置删除

void LTErase(LTN* pos)
{
  assert(pos);
  LTN* tailnext = pos->next;
  LTN* tailprev = pos->prev;
 
  tailnext->prev = tailprev;
  tailprev->next = tailnext;
  free(pos);
  pos = NULL;
}

LTErase实现尾删:

LTErase(phead->prev);

LTErase实现头删：

LTErase(phead->next);

2.8 销毁链表

void LTDestroy(LTN* phead)
{
  assert(phead);
 
  LTN* cur = phead->next;
  while (cur != phead)
  {
    LTN* next = cur->next;
    free(cur);
    cur = next;
  }
  free(phead);
}

三、完整代码

3.1 LTN.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
 
typedef int LTDataType;
typedef struct ListNode
{
  LTDataType val;
  struct ListNode* next;
  struct ListNode* prev;
}LTN;
 
LTN* LTinit();//初始化链表
 
void LTprint(LTN* phead);
 
void LTpushback(LTN* phead, LTDataType x);
void LTpushfront(LTN* phead, LTDataType x);
void LTpopback(LTN* phead);
void LTpopfront(LTN* phead);
 
LTN* LTFind(LTN* phead, LTDataType x);
 
void LTInsert(LTN* pos, LTDataType x);
void LTErase(LTN* pos);

3.2 LTN.c

#include"SLTN.h"
 
LTN* CreateLTNode(LTDataType x)
{
  LTN* newnode = (LTN*)malloc(sizeof(LTN));
  if (newnode == NULL)
  {
    perror("malloc fail");
    exit(-1);
  }
  newnode->val = x;
  newnode->next = NULL;
  newnode->prev = NULL;
  return newnode;
}
 
LTN* LTinit()
{
  LTN* phead = CreateLTNode(-1);
  phead->next = phead;
  phead->prev = phead;
 
  return phead;
}
 
void LTprint(LTN* phead)
{
  assert(phead);
 
  printf("哨兵位 <--> ");
  LTN* tail = phead->next;
  while (tail != phead)
  {
    printf("%d <--> ",tail->val);
    tail = tail->next;
  }
  printf("哨兵位\n");
}
 
void LTpushback(LTN* phead, LTDataType x)
{
  assert(phead);
  //带哨兵位头结点，只改变了结构体成员，不需要二级指针
  LTN* tail = phead->prev;
  LTN* newnode = CreateLTNode(x);
 
  tail->next = newnode;
  newnode->prev = tail;
  newnode->next = phead;
  phead->prev = newnode;
 
  //LTInsert(phead->prev, x);
}
 
void LTpushfront(LTN* phead, LTDataType x)
{
  assert(phead);
  LTN* tail = phead->next;
  LTN* newnode = CreateLTNode(x);
 
  tail->prev = newnode;
  newnode->next = tail;
  newnode->prev = phead;
  phead->next = newnode;
 
  //LTInsert(phead->next, x);
}
 
void LTpopback(LTN* phead)
{
  assert(phead);
  assert(phead->next != phead);
 
  LTN* tail = phead->prev;
  LTN* tailprev = tail->prev;
  
  tailprev->next = phead;
  phead->prev = tailprev;
  free(tail);
  tail = NULL;
 
  //LTErase(phead->prev);
}
 
void LTpopfront(LTN* phead)
{
  assert(phead);
  assert(phead->next != phead);
 
  LTN* tail = phead->next;
  LTN* tailnext = tail->next;
 
  tailnext->prev = phead;
  phead->next = tailnext;
  free(tail);
  tail = NULL;
 
  //LTErase(phead->next);
}
 
LTN* LTFind(LTN* phead, LTDataType x)
{
  assert(phead);
 
  LTN* cur = phead->next;
  while (cur != phead)
  {
    if (cur->val == x)
    {
      return cur;
    }
    else
    {
      cur = cur->next;
    }
  }
  return NULL;
}
 
void LTInsert(LTN* pos, LTDataType x)
{
  assert(pos);
  LTN* newnode = CreateLTNode(x);
  LTN* tail = pos->prev;
 
  pos->prev = newnode;
  newnode->next = pos;
  newnode->prev = tail;
  tail->next = newnode;
}
 
void LTErase(LTN* pos)
{
  assert(pos);
  LTN* tailnext = pos->next;
  LTN* tailprev = pos->prev;
 
  tailnext->prev = tailprev;
  tailprev->next = tailnext;
  free(pos);
  pos = NULL;
}

四、顺序表与链表优缺点分析

链表（双向）优势：

任意位置插入删除都是O(1)

按需申请释放，合理利用空间，不存在浪费

问题：

下标随机访问不方便

顺序表问题：

头部或中间插入删除效率低，要挪动数据O(N)

空间不够要扩容，扩容有一定消耗，且可能存在一定的空间浪费

只适合尾插尾删

优势：

支持下标随机访问O(1)，可以进行排序操作。

探索数据结构：便捷的双向链表

前言