Python链表 [英] Python Linked List

问题描述

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

What's the easiest way to use a linked list in python? In scheme, a linked list is defined simply by '(1 2 3 4 5). Python's lists, [1, 2, 3, 4, 5], and tuples, (1, 2, 3, 4, 5), are not, in fact, linked lists, and linked lists have some nice properties such as constant-time concatenation, and being able to reference separate parts of them. Make them immutable and they are really easy to work with!

推荐答案

以下是一些基于的列表函数马丁诉路易丝的陈述:

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中没有实际价值.

Although doubly linked lists are famously used in Raymond Hettinger's ordered set recipe, singly linked lists have no practical value in Python.

我从不在Python中使用单链接列表来解决除教育以外的任何问题.

I've never used a singly linked list in Python for any problem except educational.

Thomas Watnedal 建议良好的教育资源

Thomas Watnedal suggested a good educational resource How to Think Like a Computer Scientist, Chapter 17: Linked lists:

链接列表为:

• 空白列表，由None或
表示

• 一个包含货物对象和对链表的引用的节点.

• the empty list, represented by None, or

• a node that contains a cargo object and a reference to a linked list.

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")

这篇关于Python链表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！