Apa itu linked list?
linked list adalah linear data structure (struktur data linear) yang dimana datanya tidak disimpan pada lokasi memori yang bersebelahan. Data pada linked list disimpan menggunakan pointer. linked list terdiri dari node yang berisikan data dan memiliki link dengan node selanjutnya pada list tersebut. Terdapat 2 jenis Linked List, berikut contohnya :
Single Linked List
Singly linked list memiliki node yang memiliki 2 kotak yang menyimpan data tersebut dan pointer yang menyimpan alamat node berikutnya. Pada node terakhir, terdapat pointer yang menyimpan nilai "NULL" yang disebut dengan tail. sedangkan node pertama disebut dengan head.
Double Linked List
Dalam doubly linked list, setiap node terdapat pointer yang menunjuk ke node sebelum dan sesudahnya. dalam doubly linked list ini, setiap node berisikan 3 bagian, yaitu node data, dan pointer ke node sebelum dan sesudahnya.
Keunggulan linked list dibandingkan dengan array:
- ukuran untuk array harus di deklarasikan diawal, sedangkan linked list tidak harus.
- ukuran linked list bisa bertambah seiringnya pertambahan data (dinamis)
- penyimpanan linked list tidak harus disimpan secara bersebelahan pada memori
- dapat menyimpan primitive data types ataupun objek pada linked list
Stack & Queue
Stack adalah kumpulan elemen data yang disimpan dalam satu lajur linear. Kumpulan data tersebut hanya dapat diakses pada satu tempat saja, yaitu posisi yang paling atas dari tumpukkan tersebut (TOP). Konsep utamanya adalah LIFO (Last In First Out), yaitu data terakhir yang masuk kedalam urutan tersebut akan menjadi data pertama yang dikeluarkan dari kumpulan (seperti pada tumpukkan saat mencuci piring, piring yang ditaruh terakhir akan menjadi piring pertama yang diambil untuk dicuci).
Terdapat 2 operasi yang sering diterapkan dalam struktur data Stack, yaitu Push dan Pop. Beberapa contoh operasi pada Stack :
- Push : digunakan untuk menambah data pada Stack paling atas.
- Pop : digunakan untuk mengambil data pada Stack paling atas.
- Create Stack : membuat Stack baru X, dengan jumlah elemen data kosong.
- IsFull : untuk mengecek apakah Stack sudah penuh.
- IsEmpty : untuk mengecek apakah Stack kosong
Sedangkan Queue adalah struktur data linear yang dimana penambahan elemen data disalah satu ujungnya, sedangkan untuk pengurangannya dilakukan pada ujung lainnya. Queue menggunakan konsep FIFO(First In First Out), yaitu data yang pertama kali masuk kedalam urutan merupakan data yang pertama kali akan diakses.
Terdapat 2 operasi yang sering digunakan pada Queue :
- EnQueue : digunakan untuk memasukkan data kedalam queue.
- DeQueue : digunakan untuk mengeluarkan data terdepan dari Queue tersebut.
Hash Table
Hashing merupakan cara untuk mencari objek dengan spesifik dari suatu kumpulan objek yang mirip.
Hash table sendiri adalah salah satu struktur data yang terdiri atas sebuah table serta fungsi yang ditujukan untuk memetakan nilai yang unik dari setiap baris (record) menjadi angka (hash) lokasi baris tersebut kedalam sebuah table. Hash table digunakan untuk mempercepat pencarian terhadap data yang telah disimpan. Waktu yang dibutuhkan untuk insertion, deletions, dan searching relative sama dibandingkan dengan struktur data yang lain.
Operasi pada hash table :
- Insert : diberikan sebuah nilai dan key, insert nilai kedalam table
- Find : diberikan key, untuk menemukan nilai yang terhubung pada key tersebut
- Remove : diberikan key, kemudian mencari nilai yang terhubung pada key dan menghapus nilai tersebut
getIterator : mengembalikan iterator, yang memeriksa nilai.
Kelebihan Hash table :
Binary Search Tree
Binary search tree (BST) merupakan struktur data bersifat hirarkis yang menggunakan node sebagai dasarnya, seperti halnya pada linked list. BST ini digunakan untuk Fast Searching, Rapid Sorting, Easy Insertion, dan Deletion Data. Dalam BST, tiap node hanya boleh memiliki maksimal dua sub-tree dan kedua subtree tersebut harus terpisah. Subtree sebelah kiri akan memiliki node yang nilainya lebih rendah daripada parent node, sedangkan sebelah kanan berisikan node yang memiliki nilai lebih tinggi daripada parent node.
Insertion
Memasukkan sebuah nilai baru kepada binary tree akan selalu masuk ke bagian paling bawah. Dimulai dengan mencari nilai root sampai ke leaf node, dan jika nilai yang dimasukkan lebih kecil dari leaf node, maka angka yang dimasukkan akan berada di sebelah kiri leaf node, berlaku sebaliknya dengan nilai yang lebih besar.
Searching
Dalam mencari suatu nilai pada BST, akan dilihat dan dibandingkan dengan nilai pada root. Bila nilai yang diinginkan sama dengan nilai pada root, makan root adalah nilai yang dicari. Namun jika yang dicari lebih kecil, makan akan mencari pada subtree disebelah kiri node root. Berlaku sebaliknya, jika nilai yang dicari lebih besar daripada root, maka akan mencari pada subtree sebelah kanan dari node root.
Deletion
Ada beberapa kondisi didalam melakukan Deletion pada BST :
- Jika node yang akan dihapus adalah leaf node, makan dapat langsung menghapus leaf node tersebut.
- Jika node yang dihapus hanya memiliki 1 subtree, child node ini akan dicopy ke node yang akan dihapus, baru dilakukan deletion.
- Jika node yang akan dihapus memiliki 2 subtree, dapat dilakukan dengan 2 cara, yaitu dengan mengambil nilai maksimum dari sebelah kiri, atau dengan nilai minimum pada subtree sebelah kanan.
Minimarket :
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
struct toko{
int qty, price;
char name[100];
toko *next, *prev;
}*head=NULL, *tail=NULL;
toko* createNode(char *name, int qty, int price){
toko *temp = (toko*) malloc(sizeof(toko));
strcpy (temp->name, name);
temp->qty = qty;
temp->price = price;
temp->prev = temp->next = NULL;
return temp;
}
void pushHead (char *name, int qty, int price){
if (!head) head = tail = createNode(name, qty, price);
else {
toko *temp = createNode(name, qty, price);
temp->next = head;
head->prev = temp;
head = temp;
}
}
void pushTail (char *name, int qty, int price){
if (!head) head = tail = createNode(name, qty, price);
else {
toko *temp = createNode(name, qty, price);
tail->next = temp;
temp->prev = tail;
tail = temp;
}
}
void popHead(){
if(!head) return;
else if (head == tail){
toko *temp = head;
head = tail = NULL;
free(temp);
}
else {
toko *temp = head;
head = head->next;
head->prev = NULL;
free(temp);
}
}
void popTail(){
if(!head) return;
else if (head == tail){
toko *temp = head;
head = tail = NULL;
free(temp);
}
else {
toko *temp = tail;
tail = tail->prev;
tail ->next = NULL;
free(temp);
}
}
void pushMid (char *name, int qty, int price){
if (!head) head = tail = createNode(name, qty, price);
else if (strcmp(name, head->name) < 0) pushHead(name, qty, price);
else if (strcmp(name, tail->name) > 0) pushTail(name, qty, price);
else {
toko *temp = createNode(name, qty, price);
toko *curr = head;
while (strcmp(name, curr->name) > 0){
curr = curr->next;
}
temp->next = curr;
temp->prev = curr->prev;
curr->prev->next = temp;
curr->prev = temp;
}
}
void popSearch(char *name){
if (!head) {
printf("No item found\n");
return;
}
else if (strcmp(head->name, name) == 0) popHead();
else if (strcmp(tail->name, name) == 0) popTail();
else {
toko *temp = head;
toko *curr;
while (strcmp(name, temp->name) < 0){
curr = temp;
temp = temp->next;
}
curr->next = temp->next;
temp->next->prev = curr;
free(temp);
}
}
int tot=0;
void printAll(){
toko *temp = head;
if(!head){
printf("No item found\n"); return;
}
else{
while (temp){
printf ("item name : %s, quantity : %d, price each : %d\n", temp->name, temp->qty, temp->price);
temp = temp->next;
}
}
}
void printCheckout(){
toko *temp = head;
if(!head){
printf("No item found\n"); return;
}
else{
while (temp){
printf ("item name : %s, quantity : %d, price each : %d\n", temp->name, temp->qty, temp->price);
tot += temp->price * temp->qty;
temp = temp->next;
}
}
}
int main(){
char name[100];
int qty, price;
printf("Input item name : ");
scanf ("%[^\n]", &name);
printf("Input item quantity : ");
scanf ("%d", &qty); getchar();
price = rand() % 1000;
pushMid(name, qty, price);
printf("Input success\n");
printf("press enter to continue...");getchar();
system("cls");
int x = 0;
do{
printf("1. add another item\n");
printf("2. edit item quantity\n");
printf("3. delete item\n");
printf("4. view\n");
printf("5. checkout\n");
int menu;
printf("Choose menu : ");
scanf("%d", &menu); getchar();
system("cls");
switch (menu){
case 1 :{
printf("Input item name : ");
scanf ("%[^\n]", &name);
printf("Input item quantity : ");
scanf ("%d", &qty); getchar();
price = rand() % 1000;
pushMid(name, qty, price);
printf("Input success\n");
printf("press enter to continue...");getchar();
system("cls");
break;
}
case 2 :{
printf("Input item name to change the quantity : ");
scanf("%[^\n]", &name);
printf("Change quantity to : ");
scanf("%d", &qty);getchar();
price = rand() % 1000;
popSearch(name);
pushMid(name, qty, price);
printf("Input change success\n");
printf("press enter to continue...");getchar();
system("cls");
break;
}
case 3 : {
printf("Input item name to delete : ");
scanf("%[^\n]", &name);
popSearch(name);
printf("Deletion success\n");getchar();
printf("press enter to continue...");getchar();
system("cls");
break;
}
case 4 : {
printAll();
printf("press enter to continue...");getchar();
system("cls");
break;
}
case 5 : {
printCheckout();
printf ("Your total price : %d\n", tot);
printf ("press enter to continue...");getchar();
printf ("kindness is free..");getchar();
return 0;
}
}
}while(x!=4);
return 0;
}
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
struct toko{
int qty, price;
char name[100];
toko *next, *prev;
}*head=NULL, *tail=NULL;
toko* createNode(char *name, int qty, int price){
toko *temp = (toko*) malloc(sizeof(toko));
strcpy (temp->name, name);
temp->qty = qty;
temp->price = price;
temp->prev = temp->next = NULL;
return temp;
}
void pushHead (char *name, int qty, int price){
if (!head) head = tail = createNode(name, qty, price);
else {
toko *temp = createNode(name, qty, price);
temp->next = head;
head->prev = temp;
head = temp;
}
}
void pushTail (char *name, int qty, int price){
if (!head) head = tail = createNode(name, qty, price);
else {
toko *temp = createNode(name, qty, price);
tail->next = temp;
temp->prev = tail;
tail = temp;
}
}
void popHead(){
if(!head) return;
else if (head == tail){
toko *temp = head;
head = tail = NULL;
free(temp);
}
else {
toko *temp = head;
head = head->next;
head->prev = NULL;
free(temp);
}
}
void popTail(){
if(!head) return;
else if (head == tail){
toko *temp = head;
head = tail = NULL;
free(temp);
}
else {
toko *temp = tail;
tail = tail->prev;
tail ->next = NULL;
free(temp);
}
}
void pushMid (char *name, int qty, int price){
if (!head) head = tail = createNode(name, qty, price);
else if (strcmp(name, head->name) < 0) pushHead(name, qty, price);
else if (strcmp(name, tail->name) > 0) pushTail(name, qty, price);
else {
toko *temp = createNode(name, qty, price);
toko *curr = head;
while (strcmp(name, curr->name) > 0){
curr = curr->next;
}
temp->next = curr;
temp->prev = curr->prev;
curr->prev->next = temp;
curr->prev = temp;
}
}
void popSearch(char *name){
if (!head) {
printf("No item found\n");
return;
}
else if (strcmp(head->name, name) == 0) popHead();
else if (strcmp(tail->name, name) == 0) popTail();
else {
toko *temp = head;
toko *curr;
while (strcmp(name, temp->name) < 0){
curr = temp;
temp = temp->next;
}
curr->next = temp->next;
temp->next->prev = curr;
free(temp);
}
}
int tot=0;
void printAll(){
toko *temp = head;
if(!head){
printf("No item found\n"); return;
}
else{
while (temp){
printf ("item name : %s, quantity : %d, price each : %d\n", temp->name, temp->qty, temp->price);
temp = temp->next;
}
}
}
void printCheckout(){
toko *temp = head;
if(!head){
printf("No item found\n"); return;
}
else{
while (temp){
printf ("item name : %s, quantity : %d, price each : %d\n", temp->name, temp->qty, temp->price);
tot += temp->price * temp->qty;
temp = temp->next;
}
}
}
int main(){
char name[100];
int qty, price;
printf("Input item name : ");
scanf ("%[^\n]", &name);
printf("Input item quantity : ");
scanf ("%d", &qty); getchar();
price = rand() % 1000;
pushMid(name, qty, price);
printf("Input success\n");
printf("press enter to continue...");getchar();
system("cls");
int x = 0;
do{
printf("1. add another item\n");
printf("2. edit item quantity\n");
printf("3. delete item\n");
printf("4. view\n");
printf("5. checkout\n");
int menu;
printf("Choose menu : ");
scanf("%d", &menu); getchar();
system("cls");
switch (menu){
case 1 :{
printf("Input item name : ");
scanf ("%[^\n]", &name);
printf("Input item quantity : ");
scanf ("%d", &qty); getchar();
price = rand() % 1000;
pushMid(name, qty, price);
printf("Input success\n");
printf("press enter to continue...");getchar();
system("cls");
break;
}
case 2 :{
printf("Input item name to change the quantity : ");
scanf("%[^\n]", &name);
printf("Change quantity to : ");
scanf("%d", &qty);getchar();
price = rand() % 1000;
popSearch(name);
pushMid(name, qty, price);
printf("Input change success\n");
printf("press enter to continue...");getchar();
system("cls");
break;
}
case 3 : {
printf("Input item name to delete : ");
scanf("%[^\n]", &name);
popSearch(name);
printf("Deletion success\n");getchar();
printf("press enter to continue...");getchar();
system("cls");
break;
}
case 4 : {
printAll();
printf("press enter to continue...");getchar();
system("cls");
break;
}
case 5 : {
printCheckout();
printf ("Your total price : %d\n", tot);
printf ("press enter to continue...");getchar();
printf ("kindness is free..");getchar();
return 0;
}
}
}while(x!=4);
return 0;
}
