Double Linked List

Angelia
2301854492
COMP6048 - CB01

Setelah mereview materi Pointer dan Array, kemudian membahas overview Data Structure dan Single Linked List, materi berikutnya adalah pembahasan mengenai Double Linked List.

Setelah mempelajari materi 'Double Linked List' dari BinusMaya dan beberapa sumber referensi lainnya, maka saat ini saya akan membuat pembahasan dan ringkasan dari materi yang telah saya pelajari.

DOUBLE LINKED LIST
1. Pengertian Double Linked List
Double Linked List merupakan kumpulan data yang terhubung dengan 2 pointer, satu pointer merujuk pada data setelahnya dan satu pointer merujuk pada data sebelumnya.

2. Perbedaan 'Double Linked List' dengan 'Single Linked List'
Tak jauh berbeda dengan materi single linked list, double linked list memiliki konsep yang sama. Sebagai ilustrasi, single linked list hanya dapat berpegangan menggunakan tangan kanan saja (arah akses pointer hanya ke kanan saja, 1 pointer penunjuk), sedangkan double linked list dapat berpegangan menggunakan tangan kiri dan kanan (arah akses pointer dapat ke kiri dan ke kanan, 2 pointer penunjuk).

3. Model Double Linked List
* Default Linked List
Model Linked List ini (Double Linked List) dapat mengakses data sebelum dan sesudahnya, namun jika node berada di bagian akhir/awal data, salah satu pointernya tidak dapat mengakses data selanjutnya atau sebelumnya.

Penjelasan:
Sumber: Geeksforgeeks.org

Berdasarkan contoh gambar di atas, jika node berada di value data 'A' maka pointer ke kiri (kembali ke data paling akhir) untuk mengakses value data 'D' tidak ada/tidak bisa. Begitu pula dengan kondisi jika node berada di value data 'D' maka pointer ke kanan (kembali ke data paling awal) untuk mengakses value data 'A' tidak ada/tidak bisa.

* Circular Linked List
Model Linked List ini dapat mengakses data sebelum dan sesudahnya, serta model Circular ini dapat mengakses data paling awal saat node berada pada data paling akhir dan dapat mengakses data paling akhir saat node berada pada data paling awal.

Penjelasan:
Sumber: Geeksforgeeks.org

Berdasarkan contoh gambar di atas, ketika node berada pada data paling awal (katakanlah Data 'A') maka model ini memiliki fitur untuk mengakses data paling akhir (katakanlah Data 'C'). Begitu pula sebaliknya, ketika posisi node berada di Data 'C', maka dapat mengakses data yang posisinya berada paling awal (Data 'A').

Perbedaan model ini dengan model yang biasanya adalah pada fitur yaitu jika posisi node berada di bagian paling awal/akhir data, maka node tersebut dapat pula mengakses posisi data yang berada di bagian paling akhir/awal data tersebut (lawan ujung dari posisi node).

Tambahan:
Model ini juga diterapkan untuk 'Circular Single Linked List'.
Sumber: javatpoint.com

Perbedaan 'Circular Double Linked List' dengan 'Circular Single Linked List' hanya terletak pada pengizinan akses pointernya saja, dimana untuk Circular Double Linked List memiliki 2 pointer penunjuk (bisa mengakses data sebelum dan sesudahnya) sedangkan untuk Circular Single Linked List hanya memiliki 1 pointer penunjuk (hanya bisa mengakses data selanjutnya saja). Untuk fitur model 'Circular'nya sendiri memiliki fungsionalitas yang sama, yaitu agar dapat mengakses data yang posisinya berada di bagian paling awal/akhir ketika node berada di posisi paling akhir/awal (ujung yang berlawanan).

4. Implementasi Penggunaan Double Linked List
# Langkah paling awal ketika menggunakan Double Linked List adalah dengan membuat struct yang akan menginisialisasi value, prev, dan next.

   struct node
   {
        int value;
        struct node *prev;     //Pointer untuk merujuk data setelah node
        struct node *next;     //Pointer untuk merujuk data sebelum node
   };

Kemudian, membuat start, end, dan current dengan value awal 0.
  struct node *head= NULL;
  struct node *tail= NULL;
  struct node *current;

Untuk current, setiap kali memanggil fungsi metode (biasanya diletakkan pada baris paling awal setelah memanggil fungsi), maka current harus diassign dengan nilai:
  void Insert(int x){
       //Assign pointer current (untuk setiap fungsi insert/push)
       current = (struct node*)malloc(sizeof(struct node));

        //... isi code sesuai kondisi
       //... isi code
       return
   }
#menggunakan sizeof agar besar memory yang disimpan pas, tidak kekecilan atau kebesaran.

==> Metode INSERT (Push)
Metode Insertion Data bisa dilakukan dengan 4 kondisi:
a) Insert Data pada list kosong
//Assign value
current->value = x;
//Posisi head dan tail ada di current, karena data yang masuk hanya/baru 1 data
head = tail = current;
//ini berlaku untuk model default dan circular

b) Insert Data dengan node pada posisi paling awal list
//Assign value
current->value = x;
//Buat kedua pointer NULL
current->next = current->prev = NULL;
//Posisi sebelum head adalah data current
head->prev = current;
//Posisi head terletak 1 step di sebelah kanan current
current->next = head;
//Posisi head sekarang diletakkan sesuai posisi current sekarang (posisinya paling depan)
head = current;

*Jika model default
//Data sebelum current dibuat NULL, karena current paling depan
current->prev = NULL;
head->prev = NULL;
tail->next = NULL;

*Jika model circular
head->prev = tail;
tail->next = head;

c) Insert Data dengan node pada posisi paling akhir list
//Assign value
current->value = x;

 //Set kedua pointer NULL
current->next = current ->prev = NULL;

 //Memposisikan letak current
//Posisi current ada di setelah tail
tail->next  = current;
//Posisi tail di sebelum current

current->prev  = tail;
//Posisi tail sekarang ada di posisi data current (paling belakang)

tail = current;

* Jika model default
head->prev = NULL;
tail->next = NULL;

*Jika model circular
head->prev = tail;
tail->next = head;

d) Insert Data dengan node pada posisi di antara list-list
//Posisi a dan b disesuaikan
struct node *a = (diisi);
struct node *b = (diisi);
//Node baru diselipkan di antara data dengan value a dan b
//Value data sekarang adalah x
current->value = x;
//Data setelah current adalah b
current->next = b;
//Data sebelum current adalah a
current->prev = a;
//Data setelah value a adalah current
a->next = current;
//Data setelah value b adalah current
b->prev = current;
//Model tidak diperhatikan karena posisi insert data ada di antara

==> Metode DELETE (Pop)
#Tambahkan case jika data kosong
if(head==NULL) return

a) Delete Data jika pada list hanya ada 1 data
//Menghilangkan data head
free(head);
//Mengembalikan head dan tail menjadi NULL (kosong)
head = NULL;
tail = NULL;

 b) Delete Data jika node berada di head
//Ubah posisi head ke sebelah kanan 1 step
head = head->next;
//Hilangkan memori data pada posisi 1 step sebelum head
free(head->prev);
//Buat 1 posisi sebelum head menjadi NULL
head->prev = NULL;

c) Delete Data jika node berada di tail
//Ubah posisi tail menjadi mundur 1 step ke sebelah kiri
tail = tail->prev;
//Hilangkan memori data pada posisi 1 step setelah tail
free(tail->next);
//Buat 1 posisi setelah tail menjadi NULL
tail->next = NULL;

d) Delete Data jika node ada di antara list-list
#Khusus untuk delete bukan di head dan tail, assign current dengan head
struct node *current = head;

//Selama nilai data setelah posisi current tidak sama dengan x, maka posisi current maju 1 step ke kanan
while ( current->next->value != x ) current= current->next;
//Assign current untuk a (data 1 step ke kiri sebelum data delete)
struct node *a   = current;
//Assign data setelah current ke delete (bagian ini yang akan dihapus)
struct node *delete = current->next;
//Assign b dengan data 2 step ke kanan setelah current
struct node *b   = current->next->next;
//Setting data setelah a adalah b
a->next = b;
//Setting data sebelum b adalah a
b->prev = a;
//Setelah data a dan b tersambung, maka hapus memori pada data delete
free(delete);

Demikian pembahasan mengenai Double Linked List. Mohon maaf apabila ada kesalahan.
Terima kasih.

Angelia
2301854492
COMP6048 - CB01

Referensi Materi:

Comments

Post a Comment

Popular Posts