经典面试题之顺序表和链表的优缺点

1.什么是顺序表？

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改,并且插入时可以动态增长。

2、什么是链表？

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链
接次序实现的 。每个结点的构成：数据域 + 指针域(结构体指针）。
实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：

1. 单向、双向
2. 带头、不带头
3. 循环、非循环
   

①顺序表的优缺点：

优点：

(1).空间连续。
(2).缓存利用率较高(相对于链式)，物理空间连续，预加载有优势
(3).支持随机访问。

缺点：

(1).可能存在一定的空间浪费：一般扩容是以两倍扩容
(2).增容有一些效率损失
(3).中间或者头部的插入删除需要遍历整个顺序表，时间复杂度为O(n).

②链表的优缺点

优点：

(1).不存在空间浪费，用就申请不用就不申请。
(2).任意位置的插入删除的效率高

缺点

(1).缓存利用率低，并且容易造成内存碎片
(2).不能随机访问