单向链表：
最好情况：头节点 O(1)
最坏情况：尾节点 O(n)
双向链表：
最好情况：insert/delete 头节点/尾节点 O(1)
最坏情况：元素不在数组中，遍历所有元素 O(n)
数组擅长读取，链表擅长写入。写入要先读取定位，再写入。
读取场景：
任意序位读取，复杂度： 数组O(1)，链表O(n)。
写入场景：
任意序位写入，定位复杂度：数组O(1)，链表O(n)；写入复杂度：数组O(n)，链表O(1)。
为什么数组的插入的复杂度是O(1)?
在数组尾部插入就是O(1)，因为不影响别的操作，假如说数组为a长度为10，你要在a[4]处插入一个值，因为数组是连续的，不可能再中间凭空新增一个空间，你要在a[4]上插入一个值，就需要将原来的a[4]-a[9]向后移一位原文：https://www.cnblogs.com/ygao/p/13955970.html