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!

推荐答案

这里是一些基于的列表函数Martin v. 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
")

其中 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 建议一个很好的教育资源如何像计算机科学家一样思考，第 17 章:链表:

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

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