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

Element的构造函数很简单,只是用参数初始化新的节点.

接下来,我们定义LinkedList的初始化函数:

    def __init__(self):

        self._head = None
        self._tail = None

这个函数初始化列表的头和尾元素.
另,我们也定义一个链表清空函数,用于将链表初始化为空链表:

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

我们为链表类定义3个属性:head,tail和isEmpty

,分别表示链表的头,尾和判断链表是否为空.

    def getHead(self):
        return self._head
    head = property(
        fget = lambda self: self.getHead())
    def getTail(self):
        return self._tail
    tail = property(
        fget = lambda self: self.getTail())
    def IsEmpty(self):
        return self._head == None
    isEmpty = property(
        fget = lambda self: self.IsEmpty())

我们为链表类再定义两个属性,first和last, 用于获得链表的头和尾元素的值.当链表为空时,抛出ContainerEmpty异常:

    def getFirst(self):
        if self._head is None:
            raise ContainerEmpty
        return self._head._datum
    first = property(
        fget = lambda self: self.getFirst())

    def getLast(self):
        if self._tail is None:
            raise ContainerEmpty
        return self._tail._datum
    last = property(
        fget = lambda self: self.getLast ())

prepend函数用于将元素插入链表头,这样,插入后的元素变成新的链表头:

    def prepend(self,item):
        tmp = self.Element (self,item,self._head)
        if self._head is None:
            self._tail = tmp
        self._head = tmp

append函数用于给链表末尾添加元素.当链表为空时,添加的元素成为链表的头元素,然后,将元素添加到链表的尾部.

    def append(self,item):
        tmp = Element(self,item,None)
        if self._head is None:
            self._head = tmp
        else:
            self._tail._next = tmp
        self._tail = tmp

给链表定义copy函数,它是 一个浅拷贝函数,首先建立一个空链表,然后逐个添加元素:

    def __copy__(self):
        lst = LinkedList()
        ptr = self._head
        while ptr is not None:
            lst.append(ptr._datum)
            ptr = ptr._next
        return lst

定义链表的删除函数extract,用于删除链表中的特定元素.首先查找该元素的位置,如果不存在,提示KeyError异常.当元素是头元素时,将其下一个节点变为头元素;当其节点是尾元素时,将上一个节点变成尾元素.然后删除它.

    def extract(self,item):
        prePtr = ptr = self._head
        while ptr is not None and ptr._datum is not item:
            prePtr = ptr
            ptr = ptr._next
        if ptr is None:
            raise KeyError
        if ptr == self._head:
            self._head = ptr._next
        else:
            prePtr._next = ptr._next
        if ptr == self._tail:
            self._tail = prePtr

find函数用于查找指定的元素,当没有找到时,返回None:

    def find(self,item):
        ptr = self._head
        while ptr is not None and ptr._datum is not item:
            ptr = ptr._next
        return ptr

至此,一个简单的单链表就已经实现了,可以继续扩展它的功能.