Python数据结构——链表的实现

链表由一系列不必在内存中相连的结构构成，这些对象按线性顺序排序。每个结构含有表元素和指向后继元素的指针。最后一个单元的指针指向NULL。为了方便链表的删除与插入操作，可以为链表添加一个表头。

 

 删除操作可以通过修改一个指针来实现。

插入操作需要执行两次指针调整。

1. 单向链表的实现

1.1 Node实现

    每个Node分为两部分。一部分含有链表的元素，可以称为数据域；另一部分为一指针，指向下一个Node。

class Node):
    __slots__=['_item','_next']    #限定Node实例的属性
    def __init__self,item):
        self._item=item
        self._next=None     #Node的指针部分默认指向None
    def getItemself):
        return self._item
    def getNextself):
        return self._next
    def setItemself,newitem):
        self._item=newitem
    def setNextself,newnext):
        self._next=newnext

1.2 SinglelinkedList的实现

class SingleLinkedList):   
    def __init__self):
        self._head=None    #初始化链表为空表
        self._size=0

1.3 检测链表是否为空

def isEmptyself):
    return self._head==None   

1.4 add在链表前端添加元素

def addself,item):
    temp=Nodeitem)
    temp.setNextself._head)
    self._head=temp

1.5 append在链表尾部添加元素

def appendself,item):
    temp=Nodeitem)
    if self.isEmpty):
        self._head=temp   #若为空表，将添加的元素设为第一个元素
    else:
        current=self._head
        while current.getNext)!=None:
            current=current.getNext)   #遍历链表
        current.setNexttemp)   #此时current为链表最后的元素
    

1.6 search检索元素是否在链表中

def searchself,item):
    current=self._head
    founditem=False
    while current!=None and not founditem:
        if current.getItem)==item:
            founditem=True
        else:
            current=current.getNext)
    return founditem

1.7 index索引元素在链表中的位置

def indexself,item):
    current=self._head
    count=0
    found=None
    while current!=None and not found:
        count+=1
        if current.getItem)==item:
            found=True
        else:
            current=current.getNext)
    if found:
        return count
    else:
        raise ValueError,'%s is not in linkedlist'%item  

1.8 remove删除链表中的某项元素

def removeself,item):
    current=self._head
    pre=None
    while current!=None:
        if current.getItem)==item:
            if not pre:
                self._head=current.getNext)
            else:
                pre.setNextcurrent.getNext))
            break
        else:
            pre=current
            current=current.getNext)

1.9 insert链表中插入元素

 def insertself,pos,item):
    if pos<=1:
        self.additem)
    elif pos>self.size):
        self.appenditem)
    else:
        temp=Nodeitem)
        count=1
        pre=None
        current=self._head
        while count<pos:
            count+=1
            pre=current
            current=current.getNext)
        pre.setNexttemp)
        temp.setNextcurrent)

全部代码

class Node):
    __slots__=['_item','_next']
    def __init__self,item):
        self._item=item
        self._next=None
    def getItemself):
        return self._item
    def getNextself):
        return self._next
    def setItemself,newitem):
        self._item=newitem
    def setNextself,newnext):
        self._next=newnext
        
class SingleLinkedList):   
    def __init__self):
        self._head=None  #初始化为空链表
    def isEmptyself):
        return self._head==None
    def sizeself):
        current=self._head
        count=0
        while current!=None:
            count+=1
            current=current.getNext)
        return count
    def travelself):
        current=self._head
        while current!=None:
            print current.getItem)
            current=current.getNext)
    def addself,item):
        temp=Nodeitem)
        temp.setNextself._head)
        self._head=temp

    def appendself,item):
        temp=Nodeitem)
        if self.isEmpty):
            self._head=temp   #若为空表，将添加的元素设为第一个元素
        else:
            current=self._head
            while current.getNext)!=None:
                current=current.getNext)   #遍历链表
            current.setNexttemp)   #此时current为链表最后的元素
    def searchself,item):
        current=self._head
        founditem=False
        while current!=None and not founditem:
            if current.getItem)==item:
                founditem=True
            else:
                current=current.getNext)
        return founditem
    def indexself,item):
        current=self._head
        count=0
        found=None
        while current!=None and not found:
            count+=1
            if current.getItem)==item:
                found=True
            else:
                current=current.getNext)
        if found:
            return count
        else:
            raise ValueError,'%s is not in linkedlist'%item                
    def removeself,item):
        current=self._head
        pre=None
        while current!=None:
            if current.getItem)==item:
                if not pre:
                    self._head=current.getNext)
                else:
                    pre.setNextcurrent.getNext))
                break
            else:
                pre=current
                current=current.getNext)                        
    def insertself,pos,item):
        if pos<=1:
            self.additem)
        elif pos>self.size):
            self.appenditem)
        else:
            temp=Nodeitem)
            count=1
            pre=None
            current=self._head
            while count<pos:
                count+=1
                pre=current
                current=current.getNext)
            pre.setNexttemp)
            temp.setNextcurrent)

if __name__=='__main__':
    a=SingleLinkedList)
    for i in range1,10):
        a.appendi)
    print a.size)
    a.travel)
    print a.search6)
    print a.index5)
    a.remove4)
    a.travel)
    a.insert4,100)
    a.travel)