Summary Martin Leonardo Hermawan 2301873043

Summary

Linked List

Linked list atau senarai berantai adalah sebuah struktur data yang digunakan untuk meyimpan sejumlah objek data biasanya secara terurut sehingga operasi penambahan, pengurangan, dan pencari data yang tersimpan dapat dilakukan dengan lebih mudah tentunya lebih cepat. Dalam suatu linked list, pasti ada yang namanya head dan tail. Head adalah elemen yang berada pada posisi pertama suat linked, sedangkan tail adalah elemen yang berada pada posisi terakhir suatu linked list. Dalam linked list, selalu ada function push dan pop.
- Push
Push sendiri dibagi menjadi 3, yaitu :
Push head : untuk menginput data dari depan
Push tail : untuk menginput data dari belakang
Push mid : untuk menginput data ke tengah dan biasanya sudah sorted

- Pop
Pop juga dibagi 3, yaitu :
Pop head : untuk mendelete data paling depan
Pop tail : untuk mendelete data paling belakang
Pop : untuk mendelete data sesuai inputan user

Linked list sendiri memiliki 3 jenis yaitu single linked list, double linked list, dan circular linked list.

1. Single Linked List

Single linked list adalah sebuah linked list yang hanya memiliki satu buah pointer dan pointer tersebut hanya menunjuk ke node berikutnya. Oleh karena itu, biasanya tail menunjuk NULL.

Contoh :

2. Double Linked List

Double linked list adalah sebuah linked list yang memiliki 2 buah pointer. Pointer pertama menunjuk ke node berikutnya, sedangkan pointer kedua menunjuk ke node sebelumnya. Selain itu, setiap head dan tail juga menunjuk ke NULL.
Contoh :

3. Circular Linked List

Circular linked list adalah suatu single atau double linked list yang node terakhirnya menunjukk ke node awal, node awal menunjuk ke node terakhir. Oleh karena itu, linked list ini disebut circular karena seperti terus mengular atau berputar. Ada 2 jjenis circular linked list, yaitu single linked list dan double linked list
- Circular Single Linked List
   Contoh :

- Circular Double Linked List

   Contoh :

Stack and Queue

Stack

Stack adalah kumpulan elemen-elemen data yang disimpan dalam satu lajur linear. Kumpulan elemen data hanya boleh diakses pada satu lokasi saja yaitu posisi atas. Konsep utama yang digunakan adalah LIFO.

Queue

Queue merupakan suatu struktur data linear. Konsepnya hampir sama dengan stack perbedaannya adalah operasi penambahan dan penghapusan apda ujung yang berbeda. Penghapusan dilakukan pada bagian depan dan penambahan berlaku pada bagian belakang.

Hashing

Hashing berasal dari kata hash yaitu suatu kode hasil enkripsi yang biasanya terdiri atas huruf ataupun angka yang acak. Hash berfungsi untuk mempercepat pencarian data misalnya dalam sebuah tabel data. Oleh karena itu, hashing digunakan untuk menyimpan data dalam sebuah array sehingga proses prnyimpanan, pencarian, penambahan, dan penghapusan data dapat dilakukan dengan cepat. Hashing juga dapat dikatakan transformasi aritmatik sebuah string karakter menjadi nilai yang merepresentasikan string aslinya. Ide dasar hashing adalah menghitung posisi record yang dicari dalam array. Fungsi yang digunakan adalah fungsi hash atau biasa disebut hash function. Array yang digunakan dalam hasing disebut hash table yang menggunakan struktur data array asosiatif yang mengasosiasikan record dengan sebuah field kunci unik berupa bilangan (hash) yang merupakan representasi dari record tersebut.

Fungsi hash menyimpan nilai asli atau kunci pada alamat yang sama dengan nilai hashnya. Pertama, akan dilakukan penghitungan nilai hash dari kuncinya. Lalu, kunci dibandingkan dengan isi pada memori yang beralamatkan nomor hashnya. Oleh karena itu, fungsi ini dapat berjalan dengan cepat.

Hashing sangat berguna dalam blockchain, hash sangat berguna dalam memecahkan data yang terenkripsu untuk menyelesaikan perhitungan blockchain. Hash memiliki panjang yang tetap karena tidak mungkin seseorang menebak panjang hash untuk memecahkan blockchain.

Ada beberapa cara untuk mengubah string menjadi key dalam fungsi hash. Cara-cara tersebut adalah
1. Division
2. Multiplication
3. Mid Square
4. Folding
5. Digit Extraction
6. Rotating hash

Dalam hashing ada yang disebut collision, yaitu adanya tabrakan antara kunci hash dikarenakan adanya record yang memiliki key yang sama. Ada 2 cara untuk menyelesaikan collision, yaitu :
1. Linear Probing
2. Chaining

Binary Tree

Binary tree adalah sebuah pohon struktur data dimana setiap node memilki paling banyak dua cabang. Biasanya cabang-cabangnya disebut kiri dan kanan.

Ada 4 jenis binary tree, yaitu :

1. Perfect binary tree : binary tree dimana tiap level berada pada kedalaman yang sama

2. Complete binary tree : binary tree dimana tiap level semuanya terisi kecuali biasanya yang terakhir dan biasanya semua node berada di kiri.

3. Skewed binary tree : binary tree dimana setiap node paling banyak memiliki 1 cabang/anak

4. Balanced binary tree : binary tree dimana tidak ada daun yang lebih jauh dari akar daripada daun lainnya.

Binary tree selalu memiliki data, pointer untuk cabang kiri/anak kiri, dan pointer untuk cabang kanan/anak kanan.

struct node {
   int data;   
   struct node *leftChild;
   struct node *rightChild;
};