图解数组与链表

写在最前:

数组:所有元素地址是连续的,支持随机读取,读取速度快。
链表:元素地址是分散的,前一个元素有指针指向后一个元素地址。读取速度慢,但是在插入、删除时速度更快。

图解数据结构

假设我们把内存空间看成一张表格,那么数组就是连续占用了几个格子,而链表则是随机占用了一些格子。

先看数组

前面三格是你的待办事项(数组中的内容),它们连续的,所以当你看到第一个(吃午饭)后立马就能看到后面的待办事项。
但是当你想增加代办事项时就比较麻烦,因为后面的格子已经被别人占用了,你只能把你之前的待办事项删掉,重新找一个够你用的格子再写一遍你的代办事项,这样效率就非常的低!

数组

再看链表

链表的内容是分散的,比如说第一项待办事项在01号格子的吃饭,然后它还告诉你下一项代办事项在13号格子,于是你又去找13号格子,以此类推…
所以链表查询的效率就会非常的低。但是不管是在插入还是删除,链表效率都会非常高,只需修改一下指针的指向即可。

链表

附上复杂度对比