面试题：数组和顺序表链表的区别

本是古典何须时尚 2022-09-14 09:07 16阅读 0赞

### 文章目录 ###

*  一、数组(Array)
 *   *   *  1.数组特点
         *  2.数组优点
         *  3.数组缺点
 *  二、链表(ListNode)
 *   *   *  1.链表的特点：
         *  2.链表的优点
         *  3.链表的缺点
 *  三、数组、链表总结

# 一、数组(Array) #

### 1.数组特点 ###

所谓数组，就是**相同数据类型的元素**按一定顺序排列的集合；数组的存储区间是连续的，占用内存比较大，故空间复杂的很大。但数组的二分查找时间复杂度小，都是O(1)；数组的特点是：查询简单，增加和删除困难。

*  在内存中，数组是一块连续的区域。
 *  数组需要预留空间。  
    在使用前需要提前申请所占内存的大小，如果提前不知道需要的空间大小时，预先申请就可能会浪费内存空间，即数组的空间利用率较低。注：数组的空间在编译阶段就需要进行确定，所以需要提前给出数组空间的大小(在运行阶段是不允许改变的)。
 *  在数组起始位置处，插入数据和删除数据效率低。  
    插入数据时，待插入位置的元素和他后面的所有元素都需要向后搬移。 删除数据时，待删除位置后面的所有元素都需要向前搬移。
 *  随机访问效率很高，时间复杂度可以达到O(1)。  
    因为数组的内存是连续的，想要访问那个元素，直接从数组的首地址向后偏移就可以访问到了。
 *  **数组开辟的空间，在不够使用的时候需要进行扩容；扩容的话，就涉及到需要把旧数组中的所有元素向新数组中搬移。**
 *  数组的空间是从栈分配的。（栈：先进后出）

### 2.数组优点 ###

*  **随机访问性强,查找速度快，时间复杂度是0（1）。**

### 3.数组缺点 ###

*  从头部删除、从头部插入的效率低，时间复杂度是o(n),因为需要相应的向前搬移和向后搬移。
 *  空间利用率不高。
 *  内存空间要求高，必须要有足够的连续的内存空间。
 *  数组的空间大小是固定的，不能进行动态扩展。
 *  数组存在越界问题。

# 二、链表(ListNode) #

### 1.链表的特点： ###

所谓链表，**链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的**。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。

**链表:链表存储区间离散，占用内存比较宽松，故空间复杂度很小，但时间复杂度很大，达O（N）。链表的特点是：查询相对于数组困难，增加和删除容易。**

*  在内存中，元素的空间可以在任意地方，空间是分散的，不需要连续。
 *  链表中的元素有两个属性，一个是元素的值，另一个是指针，此指针标记了下一个元素的地址。  
    每一个数据都会保存下一个数据的内存地址，通过该地址就可以找到下一个数据。
 *  查找数据时间效率低，时间复杂度是o(n)。  
     因为链表的空间是分散的，所以不具有随机访问性，如果需要访问某个位置的数据，需要从第一个数开始找起，依次往后遍历，知道找到待查询的位置，故可能在查找某个元素时，时间复杂度是O(n)。
 *  空间不需要提前指定大小，是动态申请的，根据需求动态的申请和删除内存空间，扩展方便，故空间的利用率较高。
 *  任意位置插入元素和删除元素时间效率较高，时间复杂度是O(1)。
 *  **链表的空间是从堆中分配的。（堆：先进先出，后进后出）。**

### 2.链表的优点 ###

*  任意位置插入元素和删除元素的速度快，时间复杂度是O(1)。
 *  内存利用率高，不会浪费内存。
 *  链表的空间大小不固定，可以动态拓展。
 *  链表不存在越界问题。

### 3.链表的缺点 ###

**随机访问效率低，时间复杂度是O(1)。**

# 三、数组、链表总结 #

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qOu5piO5biu5aSn5LqO6buR6JmO5biu_size_16_color_FFFFFF_t_70_g_se_x_16]

*  **对于想要快速访问数据，不经常有插入和删除元素的时候，选择数组。**
 *  **对于需要经常的插入和删除元素，而对访问元素时的效率没有很高要求的话，选择链表。**  
    ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qOu5piO5biu5aSn5LqO6buR6JmO5biu_size_15_color_FFFFFF_t_70_g_se_x_16]

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qOu5piO5biu5aSn5LqO6buR6JmO5biu_size_16_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/8ec5d10af1f844c99455e0470fb5bc20.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qOu5piO5biu5aSn5LqO6buR6JmO5biu_size_15_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/63b270b6710a4830b24feff491403d78.png