文档章节

数组、单链表、双链表的关系区别

 最胖的瘦子
发布于 04/07 15:04
字数 509
阅读 21
收藏 0

数组:

  1. 静态分布内存
  2. 根据下标定位元素
  3. 查找的时间复杂度为O(1),插入或删除的时间复杂度为O(N)
  4. 初始化数组需要规定数组大小,不能扩展

 

数组优点:

  1. 查找速度相较于链表更快
  2. 随机访问性更强,无序遍历,直接访问table[i]可快速定位

 

 

数组缺点:

  1. 删除或插入的速度更慢
  2. 由于数组大小是初始化时规定的,可能不能充分利用完全,容易造成内存浪费
  3. 需要连续的内存空间,且剩余内存必须足够大。对内存要求较高

 

 

 

链表:

  1. 动态分布内存
  2. 通过指针定位下位元素,单链表为next()方法,双链表除了next()方法外还有pre()方法定位上一位元素
  3. 插入或删除的时间复杂度为O(1),查找的时间复杂度为O(N)
  4. 链表的长度是动态扩展的

 

 

链表的优点:

  1. 插入的速度相较于数组更快
  2. 由于链表长度动态扩展,所以能充分利用内存,不会存在内存浪费

 

 

链表的缺点

  1. 查找的速度更慢一些
  2. 不支持随机访问

 

 

 

单链表常见于双链表的原因

 

双链表由于相较于单链表每个元素多了一个向前的指针,所以占用的存储空间更大,一个指针占用的内存空间在64位系统是8个字节,n个字节就需要多8*N个内存消耗。内存浪费严重

LinkedList是双向链表

© 著作权归作者所有

粉丝 4
博文 34
码字总数 19079
作品 0
杭州
私信 提问
数据结构篇之链表1-链表的概念

近期为了面试做准备,复习了下关于链表的一些知识点,做个记录~ 首先何谓链表? 链式存储的线性表,简称链表。链表由多个链表元素组成,这些元素称为节点。结点之间通过逻辑连接,形成链式存...

青雨001
2018/11/16
0
0
Java基础知识——数组与链表的区别

1、数组与链表的区别。 数组是具有相同的数据类型且按一定次序排列的一组变量的集合体,数组在内存中的地址是连续的(链表内存地址是散列、不连续的)。数组是一种引用数据类型,数组元素类似...

小八路2222
03/08
0
0
数组和链表结构(python)_2

本文内容目录如下,会分拆为两篇笔记,另一则笔记是 "数组和链表结构(python)_1"。 3. 链表结构 Linked Structures 在数组之后,链表结构可能使程序中最常用的数据结构。 3.1 单链表结构和双...

曾翔翔
2018/07/28
0
0
Glib实例学习(8)系列一(完)

目前为止,我们学习了Glib的基本数据类型,我们基本可以用这些类型管理我们需要的数据了,我们现在来回顾下前面的内容: 单链表 双链表 哈希表 动态数组 平衡二叉树 双端队列 关系/元组 我们...

小代码2016
2015/08/16
186
0
数组和链表的本质区别I

1.数组 查询快:数组要求是一块连续的内存空间来存储,这就要求在物理上这一片空间是连续的,每个元素都有指定的索引index指向内存地址,因此查询对时候,可根据index快速找到对应地址存储的...

键盘上跳舞
2018/02/02
40
0

没有更多内容

加载失败,请刷新页面

加载更多

OSChina 周六乱弹 —— 早上儿子问我他是怎么来的

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @凉小生 :#今日歌曲推荐# 少点戾气,愿你和这个世界温柔以待。中岛美嘉的单曲《僕が死のうと思ったのは (曾经我也想过一了百了)》 《僕が死の...

小小编辑
今天
1K
12
Excption与Error包结构,OOM 你遇到过哪些情况,SOF 你遇到过哪些情况

Throwable 是 Java 中所有错误与异常的超类,Throwable 包含两个子类,Error 与 Exception 。用于指示发生了异常情况。 Java 抛出的 Throwable 可以分成三种类型。 被检查异常(checked Exc...

Garphy
今天
36
0
计算机实现原理专题--二进制减法器(二)

在计算机实现原理专题--二进制减法器(一)中说明了基本原理,现准备说明如何来实现。 首先第一步255-b运算相当于对b进行按位取反,因此可将8个非门组成如下图的形式: 由于每次做减法时,我...

FAT_mt
昨天
38
0
好程序员大数据学习路线分享函数+map映射+元祖

好程序员大数据学习路线分享函数+map映射+元祖,大数据各个平台上的语言实现 hadoop 由java实现,2003年至今,三大块:数据处理,数据存储,数据计算 存储: hbase --> 数据成表 处理: hive --> 数...

好程序员官方
昨天
53
0
tabel 中含有复选框的列 数据理解

1、el-ui中实现某一列为复选框 实现多选非常简单: 手动添加一个el-table-column,设type属性为selction即可; 2、@selection-change事件:选项发生勾选状态变化时触发该事件 <el-table @sel...

everthing
昨天
19
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部