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 .