Python链表

Question

在python中使用链表的最简单方法是什么？在方案中，链表仅由定义’(1 2 3 4 5)。实际上，Python的list [1, 2, 3, 4, 5]和tuples (1, 2, 3, 4, 5)不是链接列表，而链接列表具有一些不错的属性，例如恒定时间串联，并且能够引用其中的单独部分。使它们一成不变，并且它们真的很容易使用！

Answer 1

以下是一些基于Martin诉Löwis陈述的列表函数：

cons   = lambda el, lst: (el, lst)
mklist = lambda *args: reduce(lambda lst, el: cons(el, lst), reversed(args), None)
car = lambda lst: lst[0] if lst else lst
cdr = lambda lst: lst[1] if lst else lst
nth = lambda n, lst: nth(n-1, cdr(lst)) if n > 0 else car(lst)
length  = lambda lst, count=0: length(cdr(lst), count+1) if lst else count
begin   = lambda *args: args[-1]
display = lambda lst: begin(w("%s " % car(lst)), display(cdr(lst))) if lst else w("nil\n")

哪里 w = sys.stdout.write

尽管在Raymond Hettinger的有序集配方中使用了双向链接列表，但单链接列表在Python中没有实际价值。

除了教育方面的问题外，我从未在Python中使用过单链接列表。

托马斯·沃特纳尔（ Thomas Watnedal）提出了很好的教育资源，《如何像计算机科学家一样思考》，第17章：链接列表：

链表是：

• 空列表，由“无”表示，或
• 包含货物对象和对链表的引用的节点。

class Node: 
  def __init__(self, cargo=None, next=None): 
    self.car = cargo 
    self.cdr = next    
  def __str__(self): 
    return str(self.car)

def display(lst):
  if lst:
    w("%s " % lst)
    display(lst.cdr)
  else:
    w("nil\n")