一、简介
如下图，fe0ffeeb是计算机的一个内存单元的地址
算法图解
需要将数据存储到内存时，你请求计算机提供存储空间，计算机给你一个存储地址。需要存储多项数据时，有两种基本方式——数组和链表。但它们并非都适用于所有的情形，因此知道它们的差别很重要。接下来介绍数组和链表以及它们的优缺点。
二、数组
数组简单来说就是将所有的数据排成一排存放在系统分配的一个内存块上，通过使用特定元素的索引作为数组的下标。
1、储存
数组的所有元素都是相连的。假如你需要将有5个元素的数组存储到计算机内存，则需要向计算机请求5个连在一起的内存单元。
缺点：
- 大小固定：数组的大小是静态的（在使用前必须制定数组的大小）；
- 分配一个连续空间块：数组初始分配空间时，有时候无法分配能存储整个数组的内存空间（当数组规模太大时）
2、添加
但当你需要在数组中插入你的第6个元素时，而当前的储存空间已经没有位置，此时你需要请求计算机重新分配一块可存放6个元素的内存，再将整个数组移到那里。
缺点：
如果要在数组中的给定位置插入元素，那么可能就会需要移动存储在数组中的其他元素，这样才能腾出指定的位置来放插入的新元素；而如果在数组的开始位置插入元素，那么这样的移动操作开销就会很大。
添加操作的复杂度就是O(n)：
3、读取
由于数组元素的存储地址是连续一起的，所以数组的读取非常简单。
数组的元素带编号，编号从0而不是1开始（几乎所有的编程语言都从0开始对数组进行编号）。这个编号我们称之为索引。
4、删除
删除一个元素后，必需将后面的元素都往前移。
数组删除操作的复杂度与添加操作相同：
三、链表
链表是一种物理存储结构上非连续，非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
在单向链表中，每个节点指向链表中的下一个节点。而在双向链表中，每个节点岂同时具备指向前一个节点和后一个节点的指针。
双向链表
1、储存
链表中的元素可以存储在内存的任何地方，从而使一系列随机的内存地址串在一起，不会出现内存块不足的情况。
2、添加
在链表中添加元素很容易：只需要将其放入内存，并将其地址存储到前一个元素中。
3、读取
在需要读取链表的最后一个元素时，你不能直接读取，因为你不知道它所处的地址，必须先访问元素#1，从中获取元素#2的地址，再访问元素#2并从中获取元素#3的地址，以此类推，直到访可最后一个元素。
需要同时读取所有元素时，链表的效率很高：你读取第一个元素，根据其中的也址再读取第二个元素，以此类推。但如果你需要跳跃，链表的效率就真的很低。
4、删除
删除元素也是只需要修改前一个元素指向的地址即可。
四、运行时间
下图是数组和链表常见操作的运行时间对比：
算法图解
需要指出的是，只有当能立即访问要删除的元素时，删除操作的运行时间才为O(1)。通常我们都记录了链表的第一个元素和最后一个元素，因此删除这些元素时运行时间为O(1)。
五、拓展
混合数据结构：链表数组
链表数组可以理解为一个二维数组，但是数组的元素为链表结构，如下图：
算法图解
网友评论