文档章节

数组和链表总结

九州暮云
 九州暮云
发布于 2017/09/11 17:16
字数 492
阅读 46
收藏 1
点赞 0
评论 0

定义

  • 数组是具有相同数据类型的元素的集合

  • 链表是由链接/指针连接的元素的有序集合

访问方式

  • 在数组中,可以使用索引/下标值来访问元素,即元素可以被随机访问,比如arr[0]、arr[3]等,因此数组提供快速和随机访问。

  • 在链表中,元素不能随机访问,只能按顺序访问,访问元素需要花费O(n)时间

内存结构

  • 在数组中,元素以连续的方式存储在内存中

  • 在链表中,元素可以存储在任何可用的地方,节点的地址存储在以前的节点中

插入&删除

  • 因为元素存储在连续的内存位置,在数组中插入和删除需要更多的时间,每次操作都需要移动元素

  • 插入和删除在链表中是快速和容易的,因为只需要改变指针的值

内存分配

  • 在数组中,在编译时分配内存,即静态内存分配

  • 在链表中,内存在运行时分配,即动态内存分配

类型

  • 数组可以是单维的,二维的或多维的

  • 链表可以是单端链表、双端链表或循环链表

依赖性

  • 在数组中,每个元素都是独立的,与以前的元素或位置无关

  • 在链表中,元素的位置或地址存储在前一个元素/节点的链接部分

额外空间

  • 在数组中,没有使用类似链表的指针,因此不需要内存中的额外空间来存放指针

  • 在链表中,元素之间使用指针或链接来维护,因此使用指针,并且需要额外的内存空间

示例图

  • 数组

输入图片说明

  • 链表

输入图片说明

编译自:Difference between Array and Linked List | Array vs. Linked List

© 著作权归作者所有

共有 人打赏支持
九州暮云
粉丝 47
博文 132
码字总数 67325
作品 0
海淀
高级程序员
线性表--链式存储结构--静态链表

静态链表 一、存储结构 静态链表的存储结构.jpg 其中,有两对元素是特殊的: 第一对: 下标为0的元素,其数据不存放东西; 其游标是指向第一个没有存放数据的下标,此处为下标为5的元素。 第...

JS_HCX
03/27
0
0
Java:这是一份全面 & 详细的HashMap 1.7源码分析指南

前言 在 和 开发中非常常见 今天,我将带来 的全部源码分析,希望你们会喜欢。 目录 Entry类实现了Map.Entry接口 即 实现了getKey()、getValue()、equals(Object o)和hashCode()等方法 **/ ...

Carson_Ho
07/05
0
0
手把手带你源码分析 HashMap 1.7

前言 HashMap 在 Java 和 Android 开发中非常常见 今天,我将带来 HashMap 的全部源码分析,希望你们会喜欢。 目录 1. 简介 类定义 3. 具体使用 3.1 主要使用API(方法、函数) 3.2 使用流程...

烂猪皮
04/21
0
0
Java Collection、Map集合总结

1.Java中的Collection集合总结 Collection   |---List(存储有序,可重复)     |---ArrayList       底层数据结构是数组,查询快,增删慢。       线程不安全、效率高  ...

hafiz.zhang
2016/05/02
0
0
java8中的HashMap的putVal方法

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; if ((tab = table) == null || (n = tab.length) == 0) n = (......

清尘V
2016/03/28
64
0
小蚂蚁学习数据结构(8)——线性结构——线性结构复习

线性结构即将告一段落,来个简单总结一下。 连续存储(数组) //定义一个数组结构体struct Arr{ int * pBase; //保存数组的指针 int len; //保存数组的长度 int cnt; //数组元素的有效个数}...

嗜学如命的小蚂蚁
2016/01/05
43
0
HashMap的put和get方法原理

概述 JAVA中的数组,在添加或者删除元素的时候,都会复制一个新数组,比较耗内存。但是数组的遍历则是非常高效的。链表则是相反,遍历慢(需要遍历数组,一直找到值相等的元素才算找到),而添加和删...

linsongbin1
2017/01/23
0
0
HashMap详解(一). put方法详解

JAVA8 1.HashMap.put 方法实现了Map.put(K key,V value)的方法。直接调用内部方法 大致思路是这样的: 对key的hashCode()进行hash后计算数组下标index; 如果当前数组table为null,进行resiz...

努力学的程序员
2017/11/02
0
0
Java基础学习笔记-Collection

Collection ArrayList: 动态数组 LinkedList: 双向链表 Vector: 动态数组、线程安全 Stack: 继承Vector,动态数组,FILO HashMap: table为数组,entry为链表 HashTable: 线程安全,类似于...

杨子敬的瞎扯时刻
03/09
0
0
浅谈HashMap

HashMap结构图 image.png HashMap主要方法 final int hash(Object k) static int indexFor(int h, int length) void resize(int newCapacity) public V put(K key, V value) public V get(O......

小鱼嘻嘻
2017/10/28
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

JPA @MappedSuperclass 注解说明

基于代码复用和模型分离的思想,在项目开发中使用JPA的@MappedSuperclass注解将实体类的多个属性分别封装到不同的非实体类中。 1.@MappedSuperclass注解只能标准在类上:@Target({java.lang....

海博1600
12分钟前
0
0
Scala Configuration 相关API

Play使用了 Typesafe config library,但是也提供了一个有着更多Scala高级特性的的 Configuration 封装。不熟悉Typesafe配置的开发者可以移步 configuration文件的语法和特性文档。 读取配置...

Landas
今天
1
0
使用cookie技术 记住账号

1. 效果 2. 实现过程 2.1 前端 将用户的选中传递给后台 这个参数的获取是 参考:https://my.oschina.net/springMVCAndspring/blog/1860498 // var rememberLogin = $("#rememberLoginId").i...

Lucky_Me
今天
1
0
《趣谈网络协议》02之网络分层的真实含义

一、提出问题 1.提出问题 当你听到什么二层设备、三层设备、四层 LB 和七层 LB 中层的时候,是否有点一头雾水,不知道这些所谓的层,对应的各种协议具体要做什么“工作”? 2.这四个问题你弄...

aibinxiao
今天
2
0
Python3学习日志二 Python中的集合set和字典dict

1.集合set 定义一个集合set 我们可以看到定义集合set有两种不同的形式,如果要定义一个空的集合set不能用{}而是要用set();另外,集合是无序的,而且set中的元素是不可重复的,如果你定义了一...

Mr_bullshit
今天
0
0
adb 操作指令详解

ADB,即 Android Debug Bridge,它是 Android 开发/测试人员不可替代的强大工具,也是 Android 设备玩家的好玩具。 注:有部分命令的支持情况可能与 Android 系统版本及定制 ROM 的实现有关。...

孟飞阳
今天
0
0
nodejs安装以及环境配置(很好的node安装和配置文章,少走很多弯路)

一、安装环境 1、本机系统:Windows 10 Pro(64位) 2、Node.js:v6.9.2LTS(64位) 二、安装Node.js步骤 1、下载对应你系统的Node.js版本:https://nodejs.org/en/download/ 2、选安装目录进...

sprouting
今天
1
0
Redisson

了解了Redisson,发现使用挺简单的,接下来准备深入学习一下。 Redisson介绍 Redisson是架设于Redis基础之上的一个Java驻内存数据网格(In-Memory Data Grid) Redisson在基于NIO的Netty框架上...

to_ln
今天
0
0
python有哪些好玩的应用实现,用python爬虫做一个二维码生成器

python爬虫不止可以批量下载数据,还可以有很多有趣的应用,之前也发过很多,比如天气预报实时查询、cmd版的实时翻译、快速浏览论坛热门帖等等,这些都可以算是爬虫的另一个应用方向! 今天给...

python玩家
今天
0
0
python爬虫日志(3)-爬去异步加载网页

在浏览器检查元素页面中,选取Network中的XHR选项即可观察每次加载页面,网页发出的请求,观察url的规律即可利用封装的函数对每一页进行爬取。

茫羽行
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部