Rangkuman Linked List

-

Rangkuman Linked list

Perbedaan linked list dengan array

Linked list merupakan salah satu contoh dari data structure, dari bentuknya terlihat bahwa linked list dan array memiliki kemiripan.

Array memiliki kelebihan dalam mengakses datanya, kita bisa langsung mengakses data yang ada dari sebuah array.
1.1 array








dalam array kita bisa mengakses data yang ada di dalam array dengan cara namavariable[index] dan ini merupakan kelebihan dari array.

========================================================================

linked list mirip seperti array dan linked list juga punya kelebihannya sendiri, linked list punya kelebihan dalam penyisipan atau pembuangan data yang ada di dalam Node nya.

kita dapat membuat linked list dengan cara men declare struct terlebih dahulu.
2.1 struct yang berisi integer dan pointer






lalu buat di int main untuk memasukkan data ke dalam linked list.
2.2 mengisi linked list dengan data











jadi sekarang di dalam linked list ada data 1,2,3 dan setiap node menunjuk ke node yang berikutnya dan node terakhir menunjuk ke NULL
ini merupakan single linked list.


Jenis-Jenis Linked List

1. Single linked list
3.1 single linked list






dalam single linked list node terakhir (tail) menunjuk kepada NULL

2. Circular single linked list
3.1 Circular single linked list





dalam Circular single linked list node terakhir menjunjuk kepada node pertama

3. Doubly linked list
3.2 Doubly linked list





dalam Doubly linked list , setiap node mempunyai 2 penunjuk. yaitu menunjuk ke node berikutnya dan ke node sebelumnya.

4. Doubly circular linked list
3.3 doubly circular linked list





dalam Doubly circular linked list , sama seperti double linked list tetapi node terakhir menjunjuk ke node pertama

Insertion atau deletion dalam linked list

1. Insert data
4.1 insert data






2. delete data
4.2 delete data












Push head : membuat node baru didepan head
berikut adalah fungsinya
Kita membuat sebuah node baru dan kita hubungkan node itu ke head
lalu headnya kita pindahkan ke node baru tadi.

Push tail : membuat node baru dibelakang tail
berikut adalah fungsinya
Disini ada selection untuk menghandle error (ketika head==NULL).
if(head==NULL) maka buat sebuah node;
else 
{
buat sebuah node;
lalu loop sampai null;
dan beritahu bahwa setelah node(yang NULL) adalah node yang baru kita buat tadi;
}

Pop head : membebaskan memory dari node(head) yang tadi sudah dialokasikan
berikut adalah fungsinya
Kita membuat sebuah node temp yang akan ditaruh di node head
lalu kita pindahkan head ke node setelahnya
lalu free node temp.

Print all node : Print semua node yang ada
berikut adalah fungsinya
Dengan ini kita bisa mengeprint semua node yang ada

untuk membuktikan bahwa ini bekerja, dibawah adalah screenshoot untuk print semua node yang ada

Hashing and Hash Table


Hashing adalah teknik untuk menyimpan dan mengambil data secara cepat, lalu dalam Hashing sebuah string dari karakter akan diubah menjadi nilai (kunci) yang merepresentasikan string tersebut.
lalu string yang sudah diubah menjadi key tersebut disimpan dalam array yang biasa disebut hash table.

Hash table adalah sebuah sebuah array tempat kita menyimpan original string, index dari table nya berupa (kunci) yang kita dapatkan dari string tadi.

Ada beberapa cara untuk mengubah string menjadi kunci.
- Mid-square
- Division
- Folding
- Digit extraction
- Rotating dash

Mid-square
jadi cara ini adalah memangkatkan nilai dari sebuah string atau integer, lalu ambil bagian tengahnya.
misal angka 2020.
pangkat 2020 adalah 4.080.400
bagian tengahnya adalah 804.
804 adalah key dari 2020.

Division
ambil value ascii dari string, lalu kita modulo dengan jumlah ukuran table.
misal kata "BUDI" dan ukuran tabel kita ada 40.
kata "BUDI" mempunyai ascii (64+2 + 64+21 + 64+4 + 64+9) % 40 = 1
jadi 1 adalah key dari kata "BUDI".

Folding
pecah angka menjadi beberapa bagian, tambahkan dan ambil jumlah nya
misal angka 1234
pecah jadi 12 34
12+34 = 46
46 adalah key.

Digit extraction
mengekstrak key dari angka
misal ada angka 67890
angka pertama adalah 6, angka ketiga adalah 8, dan angka kelima adalah 0
maka key nya adalah 680.

Rotating dash
pakai metode division atau mid-square untuk mendapatkan key
lalu rotate untuk mendapatkan alamat dash yang baru.
misal key nya 804.
setelah di rotate menjadi 408.

karena kemungkinan pembentukan string atau angka sangatlah banyak, maka sangatlah mungkin ada beberapa string atau angka memiliki alamat yang sama.
bagaimana cara mengatasi nya?

kita bisa menggunakan linear probing dan chaning.

Linear probing adalah cara untuk menempatkan string di tempat yang kosong, dengan cara mengescan tiap array dan mencari tempat kosong.

Chaning adalah konsep untuk menempatkan string di tempat yang sama dan membuat chained list dengan linked list.

Implementasi hash table pada blockchain

Jadi didalam setiap block tersimpan data transaksi, siapa yang melakukan transaksi dan kapan transaksi dilakukan, data yang ada didalam setiap block akan diubah menjadi "hash"
setiap block saling terhubung dan setiap block menyimpan alamat "hash" dari block sebelumnya.

Tree

Tree adalah data-structure non linear yang merepresentasikan hubungan antara objek dalam data.


Node yang ada di paling atas disebut sebagai Node
Node yang tidak mempunyai children (cabang) disebut sebagai leaf
Node dan children nya dihubungkan dengan edge
Binary tree adalah tree yang setiap nodenya mempunyai paling banyak 2 children

Tipe-tipe dari binary tree

1.  Perfect binary tree
Adalah binary tree yang setiap nodenya mempunyai depth yang sama.
maksimum node dari perfect binary tree adalah 2^k-1.
dimana k adalah jumlah level.


2. Complete binary tree
Sama seperti perfect binary tree tetapi node yang berada di level paling bawah child nya bisa tidak ada.


3. Skewed binary tree
Adalah binary tree yang setiap node nya hanya mempunyai 1 cabang.


4. Balanced binary tree
Adalah binary tree yang ketika jumlah height di kiri - jumlah height di kanan = <=1.


Binary Search Tree

Setelah kemarin kita belajar tentang tree, sekarang kita belajar tentang binary search tree. apa itu binary search tree?

Binary search tree adalah data structure mirip seperti tree, namun ini adalah versi sorted nya. jadi data yang ada di dalam BST ini adalah data yang sudah di sort.

lalu bagaimana konsep sort nya?
pertama kita punya yang nama nya Root. biasanya data pertama yang masuk akan menjadi Rootnya.

jadi konsepnya adalah (ini berlaku untuk insertion)

1. Bandingkan data yang ingin dimasukkan dengan ROOT / Parent.
2. Jika data yang lebih kecil dari ROOT / Parent, data akan masuk ke sebelah kiri.
2.5. Jika data yang lebih besar dari ROOT / Parent, data akan masuk ke sebelah kanan.

proses ini akan di ulang terus sampai data berada di paling bawah atau menjadi leaf.







Lalu untuk Deletion konsepnya adalah :

Lakukan pencarian, dengan konsep insertion (jika data lebih kecil dari Root/parents ke sebelah kiri, dan jika lebih besar cari ke sebelah kanan). lalu setelah ketemu hapus node nya.

ada beberapa kasus dalam masalah deletion ini.

Kasus 1 : bila yang dihapus adalah node leaf.


Di kasus ini, yang ingin dihapus adalah data 21, dimana ini adalah leaf atau data yang paling bawah.

Lakukan pencarian, lalu delete node nya.

Kasus 2 : Bila yang dihapus adalah parent.


Di kasus ini, data 35 yang berupa parent akan dihapus, lalu bagaimana cara menentukan node pengganti nya?

Biasanya orang mempunyai 2 metode, 
Pilih node cabang kiri lalu cari data yang paling besar
Atau
Pilih node cabang kanan lalu cari data yang paling kecil.

Di gambar, kita menggunakan metode pertama.

Kasus 3 : Bila yang dihapus adalah rootnya.


Di kasus ini, yang dihapus adalah root nya, sama seperti kasus 2, pilih dari kiri yang paling besar, Atau dari kanan yang paling kecil.
Di gambar kita memilih kiri yang paling besar.

Sumber :
https://www.geeksforgeeks.org/linked-list-set-1-introduction/
https://media.geeksforgeeks.org/wp-content/uploads/CircularSinglLinkedList5.png
https://socs.binus.ac.id/2017/03/15/doubly-linked-list/
https://media.geeksforgeeks.org/wp-content/uploads/Circular-doubly-linked-list.png
https://www.geeksforgeeks.org/linked-list-set-2-inserting-a-node/
https://www.geeksforgeeks.org/linked-list-set-3-deleting-node/
https://www.researchgate.net/profile/Karim_Pichara/publication/322557308/figure/fig1/AS:588699666489344@1517368346649/The-generic-tree-data-structure-with-its-main-parts.png
https://www.barantum.com/blog/wp-content/uploads/2019/03/infographics-blockchain-1024x538.png


Comments

Post a Comment

Popular posts from this blog

Source code untuk Tugas GSLC

-
Source code untuk Tugas GSLC Aplikasi untuk jual beli barang Nama : Leander Ignacio Jose Antonius NIM : 2301922285 #include<stdio.h> #include<string.h> #include<stdlib.h> struct item { char namabarang[20]; int hargabarang; int quantitybarang; struct item *next; struct item *previous; }*head=NULL, *tail=NULL; void Printitem() { if(head==NULL&&tail==NULL) { printf("No Data\n"); } else { struct item *curr=head; int nomor=1; printf("==========================================\n"); while(curr!=NULL) { printf("Data %d\n",nomor); printf("Nama barang : %s\n",curr->namabarang); printf("Harga barang : %d\n",curr->hargabarang); printf("Jumlah barang : %d\n",curr->quantitybarang); curr=curr->next; printf("==========================================\n"); nomor++; } nomor=1; } } void Updateitem() { ...
Read more

Heaps and tries

-
Image
Video conference 12-5-2020 Heaps and Tries Heaps adalah sebuah binary tree yang isinya (nodenya) dapat direpresentasikan dalam sebuah array. cara memasukkan datanya adalah masukkan data dari array secara berurutan dari index 1-10 data pertamanya sebagai root, data ke 2 dan 3 sebagai left child dan right child, dan seterusnya. cara menghitung index x sebagai index menghitung index parent : x/2 menghitung index left child : 2*x menghitung index right child : (2*x)+1 misal kita mengambil node 18 yang memiliki index 4 (dari gambar di atas) untuk menghitung index parent (node 15) : 4/2=2 untuk menghitung index left child : 4*2=8 untuk menghitung index right child : (4*2)+1=9 Min heap dan max heap Min heap : setiap node pasti lebih kecil dari pada child node. angka terkecil yang ada di min heap pasti ada di rootnya. Insertion di Min heap ada 2 cara untuk insert di min heap cara 1 : Upheap Masukkan node seperti biasa, lalu bandingkan dengan node di atas...
Read more

Linked list - 002

-
Image
Linked list Rangkuman tanggal 3 maret 2020 Jadi di post ini saya akan merangkum materi yang disampaikan hari ini, dan juga materi yang ada di minggu pertama. Rangkuman minggu pertama Mulai dari cara mendeclare struct untuk linked list dan cara menambahkan node meng-set value ke node yang sudah dibuat dan meng-set penunjuk dari node ke node lain dengan ini kedua node yang baru saja kita buat sudah terhubung, dan jika kita print kedua node tadi kita bisa mengeprint node dengan cara printf("%d",node->value); printf("%d",node->next->value); Namun jika kita ingin membuat banyak node, akan lebih mudah jika kita membuat fungsi untuk membuat node fungsi ini untuk membuat node baru,cara menggunakannya adalah : struct tnode* node=node_maker(1); struct tnode* node1=node_maker(2); dan secara otomatis akan terbuat (node) yang berisi 1 dan (node1) yang terisi 2 namun disini kita tetap harus memberi tahu bahwa nod...
Read more