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

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

前言

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


  1. 在部分功能实现时因为头结点的改变需要引进二级指针(或者采用返回等更为复杂的方法)导致代码更加复杂。
  2. 寻找某个节点的前一个节点,对于单链表而言只能遍历,这样就可能造成大量时间的浪费。
  3. 尾部以及指定位置插入、删除数据的时间复杂度为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;
}


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

  • 链表(双向)优势:
  1. 任意位置插入删除都是O(1)
  2. 按需申请释放,合理利用空间,不存在浪费
  • 问题:
  1. 下标随机访问不方便


  • 顺序表问题:
  1. 头部或中间插入删除效率低,要挪动数据O(N)
  2. 空间不够要扩容,扩容有一定消耗,且可能存在一定的空间浪费
  3. 只适合尾插尾删
  • 优势:
  1. 支持下标随机访问O(1),可以进行排序操作。
相关文章
|
22天前
|
存储 算法 Perl
数据结构实验之链表
本实验旨在掌握线性表中元素的前驱、后续概念及链表的建立、插入、删除等算法,并分析时间复杂度,理解链表特点。实验内容包括循环链表应用(约瑟夫回环问题)、删除单链表中重复节点及双向循环链表的设计与实现。通过编程实践,加深对链表数据结构的理解和应用能力。
51 4
|
15天前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
37 5
|
1月前
|
存储 C语言
【数据结构】手把手教你单链表(c语言)(附源码)
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构,每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作,如头插、尾插、头删、尾删、查找、指定位置插入和删除等,并提供了完整的C语言代码示例。通过学习单链表,可以更好地理解数据结构的底层逻辑,提高编程能力。
62 4
|
1月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
1月前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构之单双链表按位、值查找;[前后]插入;删除指定节点;求表长、静态链表等代码及具体思路详解步骤;举例说明、注意点及常见报错问题所对应的解决方法
|
22天前
|
算法
数据结构之购物车系统(链表和栈)
本文介绍了基于链表和栈的购物车系统的设计与实现。该系统通过命令行界面提供商品管理、购物车查看、结算等功能,支持用户便捷地管理购物清单。核心代码定义了商品、购物车商品节点和购物车的数据结构,并实现了添加、删除商品、查看购物车内容及结算等操作。算法分析显示,系统在处理小规模购物车时表现良好,但在大规模购物车操作下可能存在性能瓶颈。
40 0
|
2月前
|
存储 Java
数据结构第三篇【链表的相关知识点一及在线OJ习题】
数据结构第三篇【链表的相关知识点一及在线OJ习题】
26 7
|
2月前
|
存储 安全 Java
【用Java学习数据结构系列】探索顺序表和链表的无尽秘密(附带练习唔)pro
【用Java学习数据结构系列】探索顺序表和链表的无尽秘密(附带练习唔)pro
26 3
|
2月前
|
算法 Java
数据结构与算法学习五:双链表的增、删、改、查
双链表的增、删、改、查操作及其Java实现,并通过实例演示了双向链表的优势和应用。
20 0
数据结构与算法学习五:双链表的增、删、改、查
|
1月前
|
C语言
【数据结构】双向带头循环链表(c语言)(附源码)
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点:双向、带头和循环。与单链表相比,它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1),提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现,包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
43 0