Python 学习:单链表的实现

vivion34

　　要定义一个单链表,首先定义链表元素: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