数组与链表的区别

查找

数组访问一个a[3]的元素与访问一个a[10000]，这两个元素的时间消耗是一样的。

链表就不是了，链表没有下标的概念，只能通过头节点指针，从每一个节点，依次往下找，因为下个节点的位置信息只能通过上个节点知晓。

• 数组：随机访问，时间复杂度O(1)
• 链表：顺序访问，时间复杂度O(n)

新增

• 数组：在某个节点前新增元素，需要把后面的进行往后移动
• 链表：只需要改变节点中的指针

删除和新增同理