文档章节

单项联表和双向联表的区别

o
 osc_w9s1w4o0
发布于 2019/03/31 13:55
字数 671
阅读 0
收藏 0

精选30+云产品,助力企业轻松上云!>>>

Reference:【https://blog.csdn.net/kangxidagege/article/details/80211225

数组的优点

  • 随机访问性强(通过下标进行快速定位)
  • 查找速度快

数组的缺点

  • 插入和删除效率低(插入和删除需要移动数据)
  • 可能浪费内存(因为是连续的,所以每次申请数组之前必须规定数组的大小,如果大小不合理,则可能会浪费内存)
  • 内存空间要求高,必须有足够的连续内存空间。
  • 数组大小固定,不能动态拓展

链表的优点

  • 插入删除速度快(因为有next指针指向其下一个节点,通过改变指针的指向可以方便的增加删除元素)
  • 内存利用率高,不会浪费内存(可以使用内存中细小的不连续空间(大于node节点的大小),并且在需要空间的时候才创建空间)
  • 大小没有固定,拓展很灵活。

链表的缺点

  • 不能随机查找,必须从第一个开始遍历,查找效率低

单链表和双链表的区别?

双链表具有的优点

  1. 删除单链表中的某个结点时,一定要得到待删除结点的前驱,得到该前驱有两种方法,第一种方法是在定位待删除结点的同时一路保存当前结点的前驱。第二种方法是在定位到待删除结点之后,重新从单链表表头开始来定位前驱。尽管通常会采用方法一。但其实这两种方法的效率是一样的,指针的总的移动操作都会有2*i次。而如果用双向链表,则不需要定位前驱结点。因此指针总的移动操作为i次。
  2. 查找时也一样,我们可以借用二分法的思路,从head(首节点)向后查找操作和last(尾节点)向前查找操作同步进行,这样双链表的效率可以提高一倍。

为什么单链表的使用多于双链表呢?

从存储结构来看,每个双链表的节点要比单链表的节点多一个指针,而长度为n就需要 n*length(这个指针的length在32位系统中是4字节,在64位系统中是8个字节) 的空间,这在一些追求时间效率不高应用下并不适应,因为它占用空间大于单链表所占用的空间;这时设计者就会采用以时间换空间的做法,这是一种工程总体上的衡量。

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
C++中 _declspec(novtable) 的探讨

(1)V TA B L E(虚函数表)和VPTR(指向虚函数标的指针)的区别 编译器到底做了什么实现的虚函数的晚绑定呢?我们来探个究竟。 编译器对每个包含虚函数的类创建一个表(称为V TA B L E)。...

风刃
2018/06/26
0
0
C++中 _declspec(novtable) 的探讨

(1)V TA B L E(虚函数表)和VPTR(指向虚函数标的指针)的区别 编译器到底做了什么实现的虚函数的晚绑定呢?我们来探个究竟。 编译器对每个包含虚函数的类创建一个表(称为V TA B L E)。...

风刃
2014/04/10
0
0
jpa配置entity(根据网上各个博客总结)

首先记录下主键生成策略,这里讨论代理主键,业务主键(比如说复合键等)这里不讨论。 JPA通用策略生成器 通过annotation来映射hibernate实体的,基于annotation的hibernate主键标识为@Id, 其...

龙鸣
2014/11/12
8
0
MyBatis联表查询与DTO类

目前项目中使用了PO和DTO,联表查询的结果直接可作为DTO类么?还是需要再转一下? ps: Mybatis联表查询,返回的关联表是对象格式,与DTO类好像有点区别.. 比如:UserInfo这个标准的DTO类 cl...

conhaifeng
2016/05/27
3.1K
2
数据库中的左连接(left join)和右连接(right join)区别

Left Join / Right Join /inner join相关 关于左连接和右连接总结性的一句话: 左连接where只影向右表,右连接where只影响左表。 Left Join select * from tbl1 Left Join tbl2 where tbl1.I...

思维80
2015/07/25
6
0

没有更多内容

加载失败,请刷新页面

加载更多

Hacker News 简讯 2020-07-10

更新时间: 2020-07-10 01:15 US Supreme Court deems half of Oklahoma a Native American Reservation - (reuters.com) 美国最高法院认为俄克拉荷马州的一半是印第安人保留地 得分:131 | 评...

FalconChen
8分钟前
0
0
OSChina 周五乱弹 —— 求求你吃了我吧,不要再玩弄食物的感情了

Osc乱弹歌单(2020)请戳(这里) 【今日歌曲】 @巴拉迪维 :张喆的单曲《陷阱 》 这首歌已经在网易找不到原唱了,不知道被哪家买了版权。#今日歌曲推荐# 《陷阱 》- 张喆 手机党少年们想听歌...

小小编辑
19分钟前
18
1
清华陈文光教授:AI 超算基准测试的最新探索和实践。

道翰天琼认知智能平台为您揭秘新一代人工智能。 无规矩不成方圆。放在超级计算机的研发领域,没有一个大家普遍接受的算力评测指标,便难以推动超算迅猛发展。 而现在伴随着人工智能的发展,大...

jackli2020
34分钟前
0
0
@RequestMapping, consumes 提交简单有意思的测试

getParm @GetMapping("getParm")public Result getParm(String id){ System.out.println(); return ResultFactory.success(id);} 等同于 == bodyParm @PostMapping("bodyParm......

莫库什勒
44分钟前
25
0
63. Unique Paths II

题目: 63. Unique Paths II A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below). The robot can only move either down or right at any p......

JiaMing
今天
46
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部