Rangkuman Akhir

Nama : Immanuel Joseph

NIM   : 230185221

Nama Dosen : Bpk Alexander

Circular Single Linked List

Circular Single Linked List pada dasarnya adalah Single Linked List yang pointer Tail (pointer terakhir) dari linked list tersebut selalu menunjuk ke Head (pointer pertama) dari linked list itu sendiri. Sehingga kalau digambarkan / dibayangkan, linked list tersebut membentuk sebuah loop karena itulah linked list tersebut dinamakan Circular. Berbeda dari Single Linked List, Circular Single Linked List pada praktiknya tidak akan memiliki pointer yang menyimpan nilai NULL, karena semuanya saling terkoneksi membentuk loop.

    Sebagai gambaran, mari perhatikan ilustrasi berikut.

Circular Single Linked List

Double Linked List

Double Linked List memiliki konsep yang sama dengan Single Linked List, yang membedakan adalah jumlah pointernya. Pada Single Linked List, setiap pointer hanya memiliki satu pointer didalamnya untuk menyimpan alamat dari record selanjutnya. Sementara pada Double Linked List, setiap pointer punya dua pointer didalamnya yang berfungsi untuk menyimpan alamat dari record sebelumnya dan alamat dari record selanjutnya. 

Contoh codingan :

struct mahasiswa{

char nama[100];
int no_urut;
mahasiswa *next, *prev;

}*head, *tail;

Seperti yang sudah saya jelaskan sebelumnya, pada codingan Double Linked List, terdapat dua pointer berupa next dan prev. Sementara, pada codingan Single Linked List, pasti hanya memiliki satu pointer berupa next.

Double Linked List : Insert

Pada proses Insert, sebenarnya ada 3 cara. yaitu,

• Push Head, apabila data baru yang akan dimasukkan ke dalam linked list ingin diletakkan ke bagian paling depan.
• Push Tail, apabila data baru yang akan dimasukkan ke dalam linked list ingin diletakkan ke bagian paling belakang.
• Push Mid, apabila data baru yang akan dimasukkan ke dalam linked list ingin diletakkan di tengah-tengah linked list (tengah-tengah di sini relatif, pokoknya berada di antara head dan tail). Umumnya, Push Mid paling sering digunakan karena dapat memasukkan data sesuai urutan / sorted.

Namun, di sini saya hanya akan memberikan contoh salah satunya, yaitu Push Head karena pada dasarnya Push Tail dan Push Mid tidak berbeda jauh logikanya.

Contoh codingan Push Head :

char name[100] = "Immanuel";
int no_urut = 10; 

mahasiswa *node = (node*) malloc(sizeof (node));
strcpy(node->name,name);
no_urut->node = no_urut;
node->prev = NULL; 

node->next = head;
head->prev = node;
head = node;

Double Linked List : Delete

Seperti Insert, Delete juga memiliki beberapa kondisi dalam prosesnya, berikut kondisinya

1. Jika hanya ada satu data di dalam linked list
2. Jika data yang ingin di hapus terletak di Head
3. Jika data yang ingin di hapus terletak di Tail
4. Jika data yang ingin di hapus terletak di antara Head dan Tail atau dalam istilah sebelumnya, Mid

Mari kita bahas satu persatu, contoh codingannya,

Untuk kondisi Pertama :

head = tail = NULL;
free(head);

 Untuk kondisi Kedua :

mahasiswa *temp = head;
head = head->next;
head->prev = temp->next = temp->prev = NULL; 

free(temp);

Untuk kondisi Ketiga :

mahasiswa *temp = tail;
tail = tail->prev;
tail->next = temp->next = temp->prev = NULL; 

free(temp);

Untuk kondisi Keempat :
anggap x adalah no_urut data yang ingin di hapus.

mahasiswa *temp = head; 

while(temp!=NULL){
    if(temp->no_urut == x) break;
    temp = temp->next;
} 

temp->prev->next = temp->next;
temp->next->prev = temp->prev;
temp->next = temp->prev = NULL; 

free(temp);

Circular Double Linked List

Di atas sudah saya jelaskan bahwa perbedaan Circular Single Linked List dengan Single Linked List hanya terletak pada tail saja yaitu tail memiliki pointer next yang tidak NULL melainkan menunjuk ke head. Maka untuk Circular Double Linked List pun demikian, hanya saja sekarang konsep Single Linked List nya dirubah menjadi Double Linked. Berikut saya beri gambarannya.

Circular Double Linked List

Demikian adalah penjelasan / rangkuman saya mengenai materi Linked List II, semoga membantu teman-teman sekalian. Beri tahu saya melalui kolom komentar kalau ada penjelasan yang kurang / salah. Terimakasih.

Single Linked List

Apasih Single Linked List itu? 

Single Linked List adalah sekumpulan record atau umumnya kita kenal juga sebagai node yang saling terhubung melalui pointer pada masing-masing record.

Gambaran Single Linked List

Single Linked List pada umumnya memiliki 2 pointer yang berfungsi  sebagai paramater untuk memudahkan saat memroses record. Pointer yang pertama yaitu Head, pointer yang menunjuk ke record paling pertama dan Tail, yaitu pointer yang menunjuk ke record paling akhir. Dalam Single Linked List, record paling akhir atau Tail selalu menunujuk ke NULL yang menandakan tidak ada record selanjutnya.

Bagaimana Coding Single Linked List?

Dalam coding Single Linked List, kita akan mengenal beberapa fungsi utama yang berperan untuk membentuk sebuah Linked List. Mari kita simak,

• Insert/Push, fungsi yang berperan untuk memasukkan record/node ke dalam Linked List.
• Delete/Pop, fungsi yang berperan untuk menghapus record/node dalam Linked List.
• Print, fungsi untuk menampilkan isi dari record/node dalam Linked List.

Nah, tapi sebelum me-ngoding fungsi-fungsi tersebut, kita pasti membutuhkan Struct atau template dari record yang akan masuk ke dalam Linked List kita.

struct mahasiswa{

char nama[100];
int no_urut;
mahasiswa *next;

}*head, *tail;

Seperti yang dapat kita lihat, setiap record di Single Linked List hanya memiliki satu pointer untuk menunjuk ke data yang bersebelahan yaitu pointer next menunjuk ke data yang berada di depan sementara pada Double Linked List terdapat dua pointer yaitu next dan prev yang berarti dapat menunjuk ke data yang berada di depan sekaligus di belakang. Inilah perbedaan mendasar antara Single Linked List dan Double Linked List.

Single Linked List : Push

Push di dalam Single Linked List sebenarnya ada beragam. Namun, kali ini akan saya contohkan dengan Push Head, artinya data yang masuk akan selalu berada di paling depan dari Linked List. Silahkan teman-teman coba sendiri untuk Push Tail ataupun Push Mid. 

Contoh codingan Push Head :

char name[100] = "Immanuel";
int no_urut = 10; 

mahasiswa *node = (node*) malloc(sizeof (node));
strcpy(node->name,name);
no_urut->node = no_urut;
node->prev = NULL; 

node->next = head;
head->prev = node;
head = node;

Single Linked List : Pop

Dalam Single Linked List, Pop hanya bisa dilakukan Pop Head dan Pop Tail karena keterbatasan fungsionalitas pada Single Linked List. Maksudnya record pada Single Linked List tidak bisa menunjuk ke record yang berada di belakangnya dan hal ini menjadikan Single Linked List terbatas dalam memroses record di dalamnya.  Bahkan untuk melakukan Pop Tail, harus traverse dulu Linked List sampai sebelum data terakhir baru bisa Pop Tail yang mana ini sangat tidak efisien.

Contoh Codingan Pop Head :

//apabila head = tail maka artinya hanya ada 1 data dalam Linked List
if (head == tail) {
   free(head);
   head = tail = NULL;
}else if(head){
   //kalau head ada isi dan bukan sama dengan tail, artinya record ada beberapa
   mahasiswa *temp = head;
   head = head->next;
   free(temp);
}
//kalau head == NULL, artinya Linked List belum ada isi dan Pop tidak akan jalan

Single Linked List : Print

Di sini saya akan mencontohkan untuk melakukan print semua record yang ada di dalam Linked List.

Contoh Codingan Print :

mahasiswa *curr = head;
//looping selama curr != NULL artinya looping sampai akhir
while(curr){
   printf("Nama : %s, No urut : %d\n", curr->nama, curr->no_urut);
   curr = curr->next;
}

Hash Table

Hash table merupakan salah satu struktur data yang digunakan dalam penyimpanan data sementara. Tujuan dari hash table adalah untuk mempercepat pencarian kembali dari banyak data yang disimpan. Hash table menggunakan suatu teknik penyimpanan sehingga waktu yang dibutuhkan untuk penambahan data (insertions), penghapusan data (deletions), dan pencarian data (searching) relatif lebih cepat dibanding struktur data atau algoritma yang lain.

Pada Hash Table, kita akan mengenal suatu fungsi sederhana yang peranannya sangat esensial pada Hash Table. Fungsi tersebut adalah Hash Function. Apa sih Hash Function itu? Hash Function adalah fungsi yang memuat Hashing di dalamnya yang peranannya untuk mengubah value dari data yang akan disimpan, menjadi key value yang nantinya akan digunakan sebagai index untuk menyimpan data tersebut dalam struktur data. Mengapa kita membutuhkan Hash Function sih? Karena, prinsip Hash table  sendiri adalah menggunakan memori penyimpanan utama berbentuk array dengan tambahan algoritma untuk mempercepat pemrosesan data. Pada intinya hash table merupakan penyimpanan data menggunakan key value yang didapat dari nilai data itu sendiri. Jadi, Hash Function sangat dibutuhkan dalam Hash Table dan justru inilah yang membedakannya dengan struktur penyimpanan lainnya.

Gambaran Hash Table

Dapat dilihat dari gambaran sederhana di atas, bahwa setiap data yang diproses melalui Hash Function akan menghasilkan key value, lalu key value tersebut digunakan sebagai index penyimpanan dari data itu sendiri. Lalu pasti kalian akan bertanya-tanya, bagaiamana cara meng-convert nya ? Karena itu mari kita masuk ke dalam materi Hashing itu sendiri.

Hashing

Secara singkat, Hasing adalah Transformasi aritmatik sebuah data menjadi nilai yang merepresentasikan diri aslinya. Data tersebut bisa beragam, misalnya bisa saja ID, Nama, Nomor Kependudukan, bisa String, Integer, dan seterusnya. Intinya, apapun itu yang unik dari sebuah data, bisa di convert menjadi key melalui Hashing. Hashing sendiri merupakan sebuah aksi yang menjadi bagian dari Hash Function.

Caranya?

Ada berbagai macam cara untuk melakukan Hashing atau lebih tepatnya ada beragam Hash Function yang dapat digunakan. Namun, perlu diperhatikan bahwa tidak semua Hash Function mempunyai fungsi yang optimal, atau bisa saja terjadi collision dalam prosesnya. Collision adalah kondisi dimana 2 data diproses ke dalam Hash Function, namun menghasilkan key value yang sama sehingga ketika di store ke array, akan tejadi bentrokan. Karena itu, kita harus pandai-pandai dalam memilih Hash Function. 

Di sini tidak akan saya contohkan Hash Function yang sederhana, hanya akan saya berikan gambarannya. Misalnya, anda ingin meng-convert String jadi key value, cukup dengan memainkan ASCII dari setiap characternya, misal ASCII dari semua characternya anda tambahkan, nah hasilnya tinggal di modulus dengan size dari array yang anda siapkan supaya tidak out of bound. Itu sangat sederhana dan possibility of collision nya pasti besar. Karena itu, saya akan contohkan algoritma Hash Function yang lebih efisien. Di sini saya punya contoh algoritma dari DJB2. 

DJB2 Hash Function in C

DJB2 cukup efisien untuk struktur data dengan size besar, namun tidak menutup kemungkinan terjadinya collision apalagi jika sizenya kecil. Karena itu perlu penanganan untuk collision.

Berikut ini cara-cara yang digunakan untuk mengatasi collision :

1.   Closed hashing (Open Addressing)

Close hashing menyelesaikan collision dengan menggunakan memori yang masih ada tanpa menggunakan memori diluar array yang digunakan. Closed hashing mencari alamat lain apabila alamat yang akan dituju sudah terisi oleh data. 3 cara untuk mencari alamat lain tersebut :

·        Linear Probing

Apabila telah terisi, linear probing mencari alamat lain dengan bergeser 1 indeks dari alamat sebelumnya hingga ditemukan alamat yang belum terisi data, dengan rumus

·        Ø Quadratic Probing

Quadratic Probing mencari alamat baru untuk ditempati dengan proses perhitungan kuadratik yang lebih kompleks. Tidak ada formula baku pada quadratic probing ini,anda dapat menentukan sendiri formula yang akan digunakan.

Contoh Mi

n-Heap

Contoh Min-Heap

Contoh Min-Heap

Contoh Min-Max Heap

Kelemahan dari closed hashing adalah ukuran array yang disediakan harus lebih besar dari jumlah data. Selain itu dibutuhkan memori yang lebih besar untuk meminimalkan collision.

2.   Open hashing (Separate Chaining)

Pada dasarnya separate chaining membuat tabel yang digunakan untuk proses hashing menjadi sebuah array of pointer yang masing-masing pointernya diikuti oleh sebuah linked list, dengan chain (mata rantai) 1 terletak pada array of pointer, sedangkan chain 2 dan seterusnya berhubungan dengan chain 1 secara memanjang.

Kelemahan dari open hashing adalah bila data menumpuk pada satu/sedikit indeks sehingga terjadi linked list yang panjang.

Hashing pada Blockchain

Blockchain sangat bergantung pada cryptography untuk mendapatkan keamanan data mereka. Satu dari fungsi cryptography yang sangatlah penting dalam konteks ini adalah hashing. 

Dalam blockchain, nilai output yang dikenal sebagai hash, digunakan sebagai sebuah penanda unik untuk blok data. Hash setiap blok yang dihasilkan berhubungan dengan hash dari blok sebelumnya. Terlebih lagi, blok hash bergantung pada data yang terdapat dalam blok tersebut, yang berarti setiap perubahan yang terjadi pada data tersebut akan membutuhkan perubahan pada blok hash.

Maka dari itu, hash dari setiap blok dihasilkan berdasarkan data yang terdapat dalam blok tersebut dan hash dari blok sebelumnya. Penanda hash tersebut memainkan peran penting dalam memastikan keamanan dan keabadian blockchain.

Hashing juga berpengaruh dalam algoritma konsensus yang digunakan untuk memvalidasi transaksi. Sebagai contohnya, algoritma Proof of Work (PoW) yang digunakan dalam blockchain Bitcoin untuk mencapai konsensus dan penambangan koin baru, yang menggunakan sebuah fungsi hash yang disebut dengan SHA-256. Sesuai dengan namanya, SHA-256 mengambil input data dan menghasilkan sebuah hash yang memiliki panjang 256 bits atau 64 karakter.

Selain memberikan proteksi pada riwayat transaksi pada buku kas, cryptography juga memainkan peran dalam memastikan keamanan dompet yang digunakan untuk menyimpan mata uang digital. Pasangan kunci publik dan pribadi yang mengizinkan pengguna untuk menerima dan mengirimkan pembayaran dibuat melalui penggunaan cryptography kunci publik atau 'asimetris'. Kunci pribadi digunakan untuk membuat sebuah tanda tangan digital untuk transaksi, dan mengizinkan otentikasi kepemilikan koin yang dikirim.

Walaupun masih banyak sifat cryptography asimetris yang tidak tercakup dalam penjelasan ini, akan tetapi, cryptography asimetris ini menghalangi siapapun diluar pemilik kunci pribadi untuk pengaksesan dana yang disimpan dalam dompet mata uang digital, dan mengamankan dana sampai pemilik memutuskan untuk menggunakannya (selama kunci pribadi tidak dibeberkan dan terkompromi).

Binary Tree

Tree Concept

Tree adalah sebuah struktur data bukan linear yang secara bentuk menyerupai sebuah struktur pohon, yang terdiri dari serangkaian node (simpul) berisi data yang saling berhubungan.

contoh Tree

Beberapa konsep terkait Tree : 

• Node paling atas di namakan Root atau akar
• Garis yang menghubungkan node parent ke node child disebut edge
• Node yang tidak memiliki child disebut leaf
• Dua node yang memiliki parent yang sama disebut sibling
• Descendant adalah seluruh node yang terletak setelah sebuah node dan terletak di jalur yang sama
• Sub-tree adalah suatu node beserta descendantnya
• Degree dari sebuah node dapat dihitung dari total sub-tree dari node tersebut
• Height / Depth adalah banyaknya tingkatan / level dalam tree

Binary Tree

Binary Tree adalah tree dengan syarat bahwa tiap node hanya memiliki boleh maksimal dua subtree dan kedua subtree tersebut harus terpisah. Sesuai dengan definisi tersebut, maka tiap node dalam binary tree hanya boleh memiliki paling banyak dua anak / child.

contoh Binary Tree

Dalam implementasi nya, Binary Tree digunakan sebagai sebuah sorted data structure, salah satu contohnya Binary Search Tree. Akan saya beri sedikit gambaran dalam codingannya. 

Contoh Codingan deklarasi Binary Search Tree :

Struct node {

    int value;
    node *left, *right; 

}*root;

Konsep Linked List sangat terpakai di sini, hanya perlu penyesuain di beberapa syarat tree saja. Namun, untuk insertion, searching, ataupun deletion akan ada perbedaan yang cukup signifikan dengan Linked List.

Tipe-tipe Binary Tree

• Perfect Binary Tree, adalah binary tree yang setiap levelnya memiliki kedalaman yang sama.

Perfect Binary Tree

• Complete Binary Tree, adalah binary tree yang seluruh node pada setiap levelnnya terisi penuh, kecuali level terakhir dan penempatan node nya diutamakan yang sebelah kiri penuh terlebih dahulu. Perfect Binary Tree bisa juga disebut Complete Binary Tree.

Complete Binary Tree

• Skewed Binary Tree, adalah binary tree yang setiap nodenya hanya punya maksimal 1 child sehingga sangat jelas bahwa binary tree ini tidak seimbang.

Skewed Binary Tree

• Balanced Binary Tree, adalah binary tree yang tinggi antara anak sebelah kiri dan kanannya hanya berselisih maksimal satu. Binary tree ini merupakan konsep yang digunakan dalam AVL (Adelson-Velskii and Landis). Perfect Binary Tree dan Complete Binary Tree termasuk juga dalam Balanced Binary Tree.

Balanced Binary Tree

Binary Search Tree atau BST adalah salah satu implementasi struktur data dinamis yang non-linear dalam bentuk binary tree yang datanya dalam kondisi terurut atau sorted. BST memungkinkan proses pencarian, penambahan, ataupun penghapusan data menjadi lebih cepat dengan rata-rata kompleksitas waktu O(log n) walaupun dalam kondisi tertentu, dapat memiliki kompleksitas O(n) atau sama seperti kompleksitas struktur data linear. Hal tersebut dapat terjadi apabila Binary Tree yang terbentuk tidak seimbang atau menjadi Skewed Binary Tree (bentuk yang sudah dijelaskan di pertemuan sebelumnya). Efisiensi Binary Search Tree dapat dilakukan dengan banyak cara salah satunya AVL, namun di pertemuan kali ini kita hanya akan membahas Binary Search Tree dan operasi-operasi yang dimilikinya. 

Umumnya ciri-ciri BST adalah sebagai berikut, 

• Setiap node memiliki value dan tidak ada value yang sama / double
• Value yang ada di sebelah kiri tree memiliki nilai yang lebih kecil dari root nya
• Value yang ada di sebelah kanan tree memiliki nilai yang lebih besar dari root nya
• Kiri dan kanan tree bisa menjadi root lagi atau bisa memiliki anak / Child lagi, sehingga seperti rekursif

Binary Search Tree

BST memiliki 3 proses utama dalam pengimplementasiannya. Proses-proses tersebut adalah

1.     Find(x) : find value x di dalam BST

2.     Insert(x) : memasukkan value baru x ke dalam BST (push)

3.     Delete(x) : menghapus value x dalam BST (pop)

Operasi: Search BST

dengan adanya ciri” atau syarat di dalam BST , maka untuk finding/searching didalam BST menjadi lebih mudah.

Bayangkan kita akan mencari value X.

• Memulai Pencarian Dari Root
• Jika Root adalah value yang kita cari , maka berhenti
• Jika x lebih kecil dari root maka cari kedalam rekrusif tree sebelah kiri
• Jika x lebih besar dari root maka cari kedalam rekrusif tree sebelah kanan

Operasi: Insertion BST

Memasukan value (data) baru kedalam BST dengan rekrusif

Bayangkan kita menginsert value x :

• Dimulai dari root
• jika x lebih kecil dari node value(key) kemudian cek dengan sub-tree sebelah kiri lakukan pengecekan secara berulang ( rekrusif )
• jika x lebih besar dari node value(key) kemudian cek dengan sub-tree sebelah kanan lakukan pengecekan secara berulang ( rekrusif )
• Ulangi sampai menemukan node yang kosong untuk memasukan value X ( X akan selalu berada di paling bawah biasa di sebut Leaf atau daun )

Operasi: Delete ( Remove )

akan ada 3 case yang ditemukan ketika ingin menghapus yang perlu diperhatikan :

• Jika value yang ingin dihapus adalah Leaf(Daun) atau paling bawah , langsung delete
• Jika value yang akan dihapus mempunyai satu anak, hapus nodenya dan gabungkan anaknya ke parent value yang dihapus
• jika value yang akan di hapus adalah node yang memiliki 2 anak , maka ada 2 cara , kita bisa cari dari left sub-tree anak kanan paling terakhir(leaf) (kiri,kanan) atau cari dari right sub-tree anak kiri paling terakhir(leaf)(kanan,kiri)

Lalu untuk melakukan print all kita akan pakai yang namanya function in-order, yaitu melakukan traverse ke kiri sampai habis lalu print kemudian cari ke kanan baru print lagi 

Contoh Full Source Code Binary Search Tree :

(Kalau pusing lihat format tulisannya, silahkan di copy lalu cari di google Source Code Beautifyer)

#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 *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;

}

Pointer 

Setiap variabel yang kita buat pada program akan memiliki alamat memori.

Alamat memori berfungsi untuk menentukan lokasi penyimpanan data pada memori (RAM).

Alamat memori biasnya direpresentasikan dalam bilangan heksa desimal.

Nah, Pointer adalah sebuah variabel berisi alamat memori dari variabel yang lain.

Ada beberapa langkah yang harus dilakukan saat menggunakan pointer:

1. Membuat pointer
2. Mengisinya dengan alamat memori
3. Mengakses nilai dari pointer

Pointer di C sangat familiar dengan asteris atau *. Berikut beberapa cara mendeklarasikan pointer.

int *nama_pointer;

double *nama_pointer;

float *nama_pointer;

char *nama_pointer;

Pointer sangat krusial dalam struktur data. Karena seperti yang kita ketahui, bahwa seluruh struktur data memerlukan pointer untuk melakukan maintanance data dan tracking.

Linked List

Linked List adalah bagian dari Struktur Data Linked list atau dikenal juga dengan sebutan senarai berantai adalah struktur data yang terdiri dari urutan record data dimana setiap record memliki field yang menyimoan alamat/ referensi dari record selanjutnya (dalam urutan) elemen data yang dihubungkan dengan link pada linked list disebut Node.

Biasanya didalam suatu lnked list, terdapat istilah head and tail.

• Head adalah elemen yang berada pada posisi pertama dalam suatu linked list
• Tail adalah element yang berada pada posisis terakhir dalam suatu linked list

Ada beberapa macam Linked List, yaitu :

• Single Linked List
Single Linked List adalah sekumpulan record atau umumnya kita kenal juga sebagai node yang saling terhubung melalui pointer pada masing-masing record.

Single Linked List

Single Linked List pada umumnya memiliki 2 pointer yang berfungsi  sebagai paramater untuk memudahkan saat memroses record. Pointer yang pertama yaitu Head, pointer yang menunjuk ke record paling pertama dan Tail, yaitu pointer yang menunjuk ke record paling akhir. Dalam Single Linked List, record paling akhir atau Tail selalu menunujuk ke NULL yang menandakan tidak ada record selanjutnya.













Circular Single Linked List
Circular Single Linked List pada dasarnya adalah Single Linked List yang pointer Tail (pointer terakhir) dari linked list tersebut selalu menunjuk ke Head (pointer pertama) dari linked list itu sendiri. Sehingga kalau digambarkan / dibayangkan, linked list tersebut membentuk sebuah loop karena itulah linked list tersebut dinamakan Circular. Berbeda dari Single Linked List, Circular Single Linked List pada praktiknya tidak akan memiliki pointer yang menyimpan nilai NULL, karena semuanya saling terkoneksi membentuk loop.



Circular Single Linked List

• Double Linked List
Double Linked List memiliki konsep yang sama dengan Single Linked List, yang membedakan adalah jumlah pointernya. Pada Single Linked List, setiap pointer hanya memiliki satu pointer didalamnya untuk menyimpan alamat dari record selanjutnya. Sementara pada Double Linked List, setiap pointer punya dua pointer didalamnya yang berfungsi untuk menyimpan alamat dari record sebelumnya dan alamat dari record selanjutnya. 





Double Linked List



Contoh codingan :


struct mahasiswa{
char nama[100];
int no_urut;
mahasiswa *next, *prev;
}*head, *tail;


Seperti yang sudah saya jelaskan sebelumnya, pada codingan Double Linked List, terdapat dua pointer berupa next dan prev. Sementara, pada codingan Single Linked List, pasti hanya memiliki satu pointer berupa next.


• Circular Double Linked List
Di atas sudah saya jelaskan bahwa perbedaan Circular Single Linked List dengan Single Linked List hanya terletak pada tail saja yaitu tail memiliki pointer next yang tidak NULL melainkan menunjuk ke head. Maka untuk Circular Double Linked List pun demikian, hanya saja sekarang konsep Single Linked List nya dirubah menjadi Double Linked. Berikut saya beri gambarannya.

Circular Double Linked List

Hash Table

Hash Table Hash table merupakan salah satu struktur data yang digunakan dalam penyimpanan data sementara. Tujuan dari hash table adalah untuk mempercepat pencarian kembali dari banyak data yang disimpan. Hash table menggunakan suatu teknik penyimpanan sehingga waktu yang dibutuhkan untuk penambahan data (insertions), penghapusan data (deletions), dan pencarian data (searching) relatif lebih cepat dibanding struktur data atau algoritma yang lain.

Pada Hash Table, kita akan mengenal suatu fungsi sederhana yang peranannya sangat esensial pada Hash Table. Fungsi tersebut adalah Hash Function. Apa sih Hash Function itu? Hash Function adalah fungsi yang memuat Hashing di dalamnya yang peranannya untuk mengubah value dari data yang akan disimpan, menjadi key value yang nantinya akan digunakan sebagai index untuk menyimpan data tersebut dalam struktur data. Mengapa kita membutuhkan Hash Function sih? Karena, prinsip Hash table sendiri adalah menggunakan memori penyimpanan utama berbentuk array dengan tambahan algoritma untuk mempercepat pemrosesan data. Pada intinya hash table merupakan penyimpanan data menggunakan key value yang didapat dari nilai data itu sendiri. Jadi, Hash Function sangat dibutuhkan dalam Hash Table dan justru inilah yang membedakannya dengan struktur penyimpanan lainnya.

Hashing

Secara singkat, Hasing adalah Transformasi aritmatik sebuah data menjadi nilai yang merepresentasikan diri aslinya. Data tersebut bisa beragam, misalnya bisa saja ID, Nama, Nomor Kependudukan, bisa String, Integer, dan seterusnya. Intinya, apapun itu yang unik dari sebuah data, bisa di convert menjadi key melalui Hashing. Hashing sendiri merupakan sebuah aksi yang menjadi bagian dari Hash Function.

Binary Tree

Binary Tree adalah tree dengan syarat bahwa tiap node hanya memiliki boleh maksimal dua subtree dan kedua subtree tersebut harus terpisah. Sesuai dengan definisi tersebut, maka tiap node dalam binary tree hanya boleh memiliki paling banyak dua anak / child.

Binary Tree

Dalam implementasi nya, Binary Tree digunakan sebagai sebuah sorted data structure, salah satu contohnya Binary Search Tree. Akan saya beri sedikit gambaran dalam codingannya.

Contoh Codingan deklarasi Binary Search Tree :

 Struct node {

 int value;
 node *left, *right; 

 }*root;

Konsep Linked List sangat terpakai di sini, hanya perlu penyesuain di beberapa syarat tree saja. Namun, untuk insertion, searching, ataupun deletion akan ada perbedaan yang cukup signifikan dengan Linked List.

Binary Search Tree

Binary Search Tree atau BST adalah salah satu implementasi struktur data dinamis yang non-linear dalam bentuk binary tree yang datanya dalam kondisi terurut atau sorted. BST memungkinkan proses pencarian, penambahan, ataupun penghapusan data menjadi lebih cepat dengan rata-rata kompleksitas waktu O(log n) walaupun dalam kondisi tertentu, dapat memiliki kompleksitas O(n) atau sama seperti kompleksitas struktur data linear. Hal tersebut dapat terjadi apabila Binary Tree yang terbentuk tidak seimbang atau menjadi Skewed Binary Tree (bentuk yang sudah dijelaskan di pertemuan sebelumnya). Efisiensi Binary Search Tree dapat dilakukan dengan banyak cara salah satunya AVL, namun di pertemuan kali ini kita hanya akan membahas Binary Search Tree dan operasi-operasi yang dimilikinya.

Binary Search Tree

Berikut saya cantumkan Source Code untuk menjawab tugas membuat Aplikasi AprilMarket dengan konsep Double Linked List :

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <time.h>

//This program does't come with proper validation since it's not mention in the query. So be wise while using this program.

struct Node{

char barang[21];

int qty, price;

Node *next, *prev;

}*head, *tail;

Node *create(char* barang, int qty, int price){

Node *temp = (Node*)malloc(sizeof(Node));

strcpy(temp->barang, barang);

temp->qty = qty;

temp->price = price;

temp->next = temp->prev = NULL;

return temp;

}

void pushHead(Node *temp){

if(!head)head = tail = temp;

else{

head->prev = temp;

temp->next = head;

head = temp;

}

}

void pushTail(Node *temp){

if(!head)head = tail = temp;

else{

tail->next = temp;

temp->prev = tail;

tail = temp;

}

}

void pushMid(Node *temp){

if(!head)head = tail = temp;

else if(strcmp(head->barang, temp->barang) > 0)pushHead(temp);

else if(strcmp(tail->barang, temp->barang) < 0)pushTail(temp);

else{

Node *curr = head;

while(strcmp(curr->barang, temp->barang) < 0){

curr = curr->next;

}

curr->prev->next = temp;

temp->prev = curr->prev;

temp->next = curr;

curr->prev = temp;

}

}

void popHead(){

Node *temp = head;

if(!head){

printf("No Data");

return;

}

else if(head==tail){

head = tail = NULL;

}else{

head = temp->next;

temp->next = temp->prev = head->prev = NULL;

temp = NULL;

}

free(temp);

}

void popTail(){

Node *temp = tail;

if(!head){

printf("No Data");

return;

}

else if(head==tail){

head = tail = NULL;

}else{

tail = temp->prev;

temp->next = temp->prev = tail->next = NULL;

temp = NULL;

}

free(temp);

}

void popSearch(char* barang){

if(!strcmp(head->barang, barang))popHead();

else if(!strcmp(tail->barang, barang))popTail();

else {

Node *curr = head;

while(strcmp(head->barang, barang)){

curr = curr->next;

if(!curr){

printf("No Data");

return;

}

}

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

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

curr->next = curr->prev = NULL;

free(curr);

}

}

void cls(){

for(size_t i = 0; i < 30; ++i){

puts("");

}

}

bool view(){

cls();

Node *curr = head;

if(!head){

printf("Please Input Some Item First!");

getchar();

return false;

}

puts("=========================================");

while(curr!=NULL){

printf("| %20s | %4d | %7d |\n", curr->barang, curr->qty, curr->price);

curr = curr->next;

}

puts("=========================================\n");

return true;

}

void input(){

int qty, price, temp, len;

char barang[101];

do{

if(head){

view();

}

printf("Input nama barang [3-20 Characters] [No duplicate name]: ");

scanf("%[^\n]", barang);getchar();

len = strlen(barang);

}while(len < 3 || len > 20);

printf("Input quantity barang : ");

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

srand(time(NULL));

temp = rand() % 10 + 1;

price = temp*1000;

pushMid(create(barang,qty,price));

cls();

printf("Item berhasil di input! ");

getchar();

}

void update(){

char barang[21];

int qty;

Node* curr;

if(!view()){

return;

}

printf("Input nama barang yang ingin diupdate [Case Sensitive] : ");

scanf("%[^\n]", barang); getchar();

if(!strcmp(head->barang, barang))curr = head;

else if(!strcmp(tail->barang, barang))curr = tail;

else{

curr = head;

while(!strcmp(curr->barang, barang)){

curr = curr->next;

if(!curr){

printf("No Data");

return;

}

}

}

printf("Input nama barang baru : ");

scanf("%[^\n]", barang);getchar();

printf("Input quantity barang baru : ");

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

srand(time(NULL));

int temp = rand()%10 + 1;

int price = temp*1000;

curr->price = price;

strcpy(curr->barang,barang);

curr->qty = qty;

cls();

printf("Update Succesfull! ");

getchar();

}

void del(){

char barang[21];

if(!view()){

return;

}

printf("Input nama barang yang ingin dihapus [Case Sensitive] : ");

scanf("%[^\n]", barang);getchar();

popSearch(barang);

cls();

printf("Delete Succesfull! ");

getchar();

}

int calculate(){

int total = 0;

Node *curr = head;

while(curr!=NULL){

total+=(curr->qty*curr->price);

curr = curr->next;

}

return total;

}

bool checkout(){

cls();

if(!view()){

return false;

}

int total = calculate();

puts("------------------------------------------");

printf("Total : %d\n\n", total);

printf("Proceed?");getchar();

cls();

printf("Kindness is FREE! Thanks for shopping!");

getchar();

return true;

}

void menu(){

int choose;

bool exit;

do{

if(head){

view();

}else{

cls();

puts("---No Item Inputted Yet---\n\n");

}

puts("1. Input New Item");

puts("2. Update Item");

puts("3. Delete Item");

puts("4. Checkout");

printf("Choose >> ");

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

switch(choose){

case 1:

input();

continue;

case 2:

update();

continue;

case 3:

del();

continue;

case 4:

exit = checkout();

continue;

}

}while(!exit);

}

int main(){

menu();

return 0;

}

Balanced Binary Search Tree

Pada rangkuman sebelumnya, kita telah membahas mengenai Binary Search Tree atau BST. Sebelumnya, juga sudah saya bahas bahwa BST memiliki kelemahan, yaitu suatu kondisi dimana ternyata Tree tersebut tidak benar-benar memiliki Time Complexity O(log n). Kondisi ini disebabkan oleh bentuk Skewed Tree atau tree hanya memanjang ke salah satu sisi saja, sehingga bentuknya mirip linear dan memiliki Time Complexity O(n). Solusi untuk masalah ini adalah Balanced Binary Search Tree yang dapat diimplementasikan melalui beberapa cara, salah satunya AVL yang akan kita bahas pada pertemuan kali ini.

AVL Tree

AVL Tree adalah Binary Search Tree yang memiliki perbedaan tinggi / height maksimal 1 antara subtree kiri dan subtree kanan.

Berikut gambarannya :

Menentukan Height

Cara menentukan Height dan Balance Factor :

Height : 

• Jika node (root) tidak memiliki subtree maka heightnya = 0
• Leaf node heightnya = 1
• Height internal node (node yang bukan root / leaf) = successor maximum height + 1

Balance Factor :

Selisih height antara anak kiri dan kanan. Apabila tidak memiliki anak, Balance Factor = 0.

AVL Tree : Insertion

Insertion pada AVL pada dasarnya sama dengan Binary Search Tree, dimana node baru akan mengisi leaf. Perbedaannya adalah pada AVL, setiap dilakukan insertion, dilakukan juga pengecekkan. Apabila terjadi AVL violation, dimana sebuah node memiliki balance factor > 1, maka dilakukan rebalancing. Pengecekkan umumnya dimulai dari node terdalam, sampai terakhirnya root. 

Umumnya pada proses balancing, terdapat 4 kasus.

Node yang menjadi poros balancing biasanya dikenal juga dengan node T.

1. Kasus 1 : node terdalam terletak pada subtree kiri dari anak kiri T (left - left)
2. Kasus 2 : node terdalam terletak pada subtree kanan dari anak kanan T (right - right)
3. Kasus 3 : node terdalam terletak pada subtree kiri dari anak kanan (left - right)
4. Kasus 4 : node terdalam terletak pada subtree kanan dari anak kiri (right - left)

Keempat kasus tersebut dapat diselesaikan melalui proses rotasi

• Kasus 1 dan 2 dengan single rotation.
• Kasus 3 dan 4 dengan double rotation.

Note : 

• Node terdalam dikenal juga dengan node yang baru di insert. 
• Left dan Right adalah proses rotasinya.

Single Rotation

Single Rotation dilakukan apabila node terdalam masih satu path yang lurus dengan node yang melakukan AVL violation, sehingga bila ditarik garis, pathnya terlihat lurus.

Contoh Single Rotation

Pada contoh di atas, T melakukan AVL violation, sehingga T menjadi poros untuk proses rebalancing. Node A adalah node terdalamnya. Proses rotasi yang terjadi adalah left - left, dimana T bertukar posisi dengan S, kemudian subtree kanan dari S, menjadi subtree kiri T.

Double Rotation

Double Rotation dilakukan apabila node terdalam memiliki path yang tidak lurus dengan node yang melakukan violation, sehingga apabila ditarik garis, pathnya akan terlihat bengkok.

Contoh Kasus :

Step 1 : right - right rotation

Step 2 : left - left rotation

Pada kasus di atas, R adalah node terdalam dan T adalah node yang melakukan violation. Proses rotation yang diperlukan untuk rebalancing kasus di atas adalah right-left rotation yang dibagi menjadi 2 step.

AVL Tree : Deletion

Proses Deletion pada AVL juga sama dengan Binary Search Tree, yaitu apabila node yang dihapus adalah leaf, maka langsung dihapus saja. Apabila node yang dihapus memiliki satu child, maka childnya yang akan menggantikan. Apabila node yang dihapus memiliki dua child, maka node yang dihapus akan digantikan dengan node terbesar pada subtree kiri atau node terkecil pada subtree kanan. Namun pada AVL, dilakukan pengecekkan setiap kali proses deletion dilakukan. Apabila tree menjadi tidak seimbang akibat proses deletion, maka rebalancing akan dilakukan (seperti pada insertion).

Contoh Kasus :

Step 1 : Node yang akan dihapus adalah node 60. Sehingga dicarikan penggantinya yaitu node terbesar dari subtree kiri, node 55.

Step 2 : Terjadi violation pada node 55, sehingga diperlukan rotation. Maka, dilakukan lah right-right rotation dengan node 55 sebagai porosnya.

Step 3 : Terjadi violation lagi di node 50. Kali ini dibutuhkan double rotation karrena pathnya bengkok. Dilakukanlah right-left Rotation dengan node 50 sebagai poros utama dan 25 sebagai poros right - right rotation.

Step 4 : Balanced AVL Tree

Heap

Heap adalah struktur data berbentuk binary tree yang menggunakan array sebagai media pengimplementasiannya. Walaupun mirip dengan Binary Search Tree, Heap memiliki perbedaan yaitu antara anak kanan dengan anak kiri tidak memiliki hubungan. Jadi, yang menjadi patokan adalah parent dari node itu sendiri.

Min-Heap

Min-Heap adalah heap dengan urutan data dari yang paling kecil (root) sampai ke data yang paling besar.

Contoh Min-Heap

Max-Heap

Max-Heap adalah kebalikan dari Min-Heap, yaitu urutan datanya dari yang paling besar sebagai root, sampai ke data yang paling kecil.

Contoh Max-Heap

Min-Max Heap

Min-Max Heap adalah gabungan antara Min-Heap dengan Max-Heap dalam satu Heap. Jadi, level 0 dimulai dari min, dilanjutkan level 1 dengan max, level 2 dengan min, dan seterusnya.

Contoh Min-Max Heap

Heap : Insertion

1. Insert pada heap selalu dimulai dari index 1 dan seterusnya. 
2. Kemudian node yang baru di insert, akan dibandingkan dengan parentnya apakah lebih kecil / lebih besar (sesuai dengan heap, min / max). 
3. Apabila ternyata node yang baru di insert memiliki value lebih kecil pada min heap / value yang lebih besar pada max heap, maka tukar posisi node baru dengan parentnya. 
4. Lakukan tahap kedua dan ketiga secara recursive sampai ke root.
5. Karena menggunakan array, maka kita memanipulasi indexnya. 
6. Index Parent = Index current node / 2
7. Index Left Child = Index Parent * 2
8. Index Right Child = (Index Parent * 2) + 1

Heap : Deletion

Konsep deletion pada heap, serupa dengan priority queue, yaitu pop dari data yang berada di urutan paling pertama terlebih dahulu.

1. Swap data yang berada di index 1 dengan index terakhir.
2. Pop data yang berada di index terakhir.
3. Lakukan Heapify Down / pengecekan posisi node yang berada di index 1 (setelah swap) terhadap left child ataupun right child.
4. Apabila posisi nya ternyata salah, lakukan swap seperti pada insertion.
5. Ulangi tahap ke 3 dan ke 4 secara recursive, sampai tidak ada child lagi.

Contoh Codingan Min-Heap

#include<stdio.h>

int heap[101];

int idx = 1;

void swap(int a, int b){

int temp = heap[a];

heap[a] = heap[b];

heap[b] = temp;

}

void insert(int val){

heap[idx] = val;

int curr = idx;

while(curr/2 > 0 && heap[curr] < heap[curr/2]){

swap(curr,curr/2);

curr/=2;

}

++idx;

}

int extract(){

int result = heap[1];

heap[1] = heap[idx-1];

int curr = 1;

--idx;

while(curr*2 < idx && (heap[curr*2]<heap[curr] || heap[curr*2+1]<heap[curr])){

if(curr*2+1<idx){

if(heap[curr*2] < heap[curr*2 + 1]){

swap(curr,curr*2);

curr*=2;

}else{

swap(curr,curr*2+1);

curr = curr*2+1;

}

}else{

swap(curr,curr*2);

curr*=2;

}

}

return result;

}

void print(){

for(size_t i = 1; i < idx; ++i){

printf("%d ", heap[i]);

if(i==idx-1)printf(" \b");

y}

int main (){

insert(2);

insert(1);

insert(5);

insert(15);

insert(11);

insert(10);

print();

extract();

puts("");

print();

return 0;

}

Tries

Tries adalah struktur data yang berbentuk pohon, yang biasanya menyimpan data berupa string (kata). Kata tries diambil dari Retrieval, karena Tries dapat menemukan sebuah kata tunggal hanya dari huruf awalannya saja.

Contoh Tries

Referensi :

- http://suciantinovi.blogspot.com/2014/05/balanced-binary-tree-and-2-3-tree.html (Saya mengakui rangkuman saya sangat mirip dengan blogspot tersebut, karena memang saya mengutip blogspot tersebut. Alasannya karena saya sangat setuju dengan isi dari blogspot tersebut, penjelasannya baik. Tapi tentu saya melakukan beberapa perubahan sesuai dengan pemahaman dan preference saya)

- Slide Binusmaya : AVL Tree (hanya mengutip kasus, karena kebanyakan di internet kasusnya kurang relevan dengan apa yang saya ingin sampaikan)

- http://dinda-dinho.blogspot.com/2013/06/pengertian-dan-konsep-avl-tree.html

Refrensi :

- https://abdilahrf.github.io/2015/06/pengenalan-binary-search-tree/

- https://sourcecodegeneration.blogspot.com/2018/08/pengertian-binary-tree-binary-search.html

Refrensi :

• https://www.binance.vision/id/blockchain/what-makes-a-blockchain-secure
• https://informatika11d.wordpress.com/2012/11/22/struktur-data-hash-table/
• http://dinda-dinho.blogspot.com/2013/07/pengertian-dan-konsep-binary-tree.html?m=1
• https://rahmatsadchalis15.blogspot.com/2015/05/konsep-dasar-tree-algoritma.html
• http://suciantinovi.blogspot.com/2014/03/binary-tree.html

Referensi Link Gambar :

- Gambar Single Linked List : https://media.geeksforgeeks.org/wp-content/cdn-uploads/gq/2013/03/Linkedlist.png

Referensi Gambar :

Gambar : Circular Single Linked List - http://geeksforgeeks.org/wp-content/uploads/cll_orig.gif

Gambar : Circular Double Linked List - https://media.geeksforgeeks.org/wp-content/uploads/Circular-doubly-linked-list.png

Immanuel Joseph - 2301852215