文章目录逻辑结构物理结构 / 存储结构顺序表顺序存储链表链式存储静态链表数据运算创建初始化销毁插入 与 删除查找总结逻辑结构数据元素之间抽象的前后关系物理/存储结构存储映像内存中真实存放形式运算查找、插入、删除、随机访问、遍历等逻辑结构结论两者的逻辑结构完全相同。逻辑结构都是线性结构即数据元素之间具有 “一对一” 的线性关系。区别无区别。逻辑结构只描述数据之间的抽象关系不涉及存储方式。无论是顺序表还是链表它们在逻辑上都是一条“线”。物理结构 / 存储结构顺序表顺序存储内存一片连续的存储单元元素相邻内存地址相邻通过下标直接定位元素依靠首地址 偏移量寻址存储密度高(1)只存储数据无指针开销优点支持随机存取存储密度高。缺点大片连续空间分配不方便改变容量不方便。链表链式存储内存物理离散结点分散、不要求连续结点 数据域 指针 / 游标域依靠指针找到下一个结点无法通过简单计算直接定位结点之间靠指针维系逻辑相邻物理地址无关存储密度低(1)每个结点除了存储数据还要存储指针优点离散的小空间分配方便改变容量方便。缺点不可随机存取存储密度低。静态链表物理上在连续数组内但逻辑依靠游标链接物理连续逻辑链式归类为链表。数据运算创建初始化顺序表顺序存储需要预分配大片连续空间。若分配空间过小则之后不方便拓展容量若分配空间过大则浪费内存资源。静态分配静态数组容量不可改变动态分配动态数组malloc、free)(容量可改变但需要移动大量元素时间代价高链表链式存储优只需分配一个头结点也可以不要头结点只声明一个头指针之后方便拓展。销毁顺序表顺序存储O(1)静态分配静态数组系统自动回收空间动态分配动态数组malloc、free)【malloc和free必须成对出现】malloc在堆区不能自动回收空间所以需要手动free链表链式存储O(n)需要写循环逐个遍历释放。必须从头开始依次free每一个数据结点。插入 与 删除顺序表顺序存储插入 / 删除元素要将后续元素都后移 / 前移时间复杂度O(n)时间开销主要来自移动元素若数据元素很大则移动的时间代价更高。链表链式存储优插入 / 删除元素只需要修改指针即可时间复杂度O(n)时间开销主要来自查找目标元素查找元素的时间代价更低。查找顺序表顺序存储优按位查找O(1)按值查找O(n)若表内元素有序可在O(log2n)时间内找到链表链式存储按位查找O(n)按位查找O(n)总结比较维度顺序表数组链表指针逻辑结构线性结构一对一线性结构一对一物理结构连续存储离散存储通过指针链接存储密度高≈1低1需存指针单链表 4/8 字节双链表 8/16 字节创建初始化一次性分配大块空间length0需预估最大容量O(1)只分配头结点或设为 NULL无需预估容量O(1)销毁释放一次释放O(1)简单快速逐个释放O(n)遍历慢极易内存泄漏随机访问按位O(1)优势O(n)劣势按值查找有序O(log~2~n)二分查找O(n)无法二分只能遍历插入/删除已知位置O(n)需移动元素O(1)优势只改指针插入/删除按位序O(n)移动元素O(n)遍历找前驱表头插入/删除O(n)需移动所有元素O(1)优势表尾插入/删除含尾指针O(1)若未满插入O(1)删除O(n)单向链表找不到尾前驱适用场景“查”多“改”少、数据量稳定、需频繁随机访问“增”多“删”多、数据量动态变化、不关心随机访问