Python单链表的简单实现方法

通常来说，要定义一个单链表,首先定义链表元素:Element.它包含3个字段:

list:标识自己属于哪一个list
datum:改元素的value
next:下一个节点的位置

具体实现代码如下：

class LinkedList(object):
 
 class Element(object):
 
 def __init__(self,list,datum,next): 
 self._list = list
 self._datum = datum 
 self._next = next

 def getDatum(self): 
 return self._datum

 datum = property(
 fget = lambda self: self.getDatum())

 def getNext(self):
 return self._next

 next = property(
 fget = lambda self: self.getNext())

 def __init__(self):

 self._head = None
 self._tail = None
 def getHead(self):
 return self._head 
 head = property(
 fget = lambda self: self.getHead()) 
 def prepend(self,item):
 tmp = self.Element (self,item,self._head)
 if self._head is None:
 self._tail = tmp 
 self._head = tmp 

 def insert(self, pos, item):
 i = 0
 p = self._head
 while p != None and i < pos -1:
 p = p._next
 i += 1
 if p == None or i > pos-1:
 return -1
 tmp = self.Element(self, item, p._next)
 p._next = tmp
 return 1
 def getItem(self, pos):
 i = 0
 p = self._head
 while p != None and i < pos -1:
 p = p._next
 i += 1
 if p == None or i > post-1:
 return -1
 return p._datum
 def delete(self, pos):
 i = 0
 p = self._head
 while p != None and i < pos -1:
 p = p._next
 i += 1
 if p == None or i > post-1:
 return -1
 q = p._next
 p._nex = q._next
 datum = p._datum
 return datum
 def setItem(self, pos, item):
 i = 0
 p = self._head
 while p != None and i < pos -1:
 p = p._next
 i += 1
 if p == None or i > post-1:
 return -1
 p._datum = item
 return 1
 def find(self, pos, item):
 i = 0
 p = self._head
 while p != None and i < pos -1:
 if p._datum == item:
 return 1
 p = p._next
 i += 1
 return -1
 def empty(self):
 if self._head == None:
 return 1
 return 0
 def size(self):
 i = 0
 p = self._head
 while p != None and i < pos -1:
 p = p._next
 i += 1
 return i

 def clear(self):
 self._head = None
 self._tail = None

test = LinkedList()
test.prepend('test0')
print test.insert(1, 'test')
print test.head.datum
print test.head.next.datum

希望本文所述对大家的Python程序设计有所帮助。