🚩算法：问题求解步骤的描述。
维度 逻辑结构 存储结构（物理结构） 定义 数据元素之间的逻辑关系 数据结构在计算机中的实现方式 分类 线性/树形/图/集合 顺序/链式 /索引/散列独立性 独立于存储结构 依赖逻辑结构 示例 线性表 、有序表 、数组 （抽象层面）顺序表 、链表、静态链表ADT描述 描述操作语义 描述具体实现
ADT List { 数据对象：D = { a_i | a_i∈ElemSet, i= 1 , 2 , . . . , n} 数据关系：R = { < a_{ i- 1 } , a_i> | a_{ i- 1 } , a_i∈D} 基本操作：InitList ( & L) , ListInsert ( & L, i, e) . . .
}
术语 本质 所属层级 与其它概念关系 线性表 逻辑结构 逻辑层 可用顺序/链式存储实现 有序表 逻辑结构+约束 逻辑层 元素有序的线性表 顺序表 存储结构 物理层 线性表的顺序存储实现 数组【随机存取】 逻辑结构+存储结构 跨层概念 可视为特殊的顺序表
特性 线性表（抽象） 顺序表（实现） 有序表（特殊） 元素关系 前驱后继关系 物理相邻存储 按关键字有序 存储方式 与实现无关 连续内存空间 通常用顺序存储 查找效率 O(n) 按位O(1)，按值O(n) 顺序存储时可二分O(logn) 插入删除 依赖实现 移动元素O(n) 需保持有序性O(n)
栈和队列的ADT相同，即逻辑结构都是线性表。 顺序表具有随机存取是指：查找序号i的元素的时间，与顺序表中元素个数n无关 扩容问题 ➡顺序表插入算法：n个空间满了时，申请m个，若申请失败，则说明系统没有：n+m 个可分配的存储空间（n也要被复制进新表）对长度为n的、顺序存储的有序表，实现给定的算法中时间复杂度为O(1)的是：获取第i个值的算法。 线性表是具有n个同类型数据元素的有限序列。除开始元素外，每个元素只有唯一的前驱 元素。 若非空线性表中的元素，既没有前驱也没有后继，则：表中只有1个元素。 线性表的顺序存储结构：是一种随机存取的存储结构。 线性表要取前驱后继则采用什么物理结构：顺序表最好。 线性表要取指定序号在最后插入删除：物理结构用顺序表最好。 按值查找一定要比较值，所以与长度有关。
特性 顺序存储 链式存储 物理结构 连续内存空间 离散节点+指针 存储密度 100% ，所以密度大 <100%（需存储指针） 访问方式 随机存取（直接计算地址） 顺序存取（必须遍历） 插入删除 O(n)（需移动元素） O(1)（已知位置） 扩容方式 需重新分配+复制 动态增长 缓存友好性 好（空间局部性） 差 代表实现 顺序表、静态数组 单链表、双链表 典型应用 频繁随机访问场景 动态数据集合 能表示的逻辑结构 种类少 种类多
不能说某一种存储结构优于另一种 元素存放顺序与存储空间大小无关 顺序和链式都能顺序存取
视角 解释 示例 逻辑层 线性结构的推广（一维数组即线性表） 矩阵是二维线性结构 物理层 顺序存储的典型实现 int a[10]连续存储 操作特性 通过下标直接访问元素（本质是基地址+偏移量计算） a[i] ≡ *(a+i)
常见混淆对 区分关键 记忆技巧 顺序表 vs 数组 顺序表强调逻辑关系，数组侧重存储 “数组是顺序表的具体实现” 有序表 vs 顺序表 有序是逻辑约束，顺序是存储方式 “有序表可以用链表实现” 线性表 vs 链表 线性表是抽象概念，链表是具体实现 “链表是实现线性表的方式”
以下是补充栈（Stack）和队列（Queue）后的完整知识图谱，严格区分逻辑结构与存储结构，并标注实现方式：
