Rangkuman Mid Semester II

Hai, jadi kali ini saya akan merangkum keseluruhan materi yang sudah dibahas sampai Mid Semester ini.

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

Kesimpulan yang bisa saya ambil dari materi Mid Semester ini adalah bahwa dalam struktur data semuanya saling terkait dan saling mencukupi satu sama lain. Sebuah Binary Search Tree tidak akan dapat berdiri sendiri tanpa konsep Linked List. Sementara Hash Table tidak akan berjalan tanpa konsep Hashing.  Kemudian, dalam struktur data, konsep pointer sangatlah krusial seperti yang saya jelaskan sebelumnya, Karena dalam struktur data, kita mencari cara paling baik dalam mengelola sebuah data. Banyak bentuk struktur data yang bisa saja diterapkan, namun kita sebagai programmer harus mengenali struktur data mana yang paling cocok digunakan dalam mengelola sebuah record. Misalnya, kita mau menerima input dari sebuah database besar, nah kita harus memikirkan efisiensinya. Dalam konteks ini, menurut saya struktur data tree akan lebih efisien digunakan daripada Hash Table atau Linked List. Jadi, kita harus paham betul seluruh konsep dalam struktur data sebelum mengimplementasikannya. Sekian dari penjelasan dan kesimpulan yang bisa saya ambil.

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. 

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;

}

Refrensi :
- https://abdilahrf.github.io/2015/06/pengenalan-binary-search-tree/
- https://sourcecodegeneration.blogspot.com/2018/08/pengertian-binary-tree-binary-search.html

Hashing and Hash Table and Binary Tree

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.

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

Demikian adalah penjelasan / rangkuman saya mengenai materi Hashing, Hash Tables, dan Binary Tree, semoga membantu teman-teman sekalian. Beri tahu saya melalui kolom komentar kalau ada penjelasan yang kurang / salah. Terimakasih.

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

Rangkuman Pertemuan 3 : Single Link List

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;
}

Kesimpulannya, sangat disarankan untuk teman-teman yang memang ingin melakukan pemrosesan data menggunakan konsep array dinamis unutk memakai Double Linked List karena fungsionalitasnya jauh lebih baik dari Single Linked List. Namun, memang untuk belajar, Single Linked List akan lebih mudah untuk dipahami. Silahkan gunakan keduanya dengan bijaksana.

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

Referensi Link Gambar :

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