Data Structure Linked List: April 2020

Summary

Linked List

Adalah bentuk implementasi dari struktur data yang paling sederhana. Seperti yang dijelaskan sebelumnya dalam konsep struktur data. Terdapat beberapa jenis Linked List

Single Linked List

Circular Single Linked List

Doubly Linked List

Circular Double Linked List

Salah satu keuntungan dari Linked List dibandingkan dengan Array adalah size dari Linked List akan bertambah hanya ketika kita membutuhkan slot tersebut, berbeda dengan array yang mereserve tempat, kemudian tempat tersebut akan menjadi terhambur jika tidak terpakai.

Dalam pembelajaran struktur data, kita akan lebih sering mengenal dengan istilah :

Push untuk menambah data.

PushHead – Menambah data ke barisan paling awal

PushTail – Menambah data ke barisan paling akhir

PushMid – Menambah data ke barisan di tengah (sorting)

Pop untuk menghapus data.

PopHead – Menghapus data paling awal

PopTail – Menghapus data paling akhir

PopMid – Menghapus data ditengah (sesuai parameter value)

- Single Linked List dan Circular Single Linked List

Tahapan awal dalam pembuatan Single Linked List dan Circular Single Linked List :

Contoh linked list yang memasukkan nilai dari sebuah integer

Pembuatan Node dan PushHead

Fungsi next adalah sebagai penghubung antara satu data dengan data yang lain.

head dan *tail sebagai penanda awal dan akhir sebuah data struktur.

IF pertama pada pushHead adalah kondisi ketika belum ada data dalam data struktur, maka diinisialisasikan pembuatan Node dengan head sama dengan tail.

ELSE menandakan adanya penempatan data baru disebelah head(data lama) kemudian data yang baru menjadi head baru.

PopHead dan Penggunaan fungsi push dan pop pada main

Untuk Pop sendiri, (dalam kasus ini Pop Head), data temp diset pada head, jika tidak ada data, maka tidak ada yang perlu dihapus, jika data hanya satu (pada kondisi 2) head sama tail bisa di NULL kan, kemudian free(fungsi untuk melepaskan memory yang tidak terpakai lagi) data temp.

Untuk kondisi terakhir, head harus dipindahkan ke data selanjutnya (diamankan), kemudian baru free data temp.

Untuk Circular, tambahkan satu fungsi yang menghubungkan data awal dan terakhir, kemudian dipanggil terakhir dalam main.

- Double Linked List dan Circular Double Linked List

Single Linked List dan Double Linked List mempunyai struktur yang hampir sama, perbedaannya hanyalah dalam penambahan pointer prev, yang bertujuan untuk menghubungkan satu data dengan data sebelumnya.

Pointer yang dibutuhkan pada Linked List

1. Pointer Awal (*head)

Pointer Awal ini berfungsi untuk menunjuk kepada data yang terakhir kali dimasukkan dalam suatu Linked List, untuk penamaan secara umum menggunakan nama head (untuk memudahkan).

Pointer Awal ini dapat digunakan untuk mengecek kondisi apakah suatu Linked List sudah terisi atau belum, sebagai pacuan dalam PushHead, PopHead.

2. Pointer Akhir (*tail)

Pointer Akhir ini berfungsi untuk menunjuk kepada data yang pertama kali dimasukkan dalam suatu Linked List, untuk penamaan secara umum menggunakan nama tail.

Pointer Akhir ini dapat digunakan untuk mengecek apakah suatu Linked List sudah terisi atau belum, dapat juga digunakan sebagai pacuan dalam PushTail, PopHead, juga dapat menandakan bahwa data yang ditunjuk merupakan data yang terakhir.

3. Pointer untuk Menunjuk Data Lainnya (*next, *prev(optional))

Pointer ini memiliki fungsi yang sangat krusial, yaitu untuk menunjuk data selajutnya, bila tidak ada pointer ini, data dalam Linked List tidak dapat saling terhubung

Hash Table

Hashing adalah sebuah cara dalam memproses data (biasanya yang diproses adalah sebuah variabel "kunci" atau sebuah string) ke dalam suatu array. hal ini bertujuan untuk mempermudah dalam menyimpan atau mencari data. Biasanya, hasil hashing yang terlalu besar, akan dimodulo dengan ukuran maksimum dari Array tersebut agar tidak terjadi Index Out of Bound

Contoh Hashing data pada gambar adalah dengan me-modulus 10 dari setiap data yang ada, kemudian dimasukkan ke dalam Array yang sama dengan hasil modulusnya.

Contoh Contoh Hashing :

1. Mid Square

Ciri khas dari hashing ini adalah, data "kunci" (bisa berupa char ataupun integer. Jika char diambil ASCII), dipangkatkan, kemudian dicari angka bagian tengah dari hasil pangkat tersebut.

Misal : key = 75, arrayMax = 35;

hasil pangkat = 5'62'5

hasil hash = 62 % 35 = 27;

Data akan dimasukkan ke index ke 27

2. Division

Menjumlahkan semua string yang ada pada data "kunci", kemudian dimodulo kan dengan angka tertentu. Angka yang memodulo bebas, tetapi harus konsisten untuk tiap kali Hashing.

Contoh : "HELLO" -> 72(H) + 69(E) + 76(L) + 76(L) + 79(O) = 372 % 35 = 22;

3. Folding

Menjumlahkan semua string ang ada pada data "kunci", kemudian hasil jumlah itu dipecah menjadi beberapa angka, kemudian dijumlah lagi.

Contoh : "HELLO" -> 72(H) + 69(E) + 76(L) + 76(L) + 79(O) = 372

Folding -> 37 + 2 (dipecah menjadi per angka puluhan)

-> 39;

4. Digit Extraction

Mengambil beberapa bagian dari data kunci, dijadikan menjadi data Hash

Misal : key = 52635;

Yang diambil misalkan hanya angka ke-1, 3 dan 5

hasil Hash = 565;

5.Rotate Hash

Memutar data kunci, menjadi hasil hash baru

Misal : key = 52635;

Hash -> 53625;

Hasil dari Hashing tidak mungkin selalu berbeda antara satu data dengan yang lain.

Misalkan jika penggunaan Hashing dengan modulo 10.

Data 25 dan Data 35 akan memiliki hasil modulo yang sama.

Hal seperti ini yang disebut dengan Collision (tabrakan)

Ada 2 cara untuk mengatasi Collision:

a. Linear Probling

Menambahkan index pada data yang tertabrak.

Misalkan Hashing berdasarkan index pertama suatu data.

Data "Anak" dan "Aku" akan memiliki hasil Hashing yang sama

(65 bila berdasarkan ASCII)

maka data "Aku" yang bertabrakan dapat dimasukkan dalam index ke 66.

Hal ini dilakukan sampai menemukan Table baru yang kosong

b. Chaining

Jika Linear Probling dilakukan dengan menambakan index pada data yang bertabrakan.

Chaining dilakukan dengan menambakan Dynamic Array pada setiap Hash Table. Jadi ketika data pertama masuk. Data tersebut akan menjadi Head dalam satu row tersebut. Ketika ada data lain yang masuk index yang sama, data itu akan digeser menjadi next. Begitu pula seterusnya, penjelasannya dapat dilihat dalam gambar

Binary Tree

Binary Tree adalah tipe data struktur yang bentuknya seperti pohon, dimana ada satu data yang menjadi Root. Berbeda dengan data structure biasa yang menggunakan Head sebagai data pacuan. Binary Tree menggunakan data root sebagai data pacuannya.

Disebut sebagai Binary Tree karena data structure ini memiliki dua cabang, yaitu left dan right. Dalam memasukkan data dalam binary tree, biasanya, data yang memiliki value lebih kecil dari root, akan diletakkan di cabang kiri, sedangkan data yang memiliki value lebih besar dari root akan diletakkan di cabang kanan.

Contoh Binary Tree

Binary Search Tree

Binary Search Tree atau BST adalah salah satu Data Structure yang memiliki atribut yang sama dengan Binary Tree, namun memiliki susunan data yang lebih terstruktur, data yang masuk otomatis telah dimasukkan secara teratur, sebagai contoh:

Apabila ada data yang masuk dengan nilai lebih kecil daripada nilai root, maka data akan diletakkan dicabang kiri, jika ada data yang masuk lebih besar daripada nilai root, data akan diletakkan di sebelah kanan.

Ciri ciri Binary Search Tree:

Cabang bagian kiri memiliki nilai lebih kecil daripada root
Cabang bagian kanan memiliki nilai lebih besar daripada root
Setiap cabang hanya dapat memiliki 2 anak

Search

Search dalam BST pastinya lebih cepat terproses dibandingkan dengan Binary Tree biasa, untuk BST sehat, memiliki kompleksitas O (log n). Untuk algoritmanya, biasanya berdasarkan dengan nilai data. Apabila data yang dicari lebih kecil daripada root, maka root sekarang menjadi anak kiri dari root, begitu juga sebaliknya. ketika datanya ternyata sudah habis atau sudah ketemu, maka program search selesai,

Insert

Untuk insert seharusnya mirip dengan algoritma search, Insert diawali dengan root, kemudian dicek datanya, apakah lebih besar atau lebih kecil dari root, jika lebih kecil, root sekarang menjadi

root->left, hal ini terus dilakukan sampai didapatkan cabang yang masih kosong (null). Begitu juga sebaliknya.

Deletion

Mirip seperti insert, root, kemudian dicek datanya, apakah lebih besar atau lebih kecil dari root, jika lebih kecil, root sekarang menjadi root->left, program selesai apabila datanya ditemukan ataupun menemukan cabang null.

Code untuk Dreammers Market:

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

struct items{
char name[105];
int qty;
int price;
items *next, *prev;
} *head, *tail;

items* createNode (char *name, int qty, int price){
items *temp = (items*)malloc(sizeof(items));
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 {
items *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 {
items *temp = createNode(name, qty, price);
temp->prev = tail;
tail->next = temp;
tail = 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 {
items *temp = createNode(name, qty, price);
items *curr = head;
while (curr && strcmp(name, curr->name) > 0){
curr = curr->next;
}

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

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

void popHead(){
if (!head){
printf ("No data");
return;
} if (head == tail){
items *temp = head;
head = tail = NULL;
free (temp);
} else {
items *temp = head;
head = head->next;
head->prev = NULL;
free(temp);
}
}

void popTail(){
if (!head){
printf ("No data");
return;
} if (head == tail){
items *temp = head;
head = tail = NULL;
free(temp);
} else {
items *temp = tail;
tail = tail->prev;
tail->next = NULL;
free(temp);
}
}

void popSearch(char *name){
if (!head){
printf ("No data");
return;
}
if (strcmp(head->name, name) == 0){
printf ("Successfully delete %s from list\n", head->name);
popHead();
}
else if (strcmp(tail->name, name) == 0){
printf ("Successfully delete %s from list\n", tail->name);
popTail();
}
else {
items *temp = head;
items *curr = temp;
while (temp && strcmp(name, temp->name) != 0){
curr = temp;
temp = temp->next;
}

if (!temp){
printf ("No data");
return;
}

printf ("Successfully delete %s from list\n", temp->name);
curr->next = temp->next;
temp->next->prev = curr;
free(temp);
}
}

void view(){
if (!head){
printf ("No data");
} else {
items *temp = head;
int i = 1;
long long int total = 0;
char space[10];
strcpy(space, " ");
printf ("No Name Qty Price Total\n");
while (temp){
long long int tempTotal = temp->price * temp->qty;
printf ("%2d %-30s%3d @Rp. %5d Rp. %7lld\n", i, temp->name, temp->qty, temp->price, tempTotal);
total += tempTotal;
temp = temp->next;
i++;
}
printf (" Total : %-40s Rp. %7lld\n", space, total);
puts("");
puts("");
}
}

void changeQty (){
if (!head){
printf ("No data\n");
return;
}
else {
printf ("Change Quantity\n");
view();
char name[100];
int len;
do {
printf ("Input item's name [3..100]: ");
scanf ("%[^\n]", name);
getchar();
len = strlen(name);
} while (len < 3 || len > 100);

items *temp = head;
while (temp && strcmp(name, temp->name) != 0){
temp = temp->next;
}

if (!temp){
printf ("No data\n");
return;
}

int qty;
do {
printf ("Item's quantity : ");
scanf ("%d", &qty);
getchar();
if (temp->qty == qty){
printf ("Type another value, this value is same is before\n");
}
} while (temp->qty == qty);

printf ("Successfully change quantity from %d to %d\n", temp->qty, qty);
temp->qty = qty;
}
}

void input(){
char name[105];
int qty;
printf ("Add item\n");

items *temp;
int len;
do {
do {
printf ("Input item's name [3..30]: ");
scanf ("%[^\n]", name);
getchar();
len = strlen(name);
} while (len < 3 || len > 30);

temp = head;
while (temp && strcmp(temp->name, name) != 0){
temp = temp->next;
}

if (temp){
printf ("Name already been included");
getchar();
continue;
}

do {
printf ("Input item's quantity [1..100]: ");
scanf ("%d", &qty);
getchar();
} while (qty < 1 || qty > 100);

} while (temp);
int price;
price = rand() % 50 + 1;
price *= 100;
pushMid(name, qty, price);
}

void deleteItems(){
char name[100];
int len;
view();
do {
printf ("Input item's name [3..30]: ");
scanf ("%[^\n]", name);
getchar();
len = strlen(name);
} while (len < 3 || len > 30);
printf ("Delete Items\n");
popSearch(name);
}

void checkOut(){
if (!head){
printf ("You haven't buy any item, please buy at least one item");
return;
}
else {
printf ("Checkout\n");
view();
printf (" Kindness is Free\n");
puts("");
puts("");
char confirm[100];
do {
printf ("Do you want to checkout all of your items?[Yes | No] : ");
scanf ("%[^\n]", confirm);
getchar();
} while (strcmp(confirm, "Yes") != 0 && strcmp(confirm, "No") != 0);

if (strcmp(confirm, "Yes") == 0){
while (head){
popHead();
}
printf ("All items has been checkout\n");
getchar();
}
}
}

int main(){
srand(time(NULL));
int menu;
do {
system("cls");
printf ("Dreammers Market\n");
printf ("================================\n");
printf (" 1. Input Items\n");
printf (" 2. Update Quantity\n");
printf (" 3. Delete Items\n");
printf (" 4. Check Out\n");
printf (" 5. Exit\n");
printf ("Choose >> ");
scanf ("%d", &menu);
getchar();
system("cls");
switch(menu){
case 1:
input();
printf ("Successfully add item");
getchar();
break;
case 2:
changeQty();
getchar();
break;
case 3:
deleteItems();
getchar();
break;
case 4:
if (!head) menu = 0;
checkOut();
break;
case 5:
printf ("Thank you for using this Application");
break;
default:
break;
}
} while (menu != 5);
}

References

https://www.mahirkoding.com/struktur-data-single-linked-list-dengan-bahasa-c/

https://www.geeksforgeeks.org/binary-search-tree-set-2-delete/

https://www.geeksforgeeks.org/binary-search-tree-set-1-search-and-insertion/

Data Structure Linked List

Monday, April 27, 2020

AVL

Monday, April 6, 2020

Summary Data Structure

Binary Search Tree

Search

Insert

Deletion