文档章节

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

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

 

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

© 著作权归作者所有

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

飞鱼说编程

粉丝 74
博文 198
码字总数 334315
作品 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
第一阶段:Java内功秘籍-线性表

前言 为什么要学习数据结构与算法,如果你学会了做安卓,javaweb,前端等,都是你的武功秘籍,但是如果你的内功不够好,再厉害的功夫也是白费。 数据结构和算法:什么是数据结构,什么是数据...

达叔小生
08/06
0
0
线性表(Linear List)

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

星汉
09/07
0
0
[转]用C写有面向对象特点的程序

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

晓寒
2011/11/15
673
5

没有更多内容

加载失败,请刷新页面

加载更多

C++ std::function 和 std::bind

C++11提供了std::function和std::bind两个工具,用于引用可调用对象。这些可调用对象包括 普通函数,Lambda表达式,类的静态成员函数,非静态成员函数以及仿函数等。引用可调用对象,可以用于...

yepanl
今天
1
0
python:可迭代对象的索引

关于 python的range的用法: 注意是[ 开始,结束)的半开区间,不包括结束 http://www.runoob.com/python/python-func-range.html import collectionsfrom collections import Iterable字符串......

Oh_really
今天
2
0
docker-compose ,docker-stack

1.例子 version: "3"services: php: image: registry.cn-hangzhou.aliyuncs.com/lxepoo/apache-php5 ports: - "38080:80" networks: - my_php_mysql volum......

chenbaojun
今天
3
0
SQL_Server2000示例数据库NorthWind的分析(转)

SQL_Server2000示例数据库NorthWind的分析 表名:Categories(食品类别表) 表结构: 字段名称 数据类型 长度 允许为空 CategoryID(主键) int 4 否 CategoryName nvarchar 15 否 Description ...

QQZZFT
今天
1
0
laravel 5.5 Session store not set on request.

laravel 5.5 数据存入session,会出现Session store not set on request.错误。查了下laravel 5.5将session放到global middleware中,需要laravel的文件 ./app/Http/Kernel.php中的加上一句:...

MichaelShu
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部