AI 助理
备案控制台
开发者社区 云计算 文章 正文

数据结构——双向循环链表

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

结构体的建立

typedef  int LTDatatype;
typedef struct ListNode
{
  struct ListNode* next;
  struct ListNode* prev;
  LTDatatype data;
}LTNode;


初始化

/*void ListInit(LTNode**pphead);*///初始化，初始化要传指针，要建立一个哨兵节点，要实质上把plist改变
LTNode* ListInit();//初始化,也可以不用二级，用一个返回值就行
LTNode* ListInit()
{
  LTNode* guard= (LTNode*)malloc(sizeof(LTNode));
  if (guard == NULL)
  {
    return NULL;
  }
  guard->next = guard;
  guard->prev = guard;
  return guard;
}

创建节点 

LTNode* BuyNode(LTDatatype x)
{
  LTNode* guard = (LTNode*)malloc(sizeof(LTNode));
  if (guard == NULL)
  {
  return NULL;
  }
  guard->next = NULL;
  guard->data = x;
  guard->prev = NULL;
  return guard;
}

头插节点  

void ListPushFront(LTNode* pphead, LTDatatype x)
{
  LTNode* newnode = BuyNode(x);
  LTNode* next = pphead->next;
  newnode->next = next;
  next->prev = newnode;
  newnode->prev = pphead;
  pphead->next = newnode;
}


尾插节点 

void ListPushBack(LTNode* pphead, LTDatatype x)
{
  assert(pphead);//pphead不可能为空
  LTNode* newnode = BuyNode(x);
  LTNode* tail = pphead->prev;//先找到尾
  tail->next = newnode;//开始尾插
  newnode->prev = tail;
  newnode->next = pphead;
  pphead->prev =newnode;
}//这种写法即使pphead是NULL，依然能插入，因为通过tail找到了pphead

头删节点 

void ListPopFront(LTNode* pphead)
{
  LTNode* next = pphead->next;
  pphead->next = next->next;
  next->next->prev = pphead;
  free(next);
}

尾删节点 

void ListPopBack(LTNode* pphead)
{
  assert(pphead);
  assert(!ListEmpty(pphead));//判断是否为空
  LTNode* tail1 = pphead->prev;
  LTNode* tail2 = tail1->prev;
  free(tail1);
  tail1 = NULL;
  tail2->next = pphead;
  pphead->prev = tail2;
}
bool ListEmpty(LTNode* pphead)
{
  assert(pphead);
    return pphead->next == pphead;//检测是否只剩头节点
}

节点查找

LTNode* ListFind(LTNode* pphead,LTDatatype x)
{
  assert(pphead);
  size_t n = 0;
  LTNode* cur = pphead->next;
  while (cur != pphead)
  {
    if (cur->data == x)
    {
      return cur;
    }
  }
}

节点前插入

void ListInsert(LTNode* pos, LTDatatype x)//在pos之前插入,若在pphead前插入，实际会变成尾插
{
  assert(pos);
  LTNode* prev = pos->prev;
  LTNode* newnode = BuyNode(x);
  prev->next = newnode;
  newnode->prev = prev;
  newnode->next = pos;
  pos->prev = newnode;
}

节点删除

void ListErase(LTNode* pos)
{
  assert(pos);
  LTNode* prev = pos->prev;
  LTNode* next = pos->next;
  prev->next = next;
  next->prev = prev;
  free(pos);
  pos = NULL;
}

销毁链表

void ListDestory(LTNode* pphead)//传一级，二级都可以
{
  assert(pphead);
  //1.先释放带数字的节点，最后释放头哨兵
  LTNode* cur = pphead->next;
  while (cur != pphead)
  {
  LTNode* next = cur->next;
  free(cur);
  cur = next;
  }
  free(pphead);
  pphead = NULL;//如果传一级指针，这里的置空不起作用，若想起作用，要传二级指针
}
//建议：使用一级指针，然后让调用ListDestory的人置空，保持接口的一致性，这里最后回到主函数把plist=NULL;即可

Dlist.h

#pragma once
#include<stdio.h>
#include<string.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef  int LTDatatype;
typedef struct ListNode
{
  struct ListNode* next;
  struct ListNode* prev;
  LTDatatype data;
}LTNode;
/*void ListInit(LTNode**pphead);*///初始化，初始化要传指针，要建立一个哨兵节点，要实质上把plist改变
LTNode* ListInit();//初始化,也可以不用二级，用一个返回值就行
void ListPushBack(LTNode* pphead,LTDatatype x);//不需要传地址，因为再怎么改变都不会改变哨兵位的头，改的是哨兵位的指向
void ListPushFront(LTNode* pphead, LTDatatype x);
void ListPopBack(LTNode* pphead);
void ListPrint(LTNode* pphead);
void ListPopFront(LTNode* pphead);
bool ListEmpty(LTNode* pphead);
size_t ListSize(LTNode* pphead);
LTNode* ListFind(LTNode* pphead, LTDatatype x);
void ListInsert(LTNode* pos, LTDatatype x);
void ListErase(LTNode* pos);
void ListDestory(LTNode* pphead);


Dlist.c

#define _CRT_SECURE_NO_WARNINGS
#include"Dlist.h"
LTNode* ListInit()
{
  LTNode* guard= (LTNode*)malloc(sizeof(LTNode));
  if (guard == NULL)
  {
  return NULL;
  }
  guard->next = guard;
  guard->prev = guard;
  return guard;
}
LTNode* BuyNode(LTDatatype x)
{
  LTNode* guard = (LTNode*)malloc(sizeof(LTNode));
  if (guard == NULL)
  {
  return NULL;
  }
  guard->next = NULL;
  guard->data = x;
  guard->prev = NULL;
  return guard;
}
void ListPrint(LTNode* pphead)
{
  assert(pphead);
  printf("guard<=>");
  LTNode* cur = pphead->next;
  while (cur!= pphead)
  {
  printf("%d<=>", cur->data);
  cur= cur->next;
  }
  printf("\n");
}
void ListPushBack(LTNode* pphead, LTDatatype x)
{
  assert(pphead);//pphead不可能为空
  LTNode* newnode = BuyNode(x);
  LTNode* tail = pphead->prev;//先找到尾
  tail->next = newnode;//开始尾插
  newnode->prev = tail;
  newnode->next = pphead;
  pphead->prev =newnode;
}//这种写法即使pphead是NULL，依然能插入，因为通过tail找到了pphead
void ListPushFront(LTNode* pphead, LTDatatype x)
{
  LTNode* newnode = BuyNode(x);
  LTNode* next = pphead->next;
  newnode->next = next;
  next->prev = newnode;
  newnode->prev = pphead;
  pphead->next = newnode;
}
void ListPopBack(LTNode* pphead)
{
  assert(pphead);
  assert(!ListEmpty(pphead));//判断是否为空
  LTNode* tail1 = pphead->prev;
  LTNode* tail2 = tail1->prev;
  free(tail1);
  tail1 = NULL;
  tail2->next = pphead;
  pphead->prev = tail2;
}
bool ListEmpty(LTNode* pphead)
{
  assert(pphead);
  return pphead->next == pphead;//检测是否只剩头节点
}
void ListPopFront(LTNode* pphead)
{
  LTNode* next = pphead->next;
  pphead->next = next->next;
  next->next->prev = pphead;
  free(next);
}
size_t ListSize(LTNode* pphead)
{
  size_t n = 0;
  LTNode* cur = pphead->next;
  while (cur != pphead)
  {
  ++n;
  cur = cur->next;
  }
  return n;
}
LTNode* ListFind(LTNode* pphead,LTDatatype x)
{
  assert(pphead);
  size_t n = 0;
  LTNode* cur = pphead->next;
  while (cur != pphead)
  {
  if (cur->data == x)
  {
    return cur;
  }
  }
}
void ListInsert(LTNode* pos, LTDatatype x)//在pos之前插入,若在pphead前插入，实际会变成尾插
{
  assert(pos);
  LTNode* prev = pos->prev;
  LTNode* newnode = BuyNode(x);
  prev->next = newnode;
  newnode->prev = prev;
  newnode->next = pos;
  pos->prev = newnode;
}
void ListErase(LTNode* pos)
{
  assert(pos);
  LTNode* prev = pos->prev;
  LTNode* next = pos->next;
  prev->next = next;
  next->prev = prev;
  free(pos);
  pos = NULL;
}
void ListDestory(LTNode* pphead)//传一级，二级都可以
{
  assert(pphead);
  //1.先释放带数字的节点，最后释放头哨兵
  LTNode* cur = pphead->next;
  while (cur != pphead)
  {
  LTNode* next = cur->next;
  free(cur);
  cur = next;
  }
  free(pphead);
  pphead = NULL;//如果传一级指针，这里的置空不起作用，若想起作用，要传二级指针
}
//建议：使用一级指针，然后让调用ListDestory的人置空，保持接口的一致性，这


顺序表和链表的区别

1.png

顺序表优点：1.尾插尾删的效率很高

                     2.可以随机访问（通过下标），链表需要遍历

                     3.和链表相比cpu高速缓存面中率很高

2.png3.png

寄存器相当于锅 ，如有数组{1，2，3，4}，这四个元素是存在主存里面的，数据结构是在主存里面管理我们的数据，链表也一样（堆是一个虚拟的内存的划分）


越往上速度越快，成本更高 ，L1,L2,L3被称为CPU的高速缓存


代码编译好了就是指令，通过CPU去运行指令，CPU访问通过访问内存数据运行指令，


CPU执行指令，不会直接访问内存


1.先看数据在不在三级缓存，在（命中），就直接访问


2.不在（不命中），先加载到缓存，再访问


顺序表的缺点：1.头部和中部的插入删除效率低——O(N)


                        2.扩容（动态开辟空间）——性能消耗，有一定空间浪费


链表的优点：1.任意位置插入删除效率很高O(1)


                     2.按需申请释放（不存在空间浪费）


链表的缺点：1.不支持随机访问（现实中随机访问很重要）


文章标签：
缓存
关键词：
数据结构链表
数据结构双向循环链表
jefcfxcg6xxjg
目录
相关文章
ephemerals__
|
8天前
|
存储 C语言
【数据结构】手把手教你单链表（c语言）（附源码）
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构，每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作，如头插、尾插、头删、尾删、查找、指定位置插入和删除等，并提供了完整的C语言代码示例。通过学习单链表，可以更好地理解数据结构的底层逻辑，提高编程能力。
ephemerals__
34 4
肾透侧视攻城狮
|
9天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解（9）【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子；这都学不会；能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛？！！！
肾透侧视攻城狮
17 2
肾透侧视攻城狮
|
9天前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
数据结构之单双链表按位、值查找；[前后]插入；删除指定节点；求表长、静态链表等代码及具体思路详解步骤；举例说明、注意点及常见报错问题所对应的解决方法
肾透侧视攻城狮
11 2
小强在此
|
30天前
|
存储 Java
数据结构第三篇【链表的相关知识点一及在线OJ习题】
数据结构第三篇【链表的相关知识点一及在线OJ习题】
小强在此
24 7
GuGuStudy
|
30天前
|
存储 安全 Java
【用Java学习数据结构系列】探索顺序表和链表的无尽秘密（附带练习唔）pro
【用Java学习数据结构系列】探索顺序表和链表的无尽秘密（附带练习唔）pro
GuGuStudy
22 3
java冯坚持
|
29天前
|
算法 Java
数据结构与算法学习五：双链表的增、删、改、查
双链表的增、删、改、查操作及其Java实现，并通过实例演示了双向链表的优势和应用。
java冯坚持
15 0
数据结构与算法学习五：双链表的增、删、改、查
ephemerals__
|
8天前
|
C语言
【数据结构】双向带头循环链表（c语言）（附源码）
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点：双向、带头和循环。与单链表相比，它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1)，提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现，包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
ephemerals__
25 0
努力学习的小廉
|
1月前
【数据结构】——双向链表详细理解和实现
【数据结构】——双向链表详细理解和实现
努力学习的小廉
27 2
椰椰椰耶
|
1月前
|
存储 Java
【数据结构】链表
【数据结构】链表
椰椰椰耶
17 1
徐霞客320
|
1月前
|
存储 缓存
数据结构3——双向链表
数据结构3——双向链表
徐霞客320
108 1

热门文章

最新文章

  • 1
    数据结构~在页面上渲染树型结构
  • 2
    我花了一夜用数据结构给女朋友写个H5走迷宫游戏
  • 3
    数据结构学习笔记【持续更新】
  • 4
    基于OHCI的USB主机 —— OHCI（自定义数据结构）
  • 5
    学数据结构，只需要基本的编程体验
  • 6
    算法导论第十四章 数据结构的扩张
  • 7
    【数据结构】C语言实现链式二叉树(附完整运行代码)
  • 8
    Python中的基础数据结构：列表（List）详解
  • 9
    攻克数据结构和算法——第五天：查找
  • 10
    数据结构上机实践第二周项目3——体验复杂度
  • 1
    `geopandas`是一个开源项目，它为Python提供了地理空间数据处理的能力。它基于`pandas`库，并扩展了其对地理空间数据（如点、线、多边形等）的支持。`GeoDataFrame`是`geopandas`中的核心数据结构，它类似于`pandas`的`DataFrame`，但包含了一个额外的地理列（通常是`geometry`列），用于存储地理空间数据。
    65
  • 2
    “解锁Python高级数据结构新姿势：图的表示与遍历，让你的算法思维跃升新高度
    39
  • 3
    Redis数据结构—跳跃表 skiplist 实现源码分析
    59
  • 4
    逆袭之路！用 Python 玩转图的 DFS 与 BFS，让数据结构难题无处遁形
    62
  • 5
    Python中的列表（List）和元组（Tuple）是两种重要的数据结构
    50
  • 6
    【数据结构OJ题】链表分割
    29
  • 7
    【数据结构常见七大排序（三）上】—交换排序篇【冒泡排序】And【快速排序】
    43
  • 8
    【数据结构常见七大排序（二）】—选择排序篇【直接选择排序】And【堆排序】
    29
  • 9
    【数据结构常见七大排序（一）】—插入排序篇【直接插入排序】And【希尔排序】
    42
  • 10
    【数据结构OJ题】链表的回文结构
    36

    • 相关课程

    更多
  • Go语言核心编程 - 数据结构和算法

    • 相关电子书

    更多
  • 如何使用Tair增强数据结构构建丰富在线实时场景
  • Apache Flink 流式应用中状态的数据结构定义升级
  • 低代码开发师（初级）实战教程
    • 下一篇
    DataWorks售前咨询