Setelah melewati
setengah semester ini, untuk mata kuliah Data Structure kelas besar telah
mempelajari tentang Array, Linked List (Single linked list dan Double linked
list), konsep Stack & Queue, Binary Tree, dan juga Hashing. Berikut adalah rangkuman
singkat dari apa yang telah di pelajari selama setengah semester ini.
· Array
dan Linked List
Pada minggu pertama di kelas besar Data Structure,
membahas tentang linked list dan perbedaan nya dengan array. Pada saat
dijelaskan saya baru mengetahui jika perbedaan paling mendasar antara array dan
linked list adalah terdapat pada alokasi memory nya, array menggunakan alokasi memory yang fix sedangkan linked
list menggunakan alokasi memory yang dynamic, sehingga penggunaan linked list
lebih memory efficient dibanding dengan array. Linked list juga mempunyai
kelebihan daripada array yaitu, karena alokasi memory
yang dimiliki array fix,
sehingga tidak bisa menambah lagi
jumlah array nya setelah di deklarasikan di awal, sedangkan karena alokasi
memory linked list dinamis jadi jumlah linked list nya bisa bertambah terus
asal masih ada memori yang kosong.
Di minggu ini juga dosen
menjelaskan macam-macam linked list seperti single/singly linked list,
double/doubly linked list .Di
materi ini pada saat dosen menjelaskan, dosen memberikan contoh tentang linked
list dengan menggunakan orang
sebagai contoh node nya dan tangan orang tersebut sebagai pointer next untuk menunjuk node berikut nya (untuk single dan double linked list) dan
pointer previous (untuk double linked list). Di materi ini juga saya
mendapatkan gambaran tentang bagaimana cara linked list bekerja dan juga bagaimana linked list di manage di
memory. Dosen juga memberikan gambaran
bagaimana menambah dan menghapus linked list .
· Stack
and Queue
Pada minggu ketiga di kelas Data Structure, membahas
tentang konsep Stack dan juga Queue. Stack dan Queue dapat digunakan baik pada
array maupun linked list, perbedaan nya hanya terdapat pada seberapa banyak
Stack dan Queue dapat terbentuk, pada array Stack dan Queue ukuran nya terbatas
karena array tidak menggunakan dynamic memory alocation, sedangkan pada linked
list ukuran nya tidak terbatas karena linked list menggunakan dynamic memory
alocation. Di minggu ini juga dibahas tentang infix, prefix, dan postfix notation
yang dapat mempercepat perhitungan aritmatik di komputer dengan menggunakan
konsep dari Stack.
STACK
Stack merupakan konsep yang digambarkan seperti tumpukan piring. Ketika
kita meletakan piring pada tumpukan piring maka piring yang akan keluar pertama
atau diambil pertama adalah piring yang paling atas (yang terakhir kali diletakan). Sehingga data
yang disimpan dengan konsep Stack akan diakses dengan cara LIFO (Last In First
Out) atau FILO (First In Last Out).
Stack memiliki 3 operation, yaitu:
·
Push(x) : memasukan item x ke atas
tumpukan (stack)
·
Pop() : membuang / menghapus item
paling atas di tumpukan (stack)
·
Top()
: memperlihatkan isi
item paling atas tumpukan (stack)
Notasi Infix merupakan notasi aritmatika yang biasa digunakan sehari-hari,
notasi prefix merupakan notasi aritmatika yang operator nya berada di sebelah
kiri operand, sedangkan notasi postfix merupakan notasi aritmatika yang
operator nya berada di sebelah kanan operand. Alasan mengapa notasi prefix dan
postfix bisa mempercepat perhitungan dibandingkan dengan notasi infix adalah
karena pada notasi prefix dan postfix tidak terdapat parentheses.
Contoh:
Infix : ( (1 + 3) / ((100 *
5)^30) )
Prefix : / + 1 3 ^ * 100 5 30
Postfix : 1 3 + 100 5 * 30 ^ /
Ketiga contoh diatas merupakan operasi aritmatika yang menghasilkan angka
yang sama akan tetapi berbeda pada cara penulisan nya.
DFS (Depth Fisrt Search) merupakan algoritma untuk berjalan dan mencari
data pada tree atau graph. Dimulai dari root (paling atas) kemudian turun
kebawah.
QUEUE
Queue merupakan konsep yang digambarkan seperti antrian. Orang yang pertama
kali masuk ke dalam antrian akan keluar dari antrian pertama kali. Sehingga
konsep Queue disebut juga FIFO (First In First Out).
Queue memiliki 3 operation, yaitu:
·
Push(x) : memasukan item ke bagian belakang
antrian (queue)
·
Pop() : menghapus item pada
bagian depan antrian (queue)
·
Front() : memperlihatkan isi item
paling depan antrian (queue)
Queue banyak digunakan pada management RAM pada operating system sehingga
saat banyak aplikasi terbuka di background management RAM nya tidak kacau. Cara
tersebut menggunakan Circular Queue, yaitu Queue yang ketika data nya sudah
overflow, maka akan kembali lagi ke bagian paling depan / awal Queue.
Pada Queue juga terdapat Dequeue (Double Ended Queue) dibaca deck
yaitu Queue yang untuk memasukan dan menghapus item nya dapat dilakukan dari 2
arah yaitu depan dan belakang. Terdapat dua jenis Dequeue, yaitu Input
Restricted Dequeue dan Output Restricted Dequeue. Input Restricted Dequeue
adalah Dequeue yang input nya hanya boleh dari 1 arah tetapi bisa di hapus dari
2 arah. Sedangkan, Output Restricted Dequeue adalah Dequeue yang input nya
boleh dari 2 arah tetapi hanya bisa dihapus dari 1 arah.
BFS (Breadth First Search) sama saja dengan DFS tetapi perbedaanya BFS
menggunakan konsep Queue.
· Hashing
dan Binary Tree
Materi minggu ini materi nya adalah Hashing dan Binary Tree. Hashing adalah
metode yang digunakan untuk mencari dan memasukan data dengan cepat ke
database. Konsep yang saya dapatkan itu hashing menggunakan array dan linked
list sekaligus. Sehingga blok memori array akan digunakan sebagai head bagi
linked list nya nanti.
Contoh syntax untuk hashing:
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<stdbool.h>
#define SIZE 20
struct DataItem{
int data;
int key;
};
struct DataItem* hashArray[SIZE];
struct DataItem* dummyItem;
struct DataItem* item;
int hashcode(int key){
return key % SIZE;
}
struct DataItem *search(int key){
// get the hash
int hashIndex = hashcode(key);
// move in array until an empty
while(hashArray[hashIndex] != NULL){
if(hashArray[hashIndex]->key == key){
return hashArray[hashIndex];
}
// go to next cell
hashIndex++;
// wrap around the table
hashIndex %= SIZE;
}
return NULL;
}
void insert(int key, int data){
struct DataItem *item = (struct DataItem*) malloc (sizeof(struct DataItem));
item->data = data;
item->key = key;
// get the hash
int hashIndex = hashcode(key);
// move in array untul an empty or deleted cell
while(hashArray[hashIndex] != NULL && hashArray[hashIndex]->key != -1){
// go to next cell
hashIndex++;
// wrap around the table
hashIndex %= SIZE;
}
hashArray[hashIndex] = item;
}
struct DataItem* deleteHash(struct DataItem* item){
int key = item->key;
// get the hash
int hashIndex = hashcode(key);
// move in array until an empty
while(hashArray[hashIndex] != NULL){
if(hashArray[hashIndex]->key == key){
struct DataItem* temp = hashArray[hashIndex];
// assign a dummy item at deleted position
hashArray[hashIndex] = dummyItem;
return temp;
}
// go to next cell
++hashIndex;
// wrap around the table
hashIndex %= SIZE;
}
return NULL;
}
void display(){
int i = 0;
for(i = 0; i < SIZE; i++){
if(hashArray[i] != NULL){
printf(" (%d, %d)", hashArray[i]->key, hashArray[i]->data);
} else {
printf("~~");
}
}
printf("\n");
}
int main(){
dummyItem = (struct DataItem*) malloc (sizeof(struct DataItem));
dummyItem->data = -1;
dummyItem->key = -1;
insert(1, 20);
insert(2, 70);
insert(42, 80);
insert(4, 25);
insert(12, 44);
insert(14, 32);
insert(17, 11);
insert(13, 78);
insert(37, 97);
display();
item = search(37);
if(item != NULL){
printf("Element found: %d\n", item->data);
} else {
printf("Elemert not found\n");
}
deleteHash(item);
display();
item = search(42);
if(item != NULL){
printf("Element found: %d\n", item->data);
} else {
printf("Elemert not found\n");
}
display();
item = search(13);
if(item != NULL){
printf("Element found: %d\n", item->data);
} else {
printf("Elemert not found\n");
}
}
Pada hashing terdapat banyak cara
untuk menkonstruksi hash function
yaitu, Mid-square, division, folding, digit extraction, dan rotating hash.
Hashing sekarang banyak digunakan
di dalam cryptocurrency seperti Bitcoin, karena transaksi akan diambil
sebagai input yang nanti nya akan menghasilkan output berupa string dengan
panjang yang tetap. Pada bitcoin algoritma hashing yang digunakan adalah
SHA-256 (Secure Hashing Algorithm 256), yaitu algoritma yang menghasilkan
output dengan panjang yang sama yaitu 256 bit, dengan panjang input berapapun.
Tree adalah data structure yang non-linear, tree memiliki banyak bagian,
bagian paling atas dari tree disebut dengan root yang berada di level 0. Garis
yang menghubungkan antar node disebut edge, dan node yang tidak memiliki anak
disebut dengan leaf.
Binary tree adalah rooted tree yang setiap node nya memiliki paling banyak
2 anak.
Comments
Post a Comment