Apa itu
Linked List
Linked list adalah struktur
data yang terdiri dari urutan record data dimana setiap record memiliki field
yang menyimpan alamat/referensi dari record selanjutnya (dalam urutan).
Macam-
Macam Linked List yang akan dibahas kali ini:
1.Single Linked List
Single Linked List
merupakan suatu linked list yang hanya memiliki satu variabel pointer saja.
Dimana pointer tersebut menunjuk ke node selanjutnya. Biasanya field pada tail
menunjuk ke NULL. Berikut source code linked list;
struct data
{
int angka;
struct data *next;
}*head,*tail,*curr;
void pushdpn(int a){
curr = (struct data*) malloc(sizeof(struct data));
curr->angka = a;
if (head==NULL)
{
head=tail=curr;
tail->next=NULL;
}
else
{
curr->next=head;
head=curr;
}
}
void pushblkg(int a)
{
curr=(struct data*) malloc (sizeof(struct data));
curr->angka=a;
if (head==NULL)
{
head=tail=curr;
tail->next=NULL;
}
else
{
tail->next=curr;
tail=curr;
tail->next=NULL;
}
}
void pop(int a){
curr=head;
if (curr->angka==a)
{
if (head!=NULL)
{
curr=head;
head=head->next;
free(curr);
}
}
else
{
while (curr->next->angka!=a)
{
curr=curr->next;
}
struct data *temp;
temp=curr->next;
curr->next=temp->next;
free(temp);
}
}
void cetak()
{
curr=head;
while(curr!=NULL)
{
printf("%d ", curr->angka);
curr=curr->next;
}
}
int main (){
pushdpn(10);
pushblkg(100);
pushblkg(40);
pushdpn(200);
pop(100);
cetak();
return 0;
}
2. Circular Single Linked List
Merupakan suatu
linked list dimana tail(node terakhir) menunjuk ke head (node pertama). Jadi,
tidak ada pointer yang menunjuk ke NULL.
3. Circular
double Linked List
Hampir sama dengan Circular
Single Linked list, akan tetapi ada 2 pointer di setiap nodes.
4. Double Linked List
Merupakan suatu
linked list yang memiliki dua variabel pointer yang menunjuk ke node
selanjutnya dan pointer yang menunjuk ke node sebelumnya. Setiap head dan tail
juga menunjuk ke NULL.
Apa itu Hashing
Hashing adalah cara untuk
menyimpan data dimana data kita akan dibuat lebih singkat dengan menggunakan
key. Biasa nya data nya bisa disimpan dalam bentuk array.Ada beberapa jenis
hash function
a.
Mid-square
b. Divisi (paling umum)
c. Fold
d. Ekstraksi Digit
e. Rotasi Hash
Untuk collision adalah cara handle ketika hash key
kita sama sehingga tidak unik lagi, makanya kita butuh penanganan kejadian
seperti ini. Ada
2 jenis penanganan collision;
1.
Linear Probing
Pada saat terjadi collision, maka akan mencari posisi
yang kosong di bawah tempat terjadinya collision, jika masih penuh terus ke
bawah, hingga ketemu tempat yang kosong. Jika tidak ada tempat yang kosong
berarti HashTable sudah penuh
2. Chaining
Tambahkan key and entry di manapun dalam list (lebih
mudah dari depan)
Kerugian: Overhead pada memory tinggi jika
jumlah entry sedikit
Keunggulan dibandingkan open addressing:
- Proses
insert dan remove lebih sederhana
- Ukuran
Array bukan batasan (tetapi harus tetap meminimalisir collision: buat
ukuran tabel sesuai dengan jumlah key dan entry yang diharapkan)
Binary Tree
Binary Search
Tree adalah binary tree yang sudah di sort atau diurutkan
Bagian sub kiri tree mengandung element yang lebih kecil daripada yang
tersimpan di variabel x
Bagian sub kanan tree mengandung element yang lebih besar daripada yang
tersimpan di variabel x
3 operasi dalam binary tree search adalah
1. Find key(x)
Anggaplah kata
kunci nya adalah variabel x:
I. Kita mulai dari akar
II. Jika root berisi X maka pencarian berhasil
dihentikan.
III. Jika X kurang dari kunci root, maka cari secara
rekursif pada sub pohon kiri, jika tidak cari secara rekursif pada sub pohon
kanan.
2. Insert key (x) pakai metode rekursif
Anggaplah kata kunci nya
adalah variabel x:
I. Mulailah dari akar
II. Jika X kurang dari
kunci simpul maka masukkan X ke sub pohon kiri,
jika tidak masukkan X ke sub pohon kanan
III. Ulangi sampai kami
menemukan simpul kosong untuk meletakkan X (X akan selalu menjadi daun baru)
3. Remove key (x)
Ada 3 kasus yang harus dipertimbangkan:
I. Jika kunci
ada di daun, hapus saja simpul itu.
II. Jika kunci ada di
simpul yang memiliki satu anak, hapus simpul itu dan
sambungkan anaknya
ke induknya
III. Jika kunci ada di simpul yang memiliki dua
anak, temukan anak paling kanan dari sub pohon kirinya (simpul P), ganti
kuncinya dengan kunci P dan hapus P secara rekursif. (atau secara bergantian Anda dapat memilih anak paling kiri dari sub
pohon kanannya)
Soal coding AprilMarket with double linked list source code:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
struct data{
char nama[101];
int jumlah;
long long int harga;
struct data *next, *prev;
}*head=NULL,*tail=NULL,*curr=NULL;
void pushdpn(char namaI[],int jumlahI,long long int hargaI){
curr=(struct data*) malloc(sizeof(struct data));
strcpy(curr->nama,namaI);
curr->jumlah=jumlahI;
curr->harga=hargaI;
if (head==NULL)
{
head=tail=curr;
}
else
{
curr->next=head;
head->prev=curr;
head=curr;
}
tail->next=head->prev=NULL;
}
void pushblkg(char namaI[],int jumlahI,long long int hargaI){
curr=(struct data*) malloc(sizeof(struct data));
strcpy(curr->nama,namaI);
curr->jumlah=jumlahI;
curr->harga=hargaI;
if (head==NULL)
{
head=tail=NULL;
}
else
{
tail->next=curr;
curr->prev=tail;
tail=curr;
}
head->prev=tail->next=NULL;
}
void push(char namaI[],int jumlahI, long long int hargaI)
{
curr = (struct data*)malloc(sizeof(struct data));
strcpy(curr->nama,namaI);
curr->jumlah=jumlahI;
curr->harga=hargaI;
if (head==NULL)
{
head=tail=curr;
}
else if (strcmp(curr->nama,head->nama)<0)
{
pushdpn(namaI,jumlahI,hargaI);
}
else if (strcmp(curr->nama,tail->nama)>0)
{
pushblkg(namaI,jumlahI,hargaI);
}
else
{
struct data*temp;
temp=head;
while (strcmp(temp->next->nama,curr->nama)<0)
{
temp=temp->next;
}
curr->next = temp->next;
temp->next->prev=curr;
temp->next=curr;
curr->prev=temp;
}
}
void edit(char namaI[],int jumlahI, long long int hargaI)
{
struct data *search=head;
while (search!=NULL)
{
if (strcmp(search->nama,namaI)==0)
{
search->jumlah=jumlahI;
search->harga=hargaI;
break;
}
search=search->next;
}
}
void popdpn()
{
curr =head;
head=head->next;
free (curr);
head->prev=NULL;
}
void popblkg(){
curr=tail;
tail=tail->prev;
free(curr);
tail->next=NULL;
}
void pop(char namaI[]){
if(strcmp(head->nama,namaI)==0)
{
popdpn();
}
else if (strcmp(tail->nama,namaI)==0)
{
popblkg();
}
else
{
struct data *temp = head;
int val=0;
val = strcmp(temp->next->nama,namaI);
while(val!=0)
{
temp=temp->next;
}
curr=temp->next;
temp->next=curr->next;
curr->next->prev=temp;
free(curr);
}
}
void cetak(){
curr=head;
if (curr==NULL)
{
printf("No Data\n");
}
else
{
printf("| %-10s | %-3s | %-10s | %-10s |\n","Nama Barang", "Jumlah Barang", "Harga","Total");
printf("-----------------------------------------------------------------\n");
while(curr!=NULL)
{
long long int total=curr->jumlah*curr->harga;
printf("| %-11s | %-13d | %-10lld | %-10lld |\n",curr->nama,curr->jumlah,curr->harga,total);
curr=curr->next;
}
}
printf("-----------------------------------------------------------------\n");
printf("Grand Total= Kindness is Free\n") ;
puts("");
}
int n=0;
//opsi tampilan
void menu(){
printf("Welcome to Aprilmarket\n");
printf("------------------------\n");
printf("1. Add Item\n");
printf("2. Edit Item Quantity\n");
printf("3. Delete Item\n");
printf("4. Print the bill\n");
printf("5. Exit\n");
printf("Your choice: ");
scanf("%d",&n);getchar();
}
void add(){
char NamaInput[101];
int jumlah=0;
long long int harga=0;
printf("Masukkan nama barang: ");
scanf("%[^\n]",NamaInput); getchar();
puts("");
printf("Masukkan jumlah yang dibeli: ");
scanf("%d",&jumlah);
getchar();
harga=(rand()%100)*1000;
push(NamaInput,jumlah,harga);
printf("Barang berhasil ditambahkan!\n\n");
}
void ganti(){
char NamaInput[101];
int jumlah=0;
long long int harga=0;
printf("Masukkan nama barang yang diedit: ");
scanf("%[^\n]",NamaInput); getchar();
puts("");
printf("Masukkan jumlah barang yang diedit: ");
scanf("%d",&jumlah);
getchar();
harga=(rand()%100)*1000;
edit(NamaInput,jumlah,harga);
printf("Barang berhasil diedit!\n\n");
}
void buang(){
char NamaInput[101];
printf("Masukkan nama barang: ");
scanf("%[^\n]",NamaInput); getchar();
puts("");
pop(NamaInput);
printf("Barang berhasil dihapus!\n\n");
}
int main(){
srand(time(0));
do{
menu();
if (n==1)
{
add();
}
else if (n==2)
{
ganti();
}
else if (n==3)
{
buang();
}
else if (n==4)
{
cetak();
n=5;
}
}while(n!=5);
return 0;
}
Terjadi ketimpangan pada node 30, dimana node terdalam berada di cabang node 22 (cabang bengkok) , maka pertama tama diperlukan penarikan node 27 ke arah berlawanan. Lalu anak dari node 27, perlu penataan ulang dari atas.