【java-面试题】顺序表和链表的区别

这也算面试中的经典问题了，当然，面试官可能不会直接问我们链表顺序表，更大可能性是问arrayList和linkedList有什么区别，这时候我们回答的重点可以放在动态数组上的动态上。

一：顺序表

顺序表的存储结构

顺序表的物理结构就是数组。数组的底层是一段物理地址连续的内存空间。通过数组下标能对数组中的元素进行随机访问，时间复杂度是O(1)。

顺序表的扩容机制

1. 向顺序表中新添加元素时，只能按照一定倍数扩容，会浪费空间。
2. 给顺序表扩容时，是通过方法Arrays.copyOf实现的。即先申请一个比原来顺序表空间更大的新空间，然后把全部数据放到这个新空间中，也就是先拷贝全部数据。最后再释放旧空间。这个过程会有不小的空间消耗。

集合类ArrayList中扩容机制的底层实现源码：
分析上述源码发现：

1. 对于一个无参构造的空顺序表，minCapacity小于等于10时，会默认扩容10个单位空间。minCapacity大于10时，会默认扩容minCapacity个单位空间。
2. 对于一个非无参构造的空顺序表，会默认扩容minCapacity个单位空间。
3. 对于非空顺序表，会按原数组的1.5倍扩容。

顺序表的插入和删除操作

顺序表的插入和删除操作，都是

1. 先遍历顺序表，找到要插入位置或删除元素，复杂度是O(n)。
2. 然后挪动元素，复杂度是O(n)。
3. 最后再进行插入或删除操作，复杂度是O(1)。

从整个插入算法或删除算法来说，插入和删除操作的时间复杂度都是O(n)。

二：链表

链表的存储结构

链表的物理结构不一定连续。所以没办法做到随机访问链表中的元素。如果想要访问链表中的元素，只能通过遍历链表，时间复杂度是O(n)。

链表的扩容机制

用链表存数据时，是随用随分配。

链表的插入和删除操作

链表的插入和删除操作，都是

1. 先遍历链表，找到要插入位置或删除结点，或者找到插入位置或删除结点的前驱，时间复杂度O(n)。
2. 然后插入或删除元素，时间复杂度O(1)。

从整个插入算法或删除算法来说，链表插入和删除操作的时间复杂度都是O(n)。

三：总结

对比链表和顺序表，可以发现：

1. 顺序表因为下标支持随机访问，但是数组扩容时会产生空间浪费，向其中每次插入和删除元素都需要挪动元素也比较麻烦。
2. 每次访问链表中的元素都要进行遍历链表，但是存数据时可以随用随分配，相比于顺序表来说，频繁向其中插入和删除元素的效率会更高。

虽然顺序表和链表，他们的插入和删除元素的时间复杂度都是O(n)，但是链表的插入和删除元素不需要挪动元素。
回顾上文中总结的顺序表和链表的插入和删除操作，其实就可以发现，顺序表的插入或删除操作的时间复杂度O(n)是从2n+C渐进过来的，而链表的插入或删除操作的时间复杂度O(n)是从n+C渐进过来的。
假设在列表中，需要频繁的插入和删除元素，每次向顺序表中插入和删除元素，都要进行挪动数据，但是向链表中插入和删除元素，却不需要。此时，链表的效率自然高于顺序表。

所以比较顺序表和链表，

1. 顺序表更适合存储静态元素，即即经常对数据进行查找和更新的操作。
2. 链表更适合存储动态元素，即经常对数据进行插入和删除的操作。