背景

去年下半年，我在微信书架里加入了许多技术书籍，各种类别的都有，断断续续的读了一部分。

没有计划的阅读，收效甚微。

新年伊始，我准备尝试一下其他方式，比如阅读周。每月抽出1~2个非连续周，完整阅读一本书籍。

这个“玩法”虽然常见且板正，但是有效，已经坚持阅读七个月。

已读完书籍：《架构简洁之道》、《深入浅出的Node.js》、《你不知道的JavaScript（上卷）》、《你不知道的JavaScript（中卷）》、《你不知道的JavaScript（下卷）》、《数据结构与算法JavaScript描述》、《WebKit技术内幕》、《前端架构：从入门到微前端》。

当前阅读周书籍：《秒懂算法：用常识解读数据结构与算法》。

基于节点的数据结构

链表

和数组一样，链表也是表示一系列元素的数据结构。乍一看二者很相似，但本质上有天壤之别。

链表中的数据不是存储在连续内存区块中，而是散落在内存的不同格子里。

节点表示散布在内存中的互相连接的数据。在链表中，每个节点都表示其中的一个元素。问题在于：如果节点互不相邻，那么计算机如何才能知道哪些节点属于同一个链表呢？

这就是链表的关键：每个节点都包含了它下一个节点的内存地址的信息。该信息就是链接，它以指针形式表示出了下一个节点的内存地址。

只要知道链表开始的内存地址，计算机就可以使用它。因为每个节点都包含到下一个节点的链接，所以计算机只需要跟踪链接就能访问整个链表。

链表数据在内存中无须相连就是它相对于数组的优势。数组需要找一整块连续的格子来存储数据，这在数组较大时就会比较困难。因为这些细节是由编程语言管理的，所以你可能无须担心。但是你马上就会发现链表和数组间有着更实际的区别。

链表实现

虽然像Java这样的编程语言内置了链表，但很多语言没有。不过实现链表相当简单。我们来用Ruby实现自己的链表。这需要Node和LinkedList两个类。首先来实现Node类。

class Node
  attr_accessor :data, :next_node
  def initialize(data)
    @data = data
  end
end

Node类包含data和next_node两个属性：前者表示节点的主要值（比如字符串"a"），后者是到下一个节点的链接。可以像下面这样使用该类。

node_1 = Node.new("once")
node_2 = Node.new("upon")
node_3 = Node.new("a")
node_4 = Node.new("time")
node_1.next_node = node_2
node_2.next_node = node_3
node_3.next_node = node_4

上面这段代码创建了一个有4个节点的链表，其中包含了字符串"once"、"upon"、"a"和"time"。`

虽然只用Node类就可以创建链表，但是需要一个简单的方法告知程序链表开始的位置。因此需要额外创建一个LinkedList类，其基本实现如下。

class LinkedList
  attr_accessor :first_node
  def initialize(first_node)
    @first_node = first_node
  end
end

LinkedList实例需要做的就是记录链表的第一个节点。

我们之前创建的链表包括节点node_1、node_2、node_3和node_4。现在可以通过下面的代码用LinkedList类来引用这个链表。

list = LinkedList.new(node_1)

list变量就像链表的一个把手，因为它是LinkedList的一个实例，并且可以访问链表的第一个节点。

有一点很重要：在使用链表时，能直接访问的只有第一个节点。你马上就会发现，这会带来严重后果。

链表操作的效率

整体来看，链表的时间复杂度平平无奇：查找、插入、删除都和数组差不多，读取甚至比数组还慢。既然这样，为什么还要用链表呢？

链表的真正优势在于实际的插入和删除都只需要O(1)时间。

但这只适用于在链表开头插入或者删除节点。要在其他地方插入或者删除节点，需要先用N步找到要删除的节点或者要插入的节点的前一个节点。

双链表

双链表是另一类链表。

双链表和链表一样，只不过每个节点有两个链接——一个指向后一个节点，一个指向前一个节点。此外，除了第一个节点，双链表还需要记录最后一个节点。

双链表核心机制的Ruby实现如下：

class Node
  attr_accessor :data, :next_node, :previous_node
  def initialize(data)
    @data = data
  end
end
class DoublyLinkedList
  attr_accessor :first_node, :last_node
  def initialize(first_node=nil, last_node=nil)
    @first_node = first_node
    @last_node = last_node
  end
end

因为双链表知道自己的第一个节点和最后一个节点所在，所以访问它们都只需要1步，也就是需花O(1)时间。因此，我们不仅能在O(1)时间内从双链表开头读取、插入和删除数据，还可以在O(1)时间内在其结尾完成相同的操作。

总结

节点表示的数据可能散布在计算机内存各处。基于节点的数据结构提供了新的管理和访问数据的方法，带来了很多性能优势。

本篇主要介绍链表。它是最简单的基于节点的数据结构，也是未来章节的基础。虽然链表看起来类似数组，但因为在效率上有所取舍，所以可以在特定情况下带来性能提升。

作者介绍
非职业「传道授业解惑」的开发者叶一一。
《趣学前端》、《CSS畅想》等系列作者。华夏美食、国漫、古风重度爱好者，刑侦、无限流小说初级玩家。
如果看完文章有所收获，欢迎点赞👍 | 收藏⭐️ | 留言📝。