双向链表

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

    双向链表


    在前面的章节中已经看到并学习了链表,但在前面只是进行介绍和入门。 在本章中,我们看到另一种链接列表,可以向前和向后移动遍历。 这种链表称为双向链表。 以下是双向链表的特点。

    • 双向链表包含第一个和最后一个的链接元素。
    • 每个链接都有一个数据字段和两个称为nextprev的链接字段。
    • 每个链接都使用其下一个链接与其下一个链接链接。
    • 每个链接都使用其上一个链接与之前的链接链接。
    • 最后一个链接将链接作为空来标记列表的结尾。

    创建双向链表

    我们使用Node类创建一个双链表。 使用与单链表中相同的方法,但是除了存在于节点中的数据之外,头指针和下一个指针将用于正确分配以在每个节点中创建两个链接。

    class Node:
        def __init__(self, data):
            self.data = data
            self.next = None
            self.prev = None
    
    
    class doubly_linked_list:
        def __init__(self):
            self.head = None
    
        # 插入数据
        def push(self,NewVal):
            NewNode = Node(NewVal)
            NewNode.next = self.head
            if self.head is not None:
                self.head.prev = NewNode
    
            self.head = NewNode
    
        # 遍历链表
        def listspint(self,node):
            while (node is not None):
                print(node.data)
                last = node
                node = node.next
    
    
    
    if __name__ == "__main__":
        list = doubly_linked_list()
        list.push(12)
        list.push(8)
        list.push(62)
        list.listspint(list.head)
    
    

    执行上面示例代码

    file

    插入双链表中


    在这里将演示如何使用以下程序将节点插入到双向链接列表中。 该程序使用一个名为insert()的方法,它将新节点插入到双向链表头部的第三个位置。

    class Node:
        def __init__(self, data):
            self.data = data
            self.next = None
            self.prev = None
    
    
    class doubly_linked_list:
        def __init__(self):
            self.head = None
    
        # 插入数据
        def push(self,NewVal):
            NewNode = Node(NewVal)
            NewNode.next = self.head
            if self.head is not None:
                self.head.prev = NewNode
    
            self.head = NewNode
    
        # 插入双链表中
        def insert(self,prev_node,NewVal):
          if prev_node is None:
              return
    
          NewNode = Node(NewVal)
          NewNode.next = prev_node.next
          prev_node.next = NewNode
          NewNode.prev = prev_node
          if NewNode.next is not None:
              NewNode.next.prev = NewNode
    
    
        # 遍历链表
        def listspint(self,node):
            while (node is not None):
                print(node.data)
                last = node
                node = node.next
    
    
    
    if __name__ == "__main__":
        list = doubly_linked_list()
        list.push(12)
        list.push(8)
        list.push(62)
        list.insert(list.head.next,13)
        list.listspint(list.head)
    

    执行上面示例代码

    file

    附加到双向链表


    追加节点(元素)到双向链表的最后位置。

    class Node:
        def __init__(self, data):
            self.data = data
            self.next = None
            self.prev = None
    
    
    class doubly_linked_list:
        def __init__(self):
            self.head = None
    
        # 插入数据
        def push(self,NewVal):
            NewNode = Node(NewVal)
            NewNode.next = self.head
            if self.head is not None:
                self.head.prev = NewNode
    
            self.head = NewNode
    
        # 插入双链表中
        def insert(self,prev_node,NewVal):
          if prev_node is None:
              return
    
          NewNode = Node(NewVal)
          NewNode.next = prev_node.next
          prev_node.next = NewNode
          NewNode.prev = prev_node
          if NewNode.next is not None:
              NewNode.next.prev = NewNode
    
    
       # 附加到双向链表
       def append(self,NewVal):
    
           NewNode = Node(NewVal)
           NewNode.next = None
           if self.head is None:
               NewNode.prev = None
               self.head = NewNode
               return
           last = self.head
           while (last.next is not None):
               last = last.next
           last.next = NewNode
           NewNode.prev = last
           return
    
        # 遍历链表
        def listspint(self,node):
            while (node is not None):
                print(node.data)
                last = node
                node = node.next
    
    
    
    if __name__ == "__main__":
        list = doubly_linked_list()
        list.push(12)
        list.push(8)
        list.push(62)
        list.insert(list.head.next,13)
        list.listspint(list.head)
    

    执行上面示例代码

    file

    注意:元素9和45在追加操作中的位置。

关键字数据结构与算法

上一篇:节点

下一篇:链表

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