数组与链表原理 （算法与数据结构系列 3）

数组和链表是数据结构中最简单也是最基础的（微笑脸，柿子挑软的捏）

原理解析：

• 数组和链表都是线性表，即所有数据都排列在只有一个维度的线上。
• 数组元素在内存中连续分布，链表在内存中是分散的，用指针串起来。

image.png

• 访问数据：因为内存中连续分布，所以知道数组的首地址，就能访问任意元素，且时间复杂度是 O(1)。
  访问链表只能遍历，故时间复杂度是 O(n)

• 插入和删除数据：因为内存中连续分布，在数组中间插入一个元素，那么所有后面的元素都要后移，故时间复杂度为 O(n)
  插入链表只需要改变前后两个元素的 Next 指针指向即可，故复杂度为 O(1)。见下图（插入，删除同理）

  
  image.png

注意点：

• 链表的考察主要是修改链表中 Next 指针的指向（调转链表，元素交换等）。

下一篇，我们一起进行一些数组和链表的实战练习，训练一下解题思路。

系列会持续更新，需要查看可以进我主页。
如有疑问或者发现错误和纰漏，请留言指正。