如何在Python中使用链表？

Question

在Python中，使用链表最简单的方法是什么呢？在Scheme语言中，链表可以简单地用 '(1 2 3 4 5) 来表示。

其实，Python的列表 [1, 2, 3, 4, 5] 和元组 (1, 2, 3, 4, 5) 并不是链表。链表有一些很不错的特点，比如可以快速地把两个链表拼接在一起，而且可以方便地引用它们的不同部分。如果把链表做成不可变的，那就更容易使用了！

Answer 1

我前几天写了这个

#! /usr/bin/env python

class Node(object):
    def __init__(self):
        self.data = None # contains the data
        self.next = None # contains the reference to the next node


class LinkedList:
    def __init__(self):
        self.cur_node = None

    def add_node(self, data):
        new_node = Node() # create a new node
        new_node.data = data
        new_node.next = self.cur_node # link the new node to the 'previous' node.
        self.cur_node = new_node #  set the current node to the new one.

    def list_print(self):
        node = self.cur_node # cant point to ll!
        while node:
            print node.data
            node = node.next



ll = LinkedList()
ll.add_node(1)
ll.add_node(2)
ll.add_node(3)

ll.list_print()

Answer 2

对于某些需求，双端队列（deque）可能会很有用。你可以在双端队列的两端都添加和删除项目，而且这个操作的时间开销是O(1)，也就是说，不管队列有多长，添加或删除的速度都是一样快的。

from collections import deque
d = deque([1,2,3,4])

print d
for x in d:
    print x
print d.pop(), d

Answer 3

这里有一些基于 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\n")

其中 w = sys.stdout.write

虽然双向链表在 Raymond Hettinger 的 有序集合示例 中非常有名，但在 Python 中，单向链表并没有实际的用途。

我从来没有在 Python 中用过单向链表来解决任何问题，除了学习用途。

Thomas Watnedal 推荐了一个很好的学习资源 《如何像计算机科学家一样思考》第17章：链表：

链表可以是：

• 空列表，用 None 表示，或者

• 一个节点，包含一个货物对象和一个指向链表的引用。

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