队列和链表

文章目录

1. 1. 数组
   1. 1.1. 优点
   2. 1.2. 缺点
2. 2. 链表
   1. 2.1. 优点
   2. 2.2. 缺点
3. 3. 复杂度比较

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

数组

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

优点

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

缺点

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

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

链表

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

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

优点

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

缺点

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

复杂度比较

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

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

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