SUMMARY

Linked List

Linked List atau dikenal juga dengan sebutan senarai berantai adalah struktur data yang terdiri dari urutan record data dimana setiap record memiliki field yang menyimpan alamat/referensi dari record selanjutnya (dalam urutan). Elemen data yang dihubungkan dengan link pada Linked List disebut Node. Biasanya didalam suatu linked list, terdapat istilah head dan tail. 

• Head adalah elemen yang berada pada posisi pertama dalam suatu linked list.
• Tail adalah elemen yang berada pada posisi terakhir dalam suatu linked list.

Adapun kelebihan dan kekurangan linked list, yaitu:

• Kelebihan:

1. Penambahan elemen tidak terbatas
2. Memungkinkan untuk dihapus

• Kekukarangan:

1. Hanya dapat diakses secara sekuensial
2. Memerlukan memori dalam jumlah yang besar, untuk menyimpan data yang besar juga.

Berikut beberapa macam Linked List:

1. Single Linked List
2. Double Linked List
3. Circular Linked List
4. Multiple Linked List 

SINGLE LINK LIST:

Single Linked List adalah sekumpulan dari node yang saling terhubung dengan node lain melalui sebuah pointer. Rangkaian single linked list tersebut diawali dengan sebuah head untuk menyimpan alamat awal dan di akhiri dengan node yang mengarah pointer ke null. Single Linked List hanya memiliki satu arah dan tidak memiliki dua arah atau bulak balik, dua arah tersebut disebut dengan double linked list.
Contoh:

Pada Implementasinya, Single Linked List terdapat dua variasi yaitu circular dan non-circular.

Contoh Non Circular:

 Contoh Circular:

Dalam pembelajaran struktur data, kita akan lebih sering mengenal dengan istilah :

• Push untuk menambah data.
  • PushHead – Menambah data ke barisan paling awal
  • PushTail – Menambah data ke barisan paling akhir
  • PushMid – Menambah data ke barisan di tengah (sorting)
• Pop untuk menghapus data.
  • PopHead – Menghapus data paling awal
  • PopTail – Menghapus data paling akhir
  • PopMid – Menghapus data ditengah (sesuai parameter value)

DOUBLE LINK LIST:
Double Linked List merupakan suatu linked list yang memiliki dua variabel pointer yaitu pointer yang menunjuk ke node selanjutnya dan pointer yang menunjuk ke node sebelumnya. Setiap head dan tailnya juga menunjuk ke NULL. 
Contoh:

CIRCULAR LINKED LIST:
Circular Linked List merupakan suatu linked list dimana tail (node terakhir) menunjuk ke head (node pertama). Jadi tidak ada pointer yang menunjuk NULL. Terdapat 2 jenis circular linked list,yaitu:

• CIRCULAR SINGLE LINKED LIST 

 

• CIRCULAR DOUBLE LINKED LIST

MULTIPLE LINKED LIST:
Multiple Linked List merupakan suatu linked list yang memiliki lebih dar 2 buat variabel pointer. 
Contoh:

Hashing Table dan Binary Tree

Sebenarnya apa itu hashing?

Hashing adalah metode untuk menyimpang data dalam sebuah array agar penyimpanan data, pencarian data, penambahan data, dan penghapusan data dapat dilakukan dengan cepat serta dengan constant average time.

Hash Table adalah salah satu struktur data yang digunakan dalam penyimpanan data sementara. Tujuan dari hash table adalah untuk mempercepat pencarian kembali dari banyak data yang disimpan. Hash table menggunakan suatu teknik penyimpanan sehingga waktu yang dibutuhkan untuk penambahan data (insertions), penghapusan data (deletions), dan pencarian data (searching) relatif sama dibanding struktur data atau algoritma yang lain.

Kelebihan dari hash table antara lain sebagai berikut:

- Waktu aksesnya cukup cepat, jika record yang dicari langsung berada pada angka hash lokasi penyimpanannya.

- Hash table relatif lebih cepat.

- Kecepatan dalam insertions, deletions, maupun searching relatif sama. 

- Cocok untuk mempresentasikan data dengan frekuensi insert, delete dan search yang tinggi.  

Kekurangan dari hash table antara lain sebagai berikut:

- Seringkali ditemukan hash table yang record-recordnya mempunyai angka hash yang sama (berantakan).

- Sulit digunakan untuk mencetak seluruh elemen pada hash table.

- Tidak efisien untuk mencari elemen minimum ataupun maksimum.

Pada intinya hash table merupakan penyimpanan data menggunakan key value yang didapat dari nilai data itu sendiri. Dengan key value tersebut didapat hash value. Jadi hash function merupakan suatu fungsi sederhana untuk mendapatkan hash value dari key value suatu data. Yang perlu diperhatikan untuk membuat hash function adalah:

1. ukuran array/table size(m), 

2. key value/nilai yang didapat dari data(k),

3. hash value/hash index/indeks yang dituju(h).

Terdapat beberapa cara untuk mengubah string menjadi kunci, yaitu:

• Division
• Mid-Square
• Folding
• Digit Extraction
• Rotating Hash

Division:

Membagi string/identifier dengan menggunakan operator modulus. Biasanya modulo nya berupa ukuran dari table/array atau menggunakan bilangan prima terdekat diatas banyaknya data.

contoh :
string "ABCD" akan distore di dalam hash table yang memiliki size 97
QWER: (81 + 87 + 69 + 82 ) = 319
Totalnya adalah 319 kemudian dimodulus 97.

319 % 97 = 28
jadi kunci dari string "QWER" adalah 28 kemudian string tersebut distore di dalam hash table yang berindeks 28.

Mid-Square:

Mengkuadratkan string/identifier, kemudian mengambil beberapa angka dari hasil kuadrat (dari tengah) untuk dijadikan hash key.

Folding:

Membagi string/identifier menjadi beberapa bagian, kemudian jumlahkan bagian-bagian tersebut untuk mendapatkan hash key.

Digit Extraction:

Mengambil bagian dari string/identifier yang diberikan.

Contoh: x = 14567, jika kita mengambil angka ke 1 dan 3, kita akan mendapatkan hash key 15.

Rotating Hash:

Yaitu dengan menggunakan metode hash seperti division atau mid-square. Kemudian balikkan hash code.

Contoh: x= 12345 dibalik menjadi 54321.


Binary Tree adalah pohon khusus dimana disetiap node atau vertex bisa tidak memiliki cabang atau juga bisa memiliki 1 atau 2 cabang dan setiap cabang bisa bercabang lagi dan memiliki sifat yang sama. Binary tree digunakan untuk mewakili struktur data nonlinear. Pohon biner memiliki peran penting dalam software application dan salah satu hal paling penting dari Binary Tree adalah searching dalam algoritma.

Terdapat banyak operasi pada binary tree seperti:
Create, Clear, Empty, Insert, Find, Update, Retrieve, DeleteSub, Characteristic, Traverse.

Binary Search Trees

Pohon cari biner adalah pohon biner yang dirancang untuk menskemakan urutan data yang akan dimasukkan ke dalam memori agar proses pencarian, penghapusan dan penambahan data dapat berjalan secara efisien dibanding dengan pemasukan data secara array maupun link.

Sifat dari skema pohon cari biner adalah : 

(1) setiap elemen yang berada di left substrees selalu lebih kecil dari elemen yang ada di right substrees.

(2) setiap elemen yang berada di right substrees selalu lebih besar atau sama dengan elemen yang berada di left substrees.

Contoh:

Ada 3 cara untuk melakukan penelusuran pada binary search trees, yaitu:

1. Pre Order: Print data, Telusur ke kiri, Telusur ke kanan.

2. In Order: Telusur ke kiri, Print Data, Telusur ke kanan.

3. Post Order: Telusur ke kiri, Telusur ke kanan, Print Data.

References:
http://suciantinovi.blogspot.com/2014/03/linked-list-i_14.html
https://medium.com/codelabs-unikom/struktur-data-single-linked-list-93bbd56b6ed1
https://www.academia.edu/32350910/MAKALAH_STRUKTUR_DATA_VARIASI_LINKED_LIST
https://www.academia.edu/25537608/TABEL_HASH_HASH_TABLE
https://informatika11d.wordpress.com/2012/11/22/struktur-data-hash-table/

https://www.slideshare.net/GRADhita/modul-praktikum-11-hashing-table 

https://www.mahirkoding.com/struktur-data-binary-search-tree-bst/

https://saragusti22.wordpress.com/2015/05/04/pengantar-struktur-data-tree-dan-binary-tree/