算法与数据结构-链表

(文章目录)

  与数组相比，链表是一个稍微复杂的数据结构。对于初学者来说，掌握它比数组稍微困难一些。我们经常把这两个非常基本和常用的数据结构放在一起进行比较。所以让我们来看看两者之间的区别。

  为了直观比较，我们画了一个例子。从图中我们可以看出，数组需要一个连续的内存空间来存储，对内存的要求相对较高。如果我们申请一个 100MB 当内存中没有连续的、足够大的存储空间时，即使内存的剩余总可用空间大于 100MB，仍将申请失败。

  相反，链表不需要连续的内存空间。它通过“指针”串联一组分散的内存块，所以如果我们申请的话 100MB 链表的大小，根本不会有问题。

  链表最常见的结构有：单链表、双向链表和循环链表。

  正如我们刚才所说，链表通过指针将一组分散的内存块串联在一起。其中，我们称内存块为链表的“结点”。为了串联所有的结点，除了存储数据外，每个链表的结点还需要记录链上下一个结点的地址。如图所示，我们称记录下一个结点地址的指针为后续指针 next。  从我画的单链表图中，你应该会发现有两个特殊的结点，即第一个结点和最后一个结点。我们习惯性地把第一个结点称为头结点，最后一个结点称为尾结点。头结点用于记录链表的基地址。有了它，我们可以得到整个链表。最后一个特殊的地方是:指针不是指向下一个结点，而是指向空地址 NULL，表示这是链表上的最后一个结点。

  链表还支持数据的搜索、插入和删除，就像数组一样。

  众所周知，在插入和删除数组时，为了保持内存数据的连续性，需要进行大量的数据移动，因此时间的复杂性是 O(n)。插入或删除链表中的数据，我们不需要移动结点来保持内存的连续性，因为链表本身的存储空间不是连续的。因此，插入和删除链表中的数据非常快。

  为了方便你理解，我画了一张图片。从图中可以看出，对于链表的插入和删除，我们只需要考虑相邻结点的指针变化，因此相应的时间复杂性是 O(1)。

请注意，虽然这里删除操作时间的复杂性是O(1) ，但是这个节点的查询操作时间复杂度仍然是O(n)

  但是，有利有弊。链表要随机访问第一 k 一个元素，没有数组那么高效。由于链表中的数据不是连续存储的，因此不能像数组一样直接计算相应的内存地址，根据第一个地址和下标公式，但需要根据指针一个接一个地通过，直到找到相应的结点。因此，链表的随机访问性能不如数组好，需要 O(n) 时间复杂。

  循环链表是一种特殊的单链表。事实上，循环链表也很简单。它和单链表之间唯一的区别在于末端。我们知道，单链表的末端指针指向空地址，这意味着这是最终的末端。循环链表的末端指针指向链表的末端。从我画的循环链表中，你应该可以看到它像一个环一样连接，所以它被称为“循环”链表。  与单链表相比，循环链表的优点是从链尾到链头更方便。当要处理的数据具有环结构特征时，特别适合使用循环链表。例如，著名的约瑟夫问题。虽然可以用单链表实现，但如果用循环链表实现，代码会简单得多。

  单向链表只有一个方向，结点只有一个后继指针 next 指向后面的结点。顾名思义，双向链表支持两个方向，每个结点都有一个以上的后继指针 next 还有一个前驱指针指向后面的结点 prev 指向前面的结点。  从我画的图中可以看出，双向链表需要两个额外的空间来存储后继结点和前驱结点的地址。因此，如果存储相同数据，双向链表占用的内存空间比单链表多。虽然这两个指针浪费了存储空间，但它们可以支持双向遍历，这也带来了双向链表操作的灵活性。双向链表适合解决哪些问题？

  从结构上看，双向链表可以支持 O(1) 在时间复杂的情况下找到前驱结点，这也使得双向链表在某些情况下的插入、删除等操作比单链表简单高效。

  数组和链表是两种完全不同的内存组织方式。由于内存存储的不同，插入、删除和随机访问的时间复杂性恰恰相反。  然而，数组和链表之间的比较并不局限于时间的复杂性。此外，在实际的软件开发中，数据存储的数据结构不能仅仅通过复杂性分析来确定。

  数组简单易用，在实现中使用连续的内存空间，可以借助 CPU 由于缓存机制，预读数组中的数据，因此访问效率更高。而且链表不是连续存储在内存中，因此对于 CPU 缓存不友好，无法有效预读。

  数组的缺点是尺寸固定，一旦声明占用整个连续内存空间。如果声明的数组太大，系统可能没有足够的连续内存空间分配给它，导致“内存不足”（out of memory）”。如果声明的数组太小，可能不够。此时只能申请更大的内存空间，复制原数组，非常耗时。链表本身没有大小限制，自然支持动态扩容。我觉得这也是它和数组最大的区别。

  你可能会说，我们 Java 中的 ArrayList 容器，也可以支持动态扩展啊？我们在最后一节课上说过，当我们在支持动态扩展的数组中插入数据时，如果数组中没有空闲空间，我们将申请一个更大的空间来复制过去的数据，而数据复制的操作非常耗时。

  我举一个稍微极端的例子。如果我们使用它 ArrayList 存储了了 1GB 大小数据，此时没有空闲空间，当我们再次插入数据时，ArrayList 会申请一个 1.5GB 大小的存储空间，以及原来的存储空间 1GB 将数据复制到新申请的空间。听起来很耗时吗？

  此外，如果您的代码对内存的使用非常苛刻，那么数组更适合您。由于链表中的每个结点都需要消耗额外的存储空间来存储指向下一个结点的指针，因此内存消耗将翻倍。此外，链表的频繁插入和删除也会导致频繁的内存应用和释放，如果是这样的话，很容易导致内存碎片 Java 语言可能会导致频繁 GC（Garbage Collection，垃圾回收)。