Rangkuman

RANGKUMAN SETENGAH SEMESTER

Pada kesempatan kali ini, saya akan membagikan tentang apa yang telah saya pelajari sejauh ini dalam kelas data structure.

1. POINTER

Setiap variabel yang kita buat pada program akan memiliki alamat memori. Alamat memori berfungsi untuk menentukan lokasi penyimpanan data pada memori (RAM). Alamat memori biasanya dalam bilangan heksa desimal. Pointer adalah sebuah variabel berisi alamat memori dari variabel lain. Seperti pada variabel umumnya, pointer harus di deklarasikan terlebih dahulu. Pointer diawali dengan simbol "*" didepannya, dan untuk mengaksesnya menggunakan simbol "&". Simbol tersebut berfungsi mengambil alamat memori dari variabel.

Contoh :

Input :

Output :

2. ARRAY

Array adalah tempat untuk menyimpan banyak data dalam satu variabel. Dapat dianalogikan seperti hotel yang mempunyai banyak kamar. Kemudian kamar - kamar tersebut dikenal dengan istilah index / urutan angka. Index itu sendiri dimulai dari angka 0. Array juga hanya mampu menyimpan data dalam satu variabel yang sama. Array biasa di deklarasikan dengan simbol "[]".

Contoh 

Input:

Output :

3. LINKED LIST

Linked List adalah struktur data yang terdiri dari kumpulan node yang bersama - sama merepresentasikan sebuah urutan. Linked List yang saya ketahui pada saat mengikuti kelas adalah Single Linked List dan Double Linked List. Dikelas kemarin pun diajarkan bagaimana cara menambahkan data dan menghapus data dengan perumpamaan orang sebagai node dan tangan sebagai pointernya. Dalam Linked list terdapat head dan tail. 

Kelebihan menggunakan linked list daripada array :

• Ukuran dari array harus ditentukan sedangkan linked list tidak.
• Jika ingin menambahkan atau menghapus data pada linked list lebih mudah.
• Array disimpan dalam memori dengan alamat berurut sedangkan linked list tidak.
• Linked list digunakan jika jumlah data belum diketahui sedangkan array sudah tahu.

Single Linked List

Single linked list adalah kumpulan node - node yang setiap node memiliki field data dan dapat menunjuk ke balok selanjutnya.

Double Linked List

Double linked list adalah kumpulan node - node yang setiap node memiliki field data dan dapat menunjukan ke balok selanjutnya serta menunjuk kebalok sebelumnya. 

4. 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 / +

5. 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).

6. HASH TABLE

Apa itu Hash Table ?

Sebuah struktur data yang terdiri dari sebuah tabel dan fungsi yang bertujuan untuk memetakan nilai kunci untuk setiap record (baris) menjadi angka (hash) lokasi record tersebut dalam sebuah tabel.

Apa itu Hashing ?

Hashing adalah transformasi sebuah input menjadi sebuah fixed value yang lebih pendek dan simple. Contohnya adalah sebuah fungsi yang meminta string dan memproduce integer dari 0-99. Fungsi hash ini bisa dipadukan dengan array untuk menghasilkan hash table. 

Kenapa Hash Table ?

Karena hash table ini memiliki kelebihan yaitu insertion dan searching value yang ada di array dengan sangat cepat.

Operasi Hash Table:

• insert : diberikan sebuah key dan nilai, insert nilai dalam table.
• find : diberikan sebuah key, temukan nilai yang berhubungan dengan key.
• remove : diberikan sebuah key, temukan nilai yang berhubungan dengan key lalu hapus.

Bagaimana cara kerja Hash Table ?

Hash table memiliki 2 komponen penting yaitu KEY dan VALUE. Key itu yang akan menjadi identifikasi dari value dan dimasukkan kedalam fungsi hash. Value adalah value/nilai yang akan dimasukkan kedalam array.

Contoh :

Jadi, key nya itu dimasukkan kedalam fungsi hash. Misalnya ConvertHash(John)->3; maka value dari john yaitu dori akan berada di index ke-3. Lalu jika ada ConvertHash(Ming)->3; padahal sudah sebelumnya terisi maka akan terjadi "Collision" yaitu bentrokan. Solusinya adalah menggunakan linked list untuk memasukkan value "Dan".

7. BINARY TREE

Binary Tree adalah sebuah pohon dalam struktur data yang bersifat hirarki. Tree adalah kumpulan dari berbagai leaves, setiap leaves paling banyak memiliki 2 anak. Anak tersebut diberi nama kiri dan kanan. 

Operasi-operasi pada Binary Tree :

1. Create : Membentuk binary tree baru yang masih kosong.
2. Clear : Mengosongkan binary tree yang sudah ada.
3. Empty : Function untuk memeriksa apakah binary tree masih kosong.
4. Insert : Memasukkan sebuah node ke dalam tree. 
5. Find : Mencari root, parent, left child, atau right child dari suatu node. (Tree tak boleh kosong)
6. Update : Mengubah isi dari node yang ditunjuk oleh pointer current. (Tree tidak boleh kosong)
7. Retrieve : Mengetahui isi dari node yang ditunjuk pointer current. (Tree tidak boleh kosong)
8. DeleteSub : Menghapus sebuah subtree (node beserta seluruh descendantnya) yang ditunjuk current. Tree tak boleh kosong. Setelah itu pointer current akan berpindah ke parent dari node yang dihapus.
9. Characteristic : Mengetahui karakteristik dari suatu tree, yakni : size, height, serta average lengthnya. Tree tidak boleh kosong. 
10. Traverse : Mengunjungi seluruh node-node pada tree, masing-masing sekali. Hasilnya adalah urutan informasi secara linier yang tersimpan dalam tree. Ada tiga cara traverse : Pre Order, In Order, dan Post Order.

8. 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.