Review Data Structure + Contoh Soal Double Linked List - Bahasa Indonesia

1. Pointer and Array
materi tentang pointer sebenarnya sudah didapatkan pada semester, namun konsep pointer ini ditekankan kembali. Mengapa ? Karena pada data structure ini pointer adalah konsep yang harus dikuasai terlebih dahulu. Semua alokasi memory yang dilakukan secara dinamis akan disimpan didalam bagian memory yang bernama heap. Untuk mengakses Heap kita harus menggunakan pointer.
Array pada semester ini akan jarang digunakan, array biasa dimunculkan untuk melakukan perbandingan dengan Linked List. Selain ini Array juga akan kita temukan pada implementasi Hash Table.

2. Linked List
Linked List adalah suatu bentuk struktur data dimana struktur daat ini bertipe linear, sama seperti Array. Lalu apa kelebihan Linked List dibandingkan Array ? Dengan menggunakan Linked List berarti kita dapat menambahkan data terus menerus secara dinamis (dalam batas memory), tidak seperti Array dimana ukuran haruslah fix di awal dan tidak bisa diubah lagi.

Pada Linked List kita biasa mengenal 2 tipe Linked List yaitu :
Single Linked List = mempunyai Link ke Node sesudahnya
Double Linked List = mempunyai Link ke Node sebelum dan sesudahnya'
Pada Single Linked List ini kita hanya membutuhkan 1 pointer sedangkan pada Double Linked List kita membutuhkan 2 pointer. Dengan menggunakan Double Linked List operasi kita akan berjalan lebih cepat.

Operasi pada Linked List antara lain :
1.Traversing = visiting data
2. Inserting = menambahkan data
3. Deleting = menghapus data
4. Searching = mencari data

3. Queue and Stack
Pertama-tama, Queue dan Stack adalah suatu konsep. Queue dan Stack pada penerapannya dapat diimplementasikan dengan Single atau Double Linked List.

Queue adalah konsep bertipe FIFO (First In First Out). Queue dapat dibayangkan seperti antrian, yang pertama mengatre akan keluar lebih cepat, begitu pula sebaliknya. Contoh penerapan Queue antara lain : Breadth First Search

Stack adalah konsep dengan tipe LIFO (Last In First Out). Stack biasa dianalogikan seperti tumpukan piring, yang ditumpuk paling atas akan diambil terlebih dahulu. Contoh penerapa Stack adalah Depth First Search.

4. Hash Table
Apa itu Hash Table ? Hash Table adalah struktur data yang dapat dibayangkan seperti tabel. Apa gunanya Hash Table ? Hash Table berguna untuk mempercepat pencarian data (searching). Penerapan hash Table adalah data yang kita miliki akan diletakkan pada posisi tertentu, biasanya dalam suatu array. Posisi yang akan ditempati ditentukan berdasarkan hash key yang dimiliki oleh data. Untuk mendapatkan hash key, kita perlu memproses data kedalam suatu fungsi yang menghasilkan hash key. Hash key inilah yang akan menjadi index suatu data.

5. Binary Search Tree
Binary Search Tree adalah implementasi dari Tree, khususnya Binary Tree. Yang membedakan Binary Search Tree and Binary Tree adalah pada BST semua left child memiliki nilai lebih kecil dibandingkan parent. Sedangkan right child memiliki nilai yang lebih besar dari parent. Hal ini dilakukan supaya kita dapat melakukan searching lebih cepat. Bagaimana searching dapat berlangsung lebih cepat ? Karena setiap kita mencari data, kita akan membandingkan data yang kita cari dengan data yang kita miliki, jika lebih kecil maka kita cari di left-sub-tree sedangkan jika lebih besar, kita akan mencari di right-sub-tree.

Operasi yang umum ada di BST :
Insert = menambah data
Search = mencari data
Delete = menghapus data -> perlu kita perhatikan apakah Node yang ingin kita hapus memiliki 1 anak, 2 anak, atau tidak punya anak sama sekali.

Dalam membuat BST kita akan banyak menggunakan rekursif. Jadi pastikan kita memperdalam teknik rekursif terlebih dahulu supaya tidak mengalam kesulitan.

Assingment Code :
Review Double Linked List
Case : Shop Case, kita dimampukan untuk membeli barang, mengedit jumlah barang, dan menghapus barang. Semua barang yang kita beli akan otomatis tersorting.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>


struct Node{
char kata[50] ;
int qty ;
int price ;
struct Node *prev, *next ;
}*head = NULL , *tail = NULL ;

int totalData = 0 ;


struct Node *createNewNode(char kata[], int qty){
struct Node *temp = (struct Node*)malloc(sizeof(struct Node)) ;
strcpy(temp->kata,kata) ;
temp->qty = qty ;
temp->price = (rand()%100)*1000 ;
temp->next = NULL ;
temp->prev = NULL ;
return temp ;
}


void pushData(char kata[], int qty){
struct Node *curr = createNewNode(kata,qty);
if(head == NULL){
head = tail = curr ;
}else if(strcmp(curr->kata, head->kata) < 0){
//pushHead
curr->next = head ;
head->prev = curr ;
head = curr ;
}else if(strcmp(curr->kata, tail->kata) > 0){
tail->next = curr ;
curr->prev = tail ;
tail = curr ;
}else{
struct Node *temp = head ;
while(strcmp(curr->kata,temp->kata) > 0){
temp = temp->next ;
}

curr->next = temp ;
curr->prev = temp->prev ;
temp->prev->next = curr ;
temp->prev = curr ;

}
}

void update(int id,int qty){
struct Node *temp = head ;
int count = 1 ;
while(count != id){
temp = temp->next ;
count++ ;
}

temp->qty = qty ;
temp->price = (rand()%100)*1000 ;
}

void deletee(int n){
int count = 1 ;
struct Node *temp = head ;

if(n == 1){
//popHead ;
if(head == tail){
head = NULL ;
free(temp) ;
}else{
head = head->next ;
head->prev = NULL ;
free(temp) ;
}
}else if(n == totalData && totalData != 1){
temp = tail ;
tail = tail->prev ;
tail->next = NULL ;
free(temp) ;
}else{
while(count != n-1){
temp = temp->next ;
count++ ;
}

struct Node *curr = temp->next ;
temp->next = curr->next ;
temp->next->prev = temp ;
free(curr) ;
}
totalData-- ;
}


void print(){
struct Node *temp = head; 
int count = 1; 

while(temp != NULL){
printf("%-3d | %-25s | %-3d | %-5d\n",count, temp->kata,temp->qty,temp->price) ;
temp = temp->next ;
count++ ;
}
printf("\n") ;
}

void buyItem(){
system("cls") ;
char kata[50] ;
int qty ;
printf("Input Product Name : ") ;
scanf("%[^\n]", kata) ; getchar() ;
printf("Input Product Qty : ") ;
scanf("%d", &qty) ; getchar() ;

pushData(kata,qty) ;
printf("Data has been added\n") ;
totalData++ ;
getchar() ;
}

void deleteItem(){
system("cls") ;
int id ;
print() ;
printf("Input Item Number to be deleted : ") ;
scanf("%d", &id) ; getchar()  ;
deletee(id) ;

printf("Item has been deleted\n") ; getchar() ;
}

void editItem(){
system("cls") ;
int id,q ;
print() ;
printf("Input Item Number to be updated : ") ;
scanf("%d", &id) ; getchar()  ;
printf("Input new quantity : ") ;
scanf("%d", &q) ; getchar() ;
update(id,q) ;
printf("Item has been updated\n") ; getchar() ;
}

void printBill(){
system("cls") ;
printf("BILL\n") ;
printf("======\n") ;
print() ;
printf("Total : -\n") ;
printf("Kindness is Free\n") ;
getchar() ;

struct Node *temp = head ;
while(temp != NULL){
struct Node *curr = temp ;
temp = temp->next ;
free(curr) ;
}

exit(0) ;


}



int main(){
srand(time(0)) ;

int c ;
do{
printf("Michael's Shop\n") ;
printf("=================\n") ;
print() ;
printf("1. Buy Item\n") ;
printf("2. Edit Item Qty\n") ;
printf("3. Delete Item\n") ;
printf("4. Print Bill\n") ;
printf("5. Exit\n") ;
printf("Choose >> ") ;

scanf("%d", &c) ; getchar() ;

switch(c){
case 1 : buyItem() ;
break ;
case 2 : editItem() ;
break ;
case 3 : deleteItem() ;
break ;
case 4 : printBill() ;
break ;
}
}while(c != 5) ;



return 0 ;
}