Data Structure 5

Rangkuman UTS

Rangkuman "Linked List II"

Circular Singly Linked List

• Masing-masing node hanya punya satu pointer, yaitu pointer yang menunjuk ke alamat node berikutnya (next)
• Pointer pada node terakhir menunjuk kembali kepada alamat dari node pertama, maka tidak ada yang menunjuk pada nilai NULL dalam linked list jenis yang ini

Doubly Linked List

• Masing-masing node mempunyai 2 pointer, pointer pertama berfungsi untuk menunjuk alamat node sebelumnya, pointer yang kedua berfungsi untuk menunjuk ke alamat pointer berikutnya
• Pointer pada node pertama yang berfungsi untuk menunjuk alamat node sebelumnya menunjuk pada NULL
• Pointer pada node terakhir yang berfungsi untuk menunjuk alamat node berikutnya menunjuk pada NULL

Circular Doubly Linked List

• Cara kerjanya sangat mirip dengan "Circular Singly Linked List", tetapi pada linked list jenis yang ini masing-masing node mempunyai 2 pointer, yaitu pointer yang menunjuk kepada node berikutnya dan pointer yang menunjuk pada node sebelumnya

Refrensi

• https://www.youtube.com/watch?v=rS3xNaDpC5w
• https://www.youtube.com/watch?v=BFYLS0uPnJk&t=

Rangkuman Pertemuan 6

Gw belajar beberapa hal dari kelas besar tadi pagi. Yang pertama, gua diajarin sama Pak Ferdinand logic dari codingan linked list. Pak Ferdinand jelasin dengan step by step dan langkah-langkah dari pembuatan codingan Singly Linked List. Mulai dari logic headnya biar bisa stay di depan dan ga gerak-gerak, current yang harus bisa gerak sesuai dengan berapa kali kita next valuenya, dan gimana caranya tail bisa didorong sampe ke data yang terakhir dan stay di sana.

Selain itu, gua juga belajar kalo dalam codingan Linked List, mungkin banget buat kami (mahasiswa yang belum berpengalaman dalam coding Linked List) buat salah logic saat coding dan ga menyadarinya sampe beberapa waktu. Misalnya, salah mendefinisikan head->nextnya atau apapun itu mungkin ga langsung membuat programnya crash dan gabisa jalan, tapi pas kita coba masukin semua value datanya pasti ada yang salah. Maka dari itu gua juga belajar bahwa kita harus bukan dengerin penjelasan Pak Ferdinand kayak yang tadi pagi kita lakuin, tapi juga coba sendiri di luar kelas dan diulang-ulang agar logicnya lebih ngerti lagi dan udah jadi terbiasa dengan kesalahan-kesalahan dalam ngoding Linked List nantinya.

Gw juga belajar logicnya "pop" (menghapus value dari data) dalam Linked List dan kesalahan-kesalahan yang seringkali dilakuin oleh mahasiswa dalam ngoding "pop". Yang banyak banget dibahas juga tadi itu, seringkali kita udah berhasil merangkai codingan suatu function, tapi kita seringkali lupa kalo codingan kita biasanya hanya berlaku di saat kondisi datanya masih lebih dari satu. Maka dari itu, kita juga gaboleh lupa untuk nambahin kondisi jika datanya udah tinggal 1 atau jika datanya udah dipaling ujung (intinya kondisi yang beda sendiri dari yang lain dan cara penyelsaiannya juga harus dibedain dari "kondisi normal" biasanya).

Gw juga belajar kalo kita bisa ngeprint semua value dari data yang ada dengan gausah ribet ngeprint satu-satu. Kita bisa dapetin pola (seperti kalo dalam kasus yang tadi itu curr->next), abis itu kita tinggal pake looping untuk ngeprint smua value dari datanya sampe datanya habis.

Dan yang terakhir, gw juga diajarin sekilas logic dari codingan Doubly Linked List dan logic dari "previous". Keunggulan dari Doubly Linked List itu salah satunya adalah saat kita mau ngebuat fungsi "pop" yang bisa dilakuin jauh lebih gampang karena kita punya tangan untuk "previous"nya. Tapi kelemahannya ya kita jadi lebih ribet karna harus ngurus 2 tangan. Pak Ferdinand juga bilang kalo dalam kasus-kasus tertentu terkadang ada baiknya kita punya lebih dari 1 current. Fungsinya adalah tentunya mempercepat pencarian data kalo datanya emang udah semakin banyak. Bahkan kita bisa buat tangan sebanyak-banyaknya yang kita mau even sampe 8 tangan. Tapi, dalam kebanyakan kasus 4 tangan udah cukup banget buat menyelsaikan permintaan yang kita minta ke komputer kita.

Hashing Table

Gw nonton beberapa video youtube tentang hashing table di data structure dan gw belajar beberapa hal. Yang pertama, gw belajar secara kasar apa itu pengertian dari hashing table. Yang gw dapet, hashing table itu mirip dengan kalo kita mau cari seseorang secara spesifik di contact hp kita. Jadi di videonya, dia gambarin hashing table itu kayak array dengan index-index seperti biasanya. Misalnya, kita mau masukin nomor seseorang. Kita tinggal masukin dengan fungsi "hash" dan masukkin kode yang menunjuk kepada nomor orang tersebut. Misalnya itu nomornya si Budi, brati yang kita masukkin ke dalem fungsi hashing tablenya adalah "Budi". Nanti, hashing tablenya bakal ngeluarin index (yang berarti, di index berapa si nomor teleponnya Budi disimpen), misalnya nomor telepon Budi disimpen di index 0. Dan kita bukan cuman bisa simpen 1 value doang..kita bisa simpen banyak value dengan kode-kode yang berbeda untuk menunjuk ke value yang beda-beda juga.

Misalnya, abis gw masukkin value yang pertama (nomor telepon Budi), gw mo masukin value yang kedua, yaitu nomor teleponnya si "Charles". Gw bisa lansung pake fungsi hash yang tadi dan masukkin kode gw yg merujuk ke valuenya (nomor telepon di Charles). Dan si hashnya juga bakal nunjukin index berapa si value Charles ini disimpen. Selanjutnya gw mau masukkin nomor teleponnya Quincy misalnya, gw juga tinggal panggil fungsi hash yang tadi dan langsung masukkin kode "Quincy" (yang merujuk kepada value nomor teleponnya si Quincy). 

Nah tapi, akan ada saat di saat kita mau masukkin value lagi (misalnya Joni), si fungsi hashnya malah ngeluarin index yang udah pernah keluar, misalnya index 0. Nah untuk menanggulangi masalah ini, dalam hashing table, kita ga ngebuang value dari Budi ataupun Joni, melainkan dia ngebuat semacem "linked list di dalam array".  Mungkin kalo liat gambar di bawah jadi lebih kebayang..

Dan setiap kali kita mau nyari nomor telepon dari si Joni, kita ga perlu cari satu-satu value apa aja yang udah pernah kita masukkin ke dalem hashing table ini, melainkan kita tinggal masukkin kata kuncinya, yaitu "Joni"..dan fungsi hashnya bakal ngeluarin di index berapa si value Joni itu disimpen. Dalam konteks ini, value (nomor telepon si Joni) disimpen di index ke 0 (bebarengan dengan value si Budi). Nah, setelah kita udah tau kita harus mulai pencarian ini dari index ke berapa, kita baru deh mulai cari dengan caranya kita nyari data di "linked list" seperti biasanya. Kalo sekarang gw balikin lagi ke metode pencarian nomor telepon seseorang dalama aplikasi contact di hp kita masing-masing udah kebayang kan maksudnya kayak apa.

Gw juga nonton apa hubungan hashing table dalam block chain. Dan dalam block chain ini bahkan lebih revolusioner lagi menurut gw. Di videonya gw belajar bahwa bahkan hashing table itu sendiri punya syarat-syarat penting kalo mau diimplementasikan ke dalam block chain (ada 5 syarat). Pertama, perubahan sedikit aja terhadap hashnya/keynya, data yang berubah juga harus signifikan perubahannya. Kedua, hashing dalam block chain setiap kali kita input key yang sama, outputnya juga harus sama persis. Ketiga, proses penyocokan input dengan outputnya juga harus berjalan dengan cepat agar prosesnya efisien. Keempat, infeasible yang berarti kita bakal bisa ngebuka suatu kode di saat kita bisa cocokin semua inputnya dengan outputnya. Kita emang bisa cobain satu-satu, tapi dalam data yang banyak banget, bisa dibilang mau kita cobain setiap detik pun sampe tua ga akan pernah kelar. Dan terakhir yang kelima, setiap output/value harus punya input/key yang unik dan berbeda dari yang lain.

Rangkuman Binary Tree

Tugas Rangkuman 004

Gw belajar apa itu "Binary Tree" dalam Data Structure itu dari Youtube. Sebelumnya, gua cuman pernah tau istilah "Binary Tree" ini dalam mata kuliah "Matematika Diskrit" pas gw masih semester 1 kemaren. Mungkin, di semester 1 yang lalu, itu juga tujuannya gw diajarin konsep "Binary Tree" ini untuk membangun pondasi konsep gw tentang Binary Tree di semester yang akan datang seperti sekarang.

Nah dari Youtube, gw belajar atau diingetin lagi apa itu Binary Tree. Yang gw dapet, Binary Tree itu adalah konsep Tree yang mempunyai akar/root pastinya. Tapi, yang membedakan dia dari Tree biasa itu adalah banyak anaknya/cabangnya. Kalau dalam Binary Tree, kita cuman bisa punya anak sebanyak 0-2 anak/cabang.

Nah, Binary Tree ini pun masih ada jenis-jenisnya lagi. Yang pertama itu, Strict Binary Tree, di mana kita cuman boleh punya anak antara 0 atau 2. Jadi, kita gaboleh cuman punya 1 anak, apalagi 3, 4, 5, dst. 

Nah, jenis Binary Tree yang ke-2 itu namanya Complete Binary Tree yang justru punya aturan lebih strik lagi dari yang sebelumnya. Aturannya adalah, kita harus punya anak sampe level yang sejajar. Maksudnya itu, dalam "dunia" Tree ini kita bakal kenal sama yang namanya level-levelan. Kalau misalnya root/akar itu kita anggap adalah level 0, maka anak pertama dari root ini kita sebut levelnya menjadi level 1. Begitu pula seterusnya. Nah jadi kalau misalnya di antara cabang-cabang kita ada yang punya anak sampe dengan level 3, maka semuanya juga harus ngikutin punya anak sampe level 3 juga. Mungkin agak susah kalo dibayangin tanpa gambar. Makanya nih gw kasih gambarannya biar lebih kebayang.

Nah kita bisa liat dari gambar di atas, perbedaannya Binary Tree yang "complete" sama yang "gak complete".

Dan jenis Binary Tree yang terakhir itu namanya "Perfect Binary Tree". Kenapa dinamain perfect, karena dia bentukannya harus kayak gambar di bawah ini.

Nah, kalo udah ngerti konsepnya dalam matematika, kita tinggal terapin ke dalam codingannya.

deklarasiin tree dalam bahasa C bisa dengan struct kayak gini:

struct node

{

     int data;

     node* left;

     node* right;

};

Kenapa harus ada left dan right? Karena masing-masing node dalam tree ini bisa punya 0-2 anak. Kalo seandainya punya 0 anak, makan nilai pointer dari left dan rightnya = NULL. 

Tapi kita juga bisa deklarasiin Binary Tree ini bukan hanya dengan struct aja, bisa juga dengan array. Tapi, ini cuman berlaku kalo kita mau bikin "Perfect Binary Tree" aja. Kita bisa mulai dari root sebagai index 0, anak left dari rootnya sebagai index 1, anak kanan dari rootnya sebagai index 2, dan seterusnya. Setelah itu, kita bisa pake logic untuk node pada index i, index anak kirinya = 2i + 1 dan index anak kanannya = 2i + 2