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

1.什么是顺序表？

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

2、什么是链表？

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

• 单向、双向
  
• 带头、不带头
  
• 循环、非循环
  
  
  
  

①顺序表的优缺点：

优点：

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

缺点：

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

②链表的优缺点

优点：

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

缺点

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

来源：https://blog.csdn.net/weixin_50843868/article/details/112060125
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！