Ringkasan Data Struct
Single Linked List
Linked List atau senarai berantai adalah struktur data yang
dibangun dari satu atau lebih node yang menempati lokasi memori secara dinamis
dan disusun saling sambung – menyambung.
Single Linked List adalah kumpulan dari node yang saling berhubungan dengan
node lain melalui sebuah pointer(next).
Macam – macam pointer yang terdapat dalam single linked
list:
- Head : elemen yang berada pada posisi pertama dalam suatu linked list
- Tail : elemen yang berada pada posisi terakhir dalam suatu linked lis
- Curr : elemen yang berada pada linked list dan pointer ini bisa pindah - pindah
- Next
Memory allocation dynamic
JIka memerlukan untuk mengalokasikan memori secara
dinamis(dalam runtime) dapat menggunakan malloc di C/ C++
Rumus:
Curr =
(struct data*)malloc(sizeof(struct data));
Keterangan : data di warnai merah artinya bisa dinamai apa
aja
Single linked list ketika belum ada data (ketika head ==
NULL)
curr ->angka = data; (misalkan diketahui int angka)
head = curr;
tail = curr;
tail ->next = NULL
Single linked list insert menambah data di bagian
belakang
tail -> next = curr;
curr -> tail;
tail -> next = NULL;
Single linked list insert menambah data di bagian depan
curr -> next = head;
head = curr;
Single linked list insert menambah data di tengah
x -> next = curr;
curr -> next = y;
x = head;
while(x -> next -> angka > curr ->angka){
x = x ->
next;
}
y = x -> next;
x -> next = curr;
curr -> next = y;
Keterangan : x dan y adalah pointer baru
Single Linked List delete depan
if(head ->angka==x){
curr =
head;
head =
head->next;
free(curr);
}
Ket : angka = deretan dari banyak angka , x = nilai yang
dihapus
Single Linked List delete tengah
If(tail->angka==x){
curr =
head;
while(curr->next!=tail){
curr= curr->next;
}
free(tail);
tail=curr;
tail->next = NULL;
}
Ket : angka = deretan dari banyak angka , x = nilai yang
dihapus
Single Linked List delete belakang
curr = head;
while(curr->next->score!=x){
curr =
curr->next;
}
temp = curr->next;
curr->next=temp->next;
free(temp);
Ket : angka = deretan dari banyak angka , x = nilai yang
dihapus
Double Linked List
Double linked list adalah linked list dengan node yang
memiliki data dan dua buah pointer(next dan prev) yang menunjuk ke node sebelum
dan node sesudah.
Macam – macam pointer yang terdapat dalam double linked
list :
- Head : elemen yang berada pada posisi pertama dalam suatu linked list
- Tail : elemen yang berada pada posisi terakhir dalam suatu linked list
- Curr : elemen yang berada pada linked list dan pointer ini bisa pindah - pindah
- Next
- Prev
Contoh syntax untuk double linked
list (dari kelas LAB)
Stack & Queue
Stack
Stack(tumpukan) artinya data yang
pertama kali masuk, maka data tersebut paling akhir keluar.
Contoh : tumpukan piring.
Stack dapat diimplementasikan
menggunakan array (ada batasannya) dan linked list(tidak ada batasan/
unlimited).
Elemen – elemen yang ada di stack
dapat ditambahkan dan dihapus hanya dari satu ujung yaitu bagian atas.
Data disimpan dengan cara Last In
First Out (LIFO).
Macam – macam stack operations :
- Push(x) : memasukkan data ke dalam stack.
- Pop() : menghapus elemen yang terletak pada posisi paling atas dati sebuah tumpukan.
- Top() : mengembalikan(return) data teratas dari tumpukan.
Infix, Postfix, dan Prefix
Notation
- Prefix : Operator yang di tulis sebelum operan ( operator operand operand)
- Contoh : * 4 10
- Infix : Operator yang ditulis antara operan ( operand operator operand)
- Contoh: 4 * 10
- Postfix : Operator yang ditulis setelah operan (operand operand operator)
- Contoh : 4 10 *
Queue
Queue(urutan) artinya data yang
pertama kali masuk maka data tersebut akan pertama kali keluar.
Queue dapat diimplementasikan
dengan menggunakan array atau linked list.
Elemen – elemen dalam queue
ditambahkan di satu ujung yang disebut bagian belakang dan dihapus dari ujung
lain yang disebut depan.
Data yang disimpan dengan cara
First in First Out (FIFO).
Macam – macam queue operations:
- Push(x) : menambahkan item x ke belakang antrian
- Pop() : menghapus item dari depan antrian
- Front() : mengungkapkan / mengembalikan item paling depan dari antrian.
Depth First Search (DFC)
Depth First Search (DFC) adalah
suatu algoritma untuk melintasi atau mencari di pohon atau grafik. DFD dapat
diimplementasikan dengan fungsi rekursif atau iterative produce menggunakan
stack, hasilnya mungkin memiliki sedikit perbedaan pesanan kunjungan tetapi
keduanya benar. Proses pencarian pada algoritma DFC akan dilakukan pada semua
anaknya terlebih dahulu, sebelum dilakukan pencarian ke node – node yang
selevel.
Deques
Deques adalah suatu daftar/list
dimana elemen yang digunakan untuk memasukkan(insert) atau menghapus(delete) di
bagian kedua ujungnya yaitu head dan tail.
Priority Queue
Ada 2 aturan umum untuk memproses
priority queue adalah:
Elemen dengan prioritas lebih
tinggi adalah proses sebelum elemen dengan prioritas lebih rendah.
Dua elemen dengan prioritas yang sama
diproses berdasarkan FCFS.
Breadth First Search(BFC)
Breadth First Search adalah metode
pencarian yang dilakukan dengan mengunjungi setiap node secara sistematis pada
tiap setiap level hingga keadaan tujuan ditemukan. Atau algoritma untuk
melintasi atau mencari di pohon atau grafik.
Hashing
Hashing adalah teknik yang digunakan
untuk menyimpan dan mengambil kunci dengan cepat. Tujuan hashing adalah sebagai
metode untuk menyimpan data dalam sebuah array agar penyimpanan data, pencarian
data, penambahan datam dan penghapusan data dapat dilakukan dengan cepat.
Hash table adalah salah satu
struktur data yang digunakan dalam penyimpanan data sementara. Hash table
menggunakan memori penyimpanan utama berbentuk array dengan tambahan algoritma untuk
mempercepat pemrosesan data.
Hash Function adalah suatu fungsi
sederhana untuk mendaoatkan nilai hash dari nilai kunci(key value) suatu data.
Ada beberapa hal dalam membuat
hash function antara lain :
- Ukuran array/ table size (m)
- Key value/ nilai yang di dapat dari data (k)
- Hash value/ hash index/index yang dituju (h)
Beberapa metode pentuk untuk
membangun hash functions antara lain:
- Mid – Square
- Metode Mid-Square yaitu teknik hashing di mana kunci unik dihasilkan.
·
Division (most common)
Metode division
yaitu Jumlah lokasi memori tersedia dihitung , kemudian jumlah tersebut
digunakan sebagai pembagi untuk membagi nilai yang asli dan menghasilkan
sisa(nilai hashnya). Secara umum rumus division sebagai berikut :
h(z)
= z mod M
Keterangan:
z = key/ suatu lokasi memori yang beralamat h(z)
M = jumlah lokasi memori yang tersedia
pada array
·
Folding
Metode folding
terbagi menjadi dua langkah yaitu :
Ø
Bagi nilai kunci menjadi beberapa bagian dimana
setiap bagian memiliki jumlah digit yang sama kecuali bagian terakhir yang
mungkin memiliki angka lebih sedikit daripada bagian lainnya.
Ø
Tambahan bagi individu. Yaitu memperoleh jumlah
part 1 + part 2 + .. + part n. Nilai hash yang dihasilkan dengan mengabaikan
carry terakhir, jika ada.
·
Digit Extraction
Metode digit extraction
yaitu mendapatkan hash key dengan cara mengambil digit – digit tertentu dari
sebuah string untuk dijadikan hash keynya.
·
Rotating Hash
Metode Rotating
Hash yaitu mendapatkan hash key maka di lakukan rotasi untuk menggeser digit
sehingga menemukan alamat hash key baru.
Dalam penyimpanan data di Hash
Table sangat dimungkinkan 1 index menyimpan lebih dari 1 data, hal ini disebut
denan Collision. Ada 2 cara untuk menangani collision yaitu :
·
Linear Probing
Mencari slot
kosong berikutnya dan letakkan string disana.
·
Chaining
Masukkan string ke
dalam slot sebagai chained list(linked list).
Tree & Binary Tree
Tree adalah salah satu bentuk struktur
data tidak linear yang menggambarkan hubungan yang bersifat hirarkis (hubungan
one to many) antara elemen-elemen. Tree bisa didefinisikan sebagai kumpulan
simpul/node dengan satu elemen khusus yang disebut Root dan node lainnya
terbagi menjadi himpunan-himpunan yang saling tak berhubungan satu sama lainnya
(disebut subtree).
Jenis – jenis binary tree:
·
Perfect binary tree
Adalah
binary tree yang setiap level berada pada kedalaman/ depth yang sama.
·
Complete binary tree
Adalah
binary tree yang setiap levelnya kecuali yang terakhir semua telah terisi penuh
dan setiap nodesnya paling panjang ke kiri.
·
Skewed binary tree
Adalah
binary tree yang semua nodenya (kecuali leaf) hanya memiliki satu child.
·
Balanced binary tree
Adalah
binary tree yang dimana yang setiap leafnya sama jauhnya dari root
Binary Search Tree (BST)
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.
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.
Syntax Binary Search Tree
Tidak ada komentar:
Posting Komentar