Python - Daftar Tertaut Lanjutan

Kami telah melihat Daftar Berantai di bab sebelumnya di mana hanya mungkin untuk melakukan perjalanan ke depan. Dalam bab ini kita melihat jenis lain dari daftar tertaut yang memungkinkan untuk melakukan perjalanan maju dan mundur. Daftar tertaut semacam itu disebut Daftar Tertaut Ganda. Berikut adalah fitur daftar tertaut ganda.

  • Daftar Tertaut Ganda berisi elemen tautan yang disebut pertama dan terakhir.
  • Setiap tautan membawa bidang data dan dua bidang tautan yang disebut next dan prev.
  • Setiap tautan ditautkan dengan tautan berikutnya menggunakan tautan berikutnya.
  • Setiap tautan ditautkan dengan tautan sebelumnya menggunakan tautan sebelumnya.
  • Tautan terakhir membawa tautan sebagai nol untuk menandai akhir dari daftar.

Membuat daftar tertaut ganda

Kami membuat daftar Doubly Linked dengan menggunakan kelas Node. Sekarang kita menggunakan pendekatan yang sama seperti yang digunakan dalam Daftar Tertaut Tunggal tetapi kepala dan penunjuk berikutnya akan digunakan untuk penugasan yang tepat untuk membuat dua tautan di setiap simpul selain data yang ada di simpul.

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)

Ketika kode di atas dijalankan, itu menghasilkan hasil sebagai berikut -

62 8 12

Memasukkan ke dalam Daftar Tertaut Ganda

di sini kita akan melihat bagaimana cara memasukkan sebuah node ke Doubly Link List menggunakan program berikut. Program ini menggunakan metode bernama insert yang menyisipkan node baru di posisi ketiga dari kepala daftar tertaut ganda.

# 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)

Ketika kode di atas dijalankan, itu menghasilkan hasil sebagai berikut -

62  8  13  12

Menambahkan ke daftar tertaut ganda

Menambahkan ke daftar tertaut ganda akan menambahkan elemen di bagian akhir.

# 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)

Ketika kode di atas dijalankan, itu menghasilkan hasil sebagai berikut -

62 8 12 9 45

Harap perhatikan posisi elemen 9 dan 45 untuk operasi penambahan.