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

Apa itu Daftar Berantai Ganda (Doubly Linked List)?

Dalam daftar berantai ganda (Doubly Linked List), setiap node memiliki tautan ke node sebelumnya dan node berikutnya. Setiap node terdiri dari tiga elemen: satu menyimpan data, dan dua lainnya adalah penunjuk ke node berikutnya dan node sebelumnya. Kedua penunjuk ini membantu bergerak maju atau mundur dari node tertentu.

Berikut adalah struktur dasar dari Doubly Linked List.

Struktur Daftar Tertaut Ganda

Setiap linked list memiliki node head dan tail. Node head tidak memiliki prev (penunjuk sebelumnya) simpul, dan simpul ekor tidak memiliki berikutnya simpul.

Berikut beberapa istilah penting untuk Daftar Berantai Ganda (Doubly Linked List):

• 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 menyimpan hal lain. Struktur Data di dalamnya. Misalnya, string, kamus, himpunan, hashmap, dan struktur lainnya dapat disimpan di dalam kolom data.

Berikut adalah struktur dasar dari satu node dalam Doubly Linked List:

Struktur sebuah node dalam Daftar Tertaut Ganda

Operations dari Daftar Tertaut Ganda

Operasi pada Doubly Linked List meliputi penambahan, penghapusan, penyisipan, dan penghapusan node, serta penelusuran daftar dari atas ke bawah atau dari bawah ke atas.

Berikut adalah daftar operasi yang dapat diimplementasikan pada Doubly Linked List:

• Penyisipan di depan
• Penyisipan di ujung 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

Implementasi dan pseudo-code untuk masing-masing operasi tersebut tercantum di bawah ini.

Penyisipan di Depan Daftar Berantai Ganda

Penyisipan di depan berarti membuat node dalam linked list dan menempatkannya di awal list.

Sebagai contoh, terdapat sebuah node tertentu. 15Ini perlu ditambahkan sebagai node kepala.

Ada dua kondisi penting yang harus dipenuhi saat melakukan operasi ini:

1. Node baru tersebut menjadi node kepala jika Daftar Berantai Ganda (Doubly Linked List) kosong.
2. Jika sudah ada node kepala, maka node kepala sebelumnya akan digantikan oleh node yang baru.

Berikut adalah 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 node depan

Penyisipan di Akhir Daftar Berantai Ganda

Penyisipan di akhir berarti membuat node dalam linked list dan menempatkannya di bagian ekor.

Ada dua metode yang melakukan operasi ini:

• Metode 1: Mulailah menelusuri dari kepala Daftar Berantai Ganda hingga berikutnya menjadi null. Kemudian hubungkan node baru dengan berikutnya penunjuk.
• Metode 2: Ambil node terakhir dari Linked List Ganda. Kemudian, berikutnya Pointer dari node terakhir menunjuk ke node baru. Node baru tersebut menjadi node ekor.

Berikut adalah kode semu untuk penyisipan pada node ekor:

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

Penyisipan di akhir daftar tertaut

Penyisipan Setelah Node

Perhatikan sebuah Linked List ganda yang sudah ada seperti berikut:

Tujuannya adalah untuk menyisipkan node tertentu yang akan dihubungkan setelah node dengan nilai tersebut. 12.

Langkah 1) Telusuri dari kepala hingga simpul terakhir. Periksa simpul mana yang memiliki nilai tersebut. 12.

Langkah 2) Buat node baru dan tetapkan sebagai penunjuk berikutnya dari node tersebut. 12. itu berikutnya simpul dari simpul baru akan menjadi 15.

Berikut adalah pseudocode untuk menyisipkan node setelah node dalam Doubly Linked List:

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

Penyisipan setelah Node

Penyisipan Sebelum Sebuah Node

Operasi ini mirip dengan penyisipan setelah sebuah node. Nilai node tertentu dicari, kemudian node baru dibuat dan disisipkan sebelum node yang dicari.

Untuk menyisipkan node tertentu 15 sebelum simpul 12, ikuti langkah ini:

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

Langkah 2) Periksa apakah penunjuk berikutnya dari node saat ini memiliki nilai tersebut. 12.

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

Berikut adalah pseudocode untuk menyisipkan node sebelum node lain dalam Doubly Linked List:

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

Memasukkan Node Sebelum Node

Hapus Head dari Linked List Ganda

Node kepala dalam Daftar Berantai Ganda tidak memiliki node sebelumnya. Jadi, berikutnya Pointer akan menjadi node kepala yang baru ketika kepala saat ini dihapus. Membebaskan memori yang ditempati oleh node yang dihapus juga diperlukan.

Berikut langkah-langkah untuk menghapus node kepala:

Langkah 1) Tetapkan variabel ke node kepala saat ini.

Langkah 2) Kunjungi berikutnya simpul dari simpul kepala saat ini dan buatlah prev Pointer NULL. Ini memutuskan sambungan node kedua dari node pertama.

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

Berikut adalah pseudocode untuk menghapus elemen pertama dari sebuah Doubly Linked List:

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

Menghapus node kepala

Membebaskan memori yang dialokasikan setelah penghapusan apa pun diperlukan. Jika tidak, memori untuk blok yang dihapus akan tetap ter occupied selama seluruh waktu eksekusi program, dan aplikasi lain tidak dapat menggunakan segmen memori tersebut.

Hapus Ekor dari Daftar Bertautan Ganda

Operasi ini mirip dengan penghapusan head. Alih-alih head, tail yang dihapus. Untuk mengidentifikasi sebuah node sebagai tail, periksa apakah pointer next bernilai null. Setelah menghapus tail, memori harus dibebaskan.

Operasi ini juga dikenal sebagai penghapusan dari belakang.

Berikut adalah langkah-langkah untuk melakukannya:

Langkah 1) Telusuri hingga simpul ekor dari Daftar Berantai Ganda.

Langkah 2) Tetapkan variabel atau penunjuk ke simpul ekor.

Langkah 3) Mengatur berikutnya Arahkan pointer ke NULL dan bebaskan memori node ekor.

Berikut adalah kode semu untuk menghapus node ekor:

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

Mencari dan Menghapus Node dari Daftar Berantai Ganda

Operasi ini mencari nilai node tertentu dan menghapus node tersebut. Pencarian linear diperlukan karena linked list adalah struktur data linear. Setelah penghapusan, memori harus dibebaskan.

Berikut langkah-langkah untuk mencari dan menghapus node dalam Doubly Linked List:

Langkah 1) Telusuri daftar tertaut dari head hingga nilai node sama dengan item pencarian.

Langkah 2) Tetapkan variabel hapusNode ke node yang cocok.

Langkah 3) Hubungkan simpul sebelumnya dari hapusNode ke node berikutnya, dan atur node berikutnya prev penunjuk ke node sebelumnya.

Langkah 4) Bebaskan ingatan akan hapusNode.

Berikut adalah pseudocode untuk mencari dan menghapus node dari linked list:

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

Operasi pencarian dan penghapusan

Menelusuri Daftar Berantai Ganda dari Depan

Penelusuran dari node kepala akan berulang ke node berikutnya hingga ditemukan nilai NULL. Saat menelusuri setiap node, nilainya dapat dicetak. Berikut adalah langkah-langkah untuk menelusuri ke arah depan:

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

Langkah 2) Lanjutkan ke node berikutnya dari head sampai mendapatkan NULL.

Langkah 3) Cetak data node di setiap iterasi.

Langkah 4) Kembalikan simpul kepala.

Berikut adalah pseudocode untuk menelusuri Doubly Linked List dari depan:

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

Pengembalian tidak wajib. Namun, mengembalikan node kepala setelah operasi adalah praktik yang baik.

Telusuri Daftar Berantai Ganda dari Belakang

Operasi ini merupakan kebalikan dari penelusuran dari depan. Pendekatannya sama dengan satu perbedaan kecil: capai simpul akhir terlebih dahulu, kemudian berjalan mundur ke kepala menggunakan prev penunjuk.

Berikut langkah-langkah untuk menelusuri Doubly Linked List dari belakang:

Langkah 1) Lakukan penelusuran hingga mencapai simpul ekor.

Langkah 2) Dari simpul ekor, telusuri menggunakan prev sampai node sebelumnya bernilai NULL. The prev Pointer untuk node kepala adalah null.

Langkah 3) Pada setiap iterasi, cetak data node.

Berikut adalah kode semu untuk menelusuri dari belakang:

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

Perbedaan Antara Linked List Tunggal dan Linked List Ganda

Perbedaan utama antara Singly Linked List dan Doubly Linked List terletak pada jumlah tautan yang dimiliki setiap node.

Berikut perbedaan antara node pada Singly Linked List dan Doubly Linked List:

Daftar Tertaut Ganda di C++

Berikut ini adalah daftar lengkapnya. C++ Implementasi dari sebuah Doubly Linked List dengan operasi insert, delete, search, dan traverse.

#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);
    return;
  }
  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 = listHead;
  cout<<"Traversal from head:\t";
  while(head != NULL){
    cout<<head->data<<"\t";
    head = head->next;
  }
  cout<<endl;
}
void traverseFromEnd(node *listHead){
  node* head = listHead;
  cout<<"Traversal from tail:\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 = (*listHead);
  while(head != 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;
}
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
Added 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 tail:    10  9  11  5  20  6  7
Deleted Node    7
Traversal from head:    6  20  5  11  9  10
Traversal from tail:    10  9  11  5  20  6

Daftar Tertaut Ganda di Python

Berikut ini adalah daftar lengkapnya. Python Implementasi dari sebuah Doubly Linked List menggunakan kelas untuk node dan list itu sendiri.

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.head = newNode
      print("Added {} at the end".format(val))
      return
    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 is not None:
      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 != 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 != 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 is not None and temp.data != searchItem:
      temp = temp.next
    if self.head is None or temp is None:
      return
    if self.head.data == 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))
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

Kompleksitas waktu umumnya dibagi menjadi tiga jenis: kasus terbaik, kasus rata-rata, dan kasus terburuk.

Kompleksitas waktu dalam kasus terbaik untuk Doubly Linked List:

1. Penyisipan di kepala atau ekor membutuhkan waktu O(1) karena tidak diperlukan penelusuran di dalam linked list. Pointer kepala dan ekor memberikan akses langsung ke node kepala dan ekor.
2. Penghapusan di bagian kepala atau ekor membutuhkan biaya O(1).
3. Pencarian pada sebuah node membutuhkan biaya O(1) ketika node target adalah node kepala.

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

1. Penyisipan di kepala atau ekor membutuhkan biaya O(1).
2. Penghapusan di bagian kepala atau ekor membutuhkan biaya O(1).
3. Pencarian pada sebuah node membutuhkan waktu O(n), karena target dapat berada di mana saja dalam daftar. Di sini, n adalah jumlah total node.

Kompleksitas waktu kasus terburuk dari Doubly Linked List 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, memori harus dibebaskan. Jika tidak, linked list yang lebih besar akan menyebabkan kebocoran memori.

Aplikasi Daftar Berantai Ganda

Daftar Berantai Ganda (Doubly Linked List) mendukung beberapa struktur data dunia nyata karena penelusuran dua arah menyederhanakan banyak operasi umum.

• Cache LRU: Cache Least-Recently-Used (LRU) menggunakan Doubly Linked List dengan hash map untuk operasi move-to-front dan eviction O(1).
• Sejarah browser: Navigasi maju dan mundur menelusuri daftar tertaut ke kedua arah.
• Tumpukan undo dan redo: Editor dan IDE track versi dokumen dengan penunjuk prev dan next.
• Deque: Doubleantrean berujung-ujung melakukan push dan pop dari kedua ujung dalam waktu O(1).
• Daftar putar musik: Sebelumnya dan selanjutnya tracTombol k bergantung pada penunjuk mundur dan maju.

Pertanyaan Umum Demo Slot