数据结构，链表，数组

数组

内存里连续的存储区域，查找时间复杂度O(1)，因为是连续存储，插入时要将后面元素分别移动，所以插入时间复杂度O(n)(插入最后一个时为O(1)),同理，删除平均时间复杂度也为O(n)

链表

单链表

元素里有一个指针指向他的后一级节点，插入时改变前一级指针位置指向新节点，新节点指针指向后一级节点，所以**插入时间复杂度O(1)，删除同理，只要改变前一级指针指向后一级，同时释放删除节点的内存即可，所以删除时间复杂度O(1)。缺点是查找时只能从第一个节点开始一级级查找，所以查找平均时间复杂度O(n)**。

双链表

与单链表相比，节点多一个指针指向前一级节点，所以插入删除时间复杂度O(1),查找时间复杂度O(n)