不可变列表最好通过两个元组表示，其中 Nothing 表示 NIL。为了简单地列出这些清单，您可以使用以下函数:

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

为了处理这样的列表，我宁愿提供 LISP 函数的整个集合(例如，第一个、第二个、第 n 个等等) ，而不是引入方法。

我前几天写的

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

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

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


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

它真的很简单，而且您可以保留像 len (ls)、 x 在 ls 中等等的附加函数。

下面是链表类的一个稍微复杂一些的版本，它与 python 的序列类型有一个类似的接口(即。支持索引、切片、任意序列的连接等)。它应该有 O (1)预置，不复制数据，除非它需要，并且可以与元组很好地交换使用。

它不会像 lisp con 单元格那样具有空间和时间效率，因为 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

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

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


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

下面是一些基于 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章: 链表:

链表可以是:

• 空列表，由 Nothing 表示，或者

• 包含货物对象和对链表的引用的节点。

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

公认的答案相当复杂。下面是一个更为标准的设计:

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 [\n' +str(current.value) +'\n'
while current.next != None:
current = current.next
out += str(current.value) + '\n'
return out + ']'
return 'LinkedList []'


def clear(self):
self.__init__()

我将这个附加函数基于 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

他的方法是在开始的时候添加新的节点，而我见过很多实现，通常在结束的时候添加一个新的节点，但是无论如何，这样做是很有趣的。

我认为下面的实现很好地填补了这个空白。

'''singly linked lists, by Yingjie Lan, December 1st, 2011'''


class linkst:
'''Singly linked list, with pythonic features.
The list has pointers to both the first and the last node.'''
__slots__ = ['data', 'next'] #memory efficient
def __init__(self, iterable=(), data=None, next=None):
'''Provide an iterable to make a singly linked list.
Set iterable to None to make a data node for internal use.'''
if iterable is not None:
self.data, self.next = self, None
self.extend(iterable)
else: #a common node
self.data, self.next = data, next


def empty(self):
'''test if the list is empty'''
return self.next is None


def append(self, data):
'''append to the end of list.'''
last = self.data
self.data = last.next = linkst(None, data)
#self.data = last.next


def insert(self, data, index=0):
'''insert data before index.
Raise IndexError if index is out of range'''
curr, cat = self, 0
while cat < index and curr:
curr, cat = curr.next, cat+1
if index<0 or not curr:
raise IndexError(index)
new = linkst(None, data, curr.next)
if curr.next is None: self.data = new
curr.next = new


def reverse(self):
'''reverse the order of list in place'''
current, prev = self.next, None
while current: #what if list is empty?
next = current.next
current.next = prev
prev, current = current, next
if self.next: self.data = self.next
self.next = prev


def delete(self, index=0):
'''remvoe the item at index from the list'''
curr, cat = self, 0
while cat < index and curr.next:
curr, cat = curr.next, cat+1
if index<0 or not curr.next:
raise IndexError(index)
curr.next = curr.next.next
if curr.next is None: #tail
self.data = curr #current == self?


def remove(self, data):
'''remove first occurrence of data.
Raises ValueError if the data is not present.'''
current = self
while current.next: #node to be examined
if data == current.next.data: break
current = current.next #move on
else: raise ValueError(data)
current.next = current.next.next
if current.next is None: #tail
self.data = current #current == self?


def __contains__(self, data):
'''membership test using keyword 'in'.'''
current = self.next
while current:
if data == current.data:
return True
current = current.next
return False


def __iter__(self):
'''iterate through list by for-statements.
return an iterator that must define the __next__ method.'''
itr = linkst()
itr.next = self.next
return itr #invariance: itr.data == itr


def __next__(self):
'''the for-statement depends on this method
to provide items one by one in the list.
return the next data, and move on.'''
#the invariance is checked so that a linked list
#will not be mistakenly iterated over
if self.data is not self or self.next is None:
raise StopIteration()
next = self.next
self.next = next.next
return next.data


def __repr__(self):
'''string representation of the list'''
return 'linkst(%r)'%list(self)


def __str__(self):
'''converting the list to a string'''
return '->'.join(str(i) for i in self)


#note: this is NOT the class lab! see file linked.py.
def extend(self, iterable):
'''takes an iterable, and append all items in the iterable
to the end of the list self.'''
last = self.data
for i in iterable:
last.next = linkst(None, i)
last = last.next
self.data = last


def index(self, data):
'''TODO: return first index of data in the list self.
Raises ValueError if the value is not present.'''
#must not convert self to a tuple or any other containers
current, idx = self.next, 0
while current:
if current.data == data: return idx
current, idx = current.next, idx+1
raise ValueError(data)

下面是我想到的。在这个线程中，它类似于 里卡多 · 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
"""

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


def insert(self, node):
if not self.next:
self.next = node
else:
self.next.insert(node)


def __str__(self):
if self.next:
return '%s -> %s' % (self.value, str(self.next))
else:
return ' %s ' % self.value


if __name__ == "__main__":
items = ['a', 'b', 'c', 'd', 'e']
ll = None
for item in items:
if ll:
next_ll = LinkedList(item)
ll.insert(next_ll)
else:
ll = LinkedList(item)
print('[ %s ]' % ll)

我刚刚做了 这个作为一个有趣的玩具。它应该是不可变的，只要不触及下划线前缀方法，并且它实现了一系列 Python 魔法，比如索引和 len。

首先，我假设您想要链表。实际上，您可以使用 collections.deque，它当前的 CPython 实现是一个块双向链表(每个块包含一个包含62个货物对象的数组)。它包含了链表的功能。您还可以在 pypi 上搜索名为 llist的 C 扩展。如果您想要链表 ADT 的纯 Python 和易于跟踪的实现，那么可以看看我的下面的最小实现。

class Node (object):
""" Node for a linked list. """
def __init__ (self, value, next=None):
self.value = value
self.next = next


class LinkedList (object):
""" Linked list ADT implementation using class.
A linked list is a wrapper of a head pointer
that references either None, or a node that contains
a reference to a linked list.
"""
def __init__ (self, iterable=()):
self.head = None
for x in iterable:
self.head = Node(x, self.head)


def __iter__ (self):
p = self.head
while p is not None:
yield p.value
p = p.next


def prepend (self, x):  # 'appendleft'
self.head = Node(x, self.head)


def reverse (self):
""" In-place reversal. """
p = self.head
self.head = None
while p is not None:
p0, p = p, p.next
p0.next = self.head
self.head = p0


if __name__ == '__main__':
ll = LinkedList([6,5,4])
ll.prepend(3); ll.prepend(2)
print list(ll)
ll.reverse()
print list(ll)

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)

我在 https://pypi.python.org/pypi/linked_list_mod/中放置了一个 Python 2.x 和3.x 单链接列表类

它使用 CPython 2.7、 CPython 3.4、 Pypy2.3.1、 Pypy32.3.1和 Jython 2.7 b2进行了测试，并附带了一个很好的自动化测试套件。

它还包括后进先出和先进先出类。

但它们并非不可改变。

我的两分钱

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


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




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


def add(self, x):
current = Node(x, None)
try:
self.last.next = current
except AttributeError:
self.first = current
self.last = current
else:
self.last = current


def print_list(self):
node = self.first
while node:
print node.value
node = node.next


ll = LinkedList()
ll.add("1st")
ll.add("2nd")
ll.add("3rd")
ll.add("4th")
ll.add("5th")


ll.print_list()


# Result:
# 1st
# 2nd
# 3rd
# 4th
# 5th

enter code here
enter code here


class node:
def __init__(self):
self.data = None
self.next = None
class linked_list:
def __init__(self):
self.cur_node = None
self.head = None
def add_node(self,data):
new_node = node()
if self.head == None:
self.head = new_node
self.cur_node = new_node
new_node.data = data
new_node.next = None
self.cur_node.next = new_node
self.cur_node = new_node
def list_print(self):
node = self.head
while node:
print (node.data)
node = node.next
def delete(self):
node = self.head
next_node = node.next
del(node)
self.head = next_node
a = linked_list()
a.add_node(1)
a.add_node(2)
a.add_node(3)
a.add_node(4)
a.delete()
a.list_print()

如果您只想创建一个简单的喜欢列表，那么请参考下面的代码

L = [1，[2，[3，[4，[5，[6，[7，[8，[9，[10]]]]]]]]

请访问 http://www.pythontutor.com/visualize.html#mode=edit以查看此鳕鱼的可视化执行

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

连结表类别

class LinkedStack:
# Nested Node Class
class Node:
def __init__(self, element, next):
self.__element = element
self.__next = next


def get_next(self):
return self.__next


def get_element(self):
return self.__element


def __init__(self):
self.head = None
self.size = 0
self.data = []


def __len__(self):
return self.size


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


def is_empty(self):
return self.size == 0


def push(self, e):
newest = self.Node(e, self.head)
self.head = newest
self.size += 1
self.data.append(newest)


def top(self):
if self.is_empty():
raise Empty('Stack is empty')
return self.head.__element


def pop(self):
if self.is_empty():
raise Empty('Stack is empty')
answer = self.head.element
self.head = self.head.next
self.size -= 1
return answer

用法

from LinkedStack import LinkedStack


x = LinkedStack()


x.push(10)
x.push(25)
x.push(55)




for i in range(x.size - 1, -1, -1):


print '|', x.data[i].get_element(), '|' ,
#next object


if x.data[i].get_next() == None:
print '--> None'
else:
print  x.data[i].get_next().get_element(), '-|---->  ',

输出

| 55 | 25 -|---->   | 25 | 10 -|---->   | 10 | --> None

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

下面是我的简单实现:

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

Llist ー Python 的链表数据类型

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

Dllist 对象

此对象表示一个双向链表数据结构。

first

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

last

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

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

如果未指定 before，则将 x添加到列表的右侧，或将 x插入到 dllistnode before的左侧。返回插入 dllistnode。

nodeat(index)

返回位于 index的节点(类型为 dllistnode)。

pop()

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

popleft()

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

popright()

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

remove(node)

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

dllistnode物体

类别 llist.dllistnode([value])

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

dllistnode对象提供以下属性:

next

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

prev

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

value

存储在此节点中的。 根据此引用编译

斯利特

类别 llist.sllist([iterable]) 返回一个使用 iterable中的元素初始化的新单链表。如果没有指定 iterable，则新的 sllist为空。

为这个 sllist对象定义了一组类似的属性和操作

双倍链表示例 (另存为 linkedlist.py) :

class node:
def __init__(self, before=None, cargo=None, next=None):
self._previous = before
self._cargo = cargo
self._next  = next


def __str__(self):
return str(self._cargo) or None


class linkedList:
def __init__(self):
self._head = None
self._length = 0


def add(self, cargo):
n = node(None, cargo, self._head)
if self._head:
self._head._previous = n
self._head = n
self._length += 1


def search(self,cargo):
node = self._head
while (node and node._cargo != cargo):
node = node._next
return node


def delete(self,cargo):
node = self.search(cargo)
if node:
prev = node._previous
nx = node._next
if prev:
prev._next = node._next
else:
self._head = nx
nx._previous = None
if nx:
nx._previous = prev
else:
prev._next = None
self._length -= 1


def __str__(self):
print 'Size of linked list: ',self._length
node = self._head
while node:
print node
node = node._next

Testing (另存为 test.py) :

from linkedlist import node, linkedList


def test():


print 'Testing Linked List'


l = linkedList()


l.add(10)
l.add(20)
l.add(30)
l.add(40)
l.add(50)
l.add(60)


print 'Linked List after insert nodes:'
l.__str__()


print 'Search some value, 30:'
node = l.search(30)
print node


print 'Delete some value, 30:'
node = l.delete(30)
l.__str__()


print 'Delete first element, 60:'
node = l.delete(60)
l.__str__()


print 'Delete last element, 10:'
node = l.delete(10)
l.__str__()




if __name__ == "__main__":
test()

产出 :

Testing Linked List
Linked List after insert nodes:
Size of linked list:  6
60
50
40
30
20
10
Search some value, 30:
30
Delete some value, 30:
Size of linked list:  5
60
50
40
20
10
Delete first element, 60:
Size of linked list:  4
50
40
20
10
Delete last element, 10:
Size of linked list:  3
50
40
20