Ringkasan Data Strucuture Sampai UTS

Halo semuanya, pada hari ini kita akan membahas semua materi yang telah kita pelajari hingga bulan april ini. Nah, materi yang akan kita bahas antara lain adalah linked list, stack & queue, hashing & hash tables, dan binary search tree. Nah supaya kita tidak lupa, mari kita bahas satu persatu.

Linked List

Linked list ada 4 macam, antara lain:

Single Linked List
Doubly Linked List
Circular Single Linked List
Circular Double Linked List

Yang kita pelajari sekarang hanya single linked list dan doubly linked list

Single linked list

Single Linked List (geeksforgeeks)

Linked list adalah data structure linear. Nah tidak seperti array, linked list itu elemennya tidak disimpan bersebelahan. Elemen – elemen dari linked list disambung dengan pointer. Dalam kata lain, linked list adalah sekumpulan data yang dihubungkan dengan pointer data sebelumnya. Pointer yang dimiliki oleh single linked list hanyalah head, next, dan tail. Operasi yang dapat dilakukan dalam linked list adalah push head, push tail, push mid, pop head, dan pop tail. Nah push itu adalah operasi yang dibuat untuk memasukan data ke dalam linked list. Sedangkan pop adalah sebuah operasi yang dibuat untuk menghapus data yang ada di dalam linked list.

Double Linked List

Doubly Linked List (geeksforgeeks)

Sebenarnya, single linked list dan doubly linked list mempunyai perbedaan yang terbilang sangat sedikit. Yang sangat membedakannya dengan single linked list adalh pointer yang dipunyai pada double linked list. Bisa kita lihat pada gambar diatas, double linked list mempunyai pointer tambahan yaitu pointer prev. Nah, keuntungannya dapat dirasakan ketika kita ingin menghapus nodus sebelumnya. Pada single linked list, kita tidak dapat melakukannya karena arahnya hanya next, tidak dapat ke belakang lagi. Nah ternyata doubly linked list ini juga mempunyai kekurangan. Mempunyai pointer dengan dua arah membuat Doubly Linked List ini mempunyai ukuran data yang besar. Jika kita tidak membutuhkan pointer dengan dua arah, sebaiknya gunakan saja single linked list.

Stack & Queue

Stack & queue merupakan implementasi dari linked list. Jadi sebelum kita mengenal stack & queue lebih lanjut, lebih baik kita mengerti baik - baik tentang linked list terlebih dahulu.

Stack

Pada rangkuman yang telah saya buat sebelumnya, saya mengaitkan stack dengan permainan DoTA. Dalam DoTA ada teknik yang bernama stack. Teknik ini membuat monster jungle dapat spawn meskipun seharusnya tidak bisa spawn karena masih ada monster jungle. Nah, stack membuat monster jungle itu lebih banyak. Bisa kita simpulkan bahwa stack itu jika di data structure akan menyimpan elemennya dalam urut. Nah, kalo di dalam DoTA, kita harus membuat monster jungle pergi dari spawn box agar monster lainnya bisa spawn lagi. Hal ini mirip dengan data structure, yaitu ketika kita mau menambah elemen ditengah misalnya, kita harus membongkar elemennya dari paling atas, lalu kita bisa menghapus atau menambah elemen di dalamnya. Nah, dalam stack ini, ada dua urutan yaitu LIFO (last in first out) atau FILO (first in last out) atau lebih gampangnya, cara memasukkannya adalah dengan urut seperti biasa, dan ketika dilakukan deletion, maka data yang paling terakhir yang dihapus.

Ilustrasi Stack (geeksforgeeks)

Operasi yang ada di stack ada 3 yaitu pop, top, dan push. Pop adalah sebuah operasi untuk menghapus data dalam stack yang berarti data yang paling terakhir dimasukkan. top adalah sebuah operasi untuk memberi tahu kita data apa yang sedang berada di paling atas dalam stack. Sedangkan operasi push adalah operasi untuk menambahkan data dalam stack.

Operasi pada Stack (geeksforgeeks)

Queue

Kita semua pasti pernah mengantri kan? Jika kalian tidak pernah mengantri, bisa dipastikan hidup kalian sangat egois hahahaha. Ilustrasi yang paling gampang untuk menggambarkan queue adalah ketika kita mengantri untuk masuk ke dalam restoran yang ramai. Nah jika kita datang paling lama dari yang lain, maka dalam waiting list, nama kita akan ada di paling bawah kan? Nah, orang yang ada di waiting list nomor pertama pasti akan mendapatkan tempat duduk duluan. Ketika ada yang ingin masuk ke dalam waiting list lagi, maka orang itu akan mendapatkan tempat di waiting list paling bawah. Nah, di dalam queue di data structure cara kerjanya mirip seperti itu. Jadi, data yang paling awal dimasukkan yang dihapus dan data yang baru ditambahkan yang ditambah. Untuk lebih jelasnya dapat dilihat pada gambar dibawah. Urutan dari queue adalah FIFO (first in, first out). Bukan merk hape yang itu ya... hehehe.

Illustrasi queue (geeksforgeeks)

Operasi yang ada pada queue sama seperti stack, yaitu ada 3. Pertama adalah operasi push yaitu sebuah operasi yang digunakan untuk menambahkan data pada queue. Pada kasus queue berarti menambahkan datanya dari data paling pertama seperti terlihat di gambar pada bagian bawah ini. Kedua adalah operasi pop pada queue. Operasi pop ini digunakan untuk menghapus data pada queue yang berarti menghapus data paling pertama. Terakhir adalah operasi front yaitu menampilkan data yang pertama yang ada pada queue sekarang. Bisa disimpulkan bahwa queue adalah kebalikan dari stack itu sendiri.

Operasi pada stack (geeksforgeeks)

Hashing & Hash Tables, Trees

Pada bagian ini kita akan membahas tentang hashing, hash tables, dan trees. Pada bagian ini dibutuhkan pengetahuan kalian tentang linked list dengan sangat baik. Jadi kembali lagi, jika kalian belum terlalu mengerti tentang linked list, sebaiknya mengertilah lebih banyak tentang hal itu.

Hashing

Hashing adalah sebuah fungsi yang dapat mengubah sebuah string menjadi bentuk yang lebih simpel yang dapat merepresentasi string tersebut. Contohnya adalah ketika kita menyimpan nomor telepon. Nomor telepon itu kan panjang, sekitar 12 digit. Nah dengan hashing, kita hanya perlu mengambil 3 angka belakangnya. Biasanya hashing akan dipakai ketika kita memasukkan password pada suatu laman untuk login. Jadi waktu kita login akun kita menggunakan password, yang dicocokan merupakan hash key dari password tersebut. Jika hash keynya sama maka kita akan masuk ke akun kita. Jika tidak, maka kita tidak akan dapat masuk ke dalam akun kita.

Hash Tables

Hash table adalah sebuah tabel dalam bentuk array yang dapat menyimpan string atau integer. Index dari tabel itu adalah data yang dihash dan nilainya merupakan string itu sendiri. Untuk lebih jelasnya, mari kita lihat ilustrasi dibawah.

Illustrasi Hashing (geeksforgeeks)

Nah, ilustrasi diatas menjelaskan kita tentang hash table yang dibuat berdasarkan operasi x%10. Kita ambil angka pertama yaitu 11. 11%10 adalah 1, sehingga dalam hash table, index ke 1 dimasukkan angka 11. Begitu juga berlaku terhadap 12 yang dimodulus 10. Hasilnya kan 2, sehingga pada indeks ke 2 kita masukkan value 12. Mari kita buat hash tablenya supaya lebih jelas.

Hash Function

Hash mempunyai beberapa fungsi yaitu:

Mid-square, Division (yang biasa dipakai), Folding, Digit Extraction, dan Rotating Hash.

Mid-square adalah dengan mempangkatkan angka atau bilangan ascii dari sebuah karakter lalu dicari nilai di bagian tengahnya. Division merupakan fungsi yang paling sering dipakai. Caranya adalah dengan memoduluskan angkanya dengan ukuran dari hash table. Folding adalah fungsi yang membagi angka menjadi dua lalu menjumlahkannya. Digit extraction adalah fungsi yang digunakan dengan cara mengambil digit dari sebuah angka. Terakhir, rotating hash adalah sebuah fungsi dengan cara melakukan fungsi apapun lalu mengubah urutan dari angka yang sudah di hash. Fungsi ini berguna untuk membuat data lebih aman.

Collision

Ini akan terjadi jika kita mempunyai nilai hash dari sebuah angka yang sama. Misalnya kita akan memasukkan data dari string "Budi", "Caca", "Danang" "Bambang". Untuk masalah ini kita dapat mengatasinya dengan Linear Probing dan Chaining.

Linear Probing

"Budi" dan "Bambang" mempunyai huruf depan yang sama kan, makanya kita akan menaruh Bambang di 1, Caca di 2, Danang di 3, dan Budi di 4. Itu adalah cara Linear Probing bekerja, yaitu menaruh datanya di tempat manapun yang kosong. Tapi cara ini mempunyai kerugian yaitu jika terjadi banyak data yang sama yang menyebabkan collision, waktu untuk mencarinya akan lebih kompleks.

Tabel dengan teknik linear probing

Chaining

Nah, dengan chaining, kita dapat menyimpan data setiap string dalam sebuah rantai atau linked list. Contohnya Bambang->Budi di 1, Caca di 2, Danang di 3, Bambang di 4.

Tabel dengan teknik chaining

Trees

Trees adalah kumpulan dari satu atau lebih nodus.

Contoh Tree (Binusmaya)

Untuk lebih mengerti bagian - bagian dari tree, maka marilah kita kenali bagian - bagian dari tree.

Derajat dari pohon tersebut adalah 3

Derajat C adalah 2

Derajat F adalah 0

Parent dari C adalah A

Parent dari E adalah B

Leluhur dari F dan G adalah C dan A

Tingginya dalah 3
Saudara dari F adalah G

Binary Search Tree

Kembali lagi dengan pengaplikasian dari linked list, yaitu binary search tree. Seperti biasa jika belum menguasai linked list ada baiknya diperdalam dahulu. Binary search tree adalah sebuah metode dari data structure yang mempunyai ciri sebagai berikut:

Bagian kiri dari subtree adalah nodus yang mempunyai nilai yang lebih kecil

Bagian kanan dari subtree adalah nodus yang mempunyai nilai yang lebih besar

Bagian kiri dan kanan dari subtree harus berupa binary search tree juga

Mencari Sebuah Angka (searching)

Ilustrasi Binary Search Tree dari geeksforgeeks

Bisa kita lihat dari contoh diatas, bagian kiri dari binary search tree merupakan nilai yang kecil sedangkan bagian kanannya adalah nilai-nilai yang besar.

Kita bisa mengambil contoh angka 7. Ketika angka 7 ingin dicari pada binary search tree diatas, maka dia akan mengecek. Apakah 8 lebih kecil atau besar dari 7? Karena lebih kecil, maka 7 akan dicari di bagian kiri. Kemudian, akan dicek lagi. Apakah 7 lebih kecil daripada 3? Jawabannya adalah tidak, sehingga 7 dicari dibagian kanan. Lalu ketika sampai di 6, karena 7 lebih besar daripada 6, maka lokasi 7 pasti di kanan dari cabang si 6. Begitulah kira - kira cara kerja dari binary search tree.

Memasukkan Sebuah Angka pada BST (insertion)

         100                               100
        /   \        Insert 5            /    \
      20     500    --------->          20     500 
     /  \                              /  \  
    10   30                           10   30
                                     / 
                                    5

Coba kita lihat illustrasi ketika kita akan melakukan insertion pada binary search tree. Nah, pada contoh diatas, saya ingin memasukkan 5 pada binary search tree tersebut. Karena angka 5 lebih kecil daripada 100, maka saya akan menaronya di bagian kiri dari cabang 100. Lalu karena lebih kecil dari 20, saya taro lagi di bagian kiri dari 20. Nah ketika bertemu 10. Otomatis 5 akan ditaro di kiri cabang dari 10 karena nilainya lebih kecil daripada 10.

Menghapus Sebuah Angka pada BST (deletion)

Setelah kita mempelajari insertion, sekarang kita akan membahas tentang delete. Seperti namanya sendiri, kita akan menghapus angka yang ada di binary search tree sesuai dengan angka yang ingin dihapus. Kemungkinan dan cara dalam melakukan delete pada binary search tree adalah sebagai berikut:

1) Nodus yang ingin di hapus ada pada daun: Yaudah hapus aja langsung, gampang kan?

              50                            50
           /     \         delete(20)      /   \
          30      70       --------->    30     70 
         /  \    /  \                     \    /  \ 
       20   40  60   80                   40  60   80

2) Nodus yang ingin di hapus hanya mempunyai satu cabang atau keturunan: Salin keturunannya lalu taro di tempat di mana angka tersebut di hapus.

              50                            50
           /     \         delete(30)      /   \
          30      70       --------->    40     70 
            \    /  \                          /  \ 
            40  60   80                       60   80

3) Nodus yang ingin di hapus hanya mempunyai dua cabang atau keturunan: Cari keturunan di bagian kanan yang mempunyai nilai paling kecil. Dalam contoh ini, karena 60 lebih besar dari 50 dan kebetulan paling kecil di bagian kanan 50, maka angka ini naik jadi paling atas dan angka 50 dihapus. Metode yang dapat dipakai adalah dengan mengambil nilai maksimal kiri atau minimal kanan.

             50                            60
           /     \         delete(50)      /   \
          40      70       --------->    40    70 
                 /  \                            \ 
                60   80                           80

The Creation Trio

Cari Blog Ini