Daftar Tertaut Ganda: C++, Python (Contoh Kode)

Apa itu daftar tertaut ganda?

Dalam daftar tertaut ganda, setiap node memiliki link ke node sebelumnya dan berikutnya. Setiap node terdiri dari tiga elemen: satu memegang data, dan dua lainnya adalah penunjuk node berikutnya dan sebelumnya. Kedua petunjuk ini membantu kita untuk maju atau mundur dari simpul tertentu.

Berikut struktur dasar daftar tertaut ganda.

Setiap daftar tertaut memiliki simpul kepala dan ekor. Node Kepala tidak memiliki node “sebelumnya” (penunjuk sebelumnya), dan node ekor tidak memiliki node “berikutnya”.

Berikut beberapa istilah penting untuk daftar tertaut ganda:

• prev: Setiap node terhubung ke node sebelumnya. Ini digunakan sebagai penunjuk atau tautan.
• Berikutnya: Setiap node terhubung ke node berikutnya. Ini digunakan sebagai penunjuk atau tautan.
• Tanggal: Ini digunakan untuk menyimpan data dalam sebuah node. “Data” dapat menampung lainnya Struktur Data di dalamnya. Misalnya, string, kamus, set, hashmap, dll dapat disimpan di “Data”.

Berikut adalah struktur dasar dari satu node dalam daftar tertaut ganda:

Operations dari Daftar Tertaut Ganda

Pengoperasian daftar tertaut ganda mencakup penambahan dan penghapusan node, penyisipan dan penghapusan node, dan melintasi daftar tertaut dari atas ke bawah.

Berikut daftar operasi yang dapat kita terapkan menggunakan daftar tertaut ganda:

• Penyisipan di depan
• Penyisipan di bagian ekor atau simpul terakhir
• Penyisipan setelah sebuah node
• Penyisipan sebelum sebuah node
• Penghapusan dari depan
• Penghapusan dari ekor
• Cari dan hapus sebuah node
• Melintasi kepala ke ekor
• Melintasi ekor ke kepala

Kita akan melihat implementasi dan pseudocode untuk semua operasi di atas.

Penyisipan di depan Daftar Tertaut Ganda

Penyisipan di depan berarti kita perlu membuat sebuah node di daftar tertaut dan menempatkannya di awal daftar tertaut.

Misalnya, ada node tertentu “15”. Kita perlu menambahkan ini ke node kepala.

Berikut dua kondisi penting saat melakukan operasi ini:

1. Node baru akan menjadi node kepala jika tidak ada node di Doubly Linked List.
2. Jika sudah ada node kepala, maka head sebelumnya akan digantikan oleh node baru.

Berikut kode semu untuk operasi ini:

function insertAtFront (ListHead, value):
  newNode = Node()
  newNode.value = value
  ListHead.prev = NewNode
  NewNode.next = ListHead
  newNode.prev = NULL
  return ListHead

Penyisipan di akhir Daftar Tertaut Ganda

“Penyisipan di akhir” berarti kita akan membuat sebuah node di daftar tertaut dan menempatkannya di akhir.

Untuk melakukan ini, kita dapat menggunakan dua metode:

• Metode 1: Mulailah menelusuri dari bagian atas Daftar Tertaut Ganda hingga "berikutnya" menjadi nol. Kemudian tautkan node baru tersebut dengan node “berikutnya”.
• Metode 2: Ambil simpul terakhir dari Daftar Tertaut Ganda. Kemudian, node “berikutnya” dari node terakhir akan terhubung ke node baru. Sekarang, simpul baru akan menjadi simpul ekor.

Berikut pseudo-code untuk penyisipan pada node ekor:

function insertAtTail(ListHead, value):
  newNode = Node()
  newNode.value = value
  newNode.next = NULL
  while ListHead.next is not NULL:
	then ListHead = ListHead.next
  newNode.prev = ListHead
  ListHead.next = newNode
  return ListHead

Penyisipan setelah sebuah node

Katakanlah kita memiliki daftar tertaut ganda seperti berikut:

Kami ingin memasukkan node tertentu yang akan dihubungkan setelah node tersebut, yang memiliki nilai “12”.

Berikut langkah-langkahnya:

Langkah 1) Melintasi dari kepala ke simpul terakhir. Periksa node mana yang memiliki nilai “12”.

Langkah 2) Buat node baru dan tetapkan sebagai penunjuk berikutnya dari node “12”. Node “berikutnya” dari node baru akan menjadi 15.

Berikut pseudo-code untuk menyisipkan node demi node dalam daftar tertaut ganda:

function insertAfter(ListHead, searchItem, value):
  List = ListHead
  NewNode = Node()
  NewNode.value = value
  while List.value is not equal searchItem
	then List = ListHead.next
  List = List.next
  NewNode.next = List.next
  NewNode.prev = List
  List.next = NewNode

Penyisipan sebelum sebuah node

Operasi ini lebih mirip dengan “penyisipan setelah sebuah node”. Kita perlu mencari nilai node tertentu untuk melakukan ini. Kemudian kita akan membuat node baru dan menyisipkannya sebelum node yang dicari.

Katakanlah kita ingin menyisipkan node tertentu “15” sebelum node “12”. Lalu inilah langkah-langkah untuk melakukannya:

Langkah 1) Lintasi daftar tertaut dari simpul kepala ke simpul ekor.

Langkah 2) Periksa apakah penunjuk berikutnya dari node saat ini memiliki nilai “12” atau tidak.

Langkah 3) Masukkan node baru sebagai node “berikutnya” dari node saat ini.

Berikut pseudo-code untuk menyisipkan node sebelum node di Double Linked List:

function insertBefore(ListHead, searchItem, value):
  List = ListHead
  NewNode = Node()
  NewNode.value = value
  while List.next.value is not equal searchItem
	then List = ListHead.next
  NewNode.next = List.next
  NewNode.prev = List
  List.next = NewNode

Hapus kepala daftar tertaut ganda

Node kepala dalam daftar tertaut ganda yang tidak memiliki node sebelumnya. Jadi, pointer berikutnya akan menjadi node kepala baru jika kita ingin menghapus node kepala tersebut. Kita juga perlu mengosongkan memori yang ditempati oleh sebuah node saat menghapus sebuah node.

Berikut langkah-langkah untuk menghapus node kepala:

Langkah 1) Tetapkan variabel ke node kepala saat ini.

Langkah 2) Kunjungi node "berikutnya" dari node kepala saat ini dan jadikan node "sebelumnya" (penunjuk sebelumnya) sebagai ''NULL". Artinya kita memutuskan sambungan node kedua dari node pertama.

Langkah 3) Bebaskan memori yang ditempati oleh node kepala sebelumnya.

Berikut kode semu untuk menghapus kepala dari daftar tertaut ganda:

function deleteHead(ListHead):
  PrevHead = ListHead
  ListHead = ListHead.next
  ListHead.prev = NULL
  PrevHead.next = NULL
  free memory(PrevHead)
  return ListHead

Memori yang dialokasikan harus dihapus setelah melakukan operasi penghapusan apa pun. Jika tidak, selama program berjalan, memori untuk blok yang dihapus akan tetap terisi. Tidak ada aplikasi lain yang dapat menggunakan segmen memori tersebut.

Hapus bagian ekor dari daftar tertaut ganda.

Operasi ini mirip dengan penghapusan kepala. Di sini, alih-alih kepalanya, kita perlu menghapus ekornya. Untuk mengidentifikasi sebuah node sebagai node ekor, kita harus memeriksa apakah penunjuk berikutnya atau node berikutnya adalah null atau tidak. Setelah menghapus ekornya, kita perlu mengosongkan memori.

Operasi ini juga dikenal sebagai “penghapusan dari belakang”.

Berikut langkah-langkah untuk melakukannya:

Langkah 1) Lintasi hingga simpul ekor dari daftar tertaut ganda.

Langkah 2) Tetapkan variabel atau penunjuk ke simpul ekor.

Langkah 3) Jadikan node "berikutnya" sebagai NULL dan kosongkan memori node ekor.

Berikut pseudo-code untuk menghapus node ekor:

function DeleteTail( ListHead ):
  head = ListHead
  while ListHead.next is not NULL:
	ListHead = ListHead.next
  Tail = ListHead.next
  ListHead.next = NULL
  free memory( Tail )
  return head

Cari dan hapus node dari Doubly Linked List

Operasi ini memungkinkan kita untuk mencari data node tertentu dan menghapus node tersebut. Kita perlu melakukan pencarian linier karena daftar tertaut adalah struktur data linier. Setelah menghapus, kita juga perlu mengosongkan memori.

Berikut langkah-langkah untuk mencari dan menghapus node dalam daftar tertaut ganda:

Langkah 1) Telusuri daftar tertaut dari kepala hingga nilai simpul sama dengan item pencarian.

Langkah 2) Tetapkan variabel “deleteNode” ke node yang cocok.

Langkah 3) Tetapkan node sebelumnya dari “deleteNode” ke node berikutnya.

Langkah 4) Bebaskan memori "deleteNode"

Berikut pseudocode untuk mencari dan menghapus node dari linked list:

function SearchAndDelete(ListHead, searchItem):
  head = ListHead
  while ListHead.next.value not equals searchItem:
	head = head.next
  deleteNode = head.next
  head.next = head.next.next
  head.next.prev = head
  deleteNode.next, deleteNode.next = NULL
  free memory(deleteNode)
  return ListHead

Lintasi daftar tertaut ganda dari depan

Untuk melintasi dari node kepala dan mengulangi node berikutnya hingga kita menemukan “NULL”. Saat melintasi setiap node, kita dapat mencetak nilai node tersebut. Berikut langkah-langkah melakukan traversing dari depan (arah depan):

Langkah 1) Tetapkan pointer atau variabel ke node kepala saat ini.

Langkah 2) Iterasi ke node kepala berikutnya sampai mendapatkan “NULL”

Langkah 3) Cetak data node di setiap iterasi.

Langkah 4) Kembalikan simpul kepala.

Berikut kode semu untuk melintasi Daftar Tertaut Ganda dari depan:

function traverseFromFront(ListHead):
  head = ListHead
  while head not equals to NULL:
	print head.data
	head = head.next
  return ListHead

Di sini, pengembalian tidak wajib. Namun merupakan praktik yang baik untuk mengembalikan node kepala setelah operasi.

Lintasi daftar tertaut ganda dari belakang

Operasi ini merupakan kebalikan dari lintasan dari depan. Pendekatannya sama dengan sedikit perbedaan. Kita harus melintasi ke simpul akhir dan kemudian melintasi dari simpul akhir ke simpul depan.

Berikut langkah-langkah untuk menelusuri daftar tertaut ganda dari belakang:

Langkah 1) Lintasi sampai kita mencapai simpul ekor.

Langkah 2) Dari node ekor kita akan melakukan tracing hingga mendapatkan node sebelumnya sebagai “NULL”. "Sebelumnya" (penunjuk sebelumnya) akan menjadi nol untuk node kepala

Langkah 3) Pada setiap iterasi, kami akan mencetak data node.

Berikut pseudo-code untuk melakukan traversing dari belakang:

function traverseFromBack(ListHead):
  head = ListHead
  while head not equals NULL:
	head = head.next
  tail = head
  while tail not equal to NULL:
	print tail.value
	tail = tail.prev
  return ListHead

Perbedaan antara daftar tertaut Tunggal dan Ganda

Perbedaan utama antara daftar Tertaut Tunggal dan Tertaut Ganda adalah jumlah tautannya.

Berikut perbedaan antara node pada daftar Tertaut Tunggal dan struktur simpul Daftar Tertaut Ganda:

Bidang	Daftar Tertaut Tunggal	Daftar Tertaut Ganda
Structure	Daftar Tertaut Tunggal memiliki satu bidang data dan satu tautan ke node berikutnya.	Daftar Tertaut Ganda memiliki satu bidang data dan dua tautan. Satu untuk node sebelumnya dan satu lagi untuk node berikutnya.
Lintasan	Ia hanya dapat berpindah dari kepala ke ekor.	Ia dapat melintasi maju dan mundur.
Memori	Menempati lebih sedikit memori.	Ini menempati lebih banyak memori daripada daftar tertaut tunggal.
Aksesibilitas	Daftar Tertaut Tunggal kurang efisien karena hanya menggunakan satu tautan ke node berikutnya. Tidak ada link untuk node sebelumnya.	Daftar Tertaut Ganda lebih efisien dibandingkan Daftar Tertaut Tunggal.

Daftar Tertaut Ganda di C++

#include<iostream>
using namespace std;
  struct node{
  int data;
  struct node *next;
  struct node *prev;
  };
void insertFront(node* &listHead, int value){
  node* newNode = new node();
  newNode->data = value;
  newNode->prev = NULL;
  newNode->next = NULL;
  if(listHead!=NULL)
  {
	listHead->prev = newNode;
  	newNode->next = listHead;
  }
  
  listHead = newNode;
  cout<<"Added "<<value<<" at the front"<<endl;
  }
void insertEnd(node * &listHead, int value){
  if(listHead==NULL)
  {
  	insertFront(listHead,value);
  }
  node* newNode = new node();
  newNode->data = value;
  newNode->prev = NULL;
  newNode->next = NULL;
  node *head = listHead;
  while(head->next!=NULL){
  head = head->next;
  }
  head->next = newNode;
  newNode->prev = head;
  cout<<"Added "<<value<<" at the end"<<endl;
  }
void insertAfter(node * &listHead, int searchValue,int value){
  node* newNode = new node();
  newNode->data = value;
  newNode->prev = NULL;	
  newNode->next = NULL;
  node *head = listHead;	
  while(head->next!=NULL &&  head->data!=searchValue){	
  head = head->next;	
  }	
  newNode->next = head->next;	
  head->next = newNode;	
  newNode->prev = head;	
  if(newNode->next !=NULL){	
  newNode->next->prev = newNode;	
  }	
  cout<<"Inserted "<<value<<" after node "<<searchValue<<endl;
  }
void insertBefore(node * &listHead, int searchValue,int value){
  node* newNode = new node();
  newNode->data = value;
  newNode->prev = NULL;	
  newNode->next = NULL;	
  node *head = listHead;	
  while(head->next!=NULL &&  head->next->data!=searchValue){	
  head = head->next;	
  }	
  newNode->next = head->next;	
  head->next = newNode;	
  newNode->prev = head;	
  if(newNode->next !=NULL){	
  newNode->next->prev = newNode;	
  }	
  cout<<"Inserted "<<value<<" before node "<<searchValue<<endl;	
  }
void traverseFromFront(node *listHead){
  node* head = new node();
  head = listHead;
  cout<<"Traversal from head:\t";	
  while(head!=NULL){	
  cout<<head->data<<"\t ";	
  head = head->next;	
  }	
  cout<<endl;
  }	
void traverseFromEnd(node *listHead){
  node* head = new node();
  head = listHead;	
  cout<<"Traversal from head:\t";	
  while(head->next!=NULL){	
  head = head->next;	
  }	
  node *tail = head;	
  while(tail!=NULL){	
  cout<<tail->data<<"\t";	
  tail = tail->prev;	
  }	
  cout<<endl;	
  }
void searchAndDelete(node **listHead, int searchItem){
  node* head = new node();
  head = (*listHead);
  while(head->next!=NULL &&  head->data!=searchItem){
  head = head->next;
  }
  if(*listHead == NULL || head == NULL) return;
  if((*listHead)->data == head->data){
  	*listHead = head->next;
  }
  if(head->next != NULL){
  	head->next->prev = head->prev;
  }
  
  if(head->prev != NULL){
  	head->prev->next = head->next;
  }
  free(head);
  cout<<"Deleted Node\t"<<searchItem<<endl;
  return;
  }
int main(){
  node *head = NULL;
  insertFront(head,5);
  insertFront(head,6);
  insertFront(head,7);
  insertEnd(head,9);
  insertEnd(head,10);
  insertAfter(head,5,11);
  insertBefore(head,5,20);
  traverseFromFront(head);
  traverseFromEnd(head);
  searchAndDelete(&head,7);
  traverseFromFront(head);
  traverseFromEnd(head);
}

Keluaran

Added 5 at the front
Added 6 at the front
Added 7 at the front
Aded 9 at the end
Added 10 at the end
Inserted 11 after node 5
Inserted 20 before node 5
Traversal from head:    7        6       20      5       11      9       10
Traversal from head:    10      9       11      5       20      6       7
Deleted Node    7
Traversal from head:    6        20      5       11      9       10
Traversal from head:    10      9       11      5       20      6

Daftar Tertaut Ganda di Python

class node:
  def __init__(self,data = None, prev=None, next = None):
    self.data = data
    self.next = next
    self.prev = prev
class DoublyLinkedList:
  def __init__(self):
    self.head = None

  def insertFront(self, val):
    newNode = node(data=val)
    newNode.next = self.head
    if self.head is not None:
      self.head.prev = newNode
    self.head = newNode
    print("Added {} at the front".format(val))

  def insertEnd(self,val):
    newNode = node(data=val)
    if self.head is None:
      self.insertFront(val)
    
    temp = self.head
    while temp.next is not None:
      temp = temp.next
    temp.next = newNode
    newNode.prev = temp
    print("Added {} at the end".format(val))

  def traverseFromFront(self):
    temp = self.head
    print("Traversing from head:\t",end="")
    while temp:
      print("{}\t".format(temp.data),end="")
      temp = temp.next
    print()

  def traverseFromEnd(self):
    temp = self.head
    print("Traversing from Tail:\t",end="")
    while temp.next is not None:
      temp = temp.next
    tail = temp
    while tail is not None:
      print("{}\t".format(tail.data),end="")
      tail = tail.prev
    print()
  
  def insertAfter(self,searchItem, value):
    newNode = node(data=value)

    temp = self.head
    while temp.next is not None and temp.data is not searchItem:
      temp = temp.next
    
    newNode.next = temp.next
    temp.next = newNode
    newNode.prev = temp

    if newNode.next is not None:
      newNode.next.prev = newNode
    print("Inserted {} after node {}".format(value,searchItem))

  def insertBefore(self,searchItem, value):
    newNode = node(data=value)

    temp = self.head
    while temp.next is not None and temp.next.data is not searchItem:
      temp = temp.next
    
    newNode.next = temp.next
    temp.next = newNode
    newNode.prev = temp

    if newNode.next is not None:
      newNode.next.prev = newNode
    print("Inserted {} before node {}".format(value,searchItem))

  def searchAndDelete(self,searchItem):
    temp = self.head

    while temp.next is not None and temp.data is not searchItem:
      temp = temp.next
    
    if self.head is None or temp is None:
      return

    if self.head.data is temp.data:
      self.head = temp.next

    if temp.next is not None:
      temp.next.prev = temp.prev
    
    if temp.prev is not None:
      temp.prev.next = temp.next
    
    print("Deleted Node\t{}".format(searchItem))
    return

doublyLinkedList = DoublyLinkedList()
doublyLinkedList.insertFront(5)
doublyLinkedList.insertFront(6)
doublyLinkedList.insertFront(7)
doublyLinkedList.insertEnd(9)
doublyLinkedList.insertEnd(10)
doublyLinkedList.insertAfter(5, 11)
doublyLinkedList.insertBefore(5, 20)
doublyLinkedList.traverseFromFront()
doublyLinkedList.traverseFromEnd()
doublyLinkedList.searchAndDelete(7)
doublyLinkedList.traverseFromFront()
doublyLinkedList.traverseFromEnd()

Keluaran

Added 5 at the front
Added 6 at the front
Added 7 at the front
Added 9 at the end
Added 10 at the end
Inserted 11 after node 5
Inserted 20 before node 5
Traversing from head:   7       6       20      5       11      9       10
Traversing from Tail:   10      9       11      5       20      6       7
Deleted Node    7
Traversing from head:   6       20      5       11      9       10
Traversing from Tail:   10      9       11      5       20      6

Kompleksitas Daftar Tertaut Ganda

Secara umum, kompleksitas waktu dibagi menjadi tiga jenis.

Mereka adalah:

1. Kasus terbaik
2. Kasus Rata-rata
3. Kasus terburuk

Kompleksitas waktu dalam kasus terbaik untuk Doubly Linked List:

1. Penyisipan di head atau tail akan menghabiskan biaya O(1). Karena kita tidak perlu melakukan traverse di dalam linked list. Pointer head dan tail dapat memberi kita akses ke node head dan tail dengan kompleksitas waktu O(1).
2. Penghapusan pada bagian kepala atau ekor akan dikenakan biaya O(1).
3. Pencarian sebuah node akan memiliki kompleksitas waktu O(1). Karena node target bisa jadi merupakan node utama.

Kompleksitas waktu dalam kasus rata-rata untuk Doubly Linked List:

1. Penyisipan di kepala atau ekor akan memiliki kompleksitas waktu biaya O(1).
2. Penghapusan pada bagian kepala atau ekor akan memiliki kompleksitas waktu dengan biaya O(1).
3. Pencarian sebuah node akan memiliki kompleksitas waktu O(n). Karena item pencarian dapat berada di mana saja di antara linked list. Di sini, “n” adalah total node yang ada di linked list.

Kompleksitas waktu kasus terburuk dari daftar tertaut ganda akan sama dengan kasus rata-rata.

Kompleksitas Memori dari Doubly Linked List

Kompleksitas memori adalah O(n), di mana “n” adalah jumlah total node. Saat mengimplementasikan linked list, kita harus membebaskan memori yang kita gunakan. Jika tidak, untuk linked list yang lebih besar, hal ini akan menyebabkan kebocoran memori.

Kesimpulan

• Daftar tertaut adalah sejenis struktur data linier, kumpulan data yang direpresentasikan secara linier.
• Daftar tertaut ganda adalah jenis daftar tertaut di mana sebuah node memiliki tautan dengan node sebelumnya dan berikutnya.
• Daftar tertaut ganda berisi semua operasi seperti menambahkan simpul, menghapus simpul, menyisipkan simpul setelah atau sebelum simpul lain, dan melintasi daftar tertaut dari kepala ke ekor.
• Daftar Tertaut Ganda memiliki satu bidang data dan dua tautan. Satu untuk node sebelumnya dan satu lagi untuk node berikutnya.
• Kompleksitas Daftar Tertaut Ganda Kasus Terbaik, Kasus Rata-rata
• Dan Kasus Terburuk.