数组、链表（Array、Linked List）

数组 Array

• 数组在内存中的存储方式

  
  image.png
  

  可以看出数组查找的时间复杂度是O(1)，因为直接通过下标就可以查找

• 数组的插入和删除操作

  
  image.png

从上图可以看出，数组插入元素到数组中间的时间复杂度是O(n)，因为插入之后插入位置后面的数据都要换位置，删除也是如此。当然，如果插入或删除的元素是数组最后，则时间复杂度为O(1)

image.png

链表 Linked List

• 插入、删除的速度比数组快

image.png

• 每个元素都有一个指针，链向下一个节点。

• Insert操作

  
  image.png

新插入的元素的Next指针直接指向后一个元素，新插入的元素的前面的元素的Next指向新插入的元素即可。

• Delete操作

image.png

删除一个元素，直接把该元素前面的元素的Next指向后面的元素即可。再把要删除的节点从内存中释放掉即可。

那么链表的插入和删除都是O(1)的时间复杂度。

但是呢，链表中想要查找某一个元素，比如查找第五个元素，则要从头遍历五次，那么链表查找的时间复杂度则是O(n)的。

所以，不用的数据结构优缺点都是不同的。使用的时候根据实际情况来应用。

双链表

image.png
image.png