Data Structure Summary

List of Sumarry:

1. linked list

2. Stack & queue

3. Malloc, push & pop

4. Hashing, Binary tree & Binary Search Tree

<Linked List>

Linked list adalah pembuatan struktur data yang terdiri dari koleksi linear dari data dimana setiap data akan menunjuk data lain (berhubungan dengan data lainnya) yang berisi referensi ke data berikutnya dalam bentuk pointer.Namun berbeda dengan array, Linked list memiliki  kelebihan dalam  pembatasan hanya dari kapasitas memory. Linked list memiliki kemampuan untuk menambah dan menghilangkan suatu elemen di tempat tertentu. 

<Jenis-jenis Linked List>

Linked List dibedakan menjadi 3 yaitu:

1. Single linked list
2. Double linked list
3. Circular Linked List

< Single Linked List>

Single Linked List merupakan linked list yang hanya memiliki satu variabel pointer saja. Dimana pointer tersebut menunjuk ke data selanjutnya. Biasanya data terakhir atau yang disebut juga dengan tail menunjuk ke NULL.

<Double Linked List>

Double Linked List hampir sama dengan single Linked List,Bedanya yang in memiliki dua pointer yang menunjuk ke node setelah nya dan sebelum nya.

< Circular Linked List>

Terakhir, ada circular linked list dimana Circular linked list dibagi lagi menjadi 2 bagian yaitu Circular Singly linked list dan Circular Doubly Linked List.

<Circular Singly linked list>

Di circular single linked list, node terakhir (tail) berisikan sebuah pointer yang terhubung ke node pertama (head), sehingga membentuk sebuah sirkuit, yang berarti tidak ada awal maupun akhir dan tidak ada NULL setelah node manapun.

<Circular Doubly linked list>

linked list yang memiliki dua variabel pointer yaitu pointer yang menunjuk ke data selanjutnya(next) dan pointer yang menunjuk ke data sebelumnya(prev). Setiap data pertama(head) dan data terakhir (tail) juga menunjuk ke NULL.

STACK & QUEUE

Stack

Diambil dari kata bahasa inggris, Stack jika diterjemahkan ke dalam bahasa indonesia berarti Tumpukan. Sama halnya seperti suatu tumpukan, misalnya tumpukan buku. Jika guru menyuruh untuk mengumpulkan buku dan buku tersebut ditumpuk, guru cenderung memeriksa buku yang paling atas terlebih dahulu, sehingga murid yang memberikan buku paling pertama akan dikoreksi terakhir.

Sama halnya dengan analogi diatas, stack menggunakan sistem LIFO (last in first out) dimana data yang masuk terakhir akan keluar yang paling pertama, begitu seterusnya sehingga data pertama yang masuk akan menjadi data terakhir yang keluar.

Queue

Kebalikan dari Stack, queue jika diterjemahkan kedalam bahasa indonesia berarti antrian. Sehingga queue menggunakan sistem sama halnya seperti kita saat mengantri akan suatu hal, seperti belanjaan, antri atm, pengobatan di rumah sakit dll. Siapapun orang pertama yang mengantri yang akan keluar, sama halnya di data structure, konsep queue adalah data pertama yang masuk adalah data pertama juga yang akan keluar atau FIFO( first in first out) sehingga sistem akan mengurus data satu persatu dibanding dengan stack dimana sistem menunggu semua data masuk dulu baru memprosesnya.

Linked List II

Ada beberapa komponen yang dipelajari yaitu:

1. Malloc

2. Push

3. Pop

Malloc

Malloc adalah suatu teknik yang digunakan agar dapat mengalokasikan memory yang kita pakai ke suatu node baru yang bisa diberi value yang baru juga, yang dihubungkan dengan teknik linked list

Push

Push disini dalam artian kita memindahkan suatu current ke bagian selanjutnya (dalam gambar diatas digambarkan sebagai titik). Caranya adalah jika head!=tail, maka tail akan berpindah ke bagian selanjutnya dan current bisa berpindah ke bagian dari head-tail.

Pop

Pop bertujuan untuk menghilangkan suatu data. Sehingga data yang mau dihapus harus terlebih dahulu di skip agar data tersebut tidak kehilangan arah baru setelahnya data tersebut aman dihapus. Masalahnya dengan single linked list adalah single linked list hanya mempunyai 1 "tangan", sehingga tidak ada fungsi prev yang bisa kita gunakan. prev adalah suatu fungsi dimana kita bisa mundur kebelakang setelah current kita sudah didepan, di single linked list kita hanya mempunyai next dimana current kita hanya bisa maju kedepan. Berbeda dengan double linked list dimana kita bisa menggunakan prev, di single linked list jika kita mau mundur current kita yang awalnya di posisi tail (data paling belakang) kita harus membuat current kita kembali ke head (Data paling depan ) lalu current tersebut berjalan satu persatu dan mencek kondisi sampai data sebelum tail.

HASHING

Hashing adalah suatu teknik untuk menyimpan dan menemukan kunci secara cepat dengan  mengubah string menjadi kunci yang lebih pendek.
Hashing juga dapat didefinisikan sebagai konsep mendistribusikan kunci dalam array yang disebut hash table menggunakan fungsi yang telah ditentukan yang disebut fungsi hash.

Hash Table

Tabel hash adalah tabel  tempat  menyimpan string asli. Indeks tabel adalah kunci hash sementara nilainya adalah string asli.

Ukuran tabel hash biasanya beberapa urutan besarnya lebih rendah dari jumlah total string yang mungkin, sehingga beberapa string mungkin memiliki kunci hash yang sama.

Dalam Hash table, ada beberapa feature / support yang bisa digunakan, yaitu:

1. Search

2. Insert

3. Delete

Salah satu contoh koding yang menggunakan feature insert:

void insert(int key, int data) {

   struct DataItem *item = (struct DataItem*) malloc(sizeof(struct DataItem));

   item->data = data;  

   item->key = key;

   int hashIndex = hashCode(key);

   while(hashArray[hashIndex] != NULL && hashArray[hashIndex]->key != -1) {

      ++hashIndex;

      hashIndex %= SIZE;

   }

   hashArray[hashIndex] = item;

}

BINARY TREE

Binary tree struktur data menyerupai pohon guna menyimpan data. Syarat dari suatu binary tree adalah bahwa setiap node nya hanya boleh maksimal 2 anak.

Terdapat 3 jenis binary tree yaitu:

• Full Binary Tree:
  Binary Tree yang tiap nodenya (kecuali leaf) memiliki dua child dan tiap subtree harus mempunyai panjang path yang sama.
• Complete Binary Tree:
  Mirip dengan Full Binary Tree, namun tiap subtree boleh memiliki panjang path yang berbeda. Node kecuali leaf memiliki 0 atau 2 child.
• Skewed Binary Tree:
  yakni Binary Tree yang semua nodenya (kecuali leaf) hanya memiliki satu child.

BINARY SEARCH TREE

Binary search tree mirip seperti Binary tree pada umumnya, tetapi binary search tree memiliki ketentuan tambahan, yaitu di sebelah kiri pada suatu node harus selalu lebih besar / kecil  dan sebaliknya untuk yang di sebelah kanan node.

Seperti pada contoh diatas, angka paling atas (root) adalah 8 dan disebelah kiri 8 ada 3 yang merupakan angka lebih kecil dari 8. Dibawah 3 ada angka 1 di sebelah kiri 3 karena merupakan angka yang lebih kecil, dan di sebelah kanan 3 ada angka 6 yang merupakan angka lebih besar dari 3. angka di sebelah kanan 3 harus lebih besar dari 3 tetapi tidak boleh lebih besar dari 8, karena sudah termasuk dari bagian sebelah kiri angka 8 dimana semua yang di sebelah kiri 8 harus lebih kecil. Sama halnya di sebelah kanan 8 yang merupakan semua angka yang lebih besar dari 8.

BINARY SEARCH TREE OPERATION

INSERTION

Insertion adalah teknik binary search tree yang mau memasukkan data / menyisipkan data pada tree. Cara pada Insertion di BST (Binary Search Tree) pun berbeda dibanding binary tree biasa karena pada BST harus memperhatikan besar kecilnya nilai pada suatu angka.

Seperti pada gambar diatas, angka yang ingin dimasukkan adalah 7, maka program akan memeriksa apakah angka 7 lebih besar dari 8 (root) atau lebih kecil. Karena lebih kecil, dia pasti masuk ke bagian sebelah kiri dari angka 8. Lalu dicek lagi apakah 7 lebih besar dari 3. Karena lebih besar, maka angka 7 masuk ke sebelah kanan dari 3 dan begitu seterusnya sampai masuk ke bagian kanan sebelah angka 5.

DELETION

Ada 2 kasus dalam proses delete di BST. Kasus pertama adalah ketika node yang ingin dihapus adalah node yang paling bawah, Maka tinggal langsung delete saja node tersebut. Namun Ketika node tersebut memiliki child, maka ada beberapa kondisi yang harus dilihat agar Tree tersebut tidak berantakan.

Seperti pada gambar diatas, angka 20 adalah angka yang mau di delete. Sehingga cara yang akan digunakan adalah dengan melihat angka paling besar dari sebelah kiri 20 atau angka paling kecil dari sebelah kanan 20. Logikanya adalah dengan melihat angka paling besar di sebelah kiri 20 (seperti pada contoh) yaitu 19, sudah pasti angka 19 akan selalu lebih besar dari node-node di sebelah kiri 20 namun tetap lebih kecil dari node-node yang ada di sebelah kanan. Sehingga setelah menghilangkan angka 20, angka yang menggantikan tempat node angka 20 adalah angka 19.