python实现单链表

发布时间：2019-07-17 10:08:44编辑：auto阅读（1345）

#encoding:utf-8

import sys

class Lnode():
    def __init__(self,elem,next=None):
        self.elem = elem    #节点的值
        self.next = next    #指向下一个节点
    def getelem(self):
        return self.elem
    def getnext(self):
        return self.next

class linklist(object):
    def __init__(self):
        L = Lnode(None,None)
        self.head = L       #定义头节点
        self.length = 0     #链表元素个数
    # 链表是否为空
    def isempty(self):
        if self.head.next is None:
            return True
        else:
            return False
    def getlength(self):
        return self.length

    #尾部添加
    def append(self,elem):
        newNode = Lnode(elem)
        if self.head.next is None:
            self.head.next = newNode
        else:
            p = self.head
            while p.next is not None:
                p = p.next
            p.next = newNode
        self.length += 1

    #头部添加
    def headpush(self,elem):
        newNode = Lnode(elem)
        if self.isempty():
            self.head.next = newNode
        else:
            newNode.next = self.head.next
            self.head.next = newNode
        self.length += 1


    #在指定元素的位置后面插入
    def insertafter(self,elem,newelem):
        newNode = Lnode(newelem)
        if self.find(elem) == -1:
            print "%s in the link list" %elem
            return -1
        else:
            #如果在链表中找到元素elem
            p = self.find(elem)
            if p.next is None:
                p.next = newNode
            else:
                newNode.next = p.next
                p.next = newNode
            self.length += 1

    # 在指定元素的位置前面插入
    def insertbefor(self,elem,newelem):
        newNode = Lnode(newelem)
        if self.find(elem) == -1:
            print "%s in not the link list" % elem
            return -1
        else:
            p = self.head
            q = self.find(elem)
            while p is not None:
                if p.next == q:
                    break
                p = p.next
            newNode.next = q
            p.next = newNode
            self.length += 1


    #遍历链表
    def for_each(self):
        if self.head.next is None:
            print "empty"
            return
        else:
            p = self.head
            while p.next is not None:
                p = p.next
                sys.stdout.write("%s " %(p.elem))
            print
            return

    #查找元素，返回指向该元素的节点
    def find(self,elem):
        #找到元素返回节点，未找到返回-1
        if self.isempty():
            print "sorry,is empty"
            return -1
        else:
            p = self.head
            while p is not None:
                if p.elem == elem:
                    return p
                else:
                    p = p.next
            return -1
    #修改指定元素
    def modify(self,elem,newelem):
        if self.find(elem) != -1:
            #如果找到
            p = self.find(elem)
            p.elem = newelem
            return 0
        else:
            print "%s is not in the linklist" %elem
            return -1
    #删除指定元素
    def delnode(self,elem):
        if self.find(elem) != -1:
            #如果找到
            p = self.find(elem)
            q = self.head
            while q.next != p:
                q = q.next
            q.next = p.next
            p.next = None

        else:
            print "%s is not in the linklist" %elem
            return -1

def main():

    #创建链表
    ll = linklist()
    print ll.isempty()
    #尾部添加元素
    ll.append(3)
    ll.append(4)
    ll.append(5)
    ll.for_each()
    print ll.getlength()

    #首部添加元素
    ll.headpush(2)
    ll.for_each()
    print ll.getlength()

    #查找元素
    print ll.find(3).elem
    ll.insertafter(3,3.3)
    ll.for_each()
    print ll.getlength()

    #测试后插法
    ll.insertafter(1,1.1)

    #测试前插法
    ll.insertbefor(5,3.9)
    ll.for_each()
    print ll.getlength()

    #修改指定元素
    ll.modify(3.9,44)
    ll.for_each()

    ll.modify(3.8,88)

    #删除指定元素
    ll.delnode(3.3)
    ll.for_each()
    ll.delnode(2)
    ll.delnode(2)
    ll.delnode(3)
    ll.delnode(4)
    ll.delnode(44)
    ll.delnode(5)


    ll.for_each()




if __name__ == '__main__':
    main()

运行结果




True

3 4 5 

3

2 3 4 5 

4

3

2 3 3.3 4 5 

5

1 in the link list

2 3 3.3 4 3.9 5 

6

2 3 3.3 4 44 5 

3.8 is not in the linklist

2 3 4 44 5 

2 is not in the linklist

empty




Process finished with exit code 0

关键字：