Rangkuman Data Structure

Nama: Melody Effendi
NIM: 2301925854
Kelas: CB01
Lecturer: Ferdinand Ariandy Luwinda (D4522) dan Henry Chong (D4460)

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.

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.

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

Skewed binary tree yakni Binary Tree yang semua nodenya (kecuali leaf) hanya memiliki satu 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.

BINARY SEARCH TREE (BST)

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

OPERATIONS

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 uapte 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.

Berikut adalah contoh implementasi Binary Search Tree pada C beserta searching datanya :

#include <stdio.h>

#include <stdlib.h>

//inisialisasi struct

struct data{

int number;

//pointer untuk menampung percabangan kiri dan kanan

data *left, *right;

}*root;

//fungsi push untuk menambah data

void push(data **current, int number){

//jika pointer current kosong maka akan membuat blok data baru

if((*current)==NULL){

(*current) = (struct data *)malloc(sizeof data);

//mengisi data

(*current)->number=number;

(*current)->left = (*current)->right = NULL;

//jika tidak kosong, maka akan dibandingkan apakah angka yang

//ingin dimasukkan lebih kecil dari pada root

//kalau iya, maka belok ke kiri dan lakukan rekursif

//terus menerus hingga kosong

}else if(number < (*current)->number){

push(&(*current)->left, number);

//jika lebih besar, belok ke kanan

}else if(number >= (*current)->number){

push(&(*current)->right, number);

}

//preOrder : cetak, kiri, kanan

void preOrder(data **current){

if((*current)!=NULL){

printf("%d -> ", (*current)->number);

preOrder(&(*current)->left);

preOrder(&(*current)->right);

}

//inOrder : kiri, cetak, kanan

void inOrder(data **current){

if((*current)!=NULL){

inOrder(&(*current)->left);

printf("%d -> ", (*current)->number);

inOrder(&(*current)->right);

}

//postOrder : kiri, kanan, cetak

void postOrder(data **current){

if((*current)!=NULL){

postOrder(&(*current)->left);

postOrder(&(*current)->right);

printf("%d -> ", (*current)->number);

}

//searching data

void search(data **current, int number){

//jika pointer current memiliki data

if((*current)!=NULL){

//cek, apakah datanya lebih kecil. Jika iya, belok ke kiri

if(number<(*current)->number){

search(&(*current)->left,number);

//jika lebih besar, maka belok ke kanan

}else if(number>(*current)->number){

search(&(*current)->right,number);

//jika sama dengan, maka angka ketemu

}else{

printf("Found : %d", (*current)->number);

}

//jika tidak ada data lagi (not found)

}else{

printf("Not Found.");

}

void main(){

push(&root, 11);

push(&root, 22);

push(&root, 13);

push(&root, 15);

push(&root, 9);

inOrder(&root);

printf("\n");

preOrder(&root);

printf("\n");

postOrder(&root);

printf("\n");

search(&root,91);

getchar();

}

CODE DREAMERS MARKET

Berikut merupakan contoh code dari pemahaman di atas:

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

AVL TREE

AVL Tree ditemukan oleh Adelson-Velskii dan Landis. AVL Tree merupakan salah satu jenis BST (binary Search Tree). BST digunakan dengan tujuan untuk mempercepat pencarian data. Apabila BST yg terbentuk cukup seimbang (mendekati complete binary tree) maka waktu pencarian data tidak lebih dari log2n langkah.

AVL Tree adalah Binary Search Tree yang memiliki perbedaan tinggi/ level maksimal 1 antara subtree kiri dan subtree kanan. AVL Tree muncul untuk menyeimbangkan Binary Search Tree. Dengan AVL Tree, waktu pencarian dan bentuk tree dapat dipersingkat dan disederhanakan.

INSERTION

Untuk menjaga tree tetap imbang, setelah penyisipan sebuah node, dilakukan pemeriksaan dari node baru → root. Node pertama yang memiliki |balance factor| > 1 diseimbangkan. Proses penyeimbangan dilakukan dengan single rotation dan double rotation.

KASUS INSERTION PADA AVL TREE

*anggap T adalah node yang harus diseimbangkan kembali

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)

Ke-4 kasus tersebut dapat diselesaikan dengan melakukan rotasi

Kasus 1 dan 2 dengan single rotation
Kasus 3 dan 4 dengan double rotation

Contoh – Single Rotation: Jika suatu Tree diinsert node baru dengan nilai 12, maka akan terjadi ketidak seimbangan dan hal ini terletak pada posisi root

Contoh – Double Rotation : Jika terdapat sebuah tree yang kemudian dilakukan insert node 26. Maka akan terjadi ketidak seimbangan, sehingga terlihat dari bentuknya dapat diselesaikan dengan kasus 4.

DELETE

Proses menghapus sebuah node di AVL tree hampir sama dengan BST. Penghapusan sebuah node dapat menyebabkan tree tidak imbang Setelah menghapus sebuah node, lakukan pengecekan dari node yang dihapus → root. Gunakan single atau double rotation untuk menyeimbangkan node yang tidak imbang. Pencarian node yang imbalance diteruskan sampai root.

HEAPS AND TRIES

HEAPS

Dalam ilmu komputer, sebuah heap adalah struktur data yang berdasarkan konsep struktur data pohon.

Contohnya jika P adalah parent dari node C, maka kunci (nilai) dari P adalah lebih besar dari atau sama dengan (dalam max heap) atau kurang dari atau sama dengan (dalam min-heap) kunci C. Node di "atas" dari struktur heap (parent) disebut root node.

1. MIN HEAP

Di dalam konsep Min Heap, node yang berada dibawahnya atau parent nilainya akan lebih kecil dibandingkan dengan node anaknya. Maka dapat disimpulkan node root merupakan node dengan nilai paling kecil , dan salah satu node dari leaf node merupakan node yang nilainya paling besar.

Contoh:

a. Find-Min

Minimum node terletak pada root

b. Insertion pada Min-heap

· Insert node selalu berurutan dari level paling rendah dengan urutan left ke right.

· New node selalu menjadi leaf node.

· Sesuaikan dengan heap properties secara rekursif.

c. Deletion pada Min-heap

· Node yang dihapus selalu root karena merupakan node paling kecil, lalu diganti dengan node yang paling terakhir di-insert.

· Sesuaikan dengan heap properties secara rekursif.

2. MAX HEAP

Konsep Max Heap hanya berbeda sedikit , perbedaannya hanya ada di node paling atas akan memiliki node dengan nilai terbesar dan salah satu node dari leaf node akan memiliki nilai yang terkecil.

Insertion dan deletion pada max heap disesuaikan dengan properties max heap.

3. MIN-MAX HEAP

Konsep Min Max Heap adalah level root akan bernilai minimum, selanjutnya akan bernilai maximum, dan seterusnya. Nilai terkecil berada di root dan nilai terbesar berada di salah satu node pada level setelah root. Level min hanya dapat dibandingkan dengan level min, dan sebaliknya.

Contoh:

· Insert node sesuai urutan, lalu cek upheap lalu sesuaikan dengan properties level. Umumnya dilakukan penyesuaian rekursif dengan urutan sebagai berikut.

a) Parent

b) Grand Parent

· Deletion selalu dilakukan pada root, lalu sesuaikan dengan downheap sesuai properties. Umumnya dilakukan penyesuaian secara rekursif dengan urutan sebahai berikut.

a) Grand Child

b) Child (grand child disesuaikan dengan parentnya)

TRIES

Tries atau prefix tree adalah suatu pohon struktur data yang terurut yang menyimpan data array, biasanya string. Kata tries diambil dari kata RETRIEVAL, karena tries dapat menemukan kata tunggal dalam kamus dengan hanya awalan katanya saja.

Tries sudah diterapkan ke banyak hal dalam kehidupan sehari-hari, contohnya pada web browser. suatu web browser dapat mengira atau mensugestikan kata-kata yang mungkin kita maksud saat kita mengetik huruf pertamanya saja. (autocomplete)

Kemudian selain itu juga pada spell checker, spell checker dapat mengetahui spelling kata yang tepat saat kita melakukan kesalahan dalam pengetikan. (autocorrect)

Tries adalah suatu tree dimana setiap vertex/pathnya menggambarkan suatu kata, rootnya kosong.

Gambarannya :

Search This Blog

Data Structure