Skip to main content

Linked List


Pada materi kali ini, kita membahas tentang Linked List dalam bahasa pemrograman C. Untuk kali ini kita akan fokus terhadap beberapa jenis Linked List yang lebih dalam termasuk :
1.       Circular Singly Linked List
2.      Doubly Linked List
3.      Circular Doubly Linked List
Linked List sendiri adalah struktur data yang menyimpan sebuah data serta sebuah referensi untuk menunjukkan data selanjutnya dalam urutan tertentu.

Circular Single Linked List
Dalam Circular Single Linked List, untuk mengakses bagian mana pun, kita perlu melewati data pertama yang ada dalam urutan. Jika dalam pengecekan kita berada dalam tengah urutan, maka tidak mungkin kita dapat mengakses data yang berada sebelum bagian di mana kita berada. Nilai NULL dalam Circular Single Linked List tidak disimpan dalam urutan data.
Berikut ini gambar untuk memasukkan nilai awal dalam Circular Single Linked List, Sama halnya seperti insertion dalam Single Linked List.






*data = node

Doubly Linked List
Tidak seperti Single Linked List, Doubly Linked List dapat menunjuk ke data setelah urutan saat ini dan data sebelumnya. Karena Doubly Linked List dapat melakukan hal tersebut, tentu saja membuat Doubly Linked List lebih kompleks. Bagian dari Doubly Linked List dibagi menjadi tiga, yaitu data dari urutan data itu sendiri, pointer untuk menuju ke data selanjutnya, dan pointer untuk menuju data sebelumnya.


Untuk insertion dalam Doubly Linked List dapat terjadi pada awal urutan data, akhir urutan data, maupun dalam tengah – tengah urutan data. Berikut penjelasan lebih lengkapnya.

Insertion pada Awal Urutan Data
Untuk melakukan Insertion dalam Doubly Linked List kita harus memberi ruangan dalam memori untuk data baru yang ingin dimasukkan. Setelah itu, kita harus mengecek terlebih dahulu apakah urutan data yang ada kosong atau tidak. Jika urutan data tersebut kosong, maka pointer untuk urutan setelah data ini dan sebelum data ini akan menjadi NULL. Jika urutan data tersebut tidak kosong, maka data yang sebelumnya menjadi awal dari urutan tersebut menjadi urutan kedua, dan data baru ini menjadi data pertama.


Insertion pada Akhir Urutan Data
Kurang lebih sama seperti Insertion pada Awal Urutan Data, Insertion pada Akhir Urutan Data hanya berbeda pada bagian jika urutan data tidak kosong. Tepatnya jika urutan data tidak kosong, maka kita harus mencari akhir dari urutan data ini. Selama data setelah urutan saat ini tidak sama dengan NULL, maka kita akan terus berpindah urutan. Saat telah mencapai akhir, maka data yang paling akhir akan menjadi data sebelum data terakhir, dan data baru akan menjadi data terakhir.


Insertion pada Tengah - Tengah Data
Bagian ini cukup berbeda dengan kedua Insertion diatas, karena lokasi yang ingin dimasukkan sebuah data sudah di tentukan oleh pengguna. Konsep awal sebenarnya sama dengan dua Insertion diatas, namun bagian yang berbeda adalah kita harus mencari lokasi yang dimaksud terlebih dahulu sebelum memasukkan data.


Setelah Insertion, terdapat juga Delete. Delete dalam Doubly Linked List dibagi menjadi empat, yaitu Delete the only data, delete the head, delete the tail, dan terakhir Delete on a specified location.

Delete the Only Data
Dapat menggunakan metode free dalam bahasa C, serta menghapus hubungan yang ada dalam data.

Delete the Head
Sebelum menggunakan metode free, kita perlu mengatur agar urutan awal dari data tidak hilang. Setelah menggunakan metode free, kita harus memastikan bahwa hubungan antara data awal yang baru dengan data kedua yang baru tidak hilang.

Delete the Tail
Kita akan membuat data sebelum data terakhir menjadi yang terakhir dan melakukan metode free untuk data terakhir yang ingin dibuang. Setelah data terakhir dibuang, kita juga perlu memastikan bahwa hubungan antara data awal dengan data akhir yang baru tidak terputus.

Delete on a Specified Location
Sebelum menghapus data, kita perlu mencari data yang ingin dihapus, serta memastikan seluruh hubungan antar data tidak terputus setelah data spesifik yang telah ditunjuk dihapus.

Circular Doubly Linked List
Sebenarnya tidak jauh berbeda dengan Circular Single Linked List, Circular Doubly Linked List hanya memiliki satu perbedaan, yaitu seluruh data dalam Circular Doubly Linked List memiliki 2 pointer.
Sekian informasi dari saya, terima kasih telah membaca! ^w^

Sumber :

BINUS University – Data Structures – Linked List II (L)

https://www.geeksforgeeks.org/circular-singly-linked-list-insertion/, diakses pada 25 Februari 2020 pukul 19.05 WIB

https://www.javatpoint.com/doubly-linked-list, diakses pada 25 Februari 2020 pukul 19.12 WIB

Comments

Post a Comment

Popular posts from this blog

Rangkuman 2

Nama: Christopher Wibisono NIM: 2301913822 Nama Dosen: CB01 (Kelas Besar) : Henry Chong(D4460) & Ferdinand Ariandy Luwinda (D4522) LM01 (Kelas Kecil) : Alexander (D5319) Pada blog kali ini, kita akan mereview apa saja yang sudah dipelajari selama akhir semester 2 ini. AVL Tree  adalah lanjutan dari  Binary Search Tree . Dengan  AVL Tree ,  Binary Search Tree  yang tingginya berat sebelah akan dibuat menjadi rata dengan mengubah posisi dari  node  yang membuat  tree  tidak seimbang. Pengubahan posisi tersebut dilakukan dengan cara  rotating , dimana  node  yang menjadi akar masalah dalam  tree  tersebut akan dipindahkan menjadi node yang berada diatas nya dan node yang berada pada atasnya akan berubah tempat mengikuti dengan aturan  Binary Search Tree . Rotating  terbagi menjadi dua, yaitu  Single Rotate  dan  Double Rotate . Seperti namanya,  Single Rotation  ...
Post a Comment
Read more

AVL Tree

AVL Tree adalah lanjutan dari Binary Search Tree . Dengan AVL Tree , Binary Search Tree yang tingginya berat sebelah akan dibuat menjadi rata dengan mengubah posisi dari node yang membuat tree tidak seimbang. Pengubahan posisi tersebut dilakukan dengan cara rotating , dimana node yang menjadi akar masalah dalam tree tersebut akan dipindahkan menjadi node yang berada diatas nya dan node yang berada pada atasnya akan berubah tempat mengikuti dengan aturan Binary Search Tree . Rotating terbagi menjadi dua, yaitu Single Rotate dan Double Rotate . Seperti namanya, Single Rotation merupakan Rotasi yang dilakukan sekali saja. Rotasi ini hanya dilakukan sekali saja, dengan menemukan node yang membuat tree tersebut tidak seimbang, lalu menggantikan node tersebut dengan node yang berada di bawahnya serta memindah node itu sendiri untuk menyeimbangkan tree tersebut. Node 30 menempati node 25 dan node 25 menjadi leaf kiri node 30 untuk menyeimbangkan tree ....
Post a Comment
Read more

RANGKUMAN GANJIL

Linked list adalah struktur data yang terdiri dari serangkaian rekaman data yang memiliki penunjuk untuk mengarahkan ke rekaman data yang ada setelah rekaman data ini. Untuk menggunakan linked list , kita memerlukan memory allocation untuk menyiapkan sebagian memori yang akan digunakan oleh linked list. Contoh: int   * cth = (int *) malloc(sizeof(int)); char * ct = (char *) malloc(sizeof(char)); * cth = 205; * ct = ‘A’; printf( “%d %c\n”, * cth , * ct ); Untuk melepas memori yang tidak digunakan lagi, dapat digunakan fungsi free. Contoh: free( cth ); free( ct ); Pada materi kali ini, kita membahas tentang  Linked List  dalam bahasa pemrograman C. Untuk kali ini kita akan fokus terhadap beberapa jenis  Linked List  yang lebih dalam termasuk : 1.         Circular Singly Linked List 2.        Doubly Linked List 3.        Circular Doubly Linked L...
Post a Comment
Read more