双向链表

发布时间:2022-01-18 编辑:RainNight 阅读:423

双向链表


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

  • 双向链表包含第一个和最后一个的链接元素。
  • 每个链接都有一个数据字段和两个称为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在追加操作中的位置。

关键字词[数据结构与算法]

上一篇:链表

下一篇:节点