SUMMARY

Linked List

Linked list merupakan struktur data yang terdiri dari urutan catatan data sehingga setiap catatan ada bidang yang berisi referensi ke catatan berikutnya dalam urutan. Dari penegertian ini, dapat di simpulkan suatu linked list memiliki ciri ciri yaitu  berurutan (sequence), berisi referensi ke catatan berikutnya, memliki posisi yang acak.

Sebernarnya pengunaan linked list dengan array hampir sama tetapi linked list dan array memiliki beberapa perbedaaan yaitu :

1. Pada linked list ukuran data bisa bertambah sesuai kebutuhan sedangkan dengan  pada array ukuran data tidak dapat bertambah atau pas sesuai yang kita panggil di awal.
2. Pada linked list posisi data acak sedangkan pada array posisi data berurutan.

Linked list terdiri dari dua tipe yaitu :

1. Single linked list  
2. Double linked list

Stack

Stack adalah kumpulan data yang disimpan dalam satu lajur linear yang terlihat seperti ada data lain yang menumpuk diatasnya. Konsep utama dari stack adalah LIFO (Last In First Out) yang artinya data yang terakhir kali dimasukkan itulah data yang pertama kali keluar. Stack dapat dianalogikan seperti tumpukan piring yang akan kita cuci, piring paling atas adalah piring terakhir namun piring tersebut yang pertama kali selesai dicuci. Dalam stack juga dikenal "DFS" yaitu Depth First Search yang biasa digunakan untuk mapping.

Stack Operation terdiri dari :

• Push : Menambahkan data pada tumpukan paling atas.
• Pop : Mengambil data dari tumpukan paling atas.
• Clear : Digunakan untuk mengosongkan tumpukan.

Infix, Prefix dan Postfix

Mengapa kita perlu tahu tentang notasi prefix/postfix ? Karena notasi ini tidak memerlukan bracket "()" untuk menentukan prioritas urutan sehingga komputer menjadi lebih cepat mengeksekusinya.

• Prefix : Operator yang ditulis sebelum operan (Operator Operan Operan).
• Infix : Operator yang ditulis ditengah operan (Operan Operator Operan).
• Postfix : Operator yang ditulis setelah operan (Operan Operan Operator).

Postfix artinya komputer mengeksekusi / menscan dari kiri sedangkan prefix dari kanan.

Contoh :
4 + 6 * (5 - 2) / 3
Prefix : + 4 / *6 - 5 2 3
Postfix : 4 6 5 2 - * 3 / +

Queue

Queue adalah kumpulan data linear yang dimana penambahan data dilakukan disalah satu ujung dan pengurangan dilakukan diujung yang lainnya. Konsep Queue adalah FIFO (First In First Out) yang artinya data yang pertama masuk adalah data yang pertama kali keluar. Umumnya konsep queue harus memiliki variabel head yang berguna sebagai penanda bagian depan data, variabel tail sebagai penanda bagian belakang data. Ada istilah "BFS" yaitu Breadth First Search yang kebanyakan digunakan untuk mencari connected komponen pada graph.

Queue Operation terdiri dari :

• Push / enqueue : Menambahkan data ke bagian paling belakang antrian.
• Pop / dequeue : Mengambil data dari bagian paling depan antrian.

Adapun istilah Circular Queue yaitu jika data sudah penuh maka akan mengulang kebagian depan yang kosong. Caranya adalah tail -> next = head; . Konsep ini kebanyakan digunakan untuk OS (Operating System).

Priority Queue :

Priority Queue adalah sebuah tipe data abstrak di mana masing-masing elemen diberi prioritas.

BFS (Breadth First Search) :

Breadth-first search adalah algoritma yang melakukan pencarian secara melebar yang mengunjungi simpul secara preorder yaitu mengunjungi suatu simpul kemudian mengunjungi semua simpul yang bertetangga dengan simpul tersebut terlebih dahulu. Pada BFS menggunakan sistem dari Queue atau FIFO.

HASH TABLE

Hash Table adalah sebuah struktur data yang terdiri atas sebuah tabel dan fungsi yang bertujuan untuk memetakan nilai kunci yang unik untuk setiap record (baris) menjadi angka (hash) lokasi record tersebut dalam sebuah tabel.

Keunggulan dari struktur hash table ini adalah waktu aksesnya yang cukup cepat, jika record yang dicari langsung berada pada angka hash lokasi penyimpanannya. Akan tetapi pada kenyataannya sering sekali ditemukan hash table yang record-recordnya mempunyai angka hash yang sama (bertabrakan).

Pemetaan hash function yang digunakan bukanlah pemetaan satusatu, (antara dua record yang tidak sama dapat dibangkitkan angka hash yang sama) maka dapat terjadi bentrokan (collision) dalam penempatan suatu data record. Untuk mengatasi hal ini, maka perlu diterapkan kebijakan resolusi bentrokan (collision resolution policy) untuk menentukan lokasi record dalam tabel. Umumnya kebijakan resolusi bentrokan adalah dengan mencari lokasi tabel yang masih kosong pada lokasi setelah lokasi yang berbentrokan.

OPERASI PADA HASH TABLE

Ø  insert: diberikan sebuah key dan nilai, insert nilai dalam tabel

Ø  find: diberikan sebuah key, temukan nilai yang berhubungan dengan key

Ø  remove: diberikan sebuah key,temukan nilai yang berhubungan dengan key, kemudian hapus nilai tersebut

Ø  getIterator: mengambalikan iterator,yang memeriksa nilai satu demi satu

STRUKTUR DAN FUNGSI PADA HASH TABLE

Hash table menggunakan struktur data array asosiatif yang mengasosiasikan record dengan sebuah field kunci unik berupa bilangan (hash) yang merupakan representasi dari record tersebut. Misalnya, terdapat data berupa string yang hendak disimpan dalam sebuah hash table. String tersebut direpresentasikan dalam sebuah field kunci k.

BINARY TREE

Merupakan salat Satu bentuk Struktur Data tidak linier Yang menggambarkan hubungan Yang bersifat hirarkis (hubungan one to many) antara elemen-elemen. Tree Bisa didefinisikan sebagai kumpulan Simpul / node dengan Satu elemen KHUSUS Yang disebut root Dan Node lainnya terbagi menjadi Himpunan-Himpunan Yang tak saling berhubungan Satu sama lainnya (disebut subtree). Untuk jelasnya, di Bawah Akan diuraikan istilah-istilah umum dalam tree.

• Parent : predecssor satu level di atas suatu node.
• Child : successor satu level di bawah suatu node.
• Sibling : node-node yang memiliki parent yang sama dengan suatu node.
• Subtree : bagian dari tree yang berupa suatu node beserta descendantnya dan memiliki semua karakteristik dari tree tersebut.
• Size : banyaknya node dalam suatu tree.
• Height : banyaknya tingkatan/level dalam suatu tree.
• Root : satu-satunya node khusus dalam tree yang tak punya predecssor.
• Leaf : node-node dalam tree yang tak memiliki seccessor.
• Degree : banyaknya child yang dimiliki suatu node.
• 
  

PENGERTIAN BINARY TREE DALAM STRUKTUR DATA

Pohon biner adalah pohon dengan syarat bahwa tiap node hanya memiliki boleh maksimal dua subtree dan kedua subtree tersebut harus terpisah. Sesuai dengan definisi tersebut, maka tiap node dalam binary tree hanya boleh memiliki paling banyak dua anak/child.

NODE PADA BINARY TREE

Jumlah maksimum node pada setiap tingkat adalah 2n, Node pada binary tree maksimumnya berjumlah 2n-1.

BINARY SEARCH TREE

Binary Search Tree adalah tree yang terurut. Binary Search Tree juga sering disebut dengan Sorted Binary Tree yang berfungsi untuk menyimpan informasi nama atau bilangan yang disimpan di dalam memory. Data dibagi menjadi dua dengan 1 ditengah sebagai patokannya. Ada data kiri dan kanan. Semua data di kiri subtree dari node harus selalu lebih kecil dari data dalam node itu sedangkan semua data bagian kanan subtree dari node harus selalu lebih besar atau sama dengan data dalam node itu. Binary search tree memungkinkan pencarian dengan cepat, penambahan, juga menghapus data yang ada di dalamnya.