Linked List
Dalam istilah ilmu komputer, sebuah struktur data adalah cara penyimpanan, penyusunan dan pengaturan data di dalam media penyimpanan komputer sehingga data tersebut dapat digunakan secara efisien.Di dalam struktur data, ada 2 aspek yang kita pelajari, yakni tipe data dan structure (struct).
Tipe data merupakan kumpulan objek dan sebuah himpunan dari operasi-operasi yang menjalankan objek-objek terseubt.
Contoh tipe data pada integer, meliputi
- Objek: 0, -1, +2, dll.
- Operator: + , - , * , / , dll.
Secara umum, structure merupakan kelompok tipe data yang dibentuk oleh user yang dapat menyimpan berbagai informasi dalam berbagai tipe data yang berbeda, sementara array hanya dapat menyimpan kumpulan data dalam tipe data yang sama.
Contoh structure:
struct nama_structure{
int nama_variabel1;
char[100] nama_variabel2;
float nama_variabel3;
}
Saat deklarasi structure dalam fungsi main, kita hanya perlu menulis:
Misalnya nama structure: data, maka
data nama_variabel; --> structure siap diisi dengan data.
Struktur data adalah kumpulan/urutan data, baik dalam memori di komputer maupun di dalam ruang penyimpanan harddisk.
Beberapa contoh umum dari struktur data meliputi:
- Arrays
- Linked Lists
- Queues
- Stacks
- Binary Trees
- Hash Tables
Dalam artikel ini, kita akan membahas sedikit tentang linked list.
Dalam struktur data, linked list merupakan koleksi linear dari data, yang disebut sebagai nodes, di mana setiap node akan menunjuk pada node lain melalui sebuah pointer. Linked list dapat didefinisikan pula sebagai kumpulan node yang merepresentasikan sebuah sequence.
Contoh linked list:
Dari gambar tersebut, dapat kita lihat bahwa structure/array/node paling kiri yang merupakan head (data pertama) menunjuk pada data kedua, lalu data kedua menunjuk pada data ketiga dan kemudian menunjuk pada data kosong (null).
Linked list memiliki beberapa bentuk, yakni sebagai berikut.
Single linked list, linked list yang hanya menunjuk secara 1 arah, tanpa adanya penanda data terakhir. Jadi single linked list hanya memiliki penanda data awal (head) lalu di akhir merupakan data kosong.
Circular single linked list,
- Tidak ada store data NULL, berbeda dari single linked list
- Di bagian akhir, selalu menunjuk ke arah data awal (head)
Double Linked list,
- Melakukan store data NULL, setiap node melakukan hubungan timbal-balik
- Setiap node saling menunjuk 1 sama lain
- Data di awal dan di akhir melakukan data store pada NULL
- Data awal diberi nama head, data akhir diberi nama tail, data lainnya saling bolak-balik
Untuk menggunakan double linked list, codenya adalah:
struct tnode{
int value;
struct tnode *next;
struct tnode *prev;
};
struct tnode *head = 0;
struct tnode *tail = 0;
Jika ingin memasukkan node baru setelah data tail, codenya adalah:
struct tnode *node = (struct tnode*) malloc(sizeof(struct tnode));
node -> value = x;
node -> next = NULL;
node -> prev = tail;
tail -> next = node;
tail = node;
Source:
https://id.wikipedia.org/wiki/Struktur_data
https://socs.binus.ac.id/2017/03/15/single-linked-list/
Binary Search Tree
Binary Search Tree merupakan salah satu struktur data yang mendukung proses searching lebih cepat, penyortiran yang cepat, serta kemudahan dalam penyisipan dan penghapusan. BST juga disebut dengan versi binary tree yang tersortir. Setiap node memiliki key yang berbeda.
Keunikan BST adalah node-node yang masuk sudah tersortir menjadi 2 bagian, yaitu subtree kiri dan subtree kanan. Pada bagian paling atas merupakan akar. Subtree kiri berisi elemen-elemen yang lebih kecil dari akar/root, sedangkan subtree kanan berisi elemen-elemen yang lebih besar dari root. Node masuk akan disortir dengan cara tadi. Node yang lebih kecil akan disimpan di sebelah kiri, dan jika masuk lebih dalam akan tetap di sebelah kiri, begitu juga node yang lebih besar akan selalu masuk ke subtree yang kanan. Hal ini untuk mempermudah pencarian data, serta penyisipan dan penghapusan data.
Operasi-operasi pada BST:
· find(x) : untuk mencari x dalam BST
· insert(x) : untuk menyisipkan x baru ke dalam BST
· remove(x): menghapus x dari BST
Seperti yang telah dikatakan sebelumnya bahwa BST mendukung proses pencarian yang mudah, mari kita coba mencari node, kita sebut X.
a Dimulai dari root, jika root berisikan key yang kita cari (X), maka pencarian berhasil
b Jika X lebih kecil dari root, maka lakukan pencarian secara rekursif di sebelah kiri root, jika lebih besar maka lakukan pada sebelah kanan root.
Untuk melakukan penyisipan (Insertion) juga dilakukan metode rekursif.
a. Dimulai dari root
b. Jika key X yang ingin kita masukkan lebih kecil dari key pada node, maka key X dimasukkan ke subtree kiri, jika lebih besar, dimasukkan ke subtree kanan.
c. Ulangi langkah b sampai ada node kosong, kemudian insert
Untuk proses penghapusan (Deletion), kita perlu memperhatikan hal berikut.
50
/ \
20 75
/ \ \
10 30 80
· Jika key yang ingin dihapus berada di dalam leaf (node yang tidak memiliki child/anak), maka node dapat dihapus langsung.
Contoh: delete(10) à key 10 akan lenyap
· Jika key tersebut berada di dalam node yang memiliki 1 anak, maka hapus node tersebut dan hubungkan/copy child-nya ke parent-nya.
Contoh: delete(75) à copy key 80 ke node 75 à hapus key 75
50
/ \
20 75 (diganti jadi 80)
/ \ \
10 30 80 (dihapus)
· Jika key tersebut berada di dalam node yang memiliki 2 anak, cari anak yang paling kanan
dalam subtree kiri (kita sebut node Q, dan key tersebut merupakan key paling besar). Kemudian ganti key tersebut dengan key pada node Q secara rekursif.
Contoh: delete(50) à anak paling kanan di subtree kiri adalah 30 à pindahkan ke node yang ingin dihapus, kemudian ganti key 50 menjadi 30 à lakukan secara rekursif.
50
/ \
20 75
/ \ \
10 30 80
↓
30 (50 terhapus)
/ \
20 75
/ \
10 80
Hashing & Hash Table
1. Hashing dan Hash Table
Hashing adalah suatu teknik yang digunakan untuk menyimpan dan menerima suatu keys dengan cepat. Dalam hashing, sebuah string karakter berubah menjadi suatu value atau key yang lebih pendek yang mewakili string itu sendiri. Hashing digunakan untuk mengindeks dan mengambil item dalam database karena metode tersebut dapat lebih cepat menemukan item dengan menggunakan hashed key yang lebih pendek daripada menemukannya menggunakan value asli. Hashing juga dapat didefinisikan sebagai konsep mendistribusikan key dalam array yang disebut tabel hash menggunakan fungsi yang telah ditentukan yang disebut fungsi hash.
Hashing menggunakan suatu tabel yang disebut hash table. Hash table adalah suatu tabel (array) tempat kita menyimpan string asli. Indeks dari tabel tersebut adalah key hash, sedangkan valuenya adalah string asli. Ukuran hash table biasanya terdiri dari beberapa urutan yang besarnya lebih kecil dari jumlah total string yang ada, sehingga beberapa string mungkin memiliki hashed key yang sama. Contoh: terdapat 267 (8.031.810.176) string dengan panjang 7 karakter yang terdiri dari huruf kecil saja.
Misalkan kita ingin menyimpan 5 string: ambon, goa, exponen, delta, buaya ke hash table dengan ukuran 26. Fungsi hash yang akan digunakan adalah “mengubah huruf pertama dari setiap string ke dalam sebuah angka dari 0-25. (a = 0, b = 1, .... z = 25).
Tabel tersebut merupakan hash table dari string-string tersebut yang disimpan menurut huruf pertamanya.
ambon disimpan di str[0] karena a = 0;
buaya disimpan di str[1] karena b = 1;
delta disimpan di str[3] karena d = 3, dst.
Beberapa method yang digunakan untuk membangun fungsi has:
- Mid-square
- Division (paling sering digunakan)
- Folding
- Digit extraction
- Rotating hash
Kita akan membahas metode division/pembagian saja.
Division à membagi string/identifier dengan menggunakan operator modulus dan merupakan metode hashing paling mudah.
Misalkan ada suatu tabel untuk menyimpan string. Fungsi hash yang sangat sederhana adalah menambahkan nilai ASCII dari semua karakter dalam string dan mengambil sisa bagi ukuran tabel, misalnya 10.
Contoh:
Angka yang akan disimpan adalah: 35, 84, 22, 93, 98.
h(z) = z mod 10;
h(35) = 5
h(84) = 4
h(22) = 2
h(93) = 3
h(98) = 8
Dalam implementasi, hash table merupakan salah satu komponen penting dalam blockchain untuk menjaga konsistensi data dan memastikan tidak ada perubahan data yang terjadi. Penggunaan blockchainoleh banyak orang sekaligus menuntut penggunaan fungsi hashdengan performa yang handal. Fungsi hash Keccak dan BLAKE2 merupakan fungsi hash yang relatif baru dan dapat digunakan dalam teknologi blockchain.
Algoritma hash digunakan dalam blockchain untuk memastikan data yang dituliskan valid, sehingga perubahan data sepihak akan sulit dilakukan. Terutama jika blockchain diimplementasikan pada sistem terdistribusi dengan konsensus tertentu. Setiap perubahan data pada suatu blok akan mengakibatkan berbedanya hasil hash, sehingga blok-blok selanjutnya menjadi tidak valid. Oleh karena itu, untuk melakukan perubahan sepihak dibutuhkan usaha dan waktu yang lama.
2. Binary Tree dan Tree
Tree adalah struktur data non-linear yang mewakili hubungan hierarkis di antara objek data. Beberapa hubungan dalam tree dapat diamati dalam struktur direktori atau hierarki organisasi. Node pada tree tidak perlu disimpan secara berdekatan dan dapat disimpan di mana saja dan dihubungkan oleh pointer.
Tree memiliki elemen-elemen:
- Node
- Node paling atas disebut root
- Node yang tidak memiliki children (anak) disebut leaf (daun)
- Node yang memiliki parent yang sama disebut sibling
- Degree (tingkat) dari suatu node merupakan total subtree dari node
- Height/depth merupakan degree maximum dari node dalam tree
- Jika terdapat suatu garis yang menghubungkan p ke q, maka p disebut ancestor (leluhur) dari q, dan q merupakan descendant (keturunan) dari p.
Graf diatas merupakan contoh binary tree yang memiliki 9 node, dimana akar dari tree tersebut memiliki nilai 18. Daun-daunya adalah 9, 12, 10, 23.
Stack & Queue
source: https://anasihite.files.wordpress.com/2016/01/stack.png?w=523&h=228&crop=1
1. Stack
Secara harafiah, stack berarti tumpukan. Dalam struktur data, stack merupakan salah satu metode pengaturan data yang menggunakan sistem Last In First Out (LIFO). Data yang terakhir masuk, akan lebih dulu keluar/digunakan. Sebalikanya, data yang pertama masuk, akan keluar/digunakan terakhir. Sebagai gambaran, ketika anda menumpuk piring, piring yang pertama kali akan terletak di bawah piring kedua, dan seterusnya sampai piring yang terakhir berada di paling atas. Kemudian, saat anda ingin mengambil sebuah piring, tentunya anda akan mengambil piring yang paling atas. Piring pertama tadi akan terus berada di paling bawah sampai akhirnya mendapat giliran diambil.
Operasi-operasi yang digunakan pada stack:
· Push() à Menambah data baru ke paling atas
· Pop() à Menghapus data dari paling atas
· Top() à Mengambil data paling atas (disebut juga peek)
Dalam pengoperasiannya, ada 3 jenis operasi perhitungan:
· Infix à operasi perhitungan dengan susunan operand dan operator yang berurutan
Contoh: 4 + 6 (5-2) / 3
· Prefix à operasi perhitungan dengan susunan operator berada di sebelah kiri dari operand, komputer akan memprosesnya dari kanan ke kiri.
Contoh: mengubah 4 + 6 (5-2) / 3 ke prefix kita perlu mengetahui masing-masing tingkatan operator dari yang tertinggi
4 + 6 * (5 – 2) / 3 Operator ( ) merupakan operator tertinggi
- 5 2
4 + 6 * (5 – 2) / 3 Operator * merupakan operator tertinggi
* 6 - 5 2
4 + 6 * (5 – 2) / 3 Operator / merupakan operator tertinggi
/ * 6 – 5 2 3
4 + 6 * (5 – 2) / 3 Operator + adalah operator terakhir
+ 4 / * 6 - 5 2 3
· Postfix à operasi perhitungan dengan susunan operator di sebelah kanan dari operand, komputer akan memprosesnya dari kiri ke kanan
Contoh: mengubah 4 + 6 (5-2) / 3 ke postfix kita perlu mengetahui masing-masing tingkatan operator dari yang tertinggi.
4 + 6 * (5 – 2) / 3 Operator ( ) merupakan operator tertinggi
5 2 -
4 + 6 * (5 – 2) / 3 Operator * merupakan operator tertinggi
6 5 2 - *
4 + 6 * (5 – 2) / 3 Operator / merupakan operator tertinggi
6 5 2 - * 3 /
4 + 6 * (5 – 2) / 3 Operator + adalah operator terakhir
4 6 5 2 - * 3 / +
Mengapa kita menggunakan notasi prefix/postfix? Karena dalam pengoperasiannya, kita tidak memerlukan tanda kurung apapun untuk menentukan Presedence ataupun Associativity. Komputer juga akan lebih mudah untuk mengevaluasi operasi aritmatik tersebut.
Dalam mencari data pada stack, digunakan algoritma DFS (Depth First Search) yakni algoritma penelusuran yang dilakukan dengan menelusuri bagian dalam (akar) pada tree / graf.
source: https://he-s3.s3.amazonaws.com/media/uploads/9fa1119.jpg
Dari gambar di atas, dapat kita jabarkan algoritma dari DFS tersebut. DFS melakukan pencarian data dari paling kiri terlebih dahulu pada graf, lalu menuju ke bagian lebih dalam terlebih dahulu setelah angka 1 (sub-tree , dalam kasus ini, angka 2), kemudian melaju lebih dalam lagi ke angka 4 dan 5. Setelah itu, menuju angka disebelah angka 2, yaitu 3, dan alurnya adalah 1-2-4-5-3.
2. Queue
Secara harafiah, queue berarti antrian. Queue merupakan salah satu metode pengaturan data yang menggunakan sistem First In First Out (FIFO). Data yang pertama masuk, akan lebih dulu keluar/digunakan. Sebaliknya, data yang terakhir masuk, akan keluar/digunakan terakhir juga. Sebagai gambaran, ketika anda mengantri di sebuah loket untuk membeli karcis, maka anda akan mengantri terlebih dahulu, ke bagian paling belakang. Orang yang berada di paling depan akan dilayani terlebih dahulu, dan akan pergi saat itu juga. Lalu dilanjutkan orang kedua, sampai giliran anda (ketika tidak ada orang lagi) di bagian terakhir. Begitu juga dengan data. Data yang dimasukkan pertama akan berada di posisi paling depan/atas/kiri. Lalu ketika ingin menghapus data (pop) atau mengambil data paling atas (top), maka data pertama yang masuk duluan tadi akan diproses di awal.
Operasi-operasi yang digunakan pada queue:
· Push() à Menambah data baru ke paling belakang
· Pop() à Menghapus data dari paling atas/depan
· Top() à Mengambil data paling atas/depan
Dari gambar tersebut, jika kita melakukan pop terus-menerus, make posisi L dan R akan semakin mundur ke belakang/kanan. Jika hasil ini terus berlanjut, saat posisi L dan R berada di bagian paling belakang, maka komputer akan menginstruksikan kalau data sudah penuh, padahal data kosong. Untuk mengatasi hal itu, digunakanlah sistem circular queue (sistem lingkaran) dimana posisi R saat sudah diujung, akan dipindahkan ke bagian paling depan/kiri (R = 0).
Deque (Double Ended Queue) à queue yang bisa menghapus/menambah dari bagian depan maupun belakang.
Deque memiliki 2 varian:
· Input restricted deque
Penambahan data hanya bisa dilakukan pada 1 ujung deque, sementara penghapusan dapat dilakukan pada 2 ujung.
· Output restricted deque
Penghapusan data hanya bisa dilakukan pada 1 ujung deque, sementara penghapusan dapat dilakukan pada 2 ujung.
Priority Queue à Kita bisa mengatur prioritas pada queue, sehingga elemen/data yang lebih tinggi prioritasnya akan lebih dulu diproses.
Dalam mencari data pada queue, digunakan algoritma BFS (Breadth First Search) yakni algoritma penelusuran yang dilakukan dengan menelusuri bagian anak pada tree / graf.
source: https://pythoninwonderland.files.wordpress.com/2017/03/graphorder.png
Dari gambar tersebut, BFS akan menelusuri dulu bagian yang sejajar. Setelah itu, baru masuk ke bagian lebih dalam dan menelusuri lagi bagian yang sejajar, begitu seterusnya hingga data ditemukan.
Prosesnya A-B-E-C-D-F-G.
Contoh Implementasi Linked List
Berikut ini merupakan contoh problem yang dapat diselesaikan dengan Linked List
Diminta untuk membuat aplikasi menu yang menggunakan double linked list.
Aplikasi bisa input barang (nama & kuantitas), kuantitas bisa diedit dan bisa menghapus item yang salah. Ketika checout akan ditampilkan hasil total dari perhitungan kuantitas. Harga yang tertera random, namun hasil penjumlahan benar (totalnya benar). Setelah tahap pembayaran, dibawah tulisan total, tuliskan gratis, "kindness if free".
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
int count = 0;
struct sales{
int price;
char product_name[30];
int qty;
struct sales *next;
struct sales *prev;
}*head,*curr,*tail;
void push(char product_name[], int qty){
srand(time(NULL));
curr = (struct sales*)malloc(sizeof(struct sales));
strcpy(curr->product_name,product_name);
curr->price = rand();
curr->qty = qty;
if(head == NULL){
head = tail = curr;
}
else if(strcmp(curr->product_name,head->product_name) == 0){
printf("You've already add this item, please type another item!");
}
else if(strcmp(curr->product_name,head->product_name) < 0){
curr->next = head;
head->prev = curr;
head = curr;
}
else if(strcmp(curr->product_name,tail->product_name) > 0){
curr->prev = tail;
tail->next = curr;
tail = curr;
}
else{
struct sales* temp = head;
int flag = 0;
while(strcmp(temp->next->product_name, curr->product_name) < 0){
if(strcmp(temp->product_name, curr->product_name) == 0){
flag = 1;
break;
}
temp = temp->next;
}
if(flag = 1) {
printf("You've already add this item, please type another item!");
}
else{
curr->next = temp->next;
temp->next->prev = curr;
curr->prev = temp;
temp->next = curr;
}
}
head->prev = tail->next = NULL;
}
void edit(int angka, int qty){
int i = 1;
sales *temp = head;
while(angka != i){
temp = temp->next;
i++;
}
temp->qty = qty;
}
void printMenu(){
printf("Main menu\n");
printf("1. Add Item\n");
printf("2. Edit Item\n");
printf("3. Delete Item\n");
printf("4. Checkout & Exit\n\n");
}
void print(){
curr = head;
int i = 1;
printf("\n");
printf("==============================Item List==============================\n");
printf("| No. | Product Name\t | Qty | Price 1 Item | Price * Qty |\n");
printf("|-----|----------------------|--------|---------------|-------------|\n");
if(head == NULL){
printf("| - | No Item | - | - | - |\n");
}
while(curr != NULL){
printf("| %-2d. | %-20s | %-6d | Rp %-10d | Rp %-8d |\n",i,curr->product_name,curr->qty,curr->price,curr->price*curr->qty);
curr = curr->next;
i++;
}
printf("|-----|----------------------|--------|---------------|-------------|\n");
}
void popDepan(){
if(head != NULL){
curr = head;
head = curr->next;
free(curr);
head->prev = NULL;
}
}
void popBelakang(){
if(tail != NULL){
curr = tail;
tail = curr->prev;
free(curr);
tail->next = NULL;
}
}
void pop(int angka){
if(head == tail){
free(head);
head = tail = head->next = tail->prev = NULL;
}
if(angka == 1){
popDepan();
}
else if(angka == count){
popBelakang();
}
else{
int i = 1;
sales *temp = head;
while(angka != i){
temp = temp->next;
i++;
}
curr = temp->next;
temp->next = curr->next;
curr->next->prev = temp;
free(curr);
}
}
int main(){
int choose;
printf("========================Welcome to April Market========================\n\n");
do{
choose = 0;
char product_name[30];
int qty;
printMenu();
do{
printf("Type your choice: "); scanf("%d",&choose); fflush(stdin);
}while(choose < 1 || choose > 4);
switch(choose){
int angka;
case 1:
printf("Type product name: "); scanf("%[^\n]",product_name); getchar();
printf("Type quantity: "); scanf("%d",&qty); fflush(stdin);
push(product_name,qty);
count++;
print();
printf("\n");
break;
case 2:
if(head == NULL){
printf("There is no data in the list\n\n");
}
else{
do{
printf("Type the item number[ If no data, you'll type again..]: "); scanf("%d",&angka);
fflush(stdin);
}while(angka < 0 || angka > count);
printf("Type your new quantity: "); scanf("%d",&qty);
edit(angka,qty);
printf("Item quantity has successfully edited\n");
print();
printf("\n");
}
break;
case 3:
if(head == NULL){
printf("There is no data in the list\n\n");
}
else{
do{
printf("Type the item number[ If no data, you'll type again..]: "); scanf("%d",&angka);
fflush(stdin);
}while(angka < 0 || angka > count);
pop(angka);
print();
printf("\n");
printf("Data has succesfully Deleted\n");
}
break;
case 4:
print();
if(head == NULL){
printf("No data! Thank you!\n");
}
else{
sales *temp = head;
long total = 0;
total += (temp->price*qty);
while(temp->next != NULL){
total += (temp->next->price * qty);
temp = temp->next;
}
printf("|\t\t\t Total price\t\t | Rp %-8d |\n",total);
printf("|-----|----------------------|--------|---------------|-------------|\n");
printf("\nContinue to payment session?...\n");
printf("Press enter to continue..."); getchar();
printf("All Free\n");
printf("~~~~~~~~~~~~KINDNESS IS FREE~~~~~~~~~~~~\n");
printf("~~~~~~~~~~~~~~~Thank You!!!~~~~~~~~~~~~~\n");
}
break;
}
}while(choose != 4);
return 0;
}
No comments:
Post a Comment