问题描述：

在 Python 中使用链表的最简单方法是什么？在 Scheme 中，链表的定义很简单'(1 2 3 4 5)。

事实上， Python 的列表[1, 2, 3, 4, 5]和元组(1, 2, 3, 4, 5)并不是链表，链表具有一些不错的特性，例如常量时间连接，以及能够引用其中的不同部分。如果使它们不可变，那么它们就真的很容易使用！

解决方案 1：

对于某些需求，双端队列也可能有用。您可以以 O(1) 成本在双端队列的两端添加和删除项目。

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

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

解决方案 2：

以下是一些基于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 中没有实际价值。

除了教育用途之外，我从未在 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
")

解决方案 3：

我前几天写了这个

#! /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()

解决方案 4：

可接受的答案相当复杂。这是一个更标准的设计：

L = LinkedList()
L.insert(1)
L.insert(1)
L.insert(2)
L.insert(4)
print L
L.clear()
print L

它是一个简单的LinkedList类，基于简单的 C++ 设计和第 17 章：链表，由Thomas Watnedal推荐。

class Node:
    def __init__(self, value = None, next = None):
        self.value = value
        self.next = next

    def __str__(self):
        return 'Node ['+str(self.value)+']'

class LinkedList:
    def __init__(self):
        self.first = None
        self.last = None

    def insert(self, x):
        if self.first == None:
            self.first = Node(x, None)
            self.last = self.first
        elif self.last == self.first:
            self.last = Node(x, None)
            self.first.next = self.last
        else:
            current = Node(x, None)
            self.last.next = current
            self.last = current

    def __str__(self):
        if self.first != None:
            current = self.first
            out = 'LinkedList [
' +str(current.value) +'
'
            while current.next != None:
                current = current.next
                out += str(current.value) + '
'
            return out + ']'
        return 'LinkedList []'

    def clear(self):
        self.__init__()

解决方案 5：

不可变列表最好通过二元组来表示，其中 None 表示 NIL。为了简单地制定此类列表，您可以使用此函数：

def mklist(*args):
    result = None
    for element in reversed(args):
        result = (element, result)
    return result

为了使用这样的列表，我宁愿提供整个 LISP 函数集合（即第一个、第二个、第 n 个等等），而不是引入方法。

解决方案 6：

这是链接列表类的一个稍微复杂一点的版本，具有与 Python 序列类型类似的接口（即支持索引、切片、与任意序列连接等）。它应该具有 O(1) 前置功能，除非需要，否则不会复制数据，并且可以与元组互换使用。

它不会像 lisp cons 单元那样节省空间或时间，因为 python 类显然更重一些（您可以使用“ __slots__ = '_head','_tail'”稍微改进以减少内存使用量）。但是它将具有所需的大 O 性能特征。

使用示例：

>>> l = LinkedList([1,2,3,4])
>>> l
LinkedList([1, 2, 3, 4])
>>> l.head, l.tail
(1, LinkedList([2, 3, 4]))

# Prepending is O(1) and can be done with:
LinkedList.cons(0, l)
LinkedList([0, 1, 2, 3, 4])
# Or prepending arbitrary sequences (Still no copy of l performed):
[-1,0] + l
LinkedList([-1, 0, 1, 2, 3, 4])

# Normal list indexing and slice operations can be performed.
# Again, no copy is made unless needed.
>>> l[1], l[-1], l[2:]
(2, 4, LinkedList([3, 4]))
>>> assert l[2:] is l.next.next

# For cases where the slice stops before the end, or uses a
# non-contiguous range, we do need to create a copy.  However
# this should be transparent to the user.
>>> LinkedList(range(100))[-10::2]
LinkedList([90, 92, 94, 96, 98])

执行：

import itertools

class LinkedList(object):
    """Immutable linked list class."""

    def __new__(cls, l=[]):
        if isinstance(l, LinkedList): return l # Immutable, so no copy needed.
        i = iter(l)
        try:
            head = i.next()
        except StopIteration:
            return cls.EmptyList   # Return empty list singleton.

        tail = LinkedList(i)

        obj = super(LinkedList, cls).__new__(cls)
        obj._head = head
        obj._tail = tail
        return obj

    @classmethod
    def cons(cls, head, tail):
        ll =  cls([head])
        if not isinstance(tail, cls):
            tail = cls(tail)
        ll._tail = tail
        return ll

    # head and tail are not modifiable
    @property  
    def head(self): return self._head

    @property
    def tail(self): return self._tail

    def __nonzero__(self): return True

    def __len__(self):
        return sum(1 for _ in self)

    def __add__(self, other):
        other = LinkedList(other)

        if not self: return other   # () + l = l
        start=l = LinkedList(iter(self))  # Create copy, as we'll mutate

        while l:
            if not l._tail: # Last element?
                l._tail = other
                break
            l = l._tail
        return start

    def __radd__(self, other):
        return LinkedList(other) + self

    def __iter__(self):
        x=self
        while x:
            yield x.head
            x=x.tail

    def __getitem__(self, idx):
        """Get item at specified index"""
        if isinstance(idx, slice):
            # Special case: Avoid constructing a new list, or performing O(n) length 
            # calculation for slices like l[3:].  Since we're immutable, just return
            # the appropriate node. This becomes O(start) rather than O(n).
            # We can't do this for  more complicated slices however (eg [l:4]
            start = idx.start or 0
            if (start >= 0) and (idx.stop is None) and (idx.step is None or idx.step == 1):
                no_copy_needed=True
            else:
                length = len(self)  # Need to calc length.
                start, stop, step = idx.indices(length)
                no_copy_needed = (stop == length) and (step == 1)

            if no_copy_needed:
                l = self
                for i in range(start): 
                    if not l: break # End of list.
                    l=l.tail
                return l
            else:
                # We need to construct a new list.
                if step < 1:  # Need to instantiate list to deal with -ve step
                    return LinkedList(list(self)[start:stop:step])
                else:
                    return LinkedList(itertools.islice(iter(self), start, stop, step))
        else:       
            # Non-slice index.
            if idx < 0: idx = len(self)+idx
            if not self: raise IndexError("list index out of range")
            if idx == 0: return self.head
            return self.tail[idx-1]

    def __mul__(self, n):
        if n <= 0: return Nil
        l=self
        for i in range(n-1): l += self
        return l
    def __rmul__(self, n): return self * n

    # Ideally we should compute the has ourselves rather than construct
    # a temporary tuple as below.  I haven't impemented this here
    def __hash__(self): return hash(tuple(self))

    def __eq__(self, other): return self._cmp(other) == 0
    def __ne__(self, other): return not self == other
    def __lt__(self, other): return self._cmp(other) < 0
    def __gt__(self, other): return self._cmp(other) > 0
    def __le__(self, other): return self._cmp(other) <= 0
    def __ge__(self, other): return self._cmp(other) >= 0

    def _cmp(self, other):
        """Acts as cmp(): -1 for self<other, 0 for equal, 1 for greater"""
        if not isinstance(other, LinkedList):
            return cmp(LinkedList,type(other))  # Arbitrary ordering.

        A, B = iter(self), iter(other)
        for a,b in itertools.izip(A,B):
           if a<b: return -1
           elif a > b: return 1

        try:
            A.next()
            return 1  # a has more items.
        except StopIteration: pass

        try:
            B.next()
            return -1  # b has more items.
        except StopIteration: pass

        return 0  # Lists are equal

    def __repr__(self):
        return "LinkedList([%s])" % ', '.join(map(repr,self))

class EmptyList(LinkedList):
    """A singleton representing an empty list."""
    def __new__(cls):
        return object.__new__(cls)

    def __iter__(self): return iter([])
    def __nonzero__(self): return False

    @property
    def head(self): raise IndexError("End of list")

    @property
    def tail(self): raise IndexError("End of list")

# Create EmptyList singleton
LinkedList.EmptyList = EmptyList()
del EmptyList

解决方案 7：

llist——Python 的链接列表数据类型

llist 模块实现链表数据结构。它支持双向链表，即dllist和单向链表数据结构sllist。

dllist 对象

该对象代表双向链表数据结构。

first

dllistnode列表中的第一个对象。None如果列表为空。

last

dllistnode列表中的最后一个对象。如果列表为空，则为 None。

dllist 对象还支持以下方法：

append(x)

添加x到列表的右侧并返回插入的内容dllistnode。

appendleft(x)

添加x到列表左侧并返回插入的内容dllistnode。

appendright(x)

添加x到列表的右侧并返回插入的内容dllistnode。

clear()

从列表中删除所有节点。

extend(iterable)

将元素附加iterable到列表的右侧。

extendleft(iterable)

将元素附加iterable到列表的左侧。

extendright(iterable)

将元素附加iterable到列表的右侧。

insert(x[, before])

如果未指定，则添加x到列表的右侧，否则插入到的左侧。返回插入的。before`xdllistnode beforedllistnode`

nodeat(index)

返回 处的节点（类型dllistnode）index。

pop()

从列表右侧移除并返回一个元素的值。

popleft()

从列表左侧移除并返回一个元素的值。

popright()

从列表右侧移除并返回元素的值

remove(node)

从列表中删除node并返回其中存储的元素。

dllistnode对象

班级llist.dllistnode([value])

返回一个新的双向链表节点，用 初始化（可选）value。

dllistnode对象提供以下属性：

next

列表中的下一个节点。此属性是只读的。

prev

列表中的上一个节点。此属性是只读的。

value

存储在此节点中的值。
根据此参考编译

列表

类llist.sllist([iterable])
返回一个使用来自的元素初始化的新单链表iterable。如果未指定可迭代对象，则新列表sllist为空。

此对象定义了一组类似的属性和操作sllist。有关更多信息，请参阅此参考。

解决方案 8：

class Node(object):
    def __init__(self, data=None, next=None):
        self.data = data
        self.next = next

    def setData(self, data):
        self.data = data
        return self.data

    def setNext(self, next):
        self.next = next

    def getNext(self):
        return self.next

    def hasNext(self):
        return self.next != None


class singleLinkList(object):

    def __init__(self):
        self.head = None

    def isEmpty(self):
        return self.head == None

    def insertAtBeginning(self, data):
        newNode = Node()
        newNode.setData(data)

        if self.listLength() == 0:
            self.head = newNode
        else:
            newNode.setNext(self.head)
            self.head = newNode

    def insertAtEnd(self, data):
        newNode = Node()
        newNode.setData(data)

        current = self.head

        while current.getNext() != None:
            current = current.getNext()

        current.setNext(newNode)

    def listLength(self):
        current = self.head
        count = 0

        while current != None:
            count += 1
            current = current.getNext()
        return count

    def print_llist(self):
        current = self.head
        print("List Start.")
        while current != None:
            print(current.getData())
            current = current.getNext()

        print("List End.")



if __name__ == '__main__':
    ll = singleLinkList()
    ll.insertAtBeginning(55)
    ll.insertAtEnd(56)
    ll.print_llist()
    print(ll.listLength())

解决方案 9：

我根据Nick Stinemates 的介绍创建了这个附加功能

def add_node_at_end(self, data):
    new_node = Node()
    node = self.curr_node
    while node:
        if node.next == None:
            node.next = new_node
            new_node.next = None
            new_node.data = data
        node = node.next

他的方法是先在开头添加新节点，而我见过的很多实现通常是在结尾添加新节点，但无论如何，这样做很有趣。

解决方案 10：

以下是我想到的。它与本线程中Riccardo C. 的类似，只是它按顺序而不是反向打印数字。我还将 LinkedList 对象设为 Python 迭代器，以便像打印普通 Python 列表一样打印列表。

class Node:

    def __init__(self, data=None):
        self.data = data
        self.next = None

    def __str__(self):
        return str(self.data)


class LinkedList:

    def __init__(self):
        self.head = None
        self.curr = None
        self.tail = None

    def __iter__(self):
        return self

    def next(self):
        if self.head and not self.curr:
            self.curr = self.head
            return self.curr
        elif self.curr.next:
            self.curr = self.curr.next
            return self.curr
        else:
            raise StopIteration

    def append(self, data):
        n = Node(data)
        if not self.head:
            self.head = n
            self.tail = n
        else:
            self.tail.next = n
            self.tail = self.tail.next


# Add 5 nodes
ll = LinkedList()
for i in range(1, 6):
    ll.append(i)

# print out the list
for n in ll:
    print n

"""
Example output:
$ python linked_list.py
1
2
3
4
5
"""

解决方案 11：

我只是把它当作一个有趣的玩具。只要你不触碰下划线前缀的方法，它应该是不可变的，并且它实现了许多 Python 魔法，如索引和len。

解决方案 12：

以下是我的解决方案：

执行

class Node:
  def __init__(self, initdata):
    self.data = initdata
    self.next = None

  def get_data(self):
    return self.data

  def set_data(self, data):
    self.data = data

  def get_next(self):
    return self.next

  def set_next(self, node):
    self.next = node


# ------------------------ Link List class ------------------------------- #
class LinkList:

  def __init__(self):
    self.head = None

  def is_empty(self):
    return self.head == None

  def traversal(self, data=None):
    node = self.head
    index = 0
    found = False
    while node is not None and not found:
      if node.get_data() == data:
        found = True
      else:
        node = node.get_next()
        index += 1
    return (node, index)

  def size(self):
    _, count = self.traversal(None)
    return count

  def search(self, data):
    node, _ = self.traversal(data)
    return node

  def add(self, data):
    node = Node(data)
    node.set_next(self.head)
    self.head = node

  def remove(self, data):
    previous_node = None
    current_node = self.head
    found = False
    while current_node is not None and not found:
      if current_node.get_data() == data:
        found = True
        if previous_node:
          previous_node.set_next(current_node.get_next())
        else:
          self.head = current_node
      else:
        previous_node = current_node
        current_node = current_node.get_next()
    return found

用法

link_list = LinkList()
link_list.add(10)
link_list.add(20)
link_list.add(30)
link_list.add(40)
link_list.add(50)
link_list.size()
link_list.search(30)
link_list.remove(20)

最初的实现思路

http://interactivepython.org/runestone/static/pythonds/BasicDS/ImplementinganUnorderedListLinkedLists.html

解决方案 13：

使用不可变链表时，可以考虑直接使用Python的元组。

ls = (1, 2, 3, 4, 5)

def first(ls): return ls[0]
def rest(ls): return ls[1:]

它确实很简单，并且您可以保留附加功能，例如 len(ls)、ls 中的 x 等。

解决方案 14：

class LL(object):
    def __init__(self,val):
        self.val = val
        self.next = None

    def pushNodeEnd(self,top,val):
        if top is None:
            top.val=val
            top.next=None
        else:
            tmp=top
            while (tmp.next != None):
                tmp=tmp.next        
            newNode=LL(val)
            newNode.next=None
            tmp.next=newNode

    def pushNodeFront(self,top,val):
        if top is None:
            top.val=val
            top.next=None
        else:
            newNode=LL(val)
            newNode.next=top
            top=newNode

    def popNodeFront(self,top):
        if top is None:
            return
        else:
            sav=top
            top=top.next
        return sav

    def popNodeEnd(self,top):
        if top is None:
            return
        else:
            tmp=top
            while (tmp.next != None):
                prev=tmp
                tmp=tmp.next
            prev.next=None
        return tmp

top=LL(10)
top.pushNodeEnd(top, 20)
top.pushNodeEnd(top, 30)
pop=top.popNodeEnd(top)
print (pop.val)

解决方案 15：

我已将 Python 2.x 和 3.x 单链表类放在https://pypi.python.org/pypi/linked_list_mod/

它通过 CPython 2.7、CPython 3.4、Pypy 2.3.1、Pypy3 2.3.1 和 Jython 2.7b2 进行了测试，并附带一个很好的自动化测试套件。

它还包括 LIFO 和 FIFO 类。

但它们并不是一成不变的。

解决方案 16：

class LinkedStack:
'''LIFO Stack implementation using a singly linked list for storage.'''

_ToList = []

#---------- nested _Node class -----------------------------
class _Node:
    '''Lightweight, nonpublic class for storing a singly linked node.'''
    __slots__ = '_element', '_next'     #streamline memory usage

    def __init__(self, element, next):
        self._element = element
        self._next = next

#--------------- stack methods ---------------------------------
def __init__(self):
    '''Create an empty stack.'''
    self._head = None
    self._size = 0

def __len__(self):
    '''Return the number of elements in the stack.'''
    return self._size

def IsEmpty(self):
    '''Return True if the stack is empty'''
    return  self._size == 0

def Push(self,e):
    '''Add element e to the top of the Stack.'''
    self._head = self._Node(e, self._head)      #create and link a new node
    self._size +=1
    self._ToList.append(e)

def Top(self):
    '''Return (but do not remove) the element at the top of the stack.
       Raise exception if the stack is empty
    '''

    if self.IsEmpty():
        raise Exception('Stack is empty')
    return  self._head._element             #top of stack is at head of list

def Pop(self):
    '''Remove and return the element from the top of the stack (i.e. LIFO).
       Raise exception if the stack is empty
    '''
    if self.IsEmpty():
        raise Exception('Stack is empty')
    answer = self._head._element
    self._head = self._head._next       #bypass the former top node
    self._size -=1
    self._ToList.remove(answer)
    return answer

def Count(self):
    '''Return how many nodes the stack has'''
    return self.__len__()

def Clear(self):
    '''Delete all nodes'''
    for i in range(self.Count()):
        self.Pop()

def ToList(self):
    return self._ToList

解决方案 17：

这是我的简单实现：

class Node:
    def __init__(self):
        self.data = None
        self.next = None
    def __str__(self):
        return "Data %s: Next -> %s"%(self.data, self.next)

class LinkedList:
    def __init__(self):
        self.head = Node()
        self.curNode = self.head
    def insertNode(self, data):
        node = Node()
        node.data = data
        node.next = None
        if self.head.data == None:
            self.head = node
            self.curNode = node
        else:
            self.curNode.next = node
            self.curNode = node
    def printList(self):
        print self.head

l = LinkedList()
l.insertNode(1)
l.insertNode(2)
l.insertNode(34)

输出：

Data 1: Next -> Data 2: Next -> Data 34: Next -> Data 4: Next -> None

解决方案 18：

我也根据一些教程编写了一个单链表，它有两个基本的节点和链表类，以及一些用于插入、删除、反转、排序等的附加方法。

它不是最好或最简单的，但工作起来还不错。

"""