文档章节

数据结构与算法之双向链表

aibinxiao
 aibinxiao
发布于 06/25 11:30
字数 411
阅读 9
收藏 0
点赞 0
评论 0

一、双向链表

      1.双向链表的结点结构

typedef struct DualNode{
    ElemType data;
    struct DualNode *prior; // 前驱结点
    struct DualNode *next; // 后继结点
}DualNode, *DuLinkList;

      如图所示:

  

      2.双向循环链表

      既然存在单循环链表,那么双向链表也存在循环链表:

      3.双向链表的插入操作

      插入操作其实很简单,但是要注意顺序,不能写反,如图所示:

      通过上图,我们看看插入操作的实现步骤:

  • 1,s->next = p;
  • 2,s->prior = p->prior;
  • 3,p->prior->next = s;
  • 4,p->prior = s;

      注意:在交换的过程中不要出现矛盾,例如第4步如果先被执行了,那么p->prior就会提前变成s,使得插入操作出错

      4.双向链表的删除操作

      如图所示:

      通过上图,我们看看删除操作的实现步骤:

  • 1,p->prior->next = p->next;
  • 2,p->next ->prior = p->prior;
  • 3,free(p);

      总结一下:

  • 双向链表对于单循环链表来说,是要更复杂一点,每个结点多了一个prior指针(多耗点内存空间),对于插入和删除操作的顺序大家格外注意;
  • 但是,双向链表可以有效提高算法的时间性能,简单说就是用空间来换取时间。

 

本文为原创文章,如果对你有一点点的帮助,别忘了点赞哦!比心!如需转载,请注明出处,谢谢!

© 著作权归作者所有

共有 人打赏支持
aibinxiao
粉丝 17
博文 106
码字总数 166530
作品 0
中山
程序员
设计一个Cache系统

今天去面试,面试官让我设计一个cache系统,要求保证最近使用的数据不能被移除出cache,也就是每次添加一个cache项的时候,把最旧的cache项移除出去。 我只记得操作系统里貌似有个差不多的cac...

技术小阿哥
2017/11/27
0
0
cache 的设计与实现

本文整理自一下两篇博客:http://my.oschina.net/ScottYang/blog/298727 http://my.oschina.net/u/866190/blog/188712 Cache简介: Cache(高速缓存), 一个在计算机中几乎随时接触的概念。C...

peiquan
2014/09/26
0
0
[转]用C写有面向对象特点的程序

转一个比较老的帖子: 原文地址:http://blog.csdn.net/haoel/article/details/2864 作者:陈皓 比如在一个项目中,有大量的数据结构,他们都是双向链表,但又想共用一套对链表的操作算法,这...

晓寒
2011/11/15
673
5
线性表--链式存储结构--双向链表

双向链表 一、双向链表结构 双向链表结点结构 双向链表结点结构.png 既然单链表可以有循环链表,那么双向链表当然也可以有。 非空的双循环链表.png 由于这是双向链表,那么对于链表中的某一个...

JS_HCX
03/29
0
0
如何用C++实现一个LRU Cache

什么是LRU Cache LRU是Least Recently Used的缩写,意思是最近最少使用,它是一种Cache替换算法。 什么是Cache?狭义的Cache指的是位于CPU和主存间的快速RAM, 通常它不像系统主存那样使用D...

汉克斯
2015/08/05
0
0
LRU原理与实现

1 LRU Cache   LRU(Least Recently Used,最近最少使用)是一种Cache替换算法。什么是Cache?狭义的Cache指的是位于CPU和主存间的快速RAM,通常它不像系统主存那样使用DRAM技术,而使用昂...

fx677588
2017/08/31
0
0
LinkedHashMap 源码分析

LinkedHashMap 源码分析 1. 基本结构 1. 实现 实现的接口是 2. 继承    继承的是 这个就比较熟悉了,事实上我们会看到 代码量非常的少,主要就是因为他继承的 ,继承了大多数的操作。 仔细...

夜雁桐
03/26
0
0
链表的C语言实现(含动态内存分配)

链表的C语言实现(含动态内存分配) 上 链表的C语言实现之动态内存分配 一、为什么用动态内存分配 但我们未学习链表的时候,如果要存储数量比较多的同类型或同结构的数据的时候,总是使用一个数...

晨曦之光
2012/03/09
612
0
零基础python刷leetcode -- 2. Add Two Numbers

算法很重要,但是每天也需要学学python,于是就想用python刷leetcode 的算法题,和我一起开始零基础python刷leetcode之旅吧。 2. Add Two Numbers image.png 首先过一下python的一些基础知识...

linzechi
2017/11/21
0
0
性能优化(2.3)-LruCache源码解析

主目录见:Android高级进阶知识(这是总目录索引)  今天我们来聊聊缓存策略相关的内容,LruCache应该说是三级缓存策略会使用到的内存缓存策略。今天我们就来扒一扒这里面的原理,同时也温故...

ZJ_Rocky
2017/11/16
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

回想过往,分析当下,着眼未来

好久没有真正的在纸质笔记本上写过东西了,感觉都快不会写字了,笔画都不知道怎么写了。接下来就说说咱们的正事。 2018年7月22日,我做了一个决定,那就是去参加安全培训(可能是我职业生涯中...

yeahlife
11分钟前
0
0
关于工作中的人际交往

关于工作中的人际交往 Intro 写了篇发泄情绪的博客,但不会发布出来。 大概就是,要么忍,要么滚。 以及一些不那么符合社会主义核心价值观,不满于大资本家与小资本家剥削的废话。

uniqptr
16分钟前
0
0
springMVC的流程

1.用户发送请求至前端控制器DispatcherServlet 2.DispatcherServlet收到请求调用HandlerMapping处理器映射器。 3.处理器映射器根据请求url找到具体的处理器,生成处理器对象及处理器拦截器(...

JavaSon712
32分钟前
0
0
大数据教程(3.2):Linux系统软件安装之自动化脚本

博主前面文章有介绍过软件的安装,可以帮助IT人员顺利的完成功能软件安装;但是,对于我们运维人员或者需要管理软件安装的项目经理来说,有些应用一次行需要搭建很多台相同的软件环境(如tom...

em_aaron
50分钟前
0
0
Spring Boot 2.0.3 JDBC整合Oracle 12

整合步骤 1. Oracle驱动引入 Oracle驱动一般不能通过maven仓库直接下载得到,需自行下载并导入到项目的lib目录下,建议通过如下pom依赖引入下载的Oracle驱动 <!-- Oracle 驱动 -->...

OSC_fly
59分钟前
0
0
java 8 并行流 - 1

下面创建一个并行流,与顺序流 //顺序流Stream.iterate(0L, i -> i + 1) .limit(Integer.MAX_VALUE) .reduce(0L, Long::sum);//并行流Stream.iterate(0L, i -> i......

Canaan_
今天
0
0
数据结构与算法5

二分法采用向下取整的方法 使用有序数组的好处是查找的速度比无序数组快的多,不好的方面是因为要将所有靠后的数据移开,所以速度较慢,有序数组和无序数组的删除操作都很慢。 有序数组在查找...

沉迷于编程的小菜菜
昨天
1
1
SpringBoot | 第十一章:Redis的集成和简单使用

前言 上几节讲了利用Mybatis-Plus这个第三方的ORM框架进行数据库访问,在实际工作中,在存储一些非结构化或者缓存一些临时数据及热点数据时,一般上都会用上mongodb和redis进行这方面的需求。...

oKong
昨天
5
0
对基于深度神经网络的Auto Encoder用于异常检测的一些思考

一、前言 现实中,大部分数据都是无标签的,人和动物多数情况下都是通过无监督学习获取概念,故而无监督学习拥有广阔的业务场景。举几个场景:网络流量是正常流量还是攻击流量、视频中的人的...

冷血狂魔
昨天
0
0
并发设计之A系统调用B系统

A-->B A在发送请求之前,用乐观锁,减少对B的重复调用,这样一定程度上是幂等性。 比如A系统支付功能,要调用B系统进行支付操作,但是前端对"支付"按钮不进行控制,即用户会不断多次点击支付...

汉斯-冯-拉特
昨天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部