SUMMARY OF DASTRUCT'S MATERIALS 


Linked List

Linked list adalah salah satu bagian dari struktur data yang berisikan kumpulan record data dimana setiap record data menyimpan alamat dari data selanjutnya.  Posisi pertama linked list biasanya disebut head, dan posisi terakhir biasanya disebut tail. Ada beberapa macam linked list :

1. Single Linked List

Single linked list adalah linked list yang hanya memiliki 1 variabel pointer untuk menunjuk ke data selanjutnya. Pointer ini biasa disebut next, dimana pointer ini akan berupa NULL saat ada di tail.

2. Double Linked List

Double linked list adalah linked list yang memiliki 2 variabel pointer, yaitu untuk menunjuk ke data selanjutnya dan juga data sebelumnya, biasa disebut pointer next dan prev. Pointer next akan berupa NULL saat di tail, dan pointer prev akan berupa NULL saat di head.

3. Circular Linked List

Circular Linked List merupakan suatu linked list dimana tail menunjuk ke head. Jadi tidak ada pointer yang menunjuk NULL.

4. Multiple Linked List

Multi Linked List Merupakan Suatu Linked List yang Memiliki Lebih dari 2 buat variabel pointer.


Stack and Queue

1. Stack 

Stack adalah salah satu konsep data structure dimana elemen-elemen yang disimpan dalam lajur linear. Konsep ini mudah dipahami dengan contoh tumpukan piring, dimana piring terakhir yang ditumpuk akan menjadi piring pertama yang diambil. Istilah ini disebut LIFO yang merupakan singkatan dari Last In, First Out. Dalam stack, elemen yang terakhir dimasukkan akan menjadi yang pertama untuk diproses. Stack dapat diimplementasikan dengan Array maupun Linked List. Seperti yang kita ketahui, jika mengimplementasikannya dengan array maka kapasitas elemen akan bersifat statis. Berbeda dengan menggunakan linked list yang akan bersifat dinamis. Ada beberapa operasi yang dapat dilakukan dalam konsep stack:
1. push (x) , yaitu untuk menginsert elemen
2. pop (), yaitu untuk menghapus elemen, dan
3. top (), yaitu untuk mengembalikan elemen
semua operasi tersebut akan dilakukan dari stack paling atas atau elemen terakhir yang diinputkan.

2. Queue

Queue adalah salah satu konsep data structure yang memiliki kemiripan dengan Stack. Perbedaannya adalah elemen yang pertama kali dimasukkan akan diproses terlebih dahulu. Konsep ini mirip dengan proses mengantri. Sebut saja saat mengantri tiket bioskop. Orang yang lebih dulu mengantri akan dilayani terlebih dahulu, disebut juga dengan istilah FIFO, yang merupakan singkatan dari First In, First Out. Sama seperti stack, queue juga dapat diimplementasikan dengan array maupun linked list. Operasi yang dapat dilakukan dalam konsep queue:
1. push (x), yaitu menginsert elemen
2. pop (), yaitu untuk menghapus elemen, dan
3. front (), yaitu untuk mengembalikan elemen
semua operasi tersebut akan dilakukan dari elemen yang pertama kali diinputkan.

Infix, Postfix, dan Prefix

Contoh:
infix    : 4*10
prefix  : *4 10
postfix : 4 10*

Contoh lain : (contoh ini merupakan soal dari kelas data structure)
infix     :((1+3) / (100*5) ^30)
prefix   : /+ 1 3 ^*100 5 30
postfix  : 1 3 + 100 5 * 30^/

Umumnya, kita sehari-hari menggunakan notasi infix saat berhitung, namun mesin komputer lebih mudah menghitung dengan notasi postfix dan prefix. Notasi prefix dapat digunakan dengan konsep stack, dimana angka/ operand (dibaca dari paling belakang) akan dimasukkan kedalam stack hingga bertemu dengan operator. Saat bertemu operator, maka angka terakhir yang dimasukkan akan dioperasikan dengan angka sebelumnya. Sebaliknya, notasi postfix menggunakan konsep queue yang caranya sama dengan prefix. Hanya saja dibaca dari depan.

Hash Table and Binary Tree

1. Hashing dan Hash Table

Hashing merupakan teknik yang digunakan untuk menyimpan dan mengambil key secara cepat. Dalam hashing, sebuah string diubah ke dalam value yang lebih kecil/pendek yang disebut key. Key sendiri merepresentasikan string tersebut. Dengan hashing, maka pengambilan elemen dalam database akan lebih cepat karena string sudah diubah ke dalam bentuk yang lebih pendek. Teknik hashing didefine dalam Hash Table dan menggunakan function yang disebut Hash Function.

Hash Table merupakan tabel (array) untuk menyimpan string asli. Indexnya disebut key, sedangkan stringnya adalah value. Contoh:
ada 5 string, yaitu "budi","caca","ella","andi",dan"farel". Dengan size hash table sebesar 26. Maka, hash function yang digunakan untuk memasukkan string-string tersebut ke dalam hash table adalah = ubah character pertama dari setiap string menjadi angka 0-25 (a=0, b=1, c=2, ...,z=25). Maka hash table yang terbentuk adalah:

Beberapa operasi yang dapat dilakukan di hash table adalah:
  • insert: diberikan sebuah key dan nilai, insert nilai dalam tabel
  • find: diberikan sebuah key, temukan nilai yang berhubungan dengan key
  • remove: diberikan sebuah key,temukan nilai yang berhubungan dengan key, kemudian hapus nilai tersebut
  • getIterator: mengambalikan iterator,yang memeriksa nilai satu demi satu

Selain itu, beberapa cara untuk mengubah string ke dalam key (hash function) adalah:

  • Mid-square
  • Division
  • Folding
  • Digit Extraction
  • Rotating Hash
Setelah mengetahui tentang Hashing,hash table dan hash function, ada juga istilah "Collision" yaitu kejadian dimana record-record dalam hash table bertabrakan karena memiliki index/key yang sama. 

Implementasi hashing table dalam blockchain

Dalam konteks cryptocurrency seperti bitcoin, transaksi diambil sebagai input dan dijalankan melalui algoritma hashing yang memberikan output dengan panjang tetap. Bitcoin menggunakan SHA(Secure Hashing Algorithm) -256. tidak peduli seberapa besar/kecil inputan, output akan selalu memiliki panjang 256-bit. Jadi, hash akan membantu kita untuk tidak perlu mengingat input daya yang bisa jadi besar. 

contoh:
input = This is a test
Hash = C7BE1ED902FB8DD4D48997C6452F5D7E509FBCDBE2808B16BCF4EDCE4CO7D14E

input= Hi
Hash = 639EFCD08ABB273B1619E82E78C29A7DF02C1051B1820E99FC395DCAA3326B8

2. Binary Tree

Binary tree adalah tree yang setiap node nya memiliki jumlah maksimal anak yaitu 2. node yang tidak memiliki anak sama sekali disebut leaf.


Beberapa tipe binary tree:
  • Perfect binary tree = adalah sebuah pohon biner penuh di mana semua daun memiliki kedalaman yang sama
  • Complete binary tree = dapat didefinisikan juga sebagai sebuah pohon biner penuh di mana semua daunnya memiliki kedalaman n atau n-1 untuk beberapa n. Agar sebuah pohon dapat menjadi sebuah pohon biner lengkap, semua anak pada tingkat terakhir harus menempati titik terkiri secara teratur, dengan tidak ada titik yang menganggur di antara keduanya
  • Skewed binary tree = binary tree yang setiap nodenya maksimal memiliki 1 anak
  • Balanced binary tree = binary tree yang sub kiri dan kanannya memiliki ketinggian sama, atau maksimal berbeda 1 level.
Konsep binary tree dalam data structure dapat diimplementasikan dalam array maupun linked list.























Comments

Post a Comment

Popular Posts