【数据结构】【线性表】顺序表和链表的比较(附C语言源码)
顺序表和链表的比较
在这里，我们回顾数据结构的三要素：逻辑结构，物理结构和数据运算
- 在逻辑结构上，顺序表和链表都属于线性表。
- 在物理结构上，顺序表的各个结点之间的存储位置是连续的，顺序的；链表的存储则是链式的，不一定连续，空间随机。
- 在数据运算上
- 创建：顺序表一般需要预留空间；链表只需要分配一个头结点或者声明一个头指针
- 销毁：顺序表的静态分配系统自动回收空间，动态分配需要free空间；链表需要一个个结点删除，一个个结点空间free回收
- 插入和删除：顺序表每次插入删除都需要批量移动数据；链表插入和删除只需要修改指针。
- 查找：顺序表按位查找能立刻找到，按值查找需要遍历线性表；链表无论是按位查找还是按值查找都需要遍历链表。
不同的物理结构让它们在数据运算时的操作逻辑不同，我们可以从几个角度分析顺序表和链表的差别。
- 表的扩展性：线性表的需要预先分配最大内存，拓展性较差，链表可以在内存空间允许的情况下不断扩展，拓展性更好
- 删除插入操作性：线性表删除和插入都需要大量移动后续元素；链表只需要改变前驱结点或者后继结点的指针即可，时间复杂度较低
- 查找的简易性：顺序表可以根据位序直接定位元素位置，时间复杂度最低；链表的物理存储空间不联系查找必须经过遍历链表，时间复杂度较高
顺序表和链表的选择
其实我们可以看到，无论是哪一个，它们都有各种的优缺点，我们根据实际需求进行选择。
- 需要内存连续且有查找操作远大于插入或删除操作时选择顺序表。
- 插入或删除操作远大于查找查找时选择链表
原文地址：https://blog.csdn.net/weixin_58498967/article/details/143806642
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！