Linked List
1. Pengertian Linked List
Linked list memiliki nama lain, yaitu seranai berantai adalah struktur data yang mengandung/memiliki urutan record data dimana setiap record data memiliki suatu tempat (field) yang menyimpan alamat dari record data selanjutnya. Elemen-elemen dari suatu data disebut Node.
2. Perbedaan dengan Array
Pada array, kita telah mendeklarasikan berapa jumlah yang akan digunakan nantinya, sedangkan linked list tidak. Linked list menggunakan malloc (memory allocation) untuk menambah/mereserve NODE. Selain itu, jika kita mereserve tempat untuk array, address dari setiap index akan berdekatan/memiliki kelipatan yang sama. Sedangkan dalam linked list tidak, karena linked list menggunakan malloc, maka NODE baru dapat memiliki address yang berjauhan dengan NODE sebelumnya (address tersebut dapat random, sesuai dengan memory yang sedang tidak digunakan oleh komputer).
3. Jenis-jenis Linked List
a) Single Linked List
Merupakan Linked List yang hanya tersambung dengan NODE depannya. Contoh ada NODE A, B, dan C. A terhubung ke B dan B terhubung ke C.
b) Double Linked List
Merupakan Linked List yang tersambung dengan NODE depannya serta NODE belakangnya. Contoh ada NODE A, B, dan C. A terhubung ke B dan sebaliknya, serta B terhubung ke C dan sebaliknya.
c) Circular Linked List
i. Circular Singly Linked List
Sama seperti Single Linked List, akan tetapi NODE paling belakang terhubung dengan NODE paling depan.
ii. Circular Double Linked List
Sama seperti Double Linked List, akan tetapi NODE paling depan terhubung dengan NODE paling belakang dan sebaliknya.
Stack and Queue
1. Pengertian Stack dan Queue
a) Stack
Stack atau tumpukan adalah cara penyimpanan dalam memori, dimana data yang dimasukkan pertama akan dikeluarkan terakhir. Sama seperti kita menaruh kue kedalam toples. Jika kita ingin memakannya, kue yang pertama kali kita makan adalah kue terakhir yang masuk ke dalam toples.
b) Queue
Queue atau antrian adalah cara penyimpanan dalam memori, dimana data yang dimasukkan pertama akan dikeluarkan pertama. Seperti jika kita mengantri disebuah restoran. Orang yang datang pertama kali akan dilayani terlebih dahulu.
Hashing Table
1. Pengertian Hashing
Hashing adalah sebuah teknik yang digunakan untuk menyimpan dan mengambil kunci dalam waktu yang cepat atau singkat. Dalam hashing, string akan diubah menjadi string yang lebih pendek atau kunci yang merepresentasikan string awal. Hashing dapat diartikan sebagai konsep pembagian kunci dalam array (hash table) dengan fungsi yang telah ditentukan sebelumnya (hash function).
2. Pengertian Hash Table
Hash table adalah sebuah tabel (array) dimana kita menyimpan string awal (original string). Biasanya ukuran dari hash table lebih kecil dari jumlah total string. Jadi ada kemungkinan beberapa string memiliki hash key yang sama.
3. Metode yang dapat digunakan untuk membangun fungsi hash
a) Mid square
Kuadratkan nilai dari key, lalu ambil nilai tengah dari hasil kuadrat tersebut. Contoh: key = 3121, key2 = 9740641, bagian yang diambil = 406
b) Division
Bagi string atau identifier dengan menggunakan operator modulus (seperti contoh diatas). Metode ini merupakan metode yang paling sering dipakai.
c) Folding
Partisi string / identifier menjadi beberapa bagian, lalu menambahkan bagian-bagian yang ada untuk mendapatkan hash key.
d) Digit Extraction
Digit yang telah ditentukan dari nomor yang diberikan dianggap sebagai alamat dari hash.
e) Rotating Hash
Menggunakan metode hash apapun (seperti division, atau folding). Setelah mendapatkan hash code/alamat dari hash method, lakukan rotasi. Rotasi dilakukan dengan shifting digits untuk mendapatkan alamat hash yang baru.
Trees and Binary Tree
1. Pengertian Trees dan Binary Tree
a) Trees
Tree biasa digunakan untuk mewakili data yang memiliki struktur hierarki antar elemen.
b) Binary Tree
Merupakan tipe spesial dari tree dimana setiap node antara tidak memiliki node, memiliki satu node atau dua node.
2. Bentuk atau jenis Binary Tree
a) Full Binary Tree
b) Complete Binary Tree
c) Skewed Binary Tree
d) Dll
References
Market Application Code
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#include <conio.h>
int i=0;
struct node
{
int jumlah;
int price;
char item[15];
node *next, *prev;
}*head, *tail;
node* createNode(int banyak, char nama[])
{
node* temp = (node*)malloc(sizeof(node));
temp->jumlah = banyak;
strcpy(temp->item,nama);
temp->price = (rand()%(10000-1000+1))%1000;
temp->next = NULL;
temp->prev = NULL;
return temp;
}
void pushTail(int value, char nama[])
{
node* newData = createNode(value,nama);
if(head == NULL){
head = tail = newData;
}
else{
tail->next = newData;
newData->prev = tail;
tail = newData;
}
}
void ubah(char ganti[], int angka)
{
if(head == NULL)
{
return;
}
else if(head == tail)
{
head = tail = NULL;
node *currentNode = head;
currentNode->jumlah = angka;
}
else
{
node *currentNode = head;
while(currentNode != NULL)
{
if(strcmp(currentNode->item,ganti) == 0)
{
currentNode->jumlah = angka;
}
currentNode = currentNode->next;
}
}
}
void pop(char hapus[])
{
if(head == NULL)
{
return;
}
else if(head == tail)
{
head = tail = NULL;
free(head);
free(tail);
}
else
{
node *currentNode = head;
while(currentNode != NULL)
{
if(strcmp(currentNode->item,hapus) == 0)
{
if(currentNode == head)
{
currentNode->next->prev = NULL;
head = currentNode->next;
free(currentNode);
}
else if (currentNode == tail)
{
currentNode->prev->next = NULL;
tail = currentNode->prev;
free(currentNode);
}
else
{
currentNode->prev->next = currentNode->next;
currentNode->next->prev = currentNode->prev;
free(currentNode);
}
}
currentNode = currentNode->next;
}
}
}
void printAll()
{
node* currentNode = head;
i=1;
printf("| No. | Product's name | Quantity | Price |\n");
printf("=====================================================\n");
while(currentNode != NULL){
printf("| %-3d | %-20s | %-8d | %-9d |\n", i,currentNode->item,currentNode->jumlah,currentNode->price);
currentNode = currentNode->next;
i++;
}
}
int hitung()
{
int total=0;
node* currentNode = head;
while(currentNode != NULL){
total = currentNode->jumlah * currentNode->price;
currentNode = currentNode->next;
}
return total;
}
void space()
{
for (int i=0;i<30;i++)
{
puts("");
}
}
void pilih()
{
printf("| No. | Product's name |\n");
printf("==============================\n");
printf("| 1. | %-20s |\n","Chitoto");
printf("| 2. | %-20s |\n","Lais");
printf("| 3. | %-20s |\n","Dedek Crunch");
printf("| 4. | %-20s |\n","Nissan Wafer");
printf("| 5. | %-20s |\n","Oh-Reo");
printf("| 6. | %-20s |\n","Binusmilk");
printf("| 7. | %-20s |\n","Ricis Hewani");
printf("| 8. | %-20s |\n","Piringless");
printf("| 9. | %-20s |\n","Begal Marie");
printf("| 10. | %-20s |\n","Gud Taim");
puts("");
}
int main ()
{
srand(time(0));
int inp=0;
int makan=0;
int jumlah=0;
char ganti[20];
int angka=0;
char hapus[20];
char sudah;
int temp=0;
long int total=0;
while (inp!=6)
{
space();
printf("===========Smol Marked===========\n");
printf("=================================\n\n");
printf("1. Pilih item\n");
printf("2. Cek item\n");
printf("3. Ganti jumlah item\n");
printf("4. Delete item\n");
printf("5. Check out\n");
printf("6. Exit\n\n");
printf("Pilih angka dari 1 - 5: ");
scanf("%d",&inp); getchar();
switch(inp)
{
case 1:
{
space();
pilih();
do
{
printf("Pilih salah 1: ");
scanf("%d",&makan); getchar();
} while (makan > 10 || makan < 1);
printf("Banyaknya: ");
scanf("%d",&jumlah); getchar();
if (makan==1) pushTail(jumlah,"Chitoto");
else if (makan==2) pushTail(jumlah,"Lais");
else if (makan==3) pushTail(jumlah,"Dedek Crunch");
else if (makan==4) pushTail(jumlah,"Nissan Wafer");
else if (makan==5) pushTail(jumlah,"Oh-Reo");
else if (makan==6) pushTail(jumlah,"Binusmilk");
else if (makan==7) pushTail(jumlah,"Ricis Hewani");
else if (makan==8) pushTail(jumlah,"Piringless");
else if (makan==9) pushTail(jumlah,"Begal Marie");
else if (makan==10) pushTail(jumlah,"Gud Taim");
temp++;
break;
}
case 2:
{
space();
printAll();
getchar();
break;
}
case 3:
{
space();
if (temp == 0)
{
printf("Kamu belum beli apa-apa.. Trus ngerubah apa dongg?");
getchar();
}
else
{
printAll();
do
{
puts("");
printf("Yang mana yang mau diganti jumlahnya?\n");
printf("Masukkan namanya (case sensitive): ");
scanf("%[^\n]",ganti); getchar();
} while (strcmp(ganti,"Chitoto")!=0 && strcmp(ganti,"Lais")!=0 && strcmp(ganti,"Dedek Crunch")!=0 && strcmp(ganti,"Nissan Wafer")!=0 &&
strcmp(ganti,"Oh-Reo")!=0 && strcmp(ganti,"Binusmilk")!=0 && strcmp(ganti,"Ricis Hewani")!=0 && strcmp(ganti,"Piringless")!=0 &&
strcmp(ganti,"Begal marie")!=0 && strcmp(ganti,"Gud Taim")!=0);
do
{
puts("");
printf("Jumlahnya jadi berapa?\n");
printf("Masukkan angkanya: ");
scanf("%d",&angka); getchar();
} while (angka < 1);
ubah(ganti,angka);
space();
printf("Jumlah untuk %s telah diganti menjadi %d",ganti,angka);
getchar();
}
break;
}
case 4:
{
space();
if (temp==0)
{
printf("Kamu belum beli apa-apa :(");
getchar();
}
else
{
printAll();
do
{
printf("Yang mana yang mau dihapus?\n");
printf("Masukkan namanya (case sensitive): ");
scanf("%[^\n]",hapus); getchar();
} while (strcmp(hapus,"Chitoto")!=0 && strcmp(hapus,"Lais")!=0 && strcmp(hapus,"Dedek Crunch")!=0 && strcmp(hapus,"Nissan Wafer")!=0 &&
strcmp(hapus,"Oh-Reo")!=0 && strcmp(hapus,"Binusmilk")!=0 && strcmp(hapus,"Ricis Hewani")!=0 && strcmp(hapus,"Piringless")!=0 &&
strcmp(hapus,"Begal marie")!=0 && strcmp(hapus,"Gud Taim")!=0);
pop(hapus);
temp--;
space();
printf("Item sudah dihapus!");
getchar();
}
break;
}
case 5:
{
space();
if (temp==0)
{
printf("Beli dulu bro :D");
getchar();
}
else
{
printAll();
total = hitung();
printf("| Harga total : %-20ld |\n", total);
do
{
printf("Sudah selesai? [Y / N]: ");
scanf("%c",&sudah); getchar();
}while (sudah != 'Y' && sudah != 'N' && sudah != 'y' && sudah != 'n');
if (sudah == 'Y' || sudah == 'y')
{
space();
printf("Kindness is Free!!");
exit(0);
}
else
{
break;
}
}
break;
}
case 6:
{
space();
printf("Terima Kasih!! :D");
break;
}
default:
{
space();
printf("Pilih angka dari 1 - 6!");
getchar();
}
}
}
return 0;
}
