Data Structures - Linked List

AVL Tree
AVL Tree merupakan salah satu jenis BST (binary Search Tree) yang memiliki perbedaan tinggi/ level maksimal 1 antara subtree kiri dan subtree kanan. AVL Tree dibentuk untuk menyeimbangkan Binary Search Tree, supaya waktu pencarian dan bentuk tree dapat dipersingkat dan disederhanakan.

(Sumber: https://medium.com/@aksh0001/avl-trees-in-python-bc3d0aeb9150)

Metode penyeimbang ini dibagi menjadi 4 metode berdasarkan kondisi tree setelah melakukan insert, yaitu :

Kasus 1 : node terdalam terletak pada subtree kiri dari anak kiri T (left-left)
Kasus 2 : node terdalam terletak pada subtree kanan dari anak kanan T (right-right)
Kasus 3 : node terdalam terletak pada subtree kanan dari anak kiri T (right-left)
Kasus 4 : node terdalam terletak pada subtree kiri dari anak kanan T (left-right)

*T adalah node yang harus diseimbangkan kembali.

B-Tree
B-tree adalah suatu metode untuk menyimpan dan menemukan suatu file (disebut juga records atau keys) dalam suatu database. Algoritma b-tree meminimalkan jumlah dari media yang harus dilalui untuk mencapai suatu record database yang diinginkan sehingga akan mempercepat proses.

(Sumber: https://dzone.com/articles/database-btree-indexing-in-sqlite)

Aturan pada B-Tree : m = order

Setiap node (kecuali leaf) memiliki anak paling banyak sejumlah m anak
Setiap node (kecuali root) memiliki anak paling sedikit m/2 anak
Root memiliki anak minimal 2, selama root bukan leaf
Jika node non leaf memiliki k anak, maka jumlah data yang tersimpan dalam node k-1
Data yang tersimpan pada node harus terurut secara inorder
Semua leaf berada pada level yang sama, level terbawah

Dalam prakteknya b-tree bisa memiliki ribuan atau jutaan record. Tidak harus semua leaves memiliki suatu record, namun paling tidak adalah separuhnya harus memiliki. Perbedaan depth antara skema b-tree dan binary-tree adalah dalam penggunaan di sebuah sistem database dimana b-tree bisa memiliki order yang lebih tinggi, misalnya 32,64,128 atau lebih..

Contoh Insert dan Delete AVL Tree

Link :
https://drive.google.com/file/d/1C3H8-sHIGwofuIQzMR3DArwK22WrKfZ0/view?usp=sharing

Contoh Insert dan Delete B-Tree

Link :
https://drive.google.com/file/d/1Q0oz4jwEjYyulGO0fhvr0Y1uOQR4oxOJ/view?usp=sharing

Linked List atau dikenal juga dengan sebutan senarai berantai adalah struktur data yang terdiri dari urutan record data dimana setiap record memiliki field yang menyimpan alamat/referensi dari record selanjutnya (dalam urutan). Elemen data yang dihubungkan dengan link pada Linked List disebut Node.

Linked List dan Array

(Sumber: https://www.pinterest.se/pin/741757001101474327/)

Array

Variable bertipe array adalah suatu tipe data yang bersifat statis (urutan dan ukuran sudah pasti). Kelemahan dari array statis adalah penggunaan ruang memori yang sudah digunakan tidak dapat dihapus apabila nama variable array tersebut sudah tidak digunakan kembali dalam suatu program (penyebab kemubaziran).

Circular Linked List

(Sumber: https://algorithms.tutorialhorizon.com/circular-linked-list-complete-implementation/)

Double Linked List merupakan suatu linked list yang memiliki dua variabel pointer yaitu pointer yang menunjuk ke node selanjutnya dan pointer yang menunjuk ke node sebelumnya. Setiap head dan tailnya juga menunjuk ke NULL.

Doubly Linked List

(Sumber: https://www.studytonight.com/data-structures/doubly-linked-list)

Double Linked List adalah Linked List yang simpul terakhirnya menunjuk ke simpul awal, dan simpul awalnya menunjuk ke simpul akhir, atau dapat disebut Linked List yang dibuat seakan-akan merupakan sebuah lingkaran dengan titik awal dan titik akhir saling bersebelahan jika Linked List tersebut masih kosong.

Konsep Stack

(Sumber: https://dev.to/rinsama77/data-structure-stack-and-queue-4ecd)

Stack adalah metode atau teknik dalam menyimpan atau mengambil data ke dan dari memori. Stack dapat diibaratkan sebuah tumpukan dalam suatu tempat yang hanya memiliki suatu pintu diatasnya. kaidah stack adalah First In Last Out atau Last In First Out (LIFO), benda yang terakhir masuk akan menjadi benda yang pertama dikeluarkan.

Notasi Infix, Postfix, dan Prefix

(Sumber: http://risasisteminformasi.blogspot.com/2013/02/notasi-prefixinfix-dan-postfix.html)

Notasi ini terbentuk dari Operand dan Operator. Operand adalah data atau nilai yang membantu dalam proses,sedangkan Operasi adalah fungsi yang digunakan dalam proses. Setelah kita mengenal dan mengetahui dengan Operand dan Operator, maka mari kita mengenal juga tingkat/ level yang ada didalam notasi tersebut:

1. ( ) (Kurung).

2. ^ (Pangkat).

3. * / (Perkalian / Pembagian).

4. + - (Penjumlahan / Pengurangan).

1. Infix : notasi yang terbentuk atas operator dengan operand, dimana oprator didepan operand.

2. Postfix : notasi yang membentuk atas operator dengan operand, dimana operator berada diantara operand.

3. Prefix : notasi yang membentuk atas operator dengan operand, dimana operator berada dibelakang operand.

Contoh : A + B * C

maka notasi postfix adalah ABC*+.

Konsep Queue

(Sumber: https://saungkode.wordpress.com/2014/04/10/konsep-queue-antrian-pada-struktur-data/)

Prinsip kerja Queue adalah FIFO (First In First Out), di mana data yang masuk terlebih dahulu akan keluar pertama.

Binary Search Tree

adalah struktur data yang mengadopsi konsep Binary Tree namun terdapat aturan bahwa setiap clild node sebelah kiri selalu lebih kecil nilainya dari pada root node. Begitu pula sebaliknya, setiap child node sebelah kanan selalu lebih besar nilainya daripada root node.

(Sumber: https://www.programiz.com/dsa/binary-search-tree)

Ciri-ciri:

Setiap node mempunyai value dan tidak ada value yang double.
Value yang ada di kiri tree lebih kecil dari rootnya.
Value yang ada di kanan tree lebih besar dari rootnya.
kiri dan kanan tree bisa menjadi root lagi atau bisa mempunya child Jadi BST ini memiliki sifat (rekrusif).

Binary Search Tree Operations

Operasi insert, pada binary search tree insert dilakukan setelah ditemukan lokasi yang tepat. (lokasi tidak ditemukan oleh user sendiri).
Operasi search, pencarian dalam binary search tree untuk suatu nilai key dapat dilakukan secara recursive maupun dengan proses iterative.
Operasi Delete, operasi delete diakukan terhadap node dengan 2 child, maka untuk menggantikannya, diambil node paling kiri dari right subtree

Hashing Table

(Sumber : https://medium.com/dev-blogs/ds-with-js-hash-table-4715c94083d2)

Hash Table adalah sebuah struktur data yang terdiri atas sebuah tabel dan fungsi yang bertujuan untuk memetakan nilai kunci yang unik untuk setiap record (baris) menjadi angka (hash) lokasi record tersebut dalam sebuah tabel. Keunggulan dari struktur hash table ini adalah waktu aksesnya yang cukup cepat, jika record yang dicari langsung berada pada angka hash lokasi penyimpanannya.

(Sumber: https://medium.com/dev-blogs/ds-with-js-hash-table-4715c94083d2)

Beberapa contoh bagaimana hashing metode ini digunakan dalam kehidupan sehari-hari misalnya di universitas, setiap mahasiswa pastiya diberi NIP atau nomor identifikasi yang digunakan sebagai informasi mengenai mereka. Atau contoh paling nyatanya juga pada perpustakaan, setiap buku akan diberi nomor unik sebagai informasi mengenai buku tersebut, seperti letak penyimpanan, sehingga pengunjung yang meminjam buku tersebut bisa mencari lewat database perpustakaan apakah buku dipinjam oleh orang lain atau masih tersedia diperpustakaan. Kelebihan dari hash table antara lain relatif lebih cepat dan memiliki kecepatan dalam insertions, deletions, maupun searching relatif sama.

Binary Tree

(Sumber: https://en.wikipedia.org/wiki/Binary_tree)

Binary Tree atau Pohon Biner adalah sebuah pohon dalam struktur data yang bersifat hirarkis (hubungan one to many). Tree bisa didefenisikan sebagai kumpulan simpul dengan setiap simpul mempunyai paling banyak dua anak. Secara khusus, anaknya dinamakan kiri dan kanan. Binary tree tidak memiliki lebih dari tiga level dari Root.

Binary tree adalah suatu tree dengan syarat bahawa tiap node (simpul) hanya boleh memiliki maksimal dua subtree dan kedua subtree tersebut harus terpisah. Tiap node dalam binary treee boleh memiliki paling banyak dua child (anak simpul), secara khusus anaknya dinamakan kiri dan kanan.

Binary Search Tree adalah tree yang terurut (ordered Binary Tree). Binary Search Tree juga sering disebut dengan Sorted Binary Tree yang berfungsi untuk menyimpan informasi nama atau bilangan yang disimpan di dalam memory. Dengan ini data dibagi menjadi dua dengan mencari titik tengah seagai patokannya. Binary tree terdiri dari simpul utama yang disebut dengan istilah root. Kemudian dari root tersebut terdapat bagian kiri dan bagian kanan.

Data disimpan setelah root disimpan berdasarkan nilai perbandingan dengan root tersebut. Pengurutan dapat dilakukan bila BST ditelusuri (traversed) menggunakan metode in-order.Binary search tree memungkinkan pencarian dengan cepat, penambahan, juga menghapus data yang ada di dalamnya, bisa juga digunakan sebagai implementasi sejumlah data dinamis, atau pencarian table data dengan menggunakan informasi kunci atau key.

Implementasi Hash dalam Blockchain
Teknologi blockchain semakin berkembang dan dapat digunakan dalam berbagai bidang kehidupan manusia. Salah satu komponen penting dalam blockchain adalah fungsi hash yang berguna untuk menjaga konsistensi data dalam blockchain, dan memastikan tidak ada perubahan data yang terjadi. Penggunaan blockchain oleh banyak orang sekaligus menuntut penggunaan fungsi hash dengan performa yang handal.

Blok awal pada suatu blockchain disebut dengan blok genesis. Setiap blok memiliki nilai hash dari blok sebelumnya, waktu pembuatan blok, dan data. Desain blockchain tersebut membuatnya resisten terhadap pengubahan data, karena setiap perubahan pada suatu blok akan membuat blok selanjutnya menjadi tidak valid. Untuk menambah keamanan, blockchain disimpan dalam jaringan terdistribusi dengan protokol peer-to-peer tertentu.

(Sumber: Fadhil Imam Kurnia. Implementasi dan Perbandingan Blockchaindengan Algoritma Hash. 2018)

Konsep Stack

(Sumber: https://dev.to/rinsama77/data-structure-stack-and-queue-4ecd)

3 operasi dalam stack :

Push : Memasukkan data ke dalam stack.
Pop : Menghapus data di dalam stack.
Peek : Membaca nilai dari sebuah data, dilakukan berurutan dari awal stack tanpa menghilangkannya.

Notasi Infix, Postfix, dan Prefix

(Sumber: http://risasisteminformasi.blogspot.com/2013/02/notasi-prefixinfix-dan-postfix.html)

- ( ) (Kurung).

- ^ (Pangkat).
- * / (Perkalian / Pembagian).
- + - (Penjumlahan / Pengurangan).

1. Infix : notasi yang terbentuk atas operator dengan operand, dimana oprator didepan operand.

contoh: X + Y * Z

maka notasi prefixnya adalah: +X*YZ.

2. Postfix : notasi yang membentuk atas operator dengan operand, dimana operator berada diantara operand.

Contoh :

a) X + Y * Z
b) (X + Y) * Z
c) A - (B + C) * D ^ E

3. Prefix : notasi yang membentuk atas operator dengan operand, dimana operator berada dibelakang operand.

Contoh : A + B * C

maka notasi postfix adalah ABC*+.

Konsep Queue

(Sumber: https://saungkode.wordpress.com/2014/04/10/konsep-queue-antrian-pada-struktur-data/)

Prinsip kerja Queue adalah FIFO (First In First Out), di mana data yang masuk terlebih dahulu akan keluar pertama.

3 operasi dalam queue:

Push : Menambahkan data pada akhir antrian
Pop : Menghapus data dari awal antrian
Peek : Mengambil nilai dari sebuah data

Circular Queue

Circular array adalah suatu array yang dibuat seakan-akan merupakan sebuah lingkaran dengan titik awal (head) dan titik akhir (tail) saling bersebelahan jika array tersebut masih kosong. Queue Circular digunakan untuk menimalisir penggeseran pada Queue Linear.

Priority Queue

Antrian dalam Priority Queue tidak akan dilayani secara FIFO (First In First Out) murni tetapi biasanya didasarkan pada suatu prioritas tertentu.

Circular Linked List

(Sumber: https://algorithms.tutorialhorizon.com/circular-linked-list-complete-implementation/)

Doubly Linked List

(Sumber: https://www.studytonight.com/data-structures/doubly-linked-list)

Circular Doubly Linked List

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

Tidak jauh berbeda dengan Double Linked List, hanya saja Double Linked List Circular ini atau yang sering disingkat DLLC memiliki perbedaan yang terletak pada nodenya itu sendiri. Setiap head dan tail node pada DLLNC selalu bernilai NULL, lain halnya dengan DLLC, tail pada node harus merujuk kembali kepada headnya.

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

(Sumber: https://www.pinterest.se/pin/741757001101474327/)

Array
Variable bertipe array adalah suatu tipe data yang bersifat statis (urutan dan ukuran sudah pasti).
Kelemahan dari array statis adalah penggunaan ruang memori yang sudah digunakan tidak dapat dihapus apabila nama variable array tersebut sudah tidak digunakan kembali dalam suatu program (penyebab kemubaziran).
Untuk pemecahannya maka digunakan struktur data dinamis dengan menggunakan variable dinamis.
Variabel dinamis tidak dapat dideklarasikan secara eksplisit seperti halnya variable statis dan tidak dapat ditunjuk oleh identifier secara langsung, tetapi dapat ditunjuk secara khusus oleh variable dinamis yaitu POINTER.

Linked List
-Struktur ini terdiri dari rangkaian elemen yang saling berhubungan / berkaitan, dimana setiap elemen dihubungkan dengan elemen lainnya oleh sebuah pointer.
-Pointer, sel yang nilainya merupakan alamat sel yang lain dimana sel yang lain itu dapat berupa data atau berupa pointer juga
-Setiap elemen dalam linked list selalu berisi pointer
Istilah – istilah
*Simpul, terdiri dari dua bagian :
a. Bagian/medan data (info)
b. Bagian/medan sambungan (pointer yang menunjuk kesimpul berikutnya)
*Awal (First), variable yang berisi alamat yang menunjuk lokasi simpul pertama linked list
*Nil / Null, Tidak bernilai yaitu menyatakan tidak mengacu kealamat manapun.
*Akhir, sebuah simpul yang menunjuk pada simpul terakhir

Operasi-operasi pada Linked List
a) Insert
Istilah Insert berarti menambahkan sebuah simpul baru ke dalam suatu linked list.
b) IsEmpty
Fungsi ini menentukan apakah linked list kosong atau tidak.
c) Find First
Fungsi ini mencari elemen pertama dari linked list
d) Find Next
Fungsi ini mencari elemen sesudah elemen yang ditunjuk now
e) Retrieve
Fungsi ini mengambil elemen yang ditunjuk oleh now. Elemen tersebut lalu dikembalikan oleh fungsi.
f) Update
Fungsi ini mengubah elemen yang ditunjuk oleh now dengan isi dari sesuatu.
g) Delete Now
Fungsi ini menghapus elemen yang ditunjuk oleh now. Jika yang dihapus adalah elemen pertama dari linked list (head), head akan berpindah ke elemen berikut.
h) Delete Head
Fungsi ini menghapus elemen yang ditunjuk head. Head berpindah ke elemen sesudahnya.
i) Clear
Fungsi ini 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.

Data Structures - Linked List

Hi, I am

John Doe

ABOUT ME

John Doe

My Professional Skills

Services

Awesome features

Animated elements

Responsive Design

Modern design

Retina ready

Fast support

Portfolio

AVL Tree & B-Tree

Summary

Binary Search Tree

Hash Table & Binary Tree

Stack & Queue

Linked List (2)

Linked List

Popular Posts

GET A FREE QUOTE NOW

SAY HELLO TO ME

Blog Archive

ADDRESS

EMAIL

TELEPHONE

MOBILE