# 链表
# 概念
在计算机科学中, 一个 链表 是数据元素的线性集合, 元素的线性顺序不是由它们在内存中的物理位置给出的。 相反, 每个元素指向下一个元素。它是由一组节点组成的数据结构,这些节点一起,表示序列。
在最简单的形式下，每个节点由数据和到序列中下一个节点的引用(换句话说，链接)组成。这种结构允许在迭代期间有效地从序列中的任何位置插入或删除元素。
更复杂的变体添加额外的链接，允许有效地插入或删除任意元素引用。链表的一个缺点是访问时间是线性的(而且难以管道化)。
更快的访问，如随机访问，是不可行的。与链表相比，数组具有更好的缓存位置。
# 链表和数组
链表和数组一样，可以用于存储一系列的元素，但是链表和数组的实现机制完全不同
数组
存储多个元素，数组（或列表）可能是最常用的数据结构。几乎每种编程语言都有默认实现数组结构。
数组的缺点
- 数组的创建通常需要申请一段连续的内存空间并且大小是固定的，当数组不能满足容量需求时，需要扩容（一般是申请一个更大的数组，比如2倍，然后将原数组中的元素复制过去）
- 在数组开头或者中间位置插入数据的成本很高，需要进行大量的元素位移。
链表
- 存储多个元素，另外一个选择就是使用链表。
- 不同于数组，链表中的元素在内存中不必是连续的空间。
- 链表的每个元素由一个存储元素本身的节点和一个指向下一个元素的引用(有些语言称为指针)组成。
链表的优点：
- 链表中的元素在内存中不必是连续空间，可以充分利用计算机的内存，实现灵活的内存动态管理
- 链表不必在创建时就确定大小，并且大小可以无限延展下去
- 链表在插入和删除数据时，时间复杂度可以达到O(1),相对数组效率高很多。
链表的缺点：
- 链表访问任何一个位置的元素时，都需要从头开始访问（无法跳过第一个元素访问任何一个元素）
- 无法通过下标直接访问元素，需要从头一个个访问，直到找到对应的元素
链表类似于火车，有一个火车头，火车头会连接一个节点，节点上有乘客（数据），并且这个节点会连接下一个节点，以此类推。
火车结构
head 属性指向链表的第一个节点。 链表中的最后一个节点指向 null。 当链表中一个节点也没有的时候，head 直接指向 null。
