链表简介

链表，是链式存储结构，用于存储关系为一对一的数据。链表与顺序表不同，链表不限制数据的物理存储状态，换句话说，使用链表存储的数据元素，其物理位置是随机的。
image.png

链表的特点

  1. 插入、删除数据效率高，只需要考虑相邻节点的指针改变，不需要搬移数据，时间复杂度是 O(1)。
  2. 随机查找效率低，需要根据指针一个节点一个节点的遍历查找，时间复杂度为O(n)。
  3. 链表的空间消耗大，因为每个节点除了要存储数据本身，还要储存前后节点的地址。

数组缺点

  1. 数组必须占用整块、连续的内存空间，如果声明数组过大，可能回导致“内存不足”。

  2. 数组不够灵活，一旦需要扩容，会重新申请连续整块空间，并需要把原数组的数据全部拷贝到新申请的空间。

    链表缺点

  3. 内存空间消耗更大，用于储存结点指针信息。

  4. 对链表进行频繁的插入、删除操作会导致频繁的内存申请、释放，容易造成内存碎片，如果是JAVA语言，还有可能会导致频繁的GC（Garbage Collection，垃圾回收）。

链表的节点

链表的每个 “数据”，其实是一个 “节点”。这个节点是一个对象，这个对象里面包含大概两部分数据域和指针域

数据域：存放数据的地方，可以放多个数据 指针域：存放下一个或者上一个节点的位置的地方，就靠着节点之间的指针把节点串起来。