链表：由一系列结点node（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。
每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。
链表是如何组成的：
首先有一个头节点， 其结点指向的是空地址，比如需要储存一个数据A，保存在地址11位置，那么如何将数据A连接到头节点上？数据D地址是96位置；数据C地址是37位置；数据C和D如何连接的呢
- 将头节点的结点指向的空地址改为11，这样A就可以连接上了
- 将A的下一个结点的地址改为37，这样就可以连接上数据C了
- 数据C的下一个结点的地址改为96，数据D就连接上了
最终效果如下：
我们常说的链表结构有单向链表与双向链表。
单向链表 特点（1）多个结点之间，通过地址进行连接
（2）查找元素慢：想查找某个元素，需要通过连接的节点，依次向后查找指定元素
（3）增删元素快：
- 举例：在下图所示的链表中进行增删元素
- 在AC之间添加元素B，数据B保存在地址54位置
步骤：
- 将数据B对应的下一个数据地址变为37，即C的地址
- 将数据A对应的下一个数据地址37改为54，即B的地址
最终结果：
- 删除上面添加元素过后的列表的数据BD之间的数据C
步骤：
- 将数据B对应的下一个数据地址由37改为96，即数据D的地址
- 将数据C删除
最终结果如下：
有两个指针域分别指向前一个结点和后一个结点，还有一部分用来保存结点数据，初始化结点时需要将两个指针都指向空
1.增加结点。
增加结点时，需要将最后一个结点的next指针指向新结点，然后将新结点的prev指向最后一个结点
3.删除结点。
删除结点时需要将待删除结点的前一个结点的next指向待删除结点的后一个结点，然后，把后者的prev指针指向前者:
4.插入结点。
插入结点就是将新结点的前一个结点的next指针指向指向新结点，然后把新结点的next指针指向前一个结点原来后面的那个结点，然后把后面的结点的prev指针指向新结点，把新结点的Prev指针指向前一个结点。
数组数组(Array)：同一种类型数据的集合。是有序的元素序列，数组是在内存中开辟一段连续的空间，并在此空间存放元素。
特点：（1）查找元素快：通过索引，可以快速访问指定位置的元素；
查询数据通过索引定位，查询任意数据耗时相同，查询效率高
（2）增删元素慢
删除数据时，要将原始数据删除， 同时后面每个数据都需要(向前)移动，删除效率低
添加数据时，添加位置后的每个数据(后移)移动，最后再添加元素，添加效率极低
-
指定索引位置增加元素：需要创建一个新数组，将指定新元素存储在指定索引位置，再把原数组元素根 据索引，复制到新数组对应索引的位置。如下图
具体说明：往arr1中添加一个元素a4，没有顺序
- 创建一个新数组arr1，来存放添加完元素后的数组，数组长度为原数组长度加添加的元素个数，
- 先把arr按顺序储存入arr1，最后将a4储存入arr1中
具体说明：往arr2中添加一个元素a4，将元素储存到索引为2的位置
- 创建一个新数组arr2，用来存放指定位置的的元素，数组长度为原数组加上元素的个数
- 先将新元素a4添加到指定位置，然后再去复制原数组中的数据
- 指定索引位置删除元素：需要创建一个新数组，把原数组元素根据索引，复制到新数组对应索引的位置，原数组中指定索引位置元素不复制到新数组中。如下图
1.链表是链式存储结构，数组是顺序存储结构；
2.链表通过指针连接元素，而数组则是把所有元素按顺序进行存储；
3.链表插入和删除元素不需要移动元素，数组删除和增加元素需要移动元素。
4.链表查找慢，增删快
5.数组查找快，增删慢
链表的作用链表就将一系列不连续的内存联系起来，将那种碎片内存进行合理的利用，解决空间的问题。
所以，链表允许插入和删除表上任意位置上的节点，但是不允许随即存取。
最大的作用：可以自动给数组中的元素从0开始编号，方便操作这些元素。
