Struktur Data: Review I

Setelah membahas 4 materi sebelum ini, mari kita rangkum materi-materi tersebut.

1. Linked List

Secara singkat, linked list merupakan sebuah struktur data yang mana dapat digunakan untuk mengimplementasikan struktur data lain seperti stack, queue, dan variasi lainnya.

Linked list memiliki variabel pointer START yang menyimpan alamat dari node pertama. Node pertama tersebut juga memiliki pointer yang menyimpan alamat dari node kedua dan seterusnya sampai ketemu alamat NULL (yang mana linked list akan berakhir).

Linked list terdiri dari beberapa jenis, antara lain:

1. Non-circular single linked list,
2. Circular single linked list,
3. Non-circular double linked list,
4. Circular double linked list

1.1 Single Linked List

Bila struktur data dalam sebuah node hanya memiliki (menunjuk) satu tautan atas node berikutnya maka struktur data tersebut dinamakan sebagai single linked list. Linked list ini hanya bisa memiliki satu arah.

 1.2 Circular Single Linked List

Circular single linked list merupakan sebuah struktur data yang terdiri dari node-node yang dibuat menggunakan tautan diri sendiri. Node terakhir dari linked list ini akan menunjuk kembali ke node pertama.

 1.3 Double Linked List

Berbeda dengan single linked list, double linked list memiliki node yang terdiri dari dua buah data dan tautan yang menunjuk pada node sebelum dan sesudahnya. Maka dari itu, struktur data ini terdiri dari 3 bagian — data, pointer ke node selanjutnya, dan pointer ke node sebelumnya.

 1.4 Circular Double Linked List

Mirip dengan circular single linked list, linked list ini memiliki node dengan pointer yang menunjuk ke node sebelum dan sesudahnya secara bersamaan DAN tidak adanya NULL di sebelum node pertama dan setelah node terakhir.

2. Stack dan Queue

Selain linked list, di dalam struktur data juga terdapat teknik lain. Antaranya adalah stack dan queue.

2.1 Stack

Stack, atau dalam Bahasa Indonesianya disebut tumpukan, merupakan salah satu teknik struktur data yang bersifat LIFO (last in first out). Data yang terakhir masuk ke stack merupakan data yang akan keluar pertama (namanya juga tumpukan).

Algoritma dalam stack dilakukan dengan menguji apakah stack sudah penuh jika sedang memasukkan data (push). Jika sudah, maka data baru tidak dapat masuk. Jika belum, maka data yang terakhir dimasukkan merupakan data paling atas dari stack tersebut. Untuk mengeluarkan data (pop), maka dilakukan uji apakah stack sudah kosong atau belum. Jika sudah, maka tidak ada data yang dapat dikeluarkan. Jika belum, maka data yang paling atas lah yang dapat dikeluarkan terlebih dahulu.

2.2 Queue

Queue, atau dalam Bahasa Indonesianya disebut antrean, merupakan salah satu implementasi struktur data yang bersifat FIFO (first in first out). Data yang pertama masuk merupakan data yang pertama kali akan keluar. Queue merupakan suatu kebalikan dari stack.

  

3. Hash Table dan Binary Tree

Apa itu hash table dan binary trees? 

3.1 Hash Table

Hash table merupakan 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 memori penyimpanan utama berbentuk array dengan tambahan algoritma untuk mempercepat pemrosesan data. 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.

3.2 Binary Tree

Setiap tree yang memiliki elemen sebanyak-banyaknya 2 "anak" disebut sebagai binary tree. Karena setiap elemennya hanya memiliki 2 anak, maka biasanya kedua anak tersebut disebut anak kiri dan anak kanan. Sedangkan Node yang paling atas disebut dengan root (akar).

   

 4. Binary Search Tree

BST adalah struktur data pohon biner berbasis node yang memiliki beberapa ciri. Ciri-ciri dari BST adalah:

• Nilai node yang lebih rendah selalu berada di sebelah kiri subtree.
• Nilai node yang lebih tinggi selalu berada di sebelah kanan subtree.
• Setiap subtree juga merupakan sebuah BST.

Tujuannya untuk memberikan efisiensi terhadap proses searching (pencarian). Kalau struktur data tree sudah tersusun rapi sesuai aturan mainnya, proses search akan lebih cepat.

Penelusuran data BST dapat dilakukan dengan 3 cara, yaitu:

1. PreOrder. Cetak data, telusur ke kiri, telusur ke kanan.
2. InOrder. Telusur ke kiri, cetak data, telusur ke kanan.
3. PostOrder. Telusur ke kiri, telusur ke kanan, cetak data.