Petani x Jagung: Summary Semester 2 Before UTS

Linked List

Linked list (bahasa Indonesia : senarai berantai) adalah sebuah struktur data yang digunakan untuk menyimpan sejumlah objek data. Linked list disimpan secara terurut sehingga lebih memungkinkan atas efektifnya penambahan, pengurangan, dan pencarian atas elemen data. Linked list merupakan sekumpulan nodes yang merepresentasikan sebuah sequence, dimana nodes merupakan koleksi linear dari data. Setiap node tersebut akan menunjukkan node lain melalui sebuah pointer.

Operasi – Operasi Linked List :

1. Insert : menambahkan sebuah simpul baru ke dalam suatu linked list.

2. IsEmpty : menentukan apakah linked list kosong atau tidak.

3. Find First : mencari elemen pertama dari linked list.

4. Find Next : mencari elemen sesudah elemen yang ditunjuk now.

5. Retrieve : mengambil elemen yang ditunjuk oleh now. Elemen tersebut lalu dikembalikan oleh fungsi.

6. Update : mengubah elemen yang ditunjuk oleh now dengan isi dari sesuatu.

7. Delete Now : menghapus elemen yang ditunjuk oleh now. Jika yang dihapus adalah elemen pertama dari linked list (head), head akan berpindah ke elemen berikutnya.

8. Delete Head : menghapus elemen yang ditunjuk head. Head berpindah ke elemen sesudahnya.

9. Clear : menghapus linked list yang sudah ada. Fungsi ini wajib dilakukan bila anda ingin mengakhiri program yang menggunakan linked list. Jika anda melakukannya, data-data yang dialokasikan ke memori pada program sebelumnya akan tetap tertinggal di dalam memori.

Jenis – Jenis Linked List :

1. Single Linked List

Single Linked List (bahasa Indonesia : senarai tunggal) hanya memiliki satu tautan atas node berikutnya dalam sebuah linked list. Dalam single linked list, ada satu pointer yaitu pointer head yang menunjuk ke node selanjutnya.

(Sumber : https://www.geeksforgeeks.org/linked-list-set-1-introduction/)

2. Double Linked List

Berbeda dengan single linked list, double linked list memiliki pointer penunjuk dua arah yaitu kearah node sebelum dan node sesudah. Struktur data atas tiap node memiliki rujukan pada node sebelum dan berikutnya.

(Sumber : https://www.geeksforgeeks.org/doubly-linked-list/)

3. Circular Linked List

Pada circular linked list, rujukan pada node terakhir akan merujuk pada node pertama, dan begitu juga sebaliknya bila yang digunakan sebagai dasar implementasi adalah double linked list.

(Sumber : https://www.geeksforgeeks.org/doubly-circular-linked-list-set-1-introduction-and-insertion/)

Stack dan Queue

Pengertian Stack

(Sumber : https://github.com/yasincidem/Stack)

Stack (bahasa Indonesia : tumpukan) dalam ilmu komputer adalah suatu kumpulan data yang menggunakan prinsip data yang terakhir dimasukkan akan dikeluarkan pertama dari tumpukan tersebut. Dengan kata lain kumpulan data seolah-olah akan terlihat seperti ada data yang diletakkan di atas data lain. Stack tersebut dapat diimplementasikan sebagai representasi berkait (kontigu).

Operasi Stack

1. InsertFirst() – menambahkan sebuah elemen ke tumpukan

2. DeleteFirst() – menghapus sebuah elemen tumpukan

3. IsEmpty() – mengecek stack kosong atau sudah ada elemennya

4. IsFull() – mengecek stack sudah penuh atau belum

5. Clear() – menghapus semua data

6. Peek() – melihat data TOP

Queue

(Sumber : https://en.wikipedia.org/wiki/Queue_(abstract_data_type))

Queue (bahasa Indonesia : antrian) dalam ilmu komputer adalah suatu kumpulan struktur data linear dimana ada penambahan komponen yang hanya dapat dilakukan pada satu sisi (belakang/depan) dan pengurangan dilakukan di ujung lain.

Operasi Queue

1. Create() – menciptakan menginisialisasi queue

2. IsEmpty() – memeriksa apakah antrian sudah penuh atau belum

3. IsFull() – mengecek apakah sudah penuh atau belum

4. Enqueque() – menambah elemen ke dalam antrian

5. Dequeque() – menghapus elemen terdepan (head) dari antrian

6. Clear() – menghapus elemen antrian dengan cara membuat tail dan head = -1

7. Tampil() – menampilkan nilai-nilai elemen antrian

Notasi Prefix, Infix, dan Postfix

No.	Infix	Prefix	Postfix
1.	A + B	+ A B	A B +
2.	(A + B) * C	* + A B C	A B + C *
3.	A * (B + C)	* A + B C	A B C + *

1. Prefix, notasi yang terbentuk dari operator dan operand dengan menggunakan metode penulisan operator di depan operand.

2. Infix, notasi yang terbentuk dari operator dan operand dengan meletakkan operator di antara dua operand (dengan tanda kurung).

3. Postfix, notasi yang terbentuk dari operator dan operand dengan menuliskan operator setelah operand (tanpa tanda kurung).

Hashing Table and Binary Tree

Pengertian Hash Table

Hash table dalam ilmu komputer merupakan sebuah struktur data yang digunakan untuk menyimpan data sementara. Hashing adalah teknik untuk melakukan penambahan, penghapusan dan pencarian dengan constant average time. Hashing digunakan untuk menyimpan data yang cukup besar pada abstract data type (ADT). Selain itu, hashing juga digunakan untuk mempercepat pencarian dalam tabel data atau pembandingan data seperti di dalam database, mencari kesamaan dan sebagainya.

Fungsi Hash

1. Mid square

Mid square adalah teknik hashing yang menghasilkan key unik. Teknik ini dapat mengambil nilai dan dapat dikuadratkan. Sehingga dapat menghasilkan key dengan keacakan tinggi jika mengambil nilai yang cukup besar. Untuk mendapatkan alamat relatif, nilai key dikuadratkan lalu beberapa digit diambil dari tengah.

Fungsi : h(k) = s

Contoh :

Key	Squared Value	Middle Part
3121	9740641	406
3122	9746884	468
3123	9753129	531

2. Division

Fungsi : h(z) = z mod M

Metode division sering menghasilkan nilai hash yang sama dari dua atau lebih nilai aslinya (bentrokan). Sehingga, dibutuhkan mekanisme khusus untuk menangani bentrokan tersebut yaitu dengan kebijakan resolusi bentrokan. Alamat relatif dari nilai key adalah sisa dari hasil pembagian nilai key dengan bilangan pembagi.

Contoh :

ABCD	(64 + 1 + 64 + 2 + 64 + 3 + 64 + 4) % 97	76
HIKE	( 64 + 8 + 64 + 9 + 64 + 11 + 64 + 5) % 97	2
PPQQ	( 64 + 16 + 64 +16 + 64 + 17 + 64 + 17) % 97	35
COBB	( 64 + 3 + 64 + 15 + 64 + 2 + 64 + 2) % 97	88

3. Folding

Folding dapat dipecah menjadi beberapa bagian, kemudian tiap bagian akan digabungkan lagi ke dalam bentuk yang lain untuk mendapatkan hash key.

Contoh :

Phone Number	3 Group	Index
5373737	53 + 73 + 737	863
5125858	51 + 25 + 858	934
5315151	53 + 15 + 151	219

4. Collision

Bila terjadi collision (tabrakan) akan diselesaikan dengan menggunakan collision resolution. Collision terjadi jika dua buah keys dipetakan pada sebuah sel. Ada 2 buah cara untuk menangai collision :

1) Linear Probing

Linear probing adalah salah satu cara untuk menemukan lokasi record yang tak dapat disimpan di home addressnya. Linear probing ini merupakan sebuah pencarian secara sequential (linear) dari home address sampai lokasi yang kosong.

h[ ]	Value	Step
0	atan	1
1	acos	2
2	char	1
3	define	1
4	exp	1
5	float	1
6	ceil	5
7	floor	3

2) Chaining

Chaining dapat mengakses synonym dengan fasilitas link list untuk record daam kelas ekivalen. Link list record dengan home address yang sama tidak akan mengurangi jumlah collision, melainkan akan mengurangi waktu akses untuk me-retrieve record yang tidak terdapat di home addressnya.

h[ ]	Value
0	atan -> acos
1	NULL
2	char -> ceil
3	define
4	exp
5	float -> floor
6	NULL
7	NULL

Implementasi Hashing Table Pada Block Chain

Implementasi hashing table pada block chain dapat menggunakan algoritma hashing SHA-256. Ini dapat memberikan bukti kriptografi untuk otentikasi dan integritas data. Fungsi hash kriptografi tersebut adalah untuk mengambil data dari blok sebelumnya dan mengubahnya menjadi compact string yang memungkinkan sistem mendeteksi adanya sabotase. Hash ini merupakan sebuah algoritma yang memetakan data secara acak ke dalam bentuk string yang berukuran tetap. Hash ini dirancang untuk dapat menjadi sebuah fungsi satu arah. Hash memungkinkan setiap blok dapat memverifikasi integritasnya sehingga setiap blok tidak perlu memiliki nomor seri.

Binary Tree

Dalam ilmu komputer, binary tree (bahasa Indonesia : pohon biner) adalah sebuah pohon dalam struktur data yang memiliki simpul paling banyak dua anak pada setiap simpulnya. Binary tree ini setiap nodenya memiliki paling banyak dua anak dan dinamakan dengan anak kiri dan anak kanan.

Node Pada Binary Tree

(Gambar : http://syafrinafarahdila.blogspot.com/2018/04/tree.html)

Tipe Binary Tree

1. Perfect Binary Tree

Perfect binary tree adalah sebuah binary tree yang semua daunnya memiliki kedalaman yang sama.

2. Complete Binary Tree

Complete binary tree adalah sebuah binary tree yang di mana semua daunnya memiliki kedalman n atau n-1 untuk beberapa n. Semua anak pada tingkat terakhir harus menempati titik paling kiri secara teratur dengan tidak ada titik yang menganggur di antara keduanya.