顺序表和链表的优缺点比较
发布网友
发布时间：2023-11-01 08:11
共1个回答
热心网友
时间：2024-10-13 16:46
顺序表和链表的优缺点比较如下：
链表：
1、优点：在插入和删除操作时，只需要修改被删节点上一节点的链接地址，不需要移动元素，从而改进了在顺序存储结构中的插入和删除操作需要移动大量元素的缺点。
2、缺点：没有解决连续存储分配带来的表长难以确定的问题。失去了顺序存储结构随机存取的特性。
顺序表：
1、优点:顺序表的内存空间连续尾插、尾删效率较高，支持随机访问，可以高效的按下标进行操作，时间复杂度是O(1)。
2、缺点:在顺序表中间插入或删除元素时都涉及到元素的移动，效率较低，顺序表长度固定，有时需要扩容。
链表：
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。
顺序表：
顺序表是在计算机内存中以数组的形式保存的线性表，线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素、使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中。即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系，采用顺序存储结构的线性表通常称为顺序表。
顺序表和链表的区别：
1、存储分配方式不同：顺序存储结构是用一段连续的存储单元依次存储线性表的数据元素，单项链表是采用链式存储结构，用一组任意的存储单元存放线性表的元素。
2、空间利用率不同：顺序表的空间利用率显然要比链表高。因链表在存储数据时，每次只申请一个节点的空间，且空间的位置是随机的，这种申请存储空间的方式会产生很多空间碎片，一定程序上造成了空间浪费。
3、开辟空间的方式不同：顺序表存储数据实行的是“一次开辟，永久使用”，即存储数据之前先开辟好足够的存储空间，空间一旦开辟后期无法改变大小（使用动态数组的情况除外）。而链表则不同，链表存储数据时一次只开辟存储一个节点的物理空间，如果后期需要还可以再申请。
