顺序表与链表
- 从逻辑结构、存储结构、基本操作三个方面来对比顺序表与链表。
- 根据顺序表与链表的优缺点，分析其应用场景
- 顺序表和链表都是线性结构，都属于线性表
- 顺序表（顺序存储）：随机存取，存储密度高，需要大片连续的存储空间，改变容量不方便
- 链表（链式存储）：离散的存储空间，改变容量方便，不可随机存取，存储密度低
创建：
- 顺序表创建时必须预先分配大片的连续存储空间
- 链表开始创建时只需为头节点动态分配存储空间
- 顺序表销毁时需修改表的长度，使Length=0；静态分配方式的顺序表由系统自动回收存储空间，动态分配方式（malloc函数）的顺序表需手动回收存储空间（free函数）
- 链表销毁时依次删除每个节点即可，最终使头节点指向NULL
- 顺序表的插入和删除需要将后续元素后移和前移，时间复杂度O(n)主要体现在元素移动上
- 链表的插入和删除需要修改指针，时间复杂度O(n)主要体现在查找上
- 顺序表的按位查找时间复杂度O(1)，按值查找O(n)
- 链表的按位查找时间复杂度O(n)，按值查找O(n)
- 在表长无法预知的情况下，采用链表，无需提前分配大片连续的存储空间，有利于增加和删除操作
- 在表长可以预知的情况下，采用顺序表，有利于查找操作
推荐阅读
- 笔记|C语言数据结构——二叉树的顺序存储和二叉树的遍历
- C语言学习(bit)|16.C语言进阶——深度剖析数据在内存中的存储
- 数据结构和算法|LeetCode 的正确使用方式
- 先序遍历 中序遍历 后序遍历 层序遍历
- 数据结构|C++技巧（用class类实现链表）
- 数据结构|贪吃蛇代码--c语言版 visual c++6.0打开
- 算法|算法-二分查找
- 数据结构学习指导|数据结构初阶（线性表）
- leetcode题解|leetcode#106. 从中序与后序遍历序列构造二叉树
- java|ObjectOrientedProgramming - 面向对象的编程（多态、抽象类、接口）- Java - 细节狂魔