链表和数组

1链表是什么？

链表是一种上一个元素的引用指向下一个元素的存储结构，链表通过指针来连接元素与元素；

链表是线性表的一种，所谓的线性表包含顺序线性表和链表，顺序线性表是用数组实现的，在内存中有顺序排列，通过改变数组大小实现。
而链表不是用顺序实现的，用指针实现，在内存中不连续。意思就是说，链表就是将一系列不连续的内存联系起来，将那种碎片内存进行合理的利用，解决空间的问题。

所以，链表允许插入和删除表上任意位置上的节点，但是不允许随即存取。链表有很多种不同的类型：单向链表、双向链表及循环链表。

2.单向链表

单向链表包含两个域，一个是信息域，一个是指针域。也就是单向链表的节点被分成两部分，一部分是保存或显示关于节点的信息，第二部分存储下一个节点的地址，而最后一个节点则指向一个空值。

3.双向链表

每个节点有2个链接，一个是指向前一个节点（当此链接为第一个链接时，指向的是空值或空列表），另一个则指向后一个节点（当此链接为最后一个链接时，指向的是空值或空列表）。意思就是说双向链表有2个指针，一个是指向前一个节点的指针，另一个则指向后一个节点的指针。

4.循环链表

循环链表就是首节点和末节点被连接在一起。循环链表中第一个节点之前就是最后一个节点，反之亦然。

5.数组和链表的区别？

不同：链表是链式的存储结构；数组是顺序的存储结构。

链表通过指针来连接元素与元素，数组则是把所有元素按次序依次存储。

链表的插入删除元素相对数组较为简单，不需要移动元素，且较为容易实现长度扩充，但是寻找某个元素较为困难；

数组寻找某个元素较为简单，但插入与删除比较复杂，由于最大长度需要再编程一开始时指定，故当达到最大长度时，扩充长度不如链表方便。
相同：两种结构均可实现数据的顺序存储，构造出来的模型呈线性结构。

6.链表的优缺点

优点：
① 任意位置插入元素和删除元素的速度快，时间复杂度是o(1)

② 内存利用率高，不会浪费内存

③ 链表的空间大小不固定，可以动态拓展。

缺点：随机访问效率低，时间复杂度是o(1)

总之：

对于想要快速访问数据，不经常有插入和删除元素的时候，选择数组

对于需要经常的插入和删除元素，而对访问元素时的效率没有很高要求的话，选择链表

时间复杂度

image.png

总结：

链表是线性表的一种，线性表包括顺序线性表和链表，顺序线性表就是用数组实现的，在内存中顺序排列，链表不是用顺序实现的，用指针实现的，在内存中不连续排列
链表就是将一系列不连续的内存联系起来，将那种碎片内存进行合理的利用，解决空间的问题

链表类型：
单向，双向，循环
单：单一指向，有一个信息域和一个指针域，指针指向下一个信息域
双向：两个指针域，一个信息域，前指向上一个的后，后指向下一个的前
循环：单向链表的最后一个指针域指向第一个信息域

问题1：链表数组有什么不同？

①顺序上：
链表是链式的存储结构；数组是顺序的存储结构。
链表通过指针来连接元素与元素，数组则是把所有元素按次序依次存储。
②插入删除元素上
链表的插入删除元素相对数组较为简单，不需要移动元素，且较为容易实现长度扩充，但是寻找某个元素较为困难；
数组寻找某个元素较为简单，但插入与删除比较复杂，由于最大长度需要再编程一开始时指定，故当达到最大长度时，扩充长度不如链表方便。

问题2：插入查询的时间复杂度

数组：头部插入删除：O(N)，尾部插入删除均为O(1)，随机访问为O(1)
链表：头部插入删除：O(N)，尾部插入删除均为O(1)，随机访问为O(N)

参考链接：
1