探讨面试问题：链表和顺序表的区别

探讨面试问题：链表和顺序表的区别

 当面试官问到以下三个问题的任意一个问题：

• 顺序表和链表的区别
• 数组和链表的区别
• ArrayList 和 linkedList 的区别

 以上三个问题都是一个问题，就是在问：双向链表和顺序表的区别

技巧：当面试官问到 #### 和 #### 的区别的时候，一定记住，先从共同点出发

这两种数据结构的共同点都是：线性表

这两种数据结构的不同点都是：对数据的组织方式和 *** 作方法

组织方式：

1. 顺序表底层是一个数组，它在逻辑和物理上是连续的
2. 链表是由若干个结点组成的一个数据结构，逻辑上是连续的，但在物理上是不一定连续的

*** 作方式：

1. 顺序表适合，查找相关的 *** 作，因为可以使用下标，可以直接获得摸个位置的元素
2. 链表适合于频繁的删除和插入 *** 作，此时不需要像顺序表一样，移动元素位置，链表只需要修改指向
3. 顺序表开辟一段空间可能造成空间浪费（如果不使用的情况下），顺序表的空间利用率低

1️⃣ 顺序表：一白遮百丑

白：空间连续、支持随机访问

丑：1.中间或前面部分的插入删除时间复杂度O(N) 2.增容的代价比较大。

2️⃣ 链表：一(胖黑)毁所有

胖黑：以节点为单位存储，不支持随机访问 所有：

1.任意位置插入删除时间复杂度为O(1)

2.没有增容问题，插入一个开辟一个空间。