链表是每个程序员都应该知道的基本数据结构。这篇文章介绍如何用Python以函数式编程的形式实现链表。

构建链表

我们的链表由两个基础组件构建而成：Nil和Cons。Nil代表空列表，或者其他列表的叶子节点。Cons操作在链表的最前端插入一个新节点。

我们构建的链表使用嵌套的二元元组。例如，一个链表[1, 2, 3]由表达式cons(1, cons(2, cons(3, Nil)))表示，这个表示等价于嵌套元组(1, (2, (3, Nil)))

我们为什么使用这个结构？

首先，cons操作在函数式编程领域有着深远的历史。从 Lisp 的 cons cells 到 ML 和 Scala 的::操作符，cons操作随处可见。你可以把它当作一个动词使用。

其次，元组用来定义简单数据结构很方便。像我们这样定义一个简单的链表，实际上没有必要单独为它写一个类。当然，我也希望能让这篇介绍保持简洁。

第三，元组在Python中是不可变元素，保证了它被创建后不会被修改。不可变性非常重要，它能帮助你写出简单、并且线程安全的代码。我喜欢John Carmack的一篇文章，他论述了函数式编程和不可变性的关系。

把元组的构建过程抽象出来，使我们能够更灵活地控制链表的Python表现形式。例如，除了用元组表示这个二元结构，我们还可以使用Python中lambda匿名函数来表示。

为了给复杂的列表操作写简单的测试，我要引入帮助函数lst。它允许我们定义一个更复杂的列表结构，而不需要反复嵌套cons操作。

基本操作

所有的链表操作都可以归结为三个基本的操作：head, tail 和 is_empty。

• head返回链表中的第一个节点

• tail返回除了第一个节点的整个链表

• is_empty在链表中没有节点时返回True

一会儿你就会看到，这三个操作足以执行一些简单的排序算法了，比如插入排序法。

长度和合并

长度操作返回链表节点的数量。为了算出链表的长度，我们需要遍历整个链表（假设链表有n个节点）。所以这个算法的时间复杂度是O(n)。

concat把两个链表合并在一起。concat(xs, ys)的结果是一个全新的链表，这个链表包含了xs链表的全部节点，然后在后面接上ys链表的全部节点。这个功能就是一个简单的合并逻辑。

last, init 和 链表反转

基本操作 head, tail 都有对应的反向操作 last, init。last 是返回非空链表的最后一个节点，init 是返回除了最后一个节点的整个链表。

这两种操作的时间复杂度都是O(n)。因此如果你会频繁地使用last或者init操作，那么把列表反转过来会更好。下面reverse函数实现了简单的反转功能，不过它的时间复杂度是O(n²)

掐头去尾

接下来的两个操作take和drop是基础操作head和tail的泛化。take(2, xs)表示返回链表的头两个节点，而drop(3, xs)表示返回除了最后3个节点的整个链表。

获取节点

在链表上随机获取节点并不高效，时间复杂度在O(n)。获取节点的操作我们称之为apply，它可以由head和drop操作组合完成。

更复杂的例子

我们用最简单的head，tail 和 is_empty操作来执行一个简单的排序算法：插入排序。

下面的to_string方法把整个列表转换为一个字符串，字符串的格式类似于Python的列表。这个功能对于调试很有帮助。

补充说明

这篇文章讲解了使用Python实现一个链表的全部操作。但是这个代码示例有其局限性，最好不要在生产环境中使用。如果你的链表太大，会超出Python的递归层次限制。（CPython没有优化尾递归的情况）

英文原文：https://dbader.org/blog/functional-linked-lists-in-python

译者：诗书塞外