文档章节

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

飞鱼说编程
 飞鱼说编程
发布于 06/25 11:30
字数 411
阅读 17
收藏 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指针(多耗点内存空间),对于插入和删除操作的顺序大家格外注意;
  • 但是,双向链表可以有效提高算法的时间性能,简单说就是用空间来换取时间。

 

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

© 著作权归作者所有

共有 人打赏支持
飞鱼说编程

飞鱼说编程

粉丝 168
博文 289
码字总数 548744
作品 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
线性表(Linear List)

线性表(linear list) 1、特点 线性表是我们日常工作中最简单也是最常用的一种数据结构。 它有如下特点: 每个数据元素最多只能有一个直接前趋。 每个数据元素最多只能有一个直接后继。 只有...

星汉
09/07
0
0
线性表--链式存储结构--双向链表

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

JS_HCX
03/29
0
0
看图轻松理解数据结构与算法系列(双向链表)

前言 推出一个新系列,《看图轻松理解数据结构和算法》,主要使用图片来描述常见的数据结构和算法,轻松阅读并理解掌握。本系列包括各种堆、各种队列、各种列表、各种树、各种图、各种排序等...

超人汪小建
07/29
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Spirng事务简单入门

一、概述 spring支持编程式事务管理和声明式事务管理两种方式: 1.编程式事务管理使用TransactionTemplate或者直接使用底层的PlatformTransactionManager。对于编程式事务管理,spring推荐使...

嘴角轻扬30
4分钟前
0
0
独立IP被恶意绑定域名处理办法

80端口: listen 80 default_server; server_name _; return 444; 443端口: listen 443 ssl default_server; server_name _; 加上证书路径 return 444;...

会当凌绝顶
7分钟前
0
0
RabbitMQ+PHP 教程五(Topics)

开始 在前面的教程中,我们改进了日志系统。我们使用的是一种直接广播方式,而不是只使用一种直接(direct)广播方式的fanout交换机,从而获得了有选择地接收日志的可能性。 虽然使用直接direc...

hansonwong
14分钟前
0
0
未来Linux Kernel 将不支持可变长数组VLA

但使用 VLA 会存在问题,包括增加运行时开销——因为数组长度需要在运行时确定; LLVM Clang 编译器不支持结构内 VLA,它只支持 C99 风格的 VLA;存在安全隐患。Linus Torvalds 对 VLA 的使用...

linux-tao
16分钟前
0
0
给Jenkins增加Linux奴隶节点

Add linux slave node in the Jenkins https://mohitgoyal.co/2017/02/14/add-linux-slave-node-in-the-jenkins/ https://www.howtoforge.com/tutorial/ubuntu-jenkins-master-slave/ https:......

圣洁之子
17分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部