Учебники

Python — Расширенный связанный список

Декабрь 19, 2018

Мы уже видели Linked List в предыдущей главе, в которой возможно только продвигаться вперед. В этой главе мы видим другой тип связанного списка, в котором можно перемещаться как вперед, так и назад. Такой связанный список называется двусвязным списком. Ниже приведены особенности двусвязного списка.

  • Вдвойне связанный список содержит элемент ссылки, который называется первым и последним.
  • Каждая ссылка содержит поле (и) данных и два поля ссылки, которые называются next и prev.
  • Каждая ссылка связана со своей следующей ссылкой, используя свою следующую ссылку.
  • Каждая ссылка связана со своей предыдущей ссылкой, используя свою предыдущую ссылку.
  • Последняя ссылка содержит нулевую ссылку для обозначения конца списка.

Создание двусвязного списка

Мы создаем двусвязный список с помощью класса Node. Теперь мы используем тот же подход, который использовался в односвязном списке, но для правильного назначения будут использоваться указатели head и next для создания двух ссылок в каждом из узлов в дополнение к данным, присутствующим в узле. 

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

# Adding data elements		
   def push(self, NewVal):
      NewNode = Node(NewVal)
      NewNode.next = self.head
      if self.head is not None:
         self.head.prev = NewNode
      self.head = NewNode

# Print the Doubly Linked list		
   def listprint(self, node):
      while (node is not None):
         print(node.data),
         last = node
         node = node.next

dllist = doubly_linked_list()
dllist.push(12)
dllist.push(8)
dllist.push(62)
dllist.listprint(dllist.head)

Когда приведенный выше код выполняется, он дает следующий результат — 

62 8 12

Вставка в двусвязный список

здесь мы увидим, как вставить узел в список двойных ссылок с помощью следующей программы. Программа использует метод с именем insert, который вставляет новый узел в третью позицию от заголовка двусвязного списка. 

# Create the Node class
class Node:
   def __init__(self, data):
      self.data = data
      self.next = None
      self.prev = None

# Create the doubly linked list
class doubly_linked_list:

   def __init__(self):
      self.head = None

# Define the push method to add elements		
   def push(self, NewVal):

      NewNode = Node(NewVal)
      NewNode.next = self.head
      if self.head is not None:
         self.head.prev = NewNode
      self.head = NewNode

# Define the insert method to insert the element		
   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

# Define the method to print the linked list 
   def listprint(self, node):
      while (node is not None):
         print(node.data),
         last = node
         node = node.next

dllist = doubly_linked_list()
dllist.push(12)
dllist.push(8)
dllist.push(62)
dllist.insert(dllist.head.next, 13)
dllist.listprint(dllist.head)

Когда приведенный выше код выполняется, он дает следующий результат — 

62  8  13  12

Присоединение к двусвязному списку

Добавление к двусвязному списку добавит элемент в конце. 

# Create the node class
class Node:
   def __init__(self, data):
      self.data = data
      self.next = None
      self.prev = None
# Create the doubly linked list class
class doubly_linked_list:

   def __init__(self):
      self.head = None

# Define the push method to add elements at the begining
   def push(self, NewVal):
      NewNode = Node(NewVal)
      NewNode.next = self.head
      if self.head is not None:
         self.head.prev = NewNode
      self.head = NewNode

# Define the append method to add elements at the end
   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

# Define the method to print
   def listprint(self, node):
      while (node is not None):
         print(node.data),
         last = node
         node = node.next

dllist = doubly_linked_list()
dllist.push(12)
dllist.append(9)
dllist.push(8)
dllist.push(62)
dllist.append(45)
dllist.listprint(dllist.head)

Когда приведенный выше код выполняется, он дает следующий результат — 

62 8 12 9 45

Обратите внимание на расположение элементов 9 и 45 для операции добавления.

75
Share: