SUMMARY + Code Dreamers Market

A.  LINKED LIST

Linked list atau senarai berantai merupakan suatu kumpulan elemen bertipe sama yang berurutan sesuai dengan ketentuan tertentu. Setiap elemennya dihubungkan melalui pointer. Struktur data pada linked list ini terdiri dari urutan record data, yang masing-masingnya memiliki field untuk menyimpan alamat atau referensi dari record selanjutnya (dalam urutan).

Pada linked list, ada istilah node yang berarti elemen data yang dihubungkan dengan link pada linked list. Selain node, ada juga istilah head dan tail. Head adalah elemen yang berada di posisi pertama dalam linked list tersebut, sedangkan tail adalah elemen yang berada di posisi terakhir dalam linked list tersebut. Selain itu, istilah pointer berarti alamat elemen.

Macam-macam linked list yaitu sebagai berikut.

1. Circular Single Linked List

Arti dari single linked list sendiri adalah suatu kumpulan node yang berhubungan dengan node lain melalui pointer. Single linked list memiliki pointer Head untuk menunjuk node awal serta menyimpan alamatnya, dan juga diakhiri oleh node terakhir yang mengarah pointer ke null. Single linked list ini tidak dapat memiliki dua arah/bolak-balik. Single linked list hanya bisa memiliki satu arah.

2. Doubly Linked List

Doubly/double linked list bisa juga disebut two-way linked list. Linked list ini bisa memiliki dua arah/bolak-balik. Macam linked list ini terhubung oleh 2 bagian, yaitu untuk menunjuk ke data berikutnya dan untuk menunjuk ke data sebelumnya. Linked list ini merupakan suatu linked list yang memakai pointer dalam pengunaannya, yang nodenya memiliki masing-masing 3 field pointer, yang mencakup 1 field pointer prev, 1 field pointer next, dan field berisi data untuk node tersebut. Dengan adanya prev dan next, doubly linked list ini dapat diakses ke dua arah, yaitu ke depan dan belakang. Doubly linked list membutuhkan 2 variabel pointer (Head dan Tail). Head untuk menunjuk node pertama dan Tail untuk menunjuk node terakhir.

3. Circular Doubly Linked List

Seperti doubly linked list, circular doubly linked list ini menggunakan pointer yaitu prev dan next. Seperti namanya yaitu circular, linked list ini membentuk pola bundar yang berarti next dan prevnya menunjuk ke diri sendiri. Masing-masing node di linked list ini mempunyai field berisi data, juga memiliki pointer ke node berikutnya. Pada circular doubly linked list ini, variabel pointer Tail akan menunjuk ke Head.

B.  STACK AND QUEUE

1.    Stack

Stack, yang berarti tumpukan, merupakan kumpulan elemen-elemen data yang disimpan dalam satu lajur linear. Kumpulan elemen-elemen data hanya boleh diakses pada satu lokasi saja yaitu posisi atas tumpukan (TOP). Tumpukan digunakan dalam parsing, evaluation, dan backtrack. Elemen-elemen di dalam tumpukan dapat bertipe integer, real, record dalam bentuk sederhana atau terstruktur. Konsep utama yang digunakan stack yaitu LIFO (Last In First Out).

Array Representation

·       Stack memiliki dua variabel:

1)    TOP yang digunakan untuk menyimpan alamat elemen paling atas dari tumpukan

2)    MAX yang digunakan untuk menyimpan jumlah maksimum elemen yang dapat ditumpuk oleh stack

·       Jika TOP = NULL, maka menunjukkan bahwa tumpukan kosong

·       Jika TOP = MAX - 1, maka tumpukan penuh

·       TOP = 4, penyisipan dan penghapusan akan dilakukan pada posisi ini

Stack Operations

Operasi yang sering diterapkan pada struktur data stack (tumpukan) adalah Push dan Pop. Operasi yang dapat diterapkan yaitu sebagai berikut.

1.     Push : digunakan untuk menembah item pada stack pada tumpukan paling atas.

2.     Pop : digunakan untuk mengambil item pada stack pada tumpukan paling atas.

3.     Clear : digunakan untuk mengosongkan stack.

4.     Create Stack : membuat tumpukan baru S, dengan jumlah elemen kosong.

5.     MakeNull : mengosongkan tumpukan S, jika ada elemen maka semua elemen dihapus.

6.     IsEmpty : fungsi yang digunakan untuk mengecek apakah stack sudah kosong.

7.     Isfull : fungsi yang digunakan untuk mengecek apakah stack sudah penuh.

2.    Queue

Queue, yang berarti antrian, memiliki konsep yang hamper sama dengan stack. Perbedaan dari keduanya yaitu operasi penambahan dan penghapusan pada ujung yang berbeda. Penghapusan dilakukan pada bagian depan (front) dan penambahan berlaku pada bagian belakang (rear). Elemen di dalam antrian dapat bertipe integer, real, record dalam bentuk sederhana atau struct. Sistem pengaksesan pada Queue yaitu menggunakan system FIFO (First In First Out), artinya elemen yang pertama masuk itu yang akan pertama dikeluarkan dari Queue.

Array Representation

Sama halnya seperti stack, queue pada array juga memiliki 2 variabel, yaitu variabel FRONT dan REAR yang menunjuk ke posisi dimana insert dan delete dapat dilakukan masing-masing. Front adalah variabel yang menunjuk posisi pertama dalam antrian, dan rear adalah variabel yang menunjuk posisi terakhir dalam antrian. Berikut merupakan gambarannya.

Linked List Representation

Linked list pada queue juga sama seperti pada stack, elemennya pun disebut node dan memiliki bagian yang sama. Hanya saja pointer START pada queue digunakan sebagai FRONT. Proses penambahan node dilakukan pada bagian Rear dan penghapusan node dilakukan pada bagian Front. Jika FRONT = REAR = NULL, maka Queue dinyatakan kosong, atau belum memiliki node. Berikut merupakan gambarannya.

Queue Operations

Operasi yang digunakan dalam queue adalah sebagai berikut.

1.     Push :  Menambah item pada bagian belakang/rear suatu queue.

2.     Pop  : Menghapus item pada bagian depan/front suatu queue.

3.     Front : Mengembalikan item yang paling depan dalam suatu queue. Front dikenal juga sebagai Peek.

C.  HASHING TABLE AND BINARY TREE

Hashing 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. Ide utama dari hashing adalah mengubah suatu string menjadi suatu bilangan dengan suatu fungsi. Hash table menggunakan suatu teknik penyimpanan sehingga waktu yang dibutuhkan untuk penambahan data (insertions), penghapusan data (deletions), dan pencarian data (searching) relatif sama dibanding struktur data atau algoritma yang lain.

Yang perlu diperhatikan untuk membuat hash function adalah:

-       ukuran array/table size(m),

-       key value/nilai yang didapat dari data(k),

-       hash value/hash index/indeks yang dituju(h).

Beberapa struktur data dan algoritma pencarian (searching) yang memiliki kelebihan dan kekurangan masing-masing. Begitu pula dengan hash table ini juga memiliki kekurangan dan kelebihan. Kelebihan dari hash table antara lain sebagai berikut:

-       Hash table relatif lebih cepat

-       Kecepatan dalam insertions, deletions, maupun searching relatif sama

Hash table 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. Dengan key value tersebut didapat hash value. Jadi hash function merupakan suatu fungsi sederhana untuk mendapatkan hash value dari key value suatu data.

Sebenarnya fungsi hashing itu bebas, terserah Anda ingin mendefinisikannya seperti apa. Namun, diharapkan fungsi hashing memiliki kriteria sebagai berikut:

-       Untuk dua buah key yang sama, hasil hashing-nya selalu sama.

-       Memiliki kompleksitas rendah.

-       Meminimalkan collision (akan dijelaskan pada bagian selanjutnya).

Binary Tree

Binary Tree adalah tree dengan syarat bahwa tiap node hanya boleh memiliki 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 child.

Jenis-jenis Binary Tree :

a) Full Binary Tree

Binary Tree yang tiap nodenya (kecuali leaf) memiliki dua child dan tiap subtree harus mempunyai panjang path yang sama.

b) Complete Binary Tree

Mirip dengan Full Binary Tree, namun tiap subtree boleh memiliki panjang path yang berbeda. Node kecuali leaf memiliki 0 atau 2 child.

c) Skewed Binary Tree

yakni Binary Tree yang semua nodenya (kecuali leaf) hanya memiliki satu child.

Implementasi Binary Tree

Contoh ilustrasi Tree yang disusun dengan double linked list :

(Ket: LC=Left Child; RC=Right Child)

HASH IN BLOCK CHAIN

Secara sederhana, hashing berarti mengambil string input dengan panjang berapapun dan memberikan output dengan panjang tetap. Dalam konteks cryptocurrency seperti bitcoin, transaksi diambil sebagai input dan dijalankan melalui algoritma hashing (bitcoin menggunakan SHA-256) yang memberikan output dengan panjang tetap. SHA-256 adalah Secure Hashing Algorithm 256.

Blockchain adalah daftar tertaut yang berisi data dan pointer hash yang menunjuk ke blok sebelumnya, sehingga menciptakan rantai. Hash pointer yaitu sebuah pointer yang bukan hanya berisi alamat dari blok sebelumnya, tetapi juga berisi hash dari data di dalam blok sebelumnya.

D.  BINARY SEARCH TREE

Binary Search Tree (BST) adalah Binary Tree dengan sifat bahwa semua left child harus lebih kecil daripada right child dan parentnya. Juga semua right child harus lebih besar dari left child serta parentnya.

Kenapa harus membedakan kiri dan kanan sesuai besaran nilainya? Tujuannya untuk memberikan efisiensi terhadap proses searching. Jika struktur data tree sudah tersusun rapi sesuai aturan mainnya, proses search akan lebih cepat.

Aturan main Binary Search Tree :

-          Setiap child node sebelah kiri harus lebih kecil nilainya daripada root nodenya.

-          Setiap child node sebelah kanan harus lebih besar nilainya daripada root nodenya.

Lalu, ada 3 jenis cara untuk melakukan penelusuran data (traversal) pada BST :

-          PreOrder : Print data, telusur ke kiri, telusur ke kanan

-          InOrder : Telusur ke kiri, print data, telusur ke kanan

-          PostOrder : Telusur ke kiri, telusur ke kanan, print data

Operasi di BST

Pada dasarnya operasi dalam binary search tree sama dengan Binary tree biasa, kecuali pada operasi insert, update, dan delete.

1.     Insert : Pada Binary Search Tree, insert dilakukan setelah ditemukan lokasi yang tepat. (Lokasi tidak ditentukan oleh user sendiri).

2.     Update : Seperti pada Binary Tree biasa, namun disini update akan berpengaruh pada posisi node tersebut selanjutnya. Bila setelah diupdate mengakibatkan tree tersebut bukan Binary Search Tree lagi, maka harus dilakukan perubahan pada tree dengan melakukan perubahan pada tree dengan melakukan rotasi supaya tetap menjadi Binary Search Tree.

3.     Delete : Seperti halnya update, delete dalam Binary Search Tree juga turut mempengaruhi struktur dari tree tersebut.

E.  CODING DREAMERS MARKET

Berikut merupakan contoh code dari pemahaman di atas :

https://drive.google.com/file/d/15GQENlFE9ZAAWbYu6HAM_qt-nL26rQbE/view?usp=sharing

Nama : Melody Effendi
Jurusan : Teknik Informatika dan Statistika
NIM : 2301925854