perbedaan array dan linked list adalah
array
- kumupulan dari data
- menyimpan datanya di memory yang beruurtan
- bisa mengakses data mana saja secara langsung
linked list
- kumpulan dari node
- menyimpan node di memory yang secara acak
- hanya bisa diakses secara berurutan
array dan linked list memiliki kelebihan dan kekurangan tersendiri.
contohnya adalah
kelebihan array
- mudah digunakan
- lebih cepat megakses data mana saja
kekurangan array
- ukuran tidak dapat dirubah sehingga terkadang memakan banyak memory
kelebihan linked list
- penggunaan memory sesuai banyaknya data yang ada sehingga irit
- sistemnya fleksibel
kekurangan linked list
- pengerjaan lebih komples
linked list terdapat banyak macam, beberapa contohnya adalah
- circular linked list
- double linked list
circular linked list dalam permasalahan yang berhubungan dengan head dan tail memang lebih cepat diselesaikan dan juga ia bisa ke node manapun.
linked list cara kerjanya adalah dengan cara menyimpan alamat satu sama lain bukan dengan menyimpan isi dari alamat tersebut.
setiap alamat akan mempunyai hubungan dengan alamat berikutnya sehingga mereka akan saling menyambung
seperti di atas cara kerjanya data pertama jika di next maka dia akan ke data b karena setelah data a itu tersimpan alamat dari data b.head akan selalu ada pada data pertama sedangkan pada ujung akan bernama tail dan dia tidak akan menunjuk kemana-mana maka panak tersebut dituliskan NULL.
pada linked list biasa dia tidak bisa bergerak mundur maka ia akan selalu bergerak dari head ke tail.
seperti berikut adalah codingnya
coding di atas adalah untuk memasukan data kedalam linked list
sedangkan dibawah ini adalah cara menghapus data paling atas dari linked list
double hampir sama dengan linked list biasa namun bedanya dia bisa mundur
cara kerjanya seperti di bawah ini
Hashing
Hashing merupakan Teknik untuk menyimpan dan mengambil keys
dengan cara yang cepat.
Hashing menyimpan keysnya di array yang bernama hash table
dan menggunakan function yang sudah ditentukan yaitu hash function.
Hashing terdapat 5 jenis:
- Mid-square
- Division (paling sering digunakan)
- Folding
- Digit Extraction
- Rotating Hash
Mid
square caranya adalah dengan mempangkatkan angka yang ingin disimpan yang kemudian
akan diambil angka tengahnya.
Divison
caranya adalah dengan memodulus angka yang ingin disimpan dengan ukuran dari
size table yang diberikan/digunakan.
Folding
caranya adalah dengan membagi setiap angka menjadi 2 bagian yang kemudian akan
saling ditambahkan.
Digit
extraction caranya adalah mengambil digit pada letak-letak terntetu yang sudah
ditentukan sebelumnya dan angka tersebut kemudian akan menjadi hash addressnya.
Rotating
hash caranya adalah menggunakan mid-square atau division terlebih dahulu buat
dapet hash adressnya dan kemudian dibalik angkanya.
Hashing pada saat ini digunakan dalam blockchain, terutama
dalam cryptocurrency. Hashing sangatlah penting dalam pengaturannya. Hash bagaikan
backbone dalam cryptocurrency.
Hash membantu dalam menyimpan data yang sangat banyak dalam blockchain.
Collision
Collasion
terjadi ketika ada string yang memiliki hash key yang sama contohnya seperti
float dan floor dimana sama-sama berawalan f.
Collison
bisa diatasi dengan 2 cara:
- Linear probing
- Chaining
Linear probing adalah mencari tempat kosong selanjutnya dan menaruhnya
disana. Namun, cara ini sangatlah tidak efisien karena ketika string tersebut
ingin dicari looping yang dilakukan akan banyak.
Chaining adalah meletakkan string tersebut sebagai linked
list jadi apa bila floor terletak di hash key 5 maka ia linked list ke float
jadi tidak membuang-buang waktu untuk mencarinya.
Tree
Tree merupakan struktur yang menunjukan hirarki antar non-linear
data.
Node dalam tree tidak perlu disimpan secara berurut, ia
dapat disimpan secara asal dan kemudian dihubungkan dengan pointer.
Konsep tree
- Node yang paling diatas disebut root.
- Line yang menghubungankan antara parent dan child disebut edge.
- Node yang tidak memiliki children disebut leaf.
- Node yang memiliki parent yang sama disebut sibling.
- Degree of node mereupakan jumlah dari sub tree sebuah node.
- Height/Depth merupakan maksimum degree dalam sebuah tree.
- Jika ada line yang menghubungkan antara p dan q, maka p disebut ancestor dari q, dan q adalah descendant dari p.
Binary tree
Konsep binary tree
- Binary tree merupakan struktur data tree dimana setiap node maksimal memiliki 2 node.
- Setiap 2 children tersebut biasanya dibedakan sebagai left child atau right child.
- Node yang tidak memiliki children disebut leaf.
Tipe binary tree
- Perfect binary tree
- Complete binary tree
- Skewed binary tree
- Balanced binary tree
Perfect binary tree adalah dimana setiap level mempunyai
height/depth yang sama.
Complete binary tree adalah binary tree yang setiap
levelnya, kecuali yang terakhir terisi penuh dan semua node dipenuhkan pada
sisi kiri tree. Semua perfect binary tree merupakan complete binary tree.
Skewed binary tree merupakan tree yang setiap nodenya
maksimal memiliki 1 child.
Balanced binary tree merupakan tree dimana leaf yang satu
tidak boleh lebih jauh levelnya dari leaf yang lain jadi harus seimbang.
Berikut adalah codingan untuk menu sebuah supermarket dengan double linked list
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>
struct data{
char nama[100];
int harga;
int qty;
struct data *next;
struct data *prev;
}*head, *tail;
void push(char vnama[100], int vqty, int vharga){
struct data *node = (struct data*)malloc(sizeof(struct data));
strcpy(node->nama, vnama);
node->qty = vqty;
node->harga = vharga;
node->next = node->prev = NULL;
if(head == NULL){
head = tail = node;
}else if(strcmp(head->nama, vnama)>0){
node->next = head;
head->prev = node;
head = node;
}else if(strcmp(tail->nama, vnama)<0){
node->prev = tail;
tail->next = node;
tail = node;
}else{
struct data *curr = head;
while(strcmp(curr->next->nama, vnama)<0){
curr = curr->next;
}
curr->next->prev = node;
node->next = curr->next;
curr->next = node;
node->prev = curr;
}
}
void pop(char vnama[100]){
if(head != NULL){
if(head==tail && strcmp(head->nama,vnama)==0){
free(head);
head =tail = NULL;
}else if(strcmp(head->nama,vnama)==0){
head = head->next;
free(head->prev);
head->prev = NULL;
}else if(strcmp(tail->nama,vnama)==0){
tail = tail->prev;
free(tail->next);
tail->next = NULL;
}else{
data *node = head->next;
while(node!=tail && strcmp(node->nama, vnama)!=0){
node = node->next;
}
if(strcmp(node->nama, vnama)==0){
node->prev->next = node->next;
node->next->prev = node->prev;
free(node);
node = NULL;
}else{
printf("There is no data\n");
}
}
}else{
printf("There is no data\n");
}
}
void popall(){
while(head!=NULL){
if(head==tail){
free(head);
head =tail = NULL;
}else{
data *curr=head;
head=head->next;
free(curr);
}
}
}
void edit(char vnama[100], int vqty){
if(head != NULL){
data *node = head;
while(node!=NULL && strcmp(node->nama, vnama)!=0){
node = node->next;
}
if(strcmp(node->nama, vnama)==0){
node->qty = vqty;
}else{
printf("There is no data\n");
}
}else{
printf("There is no data\n");
}
}
void viewALL(){
int total=0;
if(head==NULL){
printf("No Items to Checkout\n");
}else{
data *node = head;
while(node!=NULL){
printf("%-15s %-3d Rp.%-5d Rp.%d\n", node->nama, node->qty, node->harga, node->qty*node->harga);
total+=node->qty*node->harga;
node = node->next;
}
printf ("\nHere is Your Total Rp.%d\n", total);
}
}
void viewcart(){
if(head==NULL){
printf("\n");
}else{
data *node = head;
while(node!=NULL){
printf("%-15s %-3d\n", node->nama, node->qty);
node = node->next;
}
}
}
int main(){
int menu;
char nama[100];
int qty, co;
int harga;
srand(time(0));
do{
printf("\nDREAMMERS MARKET\n");
printf("^^^^^^^^^^^^^^^^\n");
printf("\nCart:\n");
viewcart();
printf("\nMenu :\n");
printf("1. Add goods\n");
printf("2. Change qty\n");
printf("3. Delete goods\n");
printf("4. Checkout\n");
printf(">> Input choice : ");
scanf("%d", &menu);getchar();
printf("\n");
switch(menu){
case 1:
printf("Masukan Nama Barang: ");
scanf("%[^\n]", &nama);
printf("Masukan Qty[1-100]: ");
scanf("%d", &qty);
harga = (rand()%100)*1000;
push(nama,qty,harga);
printf("--- Add goods Success ---\n");
break;
case 2:
printf("Masukkan nama barang(pastikan namanya sama saat input): ");
scanf("%[^\n]", &nama);
printf("Masukan Qty[1-100]: ");
scanf("%d", &qty);
edit(nama,qty);
printf("--- Change goods qty Success ---\n");
break;
case 3:
printf("Masukkan nama barang(pastikan namanya sama saat input): ");
scanf("%[^\n]", &nama);
pop(nama);
printf("--- Delete goods Success ---\n");
break;
case 4:
printf("Here is your bill\n\n");
viewALL();
printf("\nDo you wish to pay?\n");
printf("1. Yes\n2. No\n");
printf(">> Input choice : ");
scanf("%d", &co);
if(co == 1){
printf("Kindness is free\n");
popall();
break;
}else{
printf("It's okay kindness is free\n");
popall();
break;
}
}
}while(menu!=4);
}
