回答您的问题,通常在所谓的“函数式”语言(如Lisp、OCaml、Haskell等)中找到的 cons 没有直接等效物。
这是因为在编程语言中有两种竞争模型来表示元素列表。
链表
你似乎熟悉的那一种被称为链表。
链表由cons单元组成,每个单元包含两个引用:
- 第一个引用指向列表中的一个元素,称为头部
- 另一个引用指向列表中的下一个cons单元,即尾部
因为列表很少是无限的,所以最后一个const单元通常会指向一个特殊值——空列表,有时称为nil。
如果您想将列表保存在变量中以备将来参考,您需要保留对第一个cons单元的引用。
这是来自维基百科的可视化表示。
在这个模型中,每个列表必须通过在前面添加元素来构造,创建一个新的cons单元,将新元素指向其头部,并将先前构建的子列表指向其尾部。这就是为什么 cons 运算符有时被称为列表构造器的原因。
数组
这通常是Python等命令式语言首选的模型。在该模型中,列表只是对内存范围的引用。
假设您像这样创建一个列表:
l = [1, 2, 3]
每当你创建一个列表时,Python 会为它分配一小段内存来存储元素,并留有一些额外的空间以备将来添加元素。要存储它,你只需存储对第一个元素的引用,以及对内存范围大小的引用,就像这样:
l <-- your variable
| ___ ___ ___ ___ ___ ___ ___ ___ ___
|-> | | | | | | | | | |
| 1 | 2 | 3 | | | | | | |
|___|___|___|___|___|___|___|___|___|
如果您决定在列表末尾添加一个元素,您可以使用append
方法。
l.append(4)
形成以下列表:
___ ___ ___ ___ ___ ___ ___ ___ ___
| | | | | | | | | |
| 1 | 2 | 3 | 4 | | | | | |
|___|___|___|___|___|___|___|___|___|
假设你忘记了一个初始的0,现在希望在开头添加它。你可以使用插入方法(插入位置为0):
l.insert(0, 0)
但是列表开头没有空间!Python别无选择,只能一个一个地将每个元素复制到直接右侧的位置:
___ ___ ___ ___ ___ ___ ___ ___ ___
| | | | | | | | | |
| 1 | 2 | 3 | 4 | | | | | |
|___|___|___|___|___|___|___|___|___|
| | |__ |___
| |___ | | First, Python has to copy the four elements
|___ | | | one space to the right
___ _\/ _\/ \/_ _\/ ___ ___ ___ ___
| | | | | | | | | |
| | 1 | 2 | 3 | 4 | | | | |
|___|___|___|___|___|___|___|___|___|
Only then can it insert the 0 at the beginning
___ ___ ___ ___ ___ ___ ___ ___ ___
| | | | | | | | | |
| 0 | 1 | 2 | 3 | | | | | |
|___|___|___|___|___|___|___|___|___|
对于这样一个小的数组来说,可能看起来并不算什么,但是想象一下,如果你的数组很大,并且你重复执行此操作多次:你将花费很多时间构建列表!
这就是为什么使用数组作为列表的语言(如Python)中没有列表构造函数。
更深入的探究:为什么有两种不同的模型?
你现在可能会想知道为什么不同的语言会选择不同的列表模型,以及这两种模型中哪一种更优秀。
这是因为这两种数据结构在不同的上下文中具有不同的性能。以下是两个例子:
访问中间元素
假设你想要获取列表的第五个元素。
在链表中,你需要获取:
- 第一个 cons 单元格
- 然后获取该单元格的尾部以获取第二个元素
- 然后获取该单元格的尾部以获取第三个元素
- 然后获取该单元格的尾部以获取第四个元素
- 最后再获取该单元格的尾部以获取第五个元素
因此,你必须通过 5 个引用进行访问!
用数组来做就简单多了:你知道第一个元素的引用。只需要访问右边 4 个位置的引用,因为这些元素都在连续的内存范围内!
如果你需要多次访问非连续的元素列表,那么数组会更好。
在中间插入元素
现在想象一下,你想要在列表中间插入一个元素。
使用链表:
- 找到插入点之前的最后一个元素对应的 cons 单元格。
- 创建一个新的 cons 单元格,其头部指向你要添加的元素,尾部与你刚刚定位的 cons 单元格相同。
- 现在可以更改该单元格的尾部,使其指向新创建的单元格。
使用数组,就像在中间添加元素时一样,您需要将插入点右侧的每个元素向右移动一个空间!
在这种情况下,链表显然更加优秀。
list(1, 2, 3 , 4, 5)
不起作用 :-) - mgilson