Review Data Struct

Linked List

Linked List atau senarai berantai adalah struktur data yang terdiri dari urutan record data dimana setiap record memiliki field yang menyimpan alamat/referensi dari record selanjutnya. Elemen data yang dihubungkan dengan dengan link pada Linked List disebut Node. Di dalam Linked List, biasanya terdapat Head yang merupakan elemen yang berada pada posisi pertama dalam suatu Linked List dan Tail yang merupakan elemen yang berada pada posisi terakhir dalam suatu Llinked List.

Macam-macam Linked List: 

1. Circular Single Linked List

    Single Linked List Circular adalah Single Linked List yang pointer nextnya menunjuk pada dirinya sendiri. Jika Single Linked List tersebut terdiri dari beberapa node,  maka pointer next pada node terakhir akan menunjuk ke node terdepannya. Circular  artinya pointer nextnya akan menunjuk pada dirinya sendiri sehingga berbentuk seperti berputar. 

2. Doubly Linked List

  Doubly Linked List adalah sekumpulan node data yang terurut linear atau sekuensial dengan dua buah pointer yaitu prev dan next. Doubly Linked List memiliki data dan dua buah reference link (biasanya disebut next dan prev) yang menunjuk ke node sebelum dan node sesudahnya. Pada implementasinya, terdapat dua variasi double linked list yaitu circular dan non-circular layaknya pada single linked list. 

3. Circular Doubly Linked List

   Circular Doubly Linked List mirip dengan Single Linked List, namun jumlah pointer pada setiap node adalah 2. Setiap node pada linked list mempunyai field yang berisi data dan pointer ke node berikutnya & ke node sebelumnya. Untuk pembentukan node baru , mulanya pointer next dan prev akan menunjuk ke nilai NULL. Selanjutnya pointer prev akan menunjuk ke node sebelumnya , dan pointer next akan menunjuk ke node selanjutnya pada list.

4. Multiple Linked List

    Multiple linked list merupakan senarai berantai yang memiliki link atau pointer lebih darisatu. Untuk multiple linked list yang memiliki dua link biasanya disebut sebagai doublylinked list (senarai berantai ganda). Senarai berantai ganda memiliki dua buah pointer yang biasanya masing-masing menunjuk ke simpul sebelumnya dan ke simipul sesudahnya. 

Operasi dalam Linked List:

1. Push

   Push merupakan operasi untuk memasukkan data pada linked list atau insert. Memasukkan data dapat dari depan(PushDepan) atau dari belakang(PushBelakang) atau juga bisa pada data yang diinginkan.

2. Pop

    Pop merupakan operasi untuk menghapus data pada linked list atau delete. Menghapus data dapat dilakukan dari depan(PopDepan) atau dari belakang(PopBelakang) atau juga bisa pada data yang diinginkan.

Hashing & Binary Tree

Hashing adalah teknik yang digunakan untuk menyimpan dan mengambil kunci dengan cepat. Hashing digunakan untuk mengindeks dan mengambil item dalam database karena lebih cepat menemukan item menggunakan kunci hash yang lebih pendek daripada menemukannya menggunakan nilai asli.

Hash Table

Tabel hash adalah tabel tempat menyimpan string asli. Indeks tabel adalah kunci hash dan nilainya adalah string asli. Ukuran tabel hash biasanya berupa urutan yang besarnya lebih rendah dari jumlah total string yang mungkin

Hash Function

Ada beberapa cara untuk membuat fungsi hash. 

1. Mid-Square

a. Kuadratkan string / identifier dan kemudian gunakan jumlah bit yang sesuai dari tengah kotak untuk mendapatkan hash-key.

b. Jika kuncinya adalah string, maka akan dikonversi ke angka.

2.Division

a. Membagi string / pengidentifikasi dengan menggunakan operator modulus.

b. Divison merupakan metode hashing integer yang paling sederhana.

3.Folding

Cara melakukan folding yaitu, buat string / identifier menjadi beberapa bagian, lalu tambahkan bagian bersama-sama untuk mendapatkan kunci hash.

4.Digit Extraction

Pada metode ini, Digit yang ditentukan sebelumnya dari nomor yang diberikan dianggap sebagai alamat hash.

5.Rotating Hash

a. Gunakan metode hash mid-square.

b. Setelah mendapatkan kode / alamat hash dari metode hash, lakukan rotasi.

c. Rotasi dilakukan dengan menggeser digit untuk mendapatkan alamat hash baru.

Tree

Tree merupakan struktur data non-linear yang mewakili hubungan hierarkis(one to many) di antara objek data. Tree bisa didefinisikan sebagai kumpulan simpul/node dengan satu elemen khusus yang disebut Root dan node lainnya.

Binary Tree

Binary tree adalah struktur data rooted tree di mana setiap node memiliki paling banyak dua anak.

Terdapat 4 macam binary tree antara lain : Perfect binary tree, Complete Binary Tree, Skewed binary tree, Balanced binary tree.

Expression Tree

Pohon ekspresi adalah pohon biner di mana setiap node internal sesuai dengan operator dan setiap node leaf sesuai dengan operand.

Prefix  : *+ab/-cde

Postfix : ab+cd-e/*

Infix  : (a+b)*((c-d)/e)