Struktur Data - Daftar Tertaut Ganda

Doubly Linked List adalah variasi dari Linked List dimana navigasi dimungkinkan dengan kedua cara, baik maju maupun mundur dengan mudah dibandingkan dengan Single Linked List. Berikut adalah istilah-istilah penting untuk memahami konsep daftar tertaut ganda.

  • Link - Setiap tautan dari daftar tertaut dapat menyimpan data yang disebut elemen.

  • Next - Setiap tautan dari daftar tertaut berisi tautan ke tautan berikutnya yang disebut Berikutnya.

  • Prev - Setiap tautan dari daftar tertaut berisi tautan ke tautan sebelumnya yang disebut Sebelumnya.

  • LinkedList - Sebuah Daftar Tertaut berisi tautan koneksi ke tautan pertama yang disebut Pertama dan ke tautan terakhir yang disebut Terakhir.

Representasi Daftar Tertaut Ganda

Sesuai ilustrasi di atas, berikut adalah poin-poin penting yang harus diperhatikan.

  • 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 null untuk menandai akhir dari daftar.

Operasi Dasar

Berikut adalah operasi dasar yang didukung oleh daftar.

  • Insertion - Menambahkan elemen di awal daftar.

  • Deletion - Menghapus elemen di awal daftar.

  • Insert Last - Menambahkan elemen di akhir daftar.

  • Delete Last - Menghapus elemen dari akhir daftar.

  • Insert After - Menambahkan elemen setelah item daftar.

  • Delete - Menghapus elemen dari daftar menggunakan kunci.

  • Display forward - Menampilkan daftar lengkap dengan cara maju.

  • Display backward - Menampilkan daftar lengkap secara terbalik.

Operasi Penyisipan

Kode berikut menunjukkan operasi penyisipan di awal daftar tertaut ganda.

Contoh

//insert link at the first location
void insertFirst(int key, int data) {

   //create a link
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key = key;
   link->data = data;
	
   if(isEmpty()) {
      //make it the last link
      last = link;
   } else {
      //update first prev link
      head->prev = link;
   }

   //point it to old first link
   link->next = head;
	
   //point first to new first link
   head = link;
}

Operasi Penghapusan

Kode berikut menunjukkan operasi penghapusan di awal daftar tertaut ganda.

Contoh

//delete first item
struct node* deleteFirst() {

   //save reference to first link
   struct node *tempLink = head;
	
   //if only one link
   if(head->next == NULL) {
      last = NULL;
   } else {
      head->next->prev = NULL;
   }
	
   head = head->next;
	
   //return the deleted link
   return tempLink;
}

Penyisipan di Akhir Operasi

Kode berikut menunjukkan operasi penyisipan di posisi terakhir dari daftar tertaut ganda.

Contoh

//insert link at the last location
void insertLast(int key, int data) {

   //create a link
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key = key;
   link->data = data;
	
   if(isEmpty()) {
      //make it the last link
      last = link;
   } else {
      //make link a new last link
      last->next = link;     
      
      //mark old last node as prev of new link
      link->prev = last;
   }

   //point last to new last node
   last = link;
}

Untuk melihat implementasinya dalam bahasa pemograman C, silahkan klik disini .