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

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

2024-10-16 14

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

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

前言

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

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

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

尾部以及指定位置插入、删除数据的时间复杂度为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)，可以进行排序操作。

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

前言

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

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

2.1 创建链表

2.2 初始化链表

2.3 创建新结点

2.4 打印链表

2.5 双向链表的查找

2.6 双向链表的插入

2.5.1 尾插

2.5.2 头插

2.5.3 任意位置插入

LTInsert实现尾插：

LTInsert实现头插:

2.7 双向链表的删除

2.6.1 尾删

2.6.2 头删

2.6.3 任意位置删除

LTErase实现尾删:

2.8 销毁链表

三、完整代码

3.1 LTN.h

3.2 LTN.c

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

热门文章

最新文章

相关课程

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

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

前言

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

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

2.1 创建链表

2.2 初始化链表

2.3 创建新结点

2.4 打印链表

2.5 双向链表的查找

2.6 双向链表的插入

2.5.1 尾插

2.5.2 头插

2.5.3 任意位置插入

LTInsert实现尾插：

LTInsert实现头插:

2.7 双向链表的删除

2.6.1 尾删

2.6.2 头删

2.6.3 任意位置删除

LTErase实现尾删:

2.8 销毁链表

三、完整代码

3.1 LTN.h

3.2 LTN.c

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

热门文章

最新文章

相关课程

相关电子书