数据结构3——双向链表

简介: 数据结构3——双向链表

在上篇文章数据结构2——单链表中,我们了解了什么是链表,以及单链表的实现,接着上篇文章,本篇文章介绍一下比单链表更常用的链表——双向循环链表。

 

1.双向链表的实现

1.1节点

单链表的节点存的有数据域和一个指向下一个节点后继指针,因此单链表只能单向遍历。

要想实现双向遍历,就需要在节点里增加一个指向前一个节点的前驱指针。

typedef int DLTDataType;
typedef struct DListNode
{
  DLTDataType data;
  struct DListNode* prev;//前继指针
  struct DListNode* next;//后继指针
}DLTNode;

1.2 初始化节点

//初始化节点函数实现
DLTNode* DLTInit()
{
  DLTNode* phead = BuyDLTNode(-1);
  phead->next = phead;
  phead->prev = phead;
 
  return phead;
}

1.3 动态开辟新节点

//开辟新节点函数实现
DLTNode* BuyDLTNode(DLTDataType x)
{
  DLTNode* node = (DLTNode*)malloc(sizeof(DLTNode));
  if (node == NULL)
  {
    perror("malloc fail");
    exit(-1);
  }
 
  node->data = x;
  node->next = NULL;
  node->prev = NULL;
 
  return node;
}

1.4 遍历链表

void DLTPrint(DLTNode* phead)
{
  assert(phead);
 
  printf("phead <-> ");
  DLTNode* cur = phead->next;
  while (cur != phead)
  {
    printf("%d <-> ", cur->data);
    cur = cur->next;
  }
  printf("\n");
}

1.5 查找

//查找
DLTNode* DLTFind(DLTNode* phead, DLTDataType x)
{
  assert(phead);
 
  DLTNode* cur = phead->next;
  while (cur != phead)
  {
    if (cur->data == x)
    {
      return cur;
    }
    cur = cur->next;
  }
 
  return NULL;
}

1.6 插入

1.尾插

//尾插函数实现
void DLTPushBack(DLTNode* phead, DLTDataType x)
{
  assert(phead);
  //①常规写法
  DLTNode* tail = phead->prev;
  DLTNode* newnode = BuyDLTNode(x);
 
  newnode->prev = tail;
  tail->next = newnode;
 
  newnode->next = phead;
  phead->prev = newnode;
  //②复用 DLTInsert
  //DLTInsert(phead, x);
}

2. 头插

//头插函数实现
void DLTPushFront(DLTNode* phead, DLTDataType x)
{
  assert(phead);
  //①常规写法
  DLTNode* newnode = BuyDLTNode(x);
 
  newnode->next = phead->next;
  phead->next->prev = newnode;
 
  phead->next = newnode;
  newnode->prev = phead;
  //②复用DLTInsert
  //DLTInsert(phead->next, x);
}

3.在pos之前插入

//在pos之前插入
void DLTInsert(DLTNode* pos, DLTDataType x)
{
  assert(pos);
 
  DLTNode* posPrev = pos->prev;
  DLTNode* newnode = BuyDLTNode(x);
 
  posPrev->next = newnode;
  newnode->prev = posPrev;
  newnode->next = pos;
  pos->prev = newnode; 
}

1.7 删除

1. 尾删

//尾删函数实现
void DLTPopBack(DLTNode* phead)
{
  assert(phead);
  assert(phead->next != phead);//检查链表是否为空
 
  //①常规写法
  DLTNode* tail = phead->prev;
  DLTNode* tailPrev = tail->prev;
  free(tail);
 
  tailPrev->next = phead;
  phead->prev = tailPrev;
  //②复用DLTErase
  //DLTErase(phead->prev);
}

2. 头删

//头删函数实现
void DLTPopFront(DLTNode* phead)
{
  assert(phead);
  assert(phead->next != phead);
 
  //①常规写法
  DLTNode* first = phead->next;
  DLTNode* second = first->next;
 
  free(first);
 
  phead->next = second;
  second->prev = phead;
  //②复用DLTErase
  //DLTErase(phead->next);
}

3.删除pos位置

//删除pos位置
void DLTErase(DLTNode* pos)
{
  assert(pos);
  DLTNode* posPrev = pos->prev;
  DLTNode* posNext = pos->next;
 
  free(pos);
 
  posPrev->next = posNext;
  posNext->prev = posPrev;
}

1.8 其他函数

1. 链表长度

//链表长度
int DLTSize(DLTNode* phead)
{
  assert(phead);
 
  int size = 0;
  DLTNode* cur = phead->next;
  while (cur != phead)
  {
    ++size;
    cur = cur->next;
  }
 
  return size;
}

2. 销毁链表

//销毁函数
void DLTDestory(DLTNode* phead)
{
  assert(phead);
 
  DLTNode* cur = phead->next;
  while (cur != phead)
  {
    DLTNode* next = cur->next;
    free(cur);
 
    cur = next;
  }
 
  free(phead);
 
}

1.9 测试

int main()
{
  DLTNode* plist = DLTInit();
  DLTPushBack(plist, 1);
  DLTPushBack(plist, 2);
  DLTPushBack(plist, 3);
  DLTPushBack(plist, 4);
  DLTPushBack(plist, 5);
  DLTPrint(plist);
  DLTPushFront(plist, 10);
  DLTPushFront(plist, 11);
  DLTPushFront(plist, 12);
  DLTPrint(plist);
  DLTDestory(plist);
  plist = NULL;
  return 0;
}

2.顺序表和链表的比较

不同点 顺序表 链表
存储空间上 物理上一定连续 逻辑上连续,但物理上不一定 连续
随机访问 支持O(1) 不支持O(N)
任意位置插入或者删除元素 可能需要搬移元素,效率低 O(N) 只需修改指针指向
插入 动态顺序表,空间不够时需要 扩容 没有容量的概念
应用场景 元素高效存储+频繁访问 任意位置插入和删除频繁
缓存利用率


*源代码

DLish.h

#pragma once
 
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
 
typedef int DLTDataType;
typedef struct DListNode
{
  DLTDataType data;
  struct DListNode* prev;//前继指针
  struct DListNode* next;//后继指针
}DLTNode;
 
//开辟新节点函数声明
DLTNode* BuyDLTNode(DLTDataType x);
 
//初始化节点函数声明
DLTNode* DLTInit();
 
//遍历函数声明
void DLTPrint(DLTNode* phead);
 
//尾插函数声明
void DLTPushBack(DLTNode* phead, DLTDataType x);
//头插函数声明
void DLTPushFront(DLTNode* phead, DLTDataType x);
 
//尾删函数声明
void DLTPopBack(DLTNode* phead);
//头删函数声明
void DLTPopFront(DLTNode* phead);
 
//链表长度
int DLTSize(DLTNode* phead);
 
//查找
DLTNode* DLTFind(DLTNode* phead, DLTDataType x);
 
//在pos之前插入 
void DLTInsert(DLTNode* pos, DLTDataType x);
//删除pos位置
void DLTErase(DLTNode* pos);
 
//销毁函数
void DLTDestory(DLTNode* phead);

DLish.c

#define _CRT_SECURE_NO_WARNINGS 1
 
#include "DList.h"
 
//开辟新节点函数实现
DLTNode* BuyDLTNode(DLTDataType x)
{
  DLTNode* node = (DLTNode*)malloc(sizeof(DLTNode));
  if (node == NULL)
  {
    perror("malloc fail");
    exit(-1);
  }
 
  node->data = x;
  node->next = NULL;
  node->prev = NULL;
 
  return node;
}
 
//初始化节点函数实现
DLTNode* DLTInit()
{
  DLTNode* phead = BuyDLTNode(-1);
  phead->next = phead;
  phead->prev = phead;
 
  return phead;
}
 
//遍历函数实现
void DLTPrint(DLTNode* phead)
{
  assert(phead);
 
  printf("phead <-> ");
  DLTNode* cur = phead->next;
  while (cur != phead)
  {
    printf("%d <-> ", cur->data);
    cur = cur->next;
  }
  printf("\n");
}
 
 
//尾插函数实现
void DLTPushBack(DLTNode* phead, DLTDataType x)
{
  assert(phead);
  //①常规写法
  DLTNode* tail = phead->prev;
  DLTNode* newnode = BuyDLTNode(x);
 
  newnode->prev = tail;
  tail->next = newnode;
 
  newnode->next = phead;
  phead->prev = newnode;
  //②复用 DLTInsert
  //DLTInsert(phead, x);
}
//头插函数实现
void DLTPushFront(DLTNode* phead, DLTDataType x)
{
  assert(phead);
  //①常规写法
  DLTNode* newnode = BuyDLTNode(x);
 
  newnode->next = phead->next;
  phead->next->prev = newnode;
 
  phead->next = newnode;
  newnode->prev = phead;
  //②复用DLTInsert
  //DLTInsert(phead->next, x);
}
 
 
 
//尾删函数实现
void DLTPopBack(DLTNode* phead)
{
  assert(phead);
  assert(phead->next != phead);//检查链表是否为空
 
  //①常规写法
  DLTNode* tail = phead->prev;
  DLTNode* tailPrev = tail->prev;
  free(tail);
 
  tailPrev->next = phead;
  phead->prev = tailPrev;
  //②复用DLTErase
  //DLTErase(phead->prev);
}
//头删函数实现
void DLTPopFront(DLTNode* phead)
{
  assert(phead);
  assert(phead->next != phead);
 
  //①常规写法
  DLTNode* first = phead->next;
  DLTNode* second = first->next;
 
  free(first);
 
  phead->next = second;
  second->prev = phead;
  //②复用DLTErase
  //DLTErase(phead->next);
}
 
//链表长度
int DLTSize(DLTNode* phead)
{
  assert(phead);
 
  int size = 0;
  DLTNode* cur = phead->next;
  while (cur != phead)
  {
    ++size;
    cur = cur->next;
  }
 
  return size;
}
 
//查找
DLTNode* DLTFind(DLTNode* phead, DLTDataType x)
{
  assert(phead);
 
  DLTNode* cur = phead->next;
  while (cur != phead)
  {
    if (cur->data == x)
    {
      return cur;
    }
    cur = cur->next;
  }
 
  return NULL;
}
 
//在pos之前插入
void DLTInsert(DLTNode* pos, DLTDataType x)
{
  assert(pos);
 
  DLTNode* posPrev = pos->prev;
  DLTNode* newnode = BuyDLTNode(x);
 
  posPrev->next = newnode;
  newnode->prev = posPrev;
  newnode->next = pos;
  pos->prev = newnode; 
}
//删除pos位置
void DLTErase(DLTNode* pos)
{
  assert(pos);
  DLTNode* posPrev = pos->prev;
  DLTNode* posNext = pos->next;
 
  free(pos);
 
  posPrev->next = posNext;
  posNext->prev = posPrev;
}
 
//销毁函数
void DLTDestory(DLTNode* phead)
{
  assert(phead);
 
  DLTNode* cur = phead->next;
  while (cur != phead)
  {
    DLTNode* next = cur->next;
    free(cur);
 
    cur = next;
  }
 
  free(phead);
 
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1
 
#include "DList.h"
 
int main()
{
  DLTNode* plist = DLTInit();
  DLTPushBack(plist, 1);
  DLTPushBack(plist, 2);
  DLTPushBack(plist, 3);
  DLTPushBack(plist, 4);
  DLTPushBack(plist, 5);
  DLTPrint(plist);
  DLTPushFront(plist, 10);
  DLTPushFront(plist, 11);
  DLTPushFront(plist, 12);
  DLTPrint(plist);
  DLTDestory(plist);
  plist = NULL;
  DLTPrint(plist);
  return 0;
}
相关文章
|
11月前
|
存储 算法 Perl
数据结构实验之链表
本实验旨在掌握线性表中元素的前驱、后续概念及链表的建立、插入、删除等算法,并分析时间复杂度,理解链表特点。实验内容包括循环链表应用(约瑟夫回环问题)、删除单链表中重复节点及双向循环链表的设计与实现。通过编程实践,加深对链表数据结构的理解和应用能力。
173 4
|
8月前
|
存储 机器学习/深度学习 算法
C 408—《数据结构》算法题基础篇—链表(下)
408考研——《数据结构》算法题基础篇之链表(下)。
203 30
|
8月前
|
存储 算法 C语言
C 408—《数据结构》算法题基础篇—链表(上)
408考研——《数据结构》算法题基础篇之链表(上)。
316 25
|
9月前
|
机器学习/深度学习 存储 C++
【C++数据结构——线性表】单链表的基本运算(头歌实践教学平台习题)【合集】
本内容介绍了单链表的基本运算任务,涵盖线性表的基本概念、初始化、销毁、判定是否为空表、求长度、输出、求元素值、按元素值查找、插入和删除数据元素等操作。通过C++代码示例详细解释了顺序表和链表的实现方法,并提供了测试说明、通 - **任务描述**:实现单链表的基本运算。 - **相关知识**:包括线性表的概念、初始化、销毁、判断空表、求长度、输出、求元素值、查找、插入和删除等操作。 - **测试说明**:平台会对你编写的代码进行测试,提供测试输入和预期输出。 - **通关代码**:给出了完整的C++代码实现。 - **测试结果**:展示了测试通过后的预期输出结果。 开始你的任务吧,祝你成功!
346 5
|
10月前
|
数据库
数据结构中二叉树,哈希表,顺序表,链表的比较补充
二叉搜索树,哈希表,顺序表,链表的特点的比较
数据结构中二叉树,哈希表,顺序表,链表的比较补充
|
11月前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
288 5
|
11月前
|
存储 C语言
【数据结构】手把手教你单链表(c语言)(附源码)
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构,每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作,如头插、尾插、头删、尾删、查找、指定位置插入和删除等,并提供了完整的C语言代码示例。通过学习单链表,可以更好地理解数据结构的底层逻辑,提高编程能力。
831 4
|
11月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
11月前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构之单双链表按位、值查找;[前后]插入;删除指定节点;求表长、静态链表等代码及具体思路详解步骤;举例说明、注意点及常见报错问题所对应的解决方法
|
12月前
|
存储 Java
数据结构第三篇【链表的相关知识点一及在线OJ习题】
数据结构第三篇【链表的相关知识点一及在线OJ习题】
94 7