Data Structure

Linked List

Sebelum dimulai, saya ingin memberikan pengertian sedikit apa itu Linked List. Linked List adalah sebuah Data Structure yang bersifat linier. Lalu, apa bedanya dengan Array? Di Array, kita harus memberikan terlebih dahulu constraint untuk me-reserve memory untuk nantinya dimasukkan sebuah variable. Sedangkan di Linked List, kita tidak perlu memberikan constraint karena kita akan memakai memory SESUAI dengan tiap node yang kita masukkan. Sebagai contoh agar lebih mudah dimengerti, kita misalkan seperti kita ingin makan di sebuah restoran, dimana jika kita mengambil contoh Array, itu seperti kita sudah melakukan booking terhadap meja tertentu di hari-hari sebelum kita makan di restoran tersebut. Sedangkan kalau Linked List, kita langsung datang ke restoran untuk makan di saat itu juga. Jika kita melakukan booking terhadap meja tertentu, tentunya kita akan tahu dimana kita akan makan, di meja ke berapa, di bagian mana meja tersebut terletak. Sedangkan jika kita tidak melakukan booking atau langsung datang ke restoran untuk makan, tentu kita akan diberikan meja yang masih kosong, kita tidak tahu di hari itu ada brp pengunjung yang makan disitu, dimana meja yang akan kita pakai, karena kita tidak melakukan booking, kita akan diberikan meja yang kosong pada WAKTU itu.

Dalam pertemuan kali ini, kita mempelajari tentang tiga jenis Linked List :

Circular Single Linked List
Doubly Linked List
Circular Doubly Linked List

1. Circular Single Linked List

Di dalam Linked List, kita memiliki Circular Single dan Circular Doubly. Persamaan diantara keduanya adalah sama sama tidak memiliki nilai NULL diakhir sebuah NODE. Namun, di Circular Single Linked List sendiri, akhiran pada sebuah node akan kembali ke HEAD yang ada di paling depan. Ini bisa diterapkan dengan melakukan loop hingga node terakhir dan jadikan node(terakhir)->next = head.

Pada gambar diatas (source:geekforgeeks), kita bisa lihat bahwa 3 itu sebagai HEAD dan 9 sebagai NODE terakhir. dan di node(9)->next = head(node 3) itu sebagai penyambung agar menjadi Circular Single Linked List.

2. Doubly Linked List

Doubly Linked List memiliki perbedaan yg cukup terlihat dibandingkan dengan Single Linked List. Disini memiliki HEAD dan TAIL. HEAD memiliki fungsi yang sama seperti di Single Linked List, yaitu sebagai awal, dan TAIL sebagai akhir dari sebuah Doubly Linked List. Untuk pointer, disini kita punya NEXT dan PREV, kegunaan PREV akan saya jelaskan nanti di bagian deletion.

didalam Doubly Linked List, kita bisa melakukan INSERT dan DELETE. INSERT sendiri yaitu memasukkan node baru kedalam Linked List. Penulisan coding INSERT dalam bahasa C/C++ bisa ditulis sabagai berikut :

Untuk membuat node baru:

Untuk melakukan pushHead (menjadikan node baru sebagai HEAD):

Untuk melakukan pushTail (menjadikan node baru sebagai TAIL):

Dan sekarang mari kita buat node dengan menulis ini:

Penulissan code DELETE adalah sebagai berikut :

Untuk menghapus HEAD:

Untuk menghapus TAIL:

Untuk menghapus node ke n:

Jika itu adalah node satu satunya:

3. Circular Doubly Linked List

Mirip seperti Circular Single Linked List, namun dalam kasus ini kita tidak hanya menyatukan node->next dengan head namun kita menyatukan head dengan tail. Caranya adalah dengan menjadikan tail->next = head dan head->prev = tail.