数组和链表的区别

  • 数组:内存上是连续的存储空间;
  • 链表:内存地址可以是不连续的,每个链表的节点包括原来的内存和下一节点的信息(单向链表一个;双向链表两个)。

数组、链表优劣势对比

读取元素

当我们需要读取元素时,数组和链表哪个更好呢?

  • 链表:在读取链表的最后一个元素时,你不能直接读取,因为你不知道它所处的地址,必须先访问元素#1,从中获取元素#2的地址,再访问元素#2并从中获取元素#3的地址,以此类推,直到访问最后一个元素。
  • 数组:知道其中每个元素的地址。因此数组的效率很高,可迅速找到数组中的任何元素。

插入元素

当我们需要在中间插入元素时,数组和链表哪个更好呢?

  • 链表:插入元素很简单,只需修改它前面的那个元素指向的地址。
  • 数组:必须将后面的元素都向后移。如果没有足够的空间,可能还得将整个数组复制到其他地方!

删除元素

当我们需要删除元素时,数组和链表哪个更好呢?

  • 链表:只需修改前一个元素指向的地址即可。
  • 数组:删除元素后,必须将后面的元素都向前移。

不同于插入,删除元素总能成功。如果内存中没有足够的空间,插入操作可能失败,但在任何情况下都能够将元素删除。

总结

下面是数组和链表的不同操作的时间复杂度:

数组链表
读取O(1)O(n)
插入O(n)O(1)
删除O(n)O(1)

《算法图解》读书笔记

赞赏一杯咖啡
0%