Nama : Arjuna Accha Dipa
NIM : 2301865735
Kelas : CB-01
Dosen : Henry Chong (D4460) dan Ferdinand Ariandy Luwinda (D4522)
Linked List
NIM : 2301865735
Kelas : CB-01
Dosen : Henry Chong (D4460) dan Ferdinand Ariandy Luwinda (D4522)
Linked List
Apa sih linked list itu? Jadi, linked list (seranai berantai) adalah struktur data yang mengandung/memiliki urutan record data dimana setiap record data memiliki suatu tempat (field) yang menyimpan alamat dari record data selanjutnya. Elemen-elemen dari suatu data disebut Node.
Lalu, apa bedanya dengan array?? Biasanya, pada array, kita telah mendeklarasikan berapa jumlah yang akan digunakan nantinya, sedangkan linked list tidak. Linked list menggunakan malloc (memory allocation) untuk menambah/mereserve NODE. Selain itu, jika kita mereserve tempat untuk array, address dari setiap index akan berdekatan/memiliki kelipatan yang sama. Sedangkan dalam linked list tidak, karena linked list menggunakan malloc, maka NODE baru dapat memiliki address yang berjauhan dengan NODE sebelumnya (address tersebut dapat random, sesuai dengan memory yang sedang tidak digunakan oleh komputer).
Dalam suatu linked list, akan ada 3 pointer yang akan digunakan, yakni pointer HEAD, TAIL, dan CURRENT.
l Pointer HEAD, digunakan untuk menunjuk address dari NODE pertama dalam linked list.
l Pointer TAIL, digunakan untuk menunjuk address dari NODE terakhir dalam linked list.
l Pointer CURRENT, digunakan sebagai pembantu pointer HEAD dan TAIL.
Sebuah linked list dinyatakan kosong apabila isi dari pointer HEAD adalah NULL. Dalam single linked list, linked list yang telah dibuat tidak dapat menunjuk ke NODE yang ada dibelakangnya (previous) dan hanya bisa menunjuk NODE yang ada di depannya (next), karena single linked list hanya memiliki satu buah tangan yang digunakan untuk menyimpan address dari NODE selanjutnya.
Dalam linked list terdapat 3 fungsi, yaitu:
l Push
Push atau insert, digunakan untuk memasukkan data. Push sendiri terdapat 3 macam, yaitu: push depan (NODE baru akan berada di depan NODE yang lama), push belakang (NODE baru akan berada di belakang NODE yang lama), dan push tengah (NODE baru akan berada di tengah-tengah NODE yang lama). Berikut merupakan contoh program yang menggunakan push depan:
Dalam potongan program tersebut dapat diketahui bahwa program tersebut digunakan untuk menambahkan/memasukkan data berupa pensil dengan harga 5000.
l Delete
Seperti namanya, delete merupakan fungsi yang digunakan untuk menghapus suatu data dalam linked list. Delete juga memiliki 3 jenis, yaitu delete depan, delete belakang, dan delete tengah. Berikut merupakan contoh program yang menggunakan fungsi delete:
Dalam potongan program tersebut dapat diketahui bahwa program tersebut digunakan untuk menghapus data buku. Mengapa data buku yang terhapus dan bukannya pensil? Karena program tersebut menggunakan push depan, sehingga data ada dalam linked list akan seperti ini: Buku, Pensil. Jika kita menggunakan fungsi delete depan maka, data bukulah yang akan terhapus.
l Print
Fungsi print, digunakan untuk menampilkan seluruh data yang ada pada linked list. Berikut merupakan contoh dari fungsi print:
Dalam potongan program tersebut, dapat dilihat bahwa, selama nilai curr->next bukan NULL, maka ia akan ngeprint nilai dari curr.
Circular Linked List
Circular Linked List merupakan variasi dari Linked List. Bedanya, pada Circular Linked List, pointer next dari TAIL adalah HEAD. Circular Linked List dapat dibuat dari Single Linked List dan Double Linked List.
Dalam Single Linked List, pointer next dari TAIL adalah HEAD.
Dalam Double Linked List, pointer next dari TAIL adalah HEAD dan pointer previous dari HEAD adalah TAIL sehingga akan terbentuk lingkaran (circular) di kedua sisinya.
Double Linked List
Double Linked List merupakan Linked List yang memiliki dua pointer penunjuk. Dua pointer penunjuk tersebut menunjuk ke arah node sebelum dan node sesudah.
Sama seperti Single Linked List, kita haru mengalikasikan node baru dan meng-assign nilai kedalamnya. Setelah itu, kita hubungkan node tersebut dengan Linked List yang telah ada. Operasi yang biasanya ada di dalam Double Linked List merupakan operasi yang sama dengan yang ada dalam Single Linked List. Berikut merupakan contoh operasi pada Double Linked List maupun Single Linked List:
1. Push
Push atau insert merupakan sebuah operasi untuk memasukkan data, dimana di dalam Linked List terdapat dua kemungkinan untuk memasukkan data. Yaitu push depan yang berarti data baru akan dimasukkan di depan data lainnya dan push belakang berarti data baru akan dimasukkan di belakang data lainnya.
Contoh untuk insert node baru dibelakang TAIL
Contoh untuk insert node baru diantara HEAD dan TAIL
Contoh untuk insert node baru dibelakang TAIL
Contoh untuk insert node baru diantara HEAD dan TAIL
2. Pop
Pop merupakan operasi delete, yang digunakan untuk membuang atau menghapus suatu list. Ada empat kondisi yang harus diperhatikan saat melakukan operasi delete ini, yaitu: node yang dihapus merupakan node yang ada di dalam Linked List, node yang dihapus merupakan HEAD, node yang dihapus merupakan TAIL, node yang dihapus bukan HEAD ataupun TAIL.
Jika yang mau didelete adalah node nya saja
Jika node yang mau didelete adalah HEAD
Jika node yang mau didelete adalah TAIL
Jika node yang mau didelete bukan di HEAD ataupun di TAIL
Hashing
Apa sih hashing itu? Hashing adalah sebuah teknik yang digunakan untuk menyimpan dan mengambil kunci dalam waktu yang cepat atau singkat. Dalam hashing, string akan diubah menjadi string yang lebih pendek atau kunci yang merepresentasikan string awal. Hashing dapat diartikan sebagai konsep pembagian kunci dalam array (hash table) dengan fungsi yang telah ditentukan sebelumnya (hash function).
Oke, sekarang kita sudah tau apa itu hashing. Kalau gitu, hash table itu apa sih? Hash table adalah sebuah tabel (array) dimana kita menyimpan string awal (original string). Biasanya ukuran dari hash table lebih kecil dari jumlah total string. Jadi ada kemungkinan beberapa string memiliki hash key yang sama.
Gambar diatas menunjukan hash table dengan ukuran n = 10. Setiap posisi dari hash table disebut slot. Hash table tidak mengandung item, sehingga setiap slotnya kosong. Contoh, kita memiliki integer items {26, 70, 18, 31, 54, 93}. Salah satu cara yang paling umum untuk mentukan hash key adalah dengan cara:
Hash key = nilai key % jumlah slot
Cara diatas merupakan cara menentukan hash key dengan metode division. Dengan menggunakan cara tersebut, maka berikut adalah hasil dari hash key
Data Item
|
Hash Key
|
Hash Value
|
26
|
26 % 10 = 6
|
6
|
70
|
70 % 10 = 0
|
0
|
18
|
18 % 10 = 8
|
8
|
31
|
31 % 10 = 1
|
1
|
54
|
54 % 10 = 4
|
4
|
93
|
93 % 10 = 3
|
3
|
Setelah itu, kita masukkan ke dalam hash table
Selain menggunakan cara diatas, berikut merupakan metode yang dapat digunakan untuk membangun fungsi hash:
l Mid square
Kuadratkan nilai dari key, lalu ambil nilai tengah dari hasil kuadrat tersebut. Contoh: key = 3121, key2 = 9740641, bagian yang diambil = 406
l Division
Bagi string atau identifier dengan menggunakan operator modulus (seperti contoh diatas). Metode ini merupakan metode yang paling sering dipakai.
l Folding
Partisi string / identifier menjadi beberapa bagian, lalu menambahkan bagian-bagian yang ada untuk mendapatkan hash key.
l Digit Extraction
Digit yang telah ditentukan dari nomor yang diberikan dianggap sebagai alamat dari hash.
l Rotating Hash
Menggunakan metode hash apapun (seperti division, atau folding). Setelah mendapatkan hash code/alamat dari hash method, lakukan rotasi. Rotasi dilakukan dengan shifting digits untuk mendapatkan alamat hash yang baru.
Trees and Binary Tree
Salah satu materi dalam Data Structures yang paling penting adalah Tree. Tree biasa digunakan untuk mewakili data yang memiliki struktur hierarki antar elemen. Selain itu, Binary Tree adalah tipe spesial dari tree dimana setiap node antara tidak memiliki node, memiliki satu node atau dua node. Ada dua cara untuk mewakili binary tree, yaitu dengan menggunakan array dan dengan menggunakan linked list. Child node dalam binary tree di sebelah kiri disebut sebagai “left child node” dan child node di sebelah kanan disebut sebagai “right childe node”.
Pada gambar di atas, root node 8 (root merupakan node yang paling atas) memiliki 2 anak (3 dan 10), kemudian kedua child node bertindak sebagai parent node untuk child node 1 dan 6 (bagi left parent node) dan 14 (bagi right parent node) dan seterusnya.
Binary tree memiliki beberapa bentuk atau jenis, berikut merupakan beberapa contohnya:
l Full Binary Tree
l Complete Binary Tree
l Skewed Binary Tree
l Dan lain-lain
Stack and Queue
1. Pengertian Stack dan Queue
a) Stack
Stack atau tumpukan adalah cara penyimpanan dalam memori, dimana data yang dimasukkan pertama akan dikeluarkan terakhir. Sama seperti kita menaruh kue kedalam toples. Jika kita ingin memakannya, kue yang pertama kali kita makan adalah kue terakhir yang masuk ke dalam toples.
b) Queue
Queue atau antrian adalah cara penyimpanan dalam memori, dimana data yang dimasukkan pertama akan dikeluarkan pertama. Seperti jika kita mengantri disebuah restoran. Orang yang datang pertama kali akan dilayani terlebih dahulu.
AVL Tree
Apa sih AVL Tree itu? AVL Tree merupakan subtipe dari Binary Search Tree (BST). AVL Tree diberi nama sesuai dengan nama penemunya, yaitu Adelson, Velskii, dan Landis. Lalu, apa bedanya dengan BST? Jadi, bedanya antara BST dan AVL Tree adalah AVL Tree memiliki kemampuan untuk menyeimbangkan secara dinamis sebuah BST agar tetap memiliki kompleksitas log (n). Mengapa demikian? BST memiliki kelemahan, kelemahan tersebut akan membuat kompleksitas pencarian suatu data dalam BST menjadi O(n). Contohnya kita akan menginputkan 5 bilangan angka berurutan dari angka 1. Maka yang terjadi adalah 2 menjadi anak kanan dari 1, 3 menjadi anak kanan dari 2, 4 menjadi anak kanan dari 3, dan 5 menjadi anak kanan dari 4. Jika kita akan mencari data bernilai 4. Maka program harus melakukan 4 kali looping. Hal inilah yang membuat kompleksitas dari BST tidak konsisten. Ketika input telah dimasukkan ke dalam tree, AVL Tree akan mengecek tinggi atau kedalaman dari anak kiri dan anak kanan. Apabila perbedaan tinggi tersebut lebih dari 1, maka akan dilakukan penyeimbangan. Berikut merupakan contoh dari tree yang seimbang dan tidak seimbang:
Pada tree ke-2, anak kiri dari C memiliki ketinggian 2 dan anak kanan dari C memiliki ketinggian 0 (tidak ada). Pada tree ke-3, anak kanan dari A memiliki ketinggian 2 dan anak kiri memiliki ketinggian 0. Karena perbedaan ketinggian pada tree ke-2 dan ke-3 adalah 2, maka akan dilakukan penyeimbangan.
Penyeimbangan
Penyeimbangan tree dapat dilakukan dengan metode rotasi. Dalam AVL Tree ada 2 cara rotasi, yaitu single rotation dan double rotation. Berikut merupakan contoh dari single rotaion:
Ketika node 12 dimasukkan, maka tree akan menjadi tidak seimbang. Mengapa tidak seimbang? Karena anak kiri dari node 30, memilki ketinggian 4 dan anak kanannya memiliki ketiggian 2. Perbedaan ketiggian tersebut lebih dari 1, maka akan dilakukan penyeimbangan.
Karena yang memiliki ketinggian lebih banyak adalah anak kiri dari node 30 dan dari node 22 yang miliki ketinggian lebih banyak adalah anak kiri juga, maka node 22 akan naik, node 30 menjadi anak kanan dari node 22, dan node 27 lepas dan menjadi anakkiri dari node 30.
Lalu, kapan double rotation akan digunakan? Doube Rotation akan digunakan apabila dalam kasus diatas, dari node 22 yang memiliki ketingan lebih banyak adalah anak kanan. Misalnya, node 12 kita ganti degan node 28 lalu kita tambahkan node 25. Maka perbedaan ketinggian anak kiri dan anak kanan dari node 30 akan menjadi 2. Oleh karena itu, node 27 akan naik dan node 22 menjadi anak kiri dari node 27. Lalu setelah itu, node 27 akan naik menggantikan posisi node 30 dan node 30 akan menjadi anak kanan dari node 27.
Heap
Apa itu Heap? Heap merupakan Data Structure yang menggunakan konsep Binary Tree yang tersimpan dalam bentuk array dalam urutan yang spesifik. Jumlah anak maksimal yang dimiliki oleh heap bergantung pada tipe heap itu sendiri. Pada umumnya, anak maksimalnya adalah dua. Saat melakukan input, input baru akan menjadi node paling akhir dari sebuah heap. Kemudian, akan dilakukan adjustment agar sesuai dengan aturan heap. Heap memiliki 3 bentuk, yaitu min heap, max heap, dan min-max heap.
Min Heap, Max Heap, Min-Max Heap
Min heap dan max heap memiliki cara kerja yang sama, bedanya pada saat melakukan adjustment min heap akan membandingkan apabila child (input baru) lebih kecil dari parent, maka dia akan melakukan swap dengan parentnya. Sedangkan max heap akan membandingkan apabila child lebih besar dari parent, maka dia akan melakukan swap dengan parentnya. Oleh karena itu, root dari min heap selalu angka yang paling kecil dan root dari max heap selalu angka yang paling besar.
Untuk min-max heap, pada tiap level tree memiliki status yang berbeda. Untuk level ganjil akan memiliki status min dan untuk level genap akan memiliki status max.
Insertion
Bagaimana cara memasukkan data ke dalam heap? Pertama-tama, data yang ingin dimasukkan akan menjadi node terakhir dalam heap (tiap level akan dipenuhi dulu setelah level tersebut tidak bisa menampung node lagi, maka akan membuat level baru). Node baru tersebut bisa jadi melanggar aturan heap (baik heap min, max, maupun min-max). Oleh karena itu, ia akan dibandingkan dengan parent (apabila heap min atau max) atau bahkan dibandingkan dengan grandparent juga (heap min-max). Apabila setelah dibandingkan, ternyata memang melanggar aturan tersebut, maka akan dilakukan adjustment yang dinamakan heapify up karena dibandingkan dengan node atasnya (parent maupun grandparent).
Deletion
Jika kita sudah tau bagaimana cara memasukkan data kedalam heap, maka kita juga harus belajar bagaimana cara menghapus data dari heap. Ketika akan menghapus dari heap. Maka yang kita hapus adalah root nya. Tidak peduli apakah itu heap min, heap max, ataupun heap min-max. Setelah itu, node paling akhir akan menjadi node, dan akan dilakukan adjustment yang dinamakan heapify down karena dibandingkan dengan node bawahnya. Lalu, bagaimana jika kita ingin menghapus node tertentu secara spesifik? Hal tersebut dapat dilakukan dengan melakukan searching lalu hapus node tersebut. Akan tetapi, hal tersebut berbeda dengan heap yang kita sebutkan tadi. Heap yang dapat menghapus node tertentu dapat disebut modified heap.
Tries
Apa itu Tries? Tries adalah tree data structure yang berurutan yang digunakan untuk menyimpan string dalam array. Tries berasal dari kata “retrieval” karena tries dapat menemukan 1 kata dari kamus hanya dengan menggunakan prefix. Apa gunanya tries? Tries dapat digunakan sebagai spell checker atau suggestion words seperti pada google atau keyboard pada hp karena tries menggunakan prefix dari yang kita inputkan.
Bagian root tidak memiliki nilai atau NULL. Serta untuk mengetahui bahwa huruf terakhir akan membentuk sebuah kata, maka trie memiliki boolean variable yang disebut dengan IsEnd (dalam gambar, bintang merupakand IsEnd). Contohnya dari node “d”, akan membentuk kata “do” apabila berhenti di “o” dan akan membentuk kata “dork” apabila berhenti di node “k”.
References:
Tidak ada komentar:
Posting Komentar