Single Linked List

Linked list merupakan kumpulan data yang disambungkan satu sama lain. Setiap alamat dari data yang terdapat di linked list merupakan alamat random yang telah dipesan melalui fungsi  malloc, sehingga tidak seperti array yang alamat dari setiap indeksnya bersebelahan.

Single Linked List meruapakan linked list yang setiap nodenya memegang alamat dari node selanjutnya. Dalam linked list ini terdapat push head, mid, dan tail, begitu juga dengan pop head, tail, dan search. Linked list ini memang menggunakan memori yang lebih sedikit karena hanya menggunakan satu pointer, akan tetapi banyak proses pengolahan pada single linked list yang menggunakan looping sehingga akan memakan lebih banyak waktu.






Circular Single Linked List

yaitu linked list yang setiap nodenya memegang alamat dari node selanjutnya tanpa terkecuali, node terakhir yang memegang node "head". Dalam circular single linked list, tidak ada node yang tidak memegang alamat dari node lain. Bila tidak terdapat node lain atau hanya terdapat head, maka node "head" itu sendiri akan memegang alamat dari head itu sendiri.





Pada linked list ini, kita dapat memasukkan data dari depan, belakang, maupun menyelipkannya di tengah. Hal-hal yang harus diperhatikan dalam melakukan ini yaitu mengecek apabila sudah terdapat node atau belum, serta dimana  kita harus menaruh node baru agar isi dari node tersebut terurut.
Dalam circular linked list, perlu diperhatikan juga jumlah node yang ada, karena node ini bersifat looping yang semua nodenya memegang alamat dari node lain. Jumah node yang ada digunakan untuk melakukan searching data, menampilan data, dll.

Double Linked  List

yaitu linked list yang setiap nodenya memegang alamat dari node setelahnya dan node sebelumnya, maka dari itu konsep linked list  ini menggunakan 2 pointer pada setiap nodenya. Pada linked list ini  terdapat head dan juga tail, head akan memegang hanya node selanjutnya, sedangkan tail akan memegang hanya node sebelumnya.sehingga prev milik head dan next milik tail akan di nullkan sebagai penanda awal dan akhir dari data.







Linked list ini memiliki berbagai cara  untuk memasukkan data, yaitu push depan, push belakang, dan push tengah. Penghapusan data pada linked list ini pun juga sama, pop depan, pop belakang, dan pop tengah. Proses push dan pop tengah akan menggunakan head sebagai comparison awal dan akan berhenti bila ketentuan memasukkan data sudah terpenuhi. Dalam linked list ini, kita harus memperhatikan next dan prev dari setiap node yang akan diproses, karena bisa saja kita lupa untuk mengganti next dari suatu node dan node tersebut menunjuk node yang salah ataupun sudah di free.

Circular Double Linked List

yaitu linked list yang mirip dengan double linked list akan tetapi prev milik head menunjuk tail dan next milik tail menunjuk head. Cara memasukkan data sama namun indikator yang dipakai yaitu dengan jumlah node yang ada seperti circular single linked list.






Sekian penjelasan dari saya mengenai circular single linked list, double linked list, dan  circular double linked list. Diharapkan blog ini dapat membantu kawan-kawan semua.

Hash Table

Hash table merupakan jenis struktur data yang sering digunakan untuk mengenkripsi data. Hashing dapat dilakukan dengan mengambil key dari data yang sudah ada lalu dimasukkan ke rumus yang ditentukan untuk disimpan pada blok data dari hash key yang dihasilkan. Hal ini membuat penyimpanan data menjadi lebih aman.

Di dalam sebuah hash table, bila terdapat dua data yang memiliki hash key sama atau terjadi collision, maka dapat dilakukan dua cara, yaitu separate chaining dan open addressing. Separate chaining berarti alamat data baru akan di simpan di samping data lama yang memiliki hash key sama dan akan membuat rantai ke samping. Open addresssing berarti data baru dengan hashkey sama akan mencari posisi lain yang kosong dimulai dari posisi data lama dengan hash key yang sama.

Berikut merupakan contoh source code dari hash table:

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

struct Node{
char name[100];
char age[100];
char key[205];
char nim[100];
Node *next;
};

Node *tableHead[100], *tableTail[100];

int hashFunction(char key[205]){
int len = strlen(key);
int total = 0;
for(int i=0;i<len;i++){
total += key[i]*i;
total %= 100;
}
return total;
}

Node *createNode(char name[100], char age[100]){
Node *temp = (Node *)malloc(sizeof(Node));
strcpy(temp->name, name);
strcpy(temp->age, age);
strcpy(temp->nim, "1");
sprintf(temp->key, "%s%s", temp->name, temp->age);
temp->next = NULL;
return temp;
}

void pushTail(int hashIndex, Node *newNode){
if(tableHead[hashIndex] == NULL){
tableHead[hashIndex] = tableTail[hashIndex] = newNode;
}else{
tableTail[hashIndex]->next = newNode;
tableTail[hashIndex] = newNode;
}
}

void insert(Node *newNode){
int hashIndex = hashFunction(newNode->key);
pushTail(hashIndex, newNode);
}

void showAll(){
for(int i=0;i<100;i++){
printf("Index %d: ", i);
Node *curr = tableHead[i];
while(curr){
printf("[Key: %s -- Name: %s -- Age: %s -- NIM: %s] -> ", curr->key, curr->name, curr->age, curr->nim);
curr = curr->next;
}
printf("\n");
}
}

int main(){
insert(createNode("Alpha","20"));
insert(createNode("Alpha","30"));
insert(createNode("Charlie","15"));
insert(createNode("Delta","10"));
insert(createNode("Echo","99"));
insert(createNode("Fanta","80"));
showAll();
return 0;
}

Binary Search Tree

Binary search tree, seperti namanya merupakan sebuah pohon yang menyimpan data, dimana dta tersebut akan tersortir meskipun data yang dimasukkan tidak teratur. Sebuah binary search tree memiliki root dan cabang left serta right pada setiap nodenya.



















Berikut merupakan contoh source code dari binary search tree:

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

struct Stuff{
int code;
char name[100];
Stuff *left, *right;
} *root;

Stuff *newNode(int code, char name[100]){
Stuff *node = (Stuff*)malloc(sizeof(Stuff));
node->code = code;
strcpy(node->name, name);
node->left = node->right = NULL;
return node;
}

Stuff *insert(Stuff *root, int code, char name[100]){
if(root == NULL)
return newNode(code, name);
else if(root->code > code)
root->left = insert(root->left, code, name);
else
root->right = insert(root->right, code, name);
return root;
}

Stuff *remove(Stuff *root, int code){
if(root == NULL)
return root;
else if(root->code > code)
root->left = remove(root->left, code);
else if(root->code < code)
root->right = remove(root->right, code);
else{
//kalo dia punya 1 anak atau ga punya anak
if(root->left == NULL || root->right == NULL){
Stuff *temp = root->left != NULL?
 root->left : root->right;
//kalo punya 1 anak
if(temp != NULL){
*root = *temp;
}
//kalo tidak punya anak
else{
temp = root;
root = NULL;
}
free(temp);
}
//kalo dia punya 2 anak
else{
Stuff *temp = root->left;
while(temp->right != NULL)
temp = temp->right;
root->code = temp->code;
strcpy(root->name, temp->name);
root->left = remove(root->left, temp->code);
}
return root;
}
}

Stuff *update(Stuff *root, int code, char name[100]){
if(root == NULL)
return root;
else if(root->code > code)
root->left = remove(root->left, code);
else if(root->code < code)
root->right = remove(root->right, code);
else
strcpy(root->name, name);
return root;
}

Stuff *removeAll(Stuff *root){
if(root != NULL){
removeAll(root->left);
removeAll(root->right);
free(root);
}
return NULL;
}

void inOrder(Stuff *root){
if(root != NULL){
inOrder(root->left);
printf("%d %s\n", root->code, root->name);
inOrder(root->right);
}

}

int main(){
root = insert(root, 5, "Hammer");
root = insert(root, 3, "Guitar");
root = insert(root, 10, "Harmonica");
root = insert(root, 2, "Card");
root = insert(root, 1, "Cars");
root = insert(root, 4, "Piano");
inOrder(root);
printf("\n");
root = removeAll(root);
inOrder(root);
return 0;
}

Comments

Post a Comment