队列和链表

文章目录

需要存储多项数据时,有两种基本的数据结构——数组和链表。

数组

生活模型:情侣一起看电影,必须挨在一起。
所有元素在内存中都是相连的。

优点

随机读取元素时,效率很高。

缺点

添加新元素时可能很麻烦,即使可以通过预留内存,因为可能导致以下问题:

  1. 额外请求的内存没有使用,导致内存浪费;
  2. 当预留内存使用完毕,所有元素都得全部迁移。

链表

生活模型:藏宝游戏
元素可以存储在内存中的任何地方。链表中的每个元素都存储下一个元素的地址,从而使一系列随机的内存地址串在一起。

链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。

优点

只要有足够的内存,就可以为链表分配内存。

缺点

假如你想读取最后一个元素,不能直接读取。但是你不知道它所在的地址,必须从头开始访问,直到访问到最后一个元素。同时访问所有元素时,效率很高,单独访问时,因为需要跳跃,导致效率很低。

复杂度比较

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

需要插入元素时,若使用链表,只需修改前面元素指向的地址;而如果使用数组,则必须把后面所有元素都向后移一位,如果内存空间不足,整个数组都得复制到其他地方。(类似排队)

因为数组支持随机访问,所以经常被用来应用在构建需要支持能够随机访问的数据结构中。