Python无内置数据结构实现prepend/get函数的代码解析求助

先看需求：实现无参函数nonlocalist，返回prepend和get两个函数，分别实现头部添加元素和获取第i个元素，且不能用列表、字典等内置数据结构。给出的代码如下：

def nonlocalist():
    get = lambda x: "Index out of range!"
    def prepend(value):
        nonlocal get
        f = get
        def get(i):
            if i == 0:
                return value
            return f(i - 1)
    return prepend, lambda x: get(x)

核心思路：用闭包模拟单向链表 #

这段代码的本质是用函数闭包保存状态，把每个函数当作链表的一个节点。每个节点（函数）保存当前元素的值，同时持有对前一个节点的引用（也就是之前定义的get函数），以此串联成类似链表的结构，完全绕开内置数据结构。

逐行拆解代码 #

1. 初始化尾节点

   get = lambda x: "Index out of range!"
   

   一开始get是一个返回"索引越界"的匿名函数，相当于链表的空尾节点——当访问不存在的位置时，就会触发这个函数。

2. 定义prepend函数：添加新节点

   def prepend(value):
       nonlocal get
       f = get
       def get(i):
           if i == 0:
               return value
           return f(i - 1)
   

   • nonlocal get：声明要修改外层函数nonlocalist里的get变量，否则Python会把get当作prepend内部的局部变量。
   • f = get：把当前的get函数保存到f里，这一步是保存对当前链表尾部的引用，新添加的节点要指向这个旧的尾部。
   • 重新定义get函数：这个新get就是链表的新节点：
     • 如果i == 0，直接返回当前要添加的value（因为新元素在头部，索引0就是它）；
     • 如果i > 0，就调用之前保存的f（旧的get函数）并传入i-1，相当于去前一个节点找第i-1个元素，递归回溯到目标位置。

3. 返回操作函数

   return prepend, lambda x: get(x)
   

   返回prepend（添加元素的函数）和一个匿名函数（用来调用最新的get）。这里用匿名函数是为了确保每次调用时都能拿到最新更新后的get函数，而不是初始化时的那个尾节点函数。

实际执行流程示例 #

我们用具体调用步骤来看：

1. 初始化链表：

   prepend_func, get_func = nonlocalist()
   

   此时get还是初始的尾节点函数，调用get_func(0)会返回"Index out of range!"。

2. 添加第一个元素：

   prepend_func(10)
   

   • 保存旧的get（尾节点函数）到f；
   • 新定义的get函数：i=0返回10，i>0调用f(i-1)（也就是尾节点函数）。

3. 添加第二个元素：

   prepend_func(20)
   

   • 保存当前的get（对应元素10的节点函数）到f；
   • 新定义的get函数：i=0返回20，i>0调用f(i-1)（去元素10的节点找第i-1个元素）。

4. 访问元素：

   • get_func(0) → 返回20（最新添加的头部元素）
   • get_func(1) → 调用保存的f（元素10的节点）并传入0，返回10
   • get_func(2) → 调用元素10的节点的f（尾节点函数）并传入1，返回"Index out of range!"

总结 #

这段代码完全利用闭包的环境保存状态和函数嵌套来模拟链表结构：

• 每次prepend都会生成一个新的get函数，作为链表的新头部节点；
• 每个节点函数通过闭包持有前一个节点的引用，实现索引访问时的递归回溯；
• 全程没有使用任何内置数据结构，纯粹用函数和闭包实现了列表的核心功能。

内容的提问来源于stack exchange，提问作者Proteus Yi