数据结构的存储方式

简介: 数据结构底层存储只有数组和链表两种,其他如栈、队列、树、图等均为其衍生。数组支持随机访问但扩容困难,链表灵活增删但无法随机访问。所有数据结构的操作本质为“增删查改”,遍历方式分为线性迭代与非线性递归。理解二者差异,是掌握各类高级数据结构的基础。(238字)

数据结构的存储方式只有两种:数组(顺序存储) 和 链表(链式存储)。
这句话怎么理解,不是还有哈希表、栈、队列、堆、树、图等等各种数据结构吗?
我们分析问题,一定要有递归的思想,自顶向下,从抽象到具体。你上来就列出这么多,那些都属于上层建筑,而数组和链表才是结构基础。因为那些多样化的数据结构,究其源头,都是在链表或者数组上的特殊操作,API 不同而已。
比如说 队列、栈 这两种数据结构既可以使用链表也可以使用数组实现。用数组实现,就要处理扩容缩容的问题;用链表实现,没有这个问题,但需要更多的内存空间存储节点指针。
图结构 的两种存储方式,邻接表就是链表,邻接矩阵就是二维数组。邻接矩阵判断连通性迅速,并可以进行矩阵运算解决一些问题,但是如果图比较稀疏的话很耗费空间。邻接表比较节省空间,但是很多操作的效率上肯定比不过邻接矩阵。
哈希表 就是通过散列函数把键映射到一个大数组里。而且对于解决散列冲突的方法,拉链法 需要链表特性,操作简单,但需要额外的空间存储指针;线性探查法 需要数组特性,以便连续寻址,不需要指针的存储空间,但操作稍微复杂些。
树结构 用数组实现就是「堆」,因为「堆」是一个完全二叉树,用数组存储不需要节点指针,操作也比较简单,经典应用有 二叉堆;用链表实现就是很常见的那种「树」,因为不一定是完全二叉树,所以不适合用数组存储。为此,在这种链表「树」结构之上,又衍生出各种巧妙的设计,比如 二叉搜索树、AVL 树、红黑树、区间树、B 树等等,以应对不同的问题。
综上,数据结构种类很多,甚至你也可以发明自己的数据结构,但是底层存储无非数组或者链表,二者的优缺点如下:
数组 由于是紧凑连续存储,可以随机访问,通过索引快速找到对应元素,而且相对节约存储空间。但正因为连续存储,内存空间必须一次性分配够,所以说数组如果要扩容,需要重新分配一块更大的空间,再把数据全部复制过去,时间复杂度 O(N);而且你如果想在数组中间进行插入和删除,每次必须搬移后面的所有数据以保持连续,时间复杂度 O(N)。
链表 因为元素不连续,而是靠指针指向下一个元素的位置,所以不存在数组的扩容问题;如果知道某一元素的前驱和后驱,操作指针即可删除该元素或者插入新元素,时间复杂度 O(1)。但是正因为存储空间不连续,你无法根据一个索引算出对应元素的地址,所以不能随机访问;而且由于每个元素必须存储指向前后元素位置的指针,会消耗相对更多的储存空间。
数据结构的基本操作
对于任何数据结构,其基本操作无非遍历 + 访问,再具体一点就是:增删查改。
数据结构种类很多,但它们存在的目的都是在不同的应用场景,尽可能高效地增删查改,这就是数据结构的使命。
如何遍历 + 访问?我们仍从最高层来看,各种数据结构的遍历 + 访问无非两种形式:线性的和非线性的。线性就是 for/while 迭代为代表,非线性就是递归为代表。再具体一步无非以下几种框架:
数组遍历框架,典型的线性迭代结构:

相关文章
|
11月前
|
存储 算法
树结构
树结构通过二叉搜索树(BST)实现二分查找:每个节点左子树值小于根,右子树值大于等于根。查找时从根节点出发,比较目标值与当前节点值,决定向左或右子树递归,每次排除一半数据,时间复杂度为O(log n),实现高效检索。
|
3月前
|
人工智能 自然语言处理 数据可视化
阿里云千问办公与普通的通用 AI 对话助手有什么区别?对比表来了
阿里云千问办公不是通用对话助手,而是企业级AI办公执行平台:支持Word/PPT/Excel等一键生成、全栈网页免部署、多模态理解、浏览器自动化及定时任务,深度打通钉钉与企业数据源,实现“一句话→交付物”的端到端自动办公。阿里云千问办公官网:https://t.aliyun.com/U/805n7O
|
11月前
|
算法 数据可视化
二叉树的递归/层序遍历 递归遍历(DFS)
本文详解二叉树的遍历框架,涵盖递归遍历的固定访问顺序及前、中、后序的本质区别——即代码在递归函数中的位置不同所致。同时深入讲解层序遍历(BFS)的三种实现方式,适用于不同场景,尤其适合求最短路径问题;而DFS则因结构天然适合搜索所有路径。通过实例对比,阐明BFS与DFS的应用偏好及原理依据。
二叉树的递归/层序遍历 递归遍历(DFS)
|
11月前
|
存储 Serverless
哈希冲突
哈希冲突可通过优化哈希函数或采用冲突解决策略应对。开放寻址法通过线性、二次探查或双散列寻找空位,但易导致聚集,影响效率;链表法则在冲突位置构建链表,避免抢占,更适应动态数据,是常用方案之一。
|
人工智能 Cloud Native 调度
容器市场高速增长,阿里云连续3年蝉联第一
国际数据机构IDC发布《中国容器市场份额,2024:从云原生到AI原生》最新报告,2024年中国容器市场整体市场规模增长46.7%。其中,阿里云以26.6%的占比稳居第一,市场份额超过二、三名总和,连续3年蝉联榜首。
|
数据采集 机器学习/深度学习 编解码
小红书 hi lab开源最强多模态大模型dots.vlm1,性能对标闭源 Gemini 2.5 Pro 和 Seed-VL1.5
小红书 hi lab开源最强多模态大模型dots.vlm1,性能对标闭源 Gemini 2.5 Pro 和 Seed-VL1.5
1183 0
小红书 hi lab开源最强多模态大模型dots.vlm1,性能对标闭源 Gemini 2.5 Pro 和 Seed-VL1.5
|
10月前
|
机器学习/深度学习 弹性计算 编解码
阿里云服务器2核4G配置租用价格参考:u2a实例504.60元起,u1实例199元起,轻量应用服务器714元起
阿里云2核4G配置提供多类型服务器选择:轻量应用服务器714元/年,适配中小型网站快速搭建;通用算力型u1实例199元/年起,适合企业级应用;u2a实例504.6元/年起,性价比突出,支持企业通用场景;经济型e实例599.93元/年起,适合开发测试;计算型c9i实例1742元/年起,支撑高性能计算。
2102 8
|
11月前
|
存储 弹性计算 人工智能
大模型应用开发
大模型应用开发指通过API与大模型交互,构建智能化应用。不同于传统Java开发,其核心在于调用部署在云端或本地的大模型服务。企业可选择开放API、云平台或本地服务器部署,各具成本、安全与性能权衡。本章将详解部署方式与开发实践,助你快速入门。
|
11月前
|
存储 算法 安全
加密算法
加密算法主要分为对称加密(如AES、SM4)、非对称加密(如RSA、SM2)、哈希摘要(如SHA-2、SM3)、电子签名及密码存储技术。对称加密加解密快但需保密密钥;非对称加密使用公私钥,安全性高但速度慢;哈希摘要用于验证数据完整性,不可逆。各类算法在信息安全中各有应用场景。
|
11月前
|
存储 NoSQL 关系型数据库
Geohash 编码
Geohash编码将经纬度转换为字符串,通过不断二分地球经纬度区间,交叉组合生成区域编码,再转为Base32简化表示。它用于高效存储和查询地理位置,广泛应用于Redis、MySQL等系统,具有相同前缀的编码代表相近区域,便于空间索引与检索。