python实现单向链表

旧城等待， 2022-05-31 14:06 278阅读 0赞

#因为没有指针，所以要构造一个Node的类
    class Node:
        #data和next都是私有变量所以都要get和set函数
        def __init__(self,data,next_node=None):
            self.__data=data
            self.__next=next_node
        def set_data(self,data):
            self.__data=data
        def get_data(self):
            return self.__data
        def set_next(self,next_node):
            self.__next=next_node
        def get_next(self):
            return self.__next
        
    class Linked_list:#单链表
        def __init__(self):
            self.__head=None
        def search(self,node,data):
            if node is None:
                return False
            if node.get_data()==data:
                return node
            return self.search(node.get.next(),data)
        def get_list(self):#获得一个链表的所有数据以列表的形式返回
            temp=self.__head
            l_list=[]
            while temp:
                l_list.append(temp.get_data())
                temp=temp.get_next()
            return l_list
        def insert_at_start(self,data):
            if self.__head is None:
                new_node=Node(data)
                self.__head=new_node
            else:
                new_node=Node(data)
                new_node.set_next(self.__head)
                self.__head=new_node
        def insert_after(self,next_node_data,data):
            new_node=Node(data)
            current_node=self.search(self.__head,next_node_data)
            new_node.set_next(current_node.get_next())
            current_node.set_next(new_node)
        def insert_at_end(self,data):
            new_node=Node(data)
            temp=self.__head
            if temp is None:
                self.__head = new_node
    
            else:
                while temp.get_next() is not None:
                    temp = temp.get_next()
                temp.set_next(new_node)
        def delete(self,data):
            temp=self.__head
            if temp is not None:
                if temp.get_data()==data:
                    self.__head=temp.get_next()
                    return
                else:
                    while temp.get_next() is not None:
                        if temp.get_data()==data:
                            break
                        prev=temp
                        temp=temp.get_next()
                    if temp.get_data()!=data:#这是最后一个数据
                        return
                    prev.set_next(temp.get_next())
    #示例程序
    mylinklist=Linked_list()
    for i in range(5,10):
        mylinklist.insert_at_end(i)
    print(mylinklist.get_list())
    mylinklist.delete(6)
    print(mylinklist.get_list())
    mylinklist.delete(10)
    print(mylinklist.get_list())
    mylinklist.insert_at_start(10)
    print(mylinklist.get_list())

输出：

[5, 6, 7, 8, 9]
    [5, 7, 8, 9]
    [5, 7, 8, 9]
    [10, 5, 7, 8, 9]