顺序表与链表的区别

Myth丶恋晨 2023-09-27 13:35 77阅读 0赞

**目录**

一、顺序表和链表的比较

顺序表

优点：

缺点：

链表

优点

缺点

二、顺序表和链表的区别

1.顺序表和链表都具有增、删、查、改功能，但算法复杂度却不相同。

2、从数据元素存储的内存角度来看

三、顺序表与链表选取方案

--------------------

## **一、[顺序表][Link 1]和链表的比较** ##

### 顺序表 ###

> 顺序表的特点是逻辑上相邻数据元素，物理存储位置相邻，并且顺序表的存储空间需要预先分配，存储空间是静态分配的。  
>

#### **优点：** ####

*  顺序表具有按数组下标随机访问的特点。
 *  不用为表示节点间的逻辑关系而增加额外的存储开销

#### **缺点：** ####

*  在顺序表中做插入、删除操作时，需要遍历数组元素，当数组元素较大时，顺序表效率低。
 *  静态分配，程序执行之前必须明确规定存储规模预先分配足够大的存储空间，估计过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出。

###  ###

### 链表 ###

>   
> 在链表中逻辑上相邻的数据元素，物理存储位置不一定相邻，它使用指针实现元素之间的逻辑关系。并且链表的存储空间是动态分配的。

#### 优点 ####

*  插入、删除运算方便。

#### 缺点 ####

*  链表不是一种随机存储结构，不能随机存取元素。
 *  要占用额外的存储空间存储元素之间的关系，存储密度降低。

## 二、顺序表和链表的区别 ##

### 1.顺序表和链表都具有增、删、查、改功能，但算法复杂度却不相同。 ###

1.  增：  
    a) 顺序表往指定位置，不覆盖的添加一个值，后面的元素要往后移动，**算法复杂度为O(n)**；b) 链表往指定位置添加一个节点，需要从表头遍历到指定位置，**算法复杂度为O(n)** 注意：如果链表带有索引的节点，算法复杂度为O(1)
2.  删：  
    a) 顺序表指定位置，删除一个值时，需要将后面的值向前移动，**算法复杂度为O(n)**;  
    b) 链表指定一个位置，删除一个时，如果没有对指定节点进行索引，需要从表头遍历到指定 位置，然后将指定节点删除，**算法复杂度为O(n)**, 注意：如果对链表指定节点做索引，删除节点的算法复杂度为O(1)。
3.  查：  
    a) 顺序表根据数组元素下标直接查询指定元素，**算法复杂度为O(1)**；  
    b) 链表需要遍历节点到指定位置，**算法复杂度为O(n)**; 注意：如果节点指定位置节点有索引，算法复杂度为O(1).
4.  改：修改其实就是查找修改值的位置，再对值进行修改。  
    a) 顺序表的增和删表数量规模比较大时平均移动一半的元素，效率不高，**算法复杂度为O(n)**;  
    b) **对于有索引的链表，添加和删除只需要O(1)算法复杂度，效率高。因此，链表用于频繁的添加和删除数据时，有优势。**

### 2、从数据元素存储的内存角度来看 ###

（1）顺序表是由数组组成的线性表，数组是一组地址连续的单元存储块，**分配于栈区**，可以自动释放。  
（2）链表是由不连续的地址节点组成的线性表，每个节点可以是一个单元的地址块或连续地址块，**分配于堆区**，节点必须手动释放。内存管理比较不方便。

## 三、顺序表与链表选取方案 ##

（1）顺序表的存储空间是静态分配的，在程序执行之前必须明确规定它的存储规模，也就是说事先对“MaxSize”要有合适的设定，设定过大会造成存储空间的浪费，过小造成溢出。

因此，**当对线性表的长度或存储规模难以估计时，不宜采用顺序表。然而，链表的动态分配则可以克服这个缺点**。链表不需要预留存储空间，也不需要知道表长如何变化，只要内存空间尚有空闲，就可以再程序运行时随时地动态分配空间，不需要时还可以动态回收。

（2）顺序存储是一种随机存取的结构，而链表则是一种顺序存取结构，因此它们对各种操作有完全不同的算法和时间复杂度。例如，要查找线性表中的第i个元素，对于顺序表可以直接计算出a(i)的的地址，不用去查找，其时间复杂度为0(1).而链表必须从链表头开始，依次向后查找，平均需要0(n)的时间。所以，如果经常做的运算是按序号访问数据元素，显然顺表优于链表。

**查找操作的线性表，适于选择顺序存储；而频繁做插入删除运算的线性表适宜选择链式存储。**

（3）顺序表容易实现，任何高级语言中都有数组类型；链表的操作是基于指针的。相对来讲前者简单些，也用户考虑的一个因素。

[Link 1]: https://so.csdn.net/so/search?q=%E9%A1%BA%E5%BA%8F%E8%A1%A8&spm=1001.2101.3001.7020