Python单链表的简单实现方法

本文实例讲述了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程序设计有所帮助。