链表

发布时间:2022-01-18编辑:RainNight阅读(443)

    链表


    链表是一系列数据元素,通过链接连接在一起。 每个数据元素都以指针的形式包含到另一个数据元素的连接。 Python在其标准库中没有链接列表。 我们使用前一章讨论的节点概念来实现链表的概念。 我们已经知道如何创建节点类以及如何遍历节点的元素。 在本章中,将学习链表的类型:单链表。 在这种类型的数据结构中,任何两个数据元素之间只有一个链接。 创建一个链表并使用一些方法来插入,更新和从列表中移除元素。

    创建链表


    Python是通过节点类来创建链表的。创建一个Node对象并创建另一个类来使用这个节点对象。 通过节点对象传递适当的值来指向下一个数据元素。 下面的程序使用三个数据元素创建链接列表。

    class Node:
        def __init__(self, dataval=None):
            self.dataval = dataval
            self.nextval = None
    
    
    class SLinkedList:
        def __init__(self):
            self.headval = None
    
    if __name__ == "__main__":
        
        list = SLinkedList()
        list.headval = Node("Mon")
        e2 = Node("Tue")
        e3 = Node("Wed")
        
        list.headval.nextval = e2
    
        e2.nextval = e3
    
    

    遍历链表


    从第一个数据元素开始,单向链表只能在向前遍历。 只需通过将下一个节点的指针指向当前数据元素来打印下一个数据元素的值。

    class Node:
        def __init__(self, dataval=None):
            self.dataval = dataval
            self.nextval = None
    
    
    class SLinkedList:
        def __init__(self):
            self.headval = None
    
        # 遍历链表
        def listspint(self):
           printval = self.headval
           while printval is not None:
              print(printval.dataval)
              printval = printval.nextval
    
    
    if __name__ == "__main__":
        
        list = SLinkedList()
        list.headval = Node("I")
        e2 = Node("am")
        e3 = Node("Tom")
        
        list.headval.nextval = e2
        e2.nextval = e3
    
        list.listspint()
    
    

    执行上面示例代码 file

    向链表插入数据


    在链表中插入元素涉及将指针从现有节点重新分配给新插入的节点。 取决于新数据元素是在链表的开始位置还是在中间位置或末尾插入,有以下解决方案。

    在链接列表的开头插入


    这涉及到将新数据节点的下一个指针指向链表的当前头部。 因此,链表的当前头成为第二个数据元素,新节点成为链表的头部。

    class Node:
        def __init__(self, dataval=None):
            self.dataval = dataval
            self.nextval = None
    
    
    class SLinkedList:
        def __init__(self):
            self.headval = None
    
        # 遍历链表
        def listspint(self):
           printval = self.headval
           while printval is not None:
              print(printval.dataval)
              printval = printval.nextval
    
        # 从头部插入
        def AtBegining(self, newdata):
            NewNode = Node(newdata)
            NewNode.nextval = self.headval
            self.headval = NewNode
    
    
    if __name__ == "__main__":
        
        list = SLinkedList()
        list.headval = Node("I")
        e2 = Node("am")
        e3 = Node("Tom")
        
        list.headval.nextval = e2
        e2.nextval = e3
    
        list.AtBegining("after,")
    
        list.listspint()
    

    执行上面示例代码 file

    在链表的末尾插入


    这包括将链表的当前最后一个节点的下一个指针指向新的数据节点。 因此链表的当前最后一个节点成为倒数第二个数据节点,新节点成为链表的最后一个节点。

    class Node:
        def __init__(self, dataval=None):
            self.dataval = dataval
            self.nextval = None
    
    
    class SLinkedList:
        def __init__(self):
            self.headval = None
    
        # 遍历链表
        def listspint(self):
           printval = self.headval
           while printval is not None:
              print(printval.dataval)
              printval = printval.nextval
    
        # 从头部插入
        def AtBegining(self, newdata):
            NewNode = Node(newdata)
            NewNode.nextval = self.headval
            self.headval = NewNode
        
        # 从尾部插入
        def Atend(self, newdata):
            NewNode = Node(newdata)
            if self.headval is None:
              self.headval = NewNode
              return
            laste = self.headval
             while (laste.nextval):
                laste = laste.nextval
             laste.nextval = NewNode
    
    
    if __name__ == "__main__":
        
        list = SLinkedList()
        list.headval = Node("I")
        e2 = Node("am")
        e3 = Node("Tom")
        
        list.headval.nextval = e2
        e2.nextval = e3
    
        list.AtBegining("after,")
    
        list.Atend(",from")
    
        list.listspint()
    

    执行上面示例代码 file

    在两个数据节点之间插入


    这涉及到将指定节点的指针指向新节点。 这可以通过传入新节点和现有节点,然后插入新节点。 所以定义一个额外的类,将新节点的下一个指针改变为中间节点的下一个指针。 然后将新节点分配给中间节点的下一个指针。

    class Node:
        def __init__(self, dataval=None):
            self.dataval = dataval
            self.nextval = None
    
    
    class SLinkedList:
        def __init__(self):
            self.headval = None
    
        # 遍历链表
        def listspint(self):
           printval = self.headval
           while printval is not None:
              print(printval.dataval)
              printval = printval.nextval
    
        # 从头部插入
        def AtBegining(self, newdata):
            NewNode = Node(newdata)
            NewNode.nextval = self.headval
            self.headval = NewNode
        
        # 从尾部插入
        def Atend(self, newdata):
            NewNode = Node(newdata)
            if self.headval is None:
              self.headval = NewNode
              return
            laste = self.headval
             while (laste.nextval):
                laste = laste.nextval
             laste.nextval = NewNode
    
       # 在两个数据节点之间插入
       def Inbetween(self, middle_node, newdata):
         if middle_node is None:
            print("The mentioned node is absent")
            return
    
         NewNode = Node(newdata)
         NewNode.nextval = middle_node.nextval
         middle_node.nextval = NewNode
    
    
    
    if __name__ == "__main__":
        
        list = SLinkedList()
        list.headval = Node("I")
        e2 = Node("am")
        e3 = Node("Tom")
        
        list.headval.nextval = e2
        e2.nextval = e3
    
            list.Inbetween(list.headval.nextval,"sun")
          list.AtBegining("after,")
    
    list.Atend(",from")
    
        list.listspint()
    

    执行上面示例代码 file

    从链表中删除项目


    可以使用该节点的键来删除一个节点。 在下面的程序中,找到要删除的节点的前一个节点。 然后将该节点的下一个指针指向要删除的节点的下一个节点。

    class Node:
        def __init__(self, dataval=None):
            self.dataval = dataval
            self.nextval = None
    
    
    class SLinkedList:
        def __init__(self):
            self.headval = None
    
        # 遍历链表
        def listspint(self):
           printval = self.headval
           while printval is not None:
              print(printval.dataval)
              printval = printval.nextval
    
        # 从头部插入
        def AtBegining(self, newdata):
            NewNode = Node(newdata)
            NewNode.nextval = self.headval
            self.headval = NewNode
        
        # 从尾部插入
        def Atend(self, newdata):
            NewNode = Node(newdata)
            if self.headval is None:
              self.headval = NewNode
              return
            laste = self.headval
             while (laste.nextval):
                laste = laste.nextval
             laste.nextval = NewNode
    
       # 在两个数据节点之间插入
       def Inbetween(self, middle_node, newdata):
         if middle_node is None:
            print("The mentioned node is absent")
            return
    
         NewNode = Node(newdata)
         NewNode.nextval = middle_node.nextval
         middle_node.nextval = NewNode
    
    
      # 从链表中删除项目
      def RemoveNode(self, Removekey):
    
        Headval = self.headval
    
        if (Headval is not None):
            if Headval.dataval == Removekey:
                self.headval = Headval.nextval
                Headval = None
                return
    
         while (Headval is not None):
            if Headval.dataval == Removekey:
                break
            prev = Headval
            Headval = Headval.nextval
    
         if (Headval == None):
            return
    
         prev.nextval = Headval.nextval
         Headval = None
    
    
    if __name__ == "__main__":
        
        list = SLinkedList()
        list.AtBegining("I")
        list.AtBegining("am")
        list.AtBegining("Tom")
        list.AtBegining("after,")
        list.AtBegining(",from")
        list.RemoveNode(",from")
        list.listspint()
    

    执行上面示例代码

    file

关键字数据结构与算法

上一篇:双向链表

下一篇:快速理解kmp算法

Collect from 雨夜的博客 雨夜的博客