目录
一、顺序表和链表的比较
顺序表
优点：
缺点：
链表
优点
缺点
二、顺序表和链表的区别
1.顺序表和链表都具有增、删、查、改功能，但算法复杂度却不相同。
2、从数据元素存储的内存角度来看
三、顺序表与链表选取方案
一、顺序表和链表的比较
顺序表
顺序表的特点是逻辑上相邻数据元素，物理存储位置相邻，并且顺序表的存储空间需要预先分配，存储空间是静态分配的。
优点：
- 顺序表具有按数组下标随机访问的特点。
- 不用为表示节点间的逻辑关系而增加额外的存储开销
缺点：
- 在顺序表中做插入、删除操作时，需要遍历数组元素，当数组元素较大时，顺序表效率低。
- 静态分配，程序执行之前必须明确规定存储规模预先分配足够大的存储空间，估计过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出。
链表
在链表中逻辑上相邻的数据元素，物理存储位置不一定相邻，它使用指针实现元素之间的逻辑关系。并且链表的存储空间是动态分配的。
优点
- 插入、删除运算方便。
缺点
- 链表不是一种随机存储结构，不能随机存取元素。
- 要占用额外的存储空间存储元素之间的关系，存储密度降低。
二、顺序表和链表的区别
1.顺序表和链表都具有增、删、查、改功能，但算法复杂度却不相同。
- 增：
a) 顺序表往指定位置，不覆盖的添加一个值，后面的元素要往后移动，算法复杂度为O(n)；b) 链表往指定位置添加一个节点，需要从表头遍历到指定位置，算法复杂度为O(n) 注意：如果链表带有索引的节点，算法复杂度为O(1) - 删：
a) 顺序表指定位置，删除一个值时，需要将后面的值向前移动，算法复杂度为O(n);
b) 链表指定一个位置，删除一个时，如果没有对指定节点进行索引，需要从表头遍历到指定 位置，然后将指定节点删除，算法复杂度为O(n), 注意：如果对链表指定节点做索引，删除节点的算法复杂度为O(1)。 - 查：
a) 顺序表根据数组元素下标直接查询指定元素，算法复杂度为O(1)；
b) 链表需要遍历节点到指定位置，算法复杂度为O(n); 注意：如果节点指定位置节点有索引，算法复杂度为O(1). - 改：修改其实就是查找修改值的位置，再对值进行修改。
a) 顺序表的增和删表数量规模比较大时平均移动一半的元素，效率不高，算法复杂度为O(n);
b) 对于有索引的链表，添加和删除只需要O(1)算法复杂度，效率高。因此，链表用于频繁的添加和删除数据时，有优势。
2、从数据元素存储的内存角度来看
（1）顺序表是由数组组成的线性表，数组是一组地址连续的单元存储块，分配于栈区，可以自动释放。
（2）链表是由不连续的地址节点组成的线性表，每个节点可以是一个单元的地址块或连续地址块，分配于堆区，节点必须手动释放。内存管理比较不方便。
三、顺序表与链表选取方案
（1）顺序表的存储空间是静态分配的，在程序执行之前必须明确规定它的存储规模，也就是说事先对“MaxSize”要有合适的设定，设定过大会造成存储空间的浪费，过小造成溢出。
因此，当对线性表的长度或存储规模难以估计时，不宜采用顺序表。然而，链表的动态分配则可以克服这个缺点。链表不需要预留存储空间，也不需要知道表长如何变化，只要内存空间尚有空闲，就可以再程序运行时随时地动态分配空间，不需要时还可以动态回收。
（2）顺序存储是一种随机存取的结构，而链表则是一种顺序存取结构，因此它们对各种操作有完全不同的算法和时间复杂度。例如，要查找线性表中的第i个元素，对于顺序表可以直接计算出a(i)的的地址，不用去查找，其时间复杂度为0(1).而链表必须从链表头开始，依次向后查找，平均需要0(n)的时间。所以，如果经常做的运算是按序号访问数据元素，显然顺表优于链表。
查找操作的线性表，适于选择顺序存储；而频繁做插入删除运算的线性表适宜选择链式存储。文章来源：https://www.toymoban.com/news/detail-716277.html
（3）顺序表容易实现，任何高级语言中都有数组类型；链表的操作是基于指针的。相对来讲前者简单些，也用户考虑的一个因素。文章来源地址https://www.toymoban.com/news/detail-716277.html
到了这里，关于顺序表与链表的区别的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
