Rangkuman Data Structure

1. Linked List

A. Apa yang dimaksud dengan Linked List?

• Linked List merupakan koleksi linear dari data, yang disebut sebagai nodes, dimana setiap node akan menunjuk pada node lain melalui sebuah pointer. Linked List dapat didefinisikan pula sebagai kumpulan nodes yang merepresentasikan sebuah sequence. 

• Linked List memiliki yang disebut head dan tail, dimana head adalah node pertama dalam linked list dan tail adalah node terakhir.
•  Linked List dibagi menjadi dua:
• Single Linked List
• Double/Doubly Linked List 

B. Single Linked List

• Single Linked List adalah salah satu bentuk implementasi dari struktur data yang paling sederhana. Satu node dengan node lainnya dihubungkan melalui penanda berupa pointer seperti gambar berikut: 

 

•  Dalam Single Linked List, pointer hanya bisa berjalan dalam satu arah saja, maju/mundur atau kanan/kiri.

C. Double Linked List

• Double Linked List adalah node-node yang dihubungkan dengan dua pointer, yang terletak sebelum dan sesudah sebuah node. 

D. Linked List vs Array

• Array

1. Elemen data bisa menggunakan RECORD.
2. Bersifat Statis
• volumenya selalu tetap tidak tergantung pada jumlah data.
• alokasi memori dilakukan pada saat array didefinisikan.
• pembebasan memori dilakukan pada saat program berhenti.
3. Cara akses bersifat random dengan menggunakan nomor index.

• Linked List

1. Elemen data selalu menggunakan RECORD.
2. Bersifat Dinamis
• ukurannya berubah-ubah disesuaikan dengan kebutuhan.
• alokasi memori ditentukan pada saat data baru dibuat.
• pembebasan memori dilakukan setiap ada penghapusan data.
3. Cara akses ke masing-masing class data dilakukan secara linier (selalu dimulai dari elemen pertama).

2. Stack and Queue

A. Apa yang dimaksud dengan Stack and Queue?

• Stack (Tumpukan) adalah kumpulan elemen-elemen data yang disimpan dalam satu lajur linear.  Elemen-elemen di dalam tumpukan dapat bertipe integer, real, record dalam bentuk sederhana atau terstruktur.
• Konsep utamanya adalah LIFO (Last In First Out), benda yang terakhir masuk dalam stack akan menjadi benda pertama yang dikeluarkan dari stack.
• Queue merupakan suatu struktur data linear. Konsepnya hampir sama dengan Stack, perbedaannya adalah operasi penambahan dan penghapusan pada ujung yang berbeda.  Elemen-elemen di dalam antrian dapat bertipe integer, real, record dalam bentuk sederhana atau terstruktur.
• Sistem pada pengaksesan pada Queue menggunakan sistem FIFO (First In First Out), artinya elemen yang pertama masuk itu yang akan pertama dikeluarkan dari Queue.

B.  Operasi dalam Stack

• Cek posisi Teratas (Peek)

•  Operasi Pop 

• Operasi Push 

•  Cek Stack kosong (Isempty) 

• Cek Stack penuh (full)

C. Operasi dalam Queue

• Prosedur enqueue

• Prosedur dequeue

• Tampil()

• Clear()

• IsFull

• IsEmpty()

• Create()  

D. Prefix, Infix, and Postfix

 

Prefix, infix dan postfix merupakan suatu cara penulisan atau notasi suatu operasi perhitungan / matematika berdasarkan operan dan operatornya. 

E. Mengapa Kita Menggunakan Notasi Prefix / Postfix?

• Prefix/Postfix tidak memerlukan bracket/tanda kurung ( ) untuk memprioritaskan presedensi operator.
• Prefix/Postfix lebih mudah dievaluasi komputer. 

3. Hashing Table

A. Hash Table

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

B. Operasi pada hash table

• insert: diberikan sebuah key dan nilai, insert nilai dalam tabel

• find: diberikan sebuah key, temukan nilai yang berhubungan dengan key

• remove: diberikan sebuah key,temukan nilai yang berhubungan dengan key, kemudian hapus nilai tersebut
• getIterator: mengambalikan iterator,yang memeriksa nilai satu demi satu

4. Hashing And Binary Tree

A. Hash Table

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

B. Operasi pada hash table

• insert: diberikan sebuah key dan nilai, insert nilai dalam tabel

• find: diberikan sebuah key, temukan nilai yang berhubungan dengan key

• remove: diberikan sebuah key,temukan nilai yang berhubungan dengan key, kemudian hapus nilai tersebut 

• getIterator: mengambalikan iterator,yang memeriksa nilai satu demi satu

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

D. Operasi pada binary tree
a. Create : Membentuk binary tree baru yang masih kosong. 
b. Clear : Mengosongkan binary tree yang sudah ada.  
c. Empty : Function untuk memeriksa apakah binary tree masih kosong. 
d. Insert : Memasukkan sebuah node ke dalam tree. Ada tiga pilihan insert: sebagai root, left child, atau right child. Khusus insert sebagai root, tree harus dalam keadaan kosong.  
e. Find : Mencari root, parent, left child, atau right child dari suatu node. (Tree tak boleh kosong) 
f. Update : Mengubah isi dari node yang ditunjuk oleh pointer current. (Tree tidak boleh kosong)  
g. Retrieve : Mengetahui isi dari node yang ditunjuk pointer current. (Tree tidak boleh kosong) 
h. DeleteSub : Menghapus sebuah subtree (node beserta seluruh descendant nya) yang ditunjuk current. Tree tak boleh kosong. Setelah itu pointer current akan berpindah ke parent dari node yang dihapus. 
i. Characteristic : Mengetahui karakteristik dari suatu tree.

Hashing Table

A. Hash Table

• 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. Akan tetapi pada kenyataannya sering sekali ditemukan hash table yang record-recordnya mempunyai angka hash yang sama (bertabrakan).

• Pemetaan hash function yang digunakan bukanlah pemetaan satusatu, (antara dua record yang tidak sama dapat dibangkitkan angka hash yang sama) maka dapat terjadi bentrokan (collision) dalam penempatan suatu data record. Untuk mengatasi hal ini, maka perlu diterapkan kebijakan resolusi bentrokan (collision resolution policy) untuk menentukan lokasi record dalam tabel. Umumnya kebijakan resolusi bentrokan adalah dengan mencari lokasi tabel yang masih kosong pada lokasi setelah lokasi yang berbentrokan.

B. Operasi pada hash table

• insert: diberikan sebuah key dan nilai, insert nilai dalam tabel

• find: diberikan sebuah key, temukan nilai yang berhubungan dengan key

• remove: diberikan sebuah key,temukan nilai yang berhubungan dengan key, kemudian hapus nilai tersebut

C. Cara penggunaan hash table Memodulus key value dengan ukuran array : h = k (mod m)
Misal kita memiliki array dengan ukuran 13, maka hash function : h = k (mod 13).
Dengan hash function tersebut didapat :

k	H
7	7
13	0
25	12
27	1
39	0

Perhatikan range dari h untuk sembarang nilai k.
Maka data 7 akan disimpan pada index 7, data 13 akan disimpan pada index 0, dst..
Untuk mencari kembali suatu data, maka kita hanya perlu menggunakan hash function yang sama sehingga mendapatkan hash index yang sama pula.
Misal : mencari data 25 → h = 25 (mod 13) = 12

D. Collision
Namun pada penerapannya, seperti contoh di atas terdapat tabrakan (collision) pada k = 13 dan k = 39. Collision berarti ada lebih dari satu data yang memiliki hash index yang sama, padahal seperti yang kita ketahui, satu alamat / satu index array hanya dapat menyimpan satu data saja.
Untuk meminimalkan collision gunakan hash function yang dapat mencapai seluruh indeks/alamat. Dalam contoh di atas gunakan m untuk me-modulo k. Perhatikan bila kita menggunakan angka m untuk me-modulo k maka pada indeks yang lebih besar dari dan sama dengan m di hash table tidak akan pernah terisi (memori yang terpakai semakin kecil), kemungkinan terjadi collision juga semakin besar.
Karena memori yang terbatas dan untuk masukan data yang belum diketahui tentu collision tidak dapat dihindari.

Berikut ini cara-cara yang digunakan untuk mengatasi collision :

1.   Closed hashing (Open Addressing)
Close hashing menyelesaikan collision dengan menggunakan memori yang masih ada tanpa menggunakan memori diluar array yang digunakan. Closed hashing mencari alamat lain apabila alamat yang akan dituju sudah terisi oleh data. 3 cara untuk mencari alamat lain tersebut :

• Ø Linear Probing

Apabila telah terisi, linear probing mencari alamat lain dengan bergeser 1 indeks dari alamat sebelumnya hingga ditemukan alamat yang belum terisi data, dengan rumus
(h+1) mod m.

• Ø Quadratic Probing

Quadratic Probing mencari alamat baru untuk ditempati dengan proses perhitungan kuadratik yang lebih kompleks. Tidak ada formula baku pada quadratic probing ini,anda dapat menentukan sendiri formula yang akan digunakan.
Contoh formula quadratic probing untuk mencari alamat baru:
h,(h+i²)mod m,(h-i²)mod m, … ,(h+((m-1)/2)²)mod m, (h-((m-1)/2)²)mod m
dengan i = 1,2,3,4, … , ((m-1)/2)
Mksud formula di atas adalah jika alamat h telah terisi, maka alamat lain yang digunakan adalah (h+1)mod m, jika telah terisi gunakan alamat (h-1)mod m,  jika telah terisi gunakan alamat (h+4)mod m, jika telah terisi gunakan alamat (h-4)mod m, dan seterusnya.
Jadi jika m=23,maka nilai maksimal i adalah : ((23-1)/2)=11.

• Double hashing

Sesuai dengan namanya, alamat baru untuk menyimpan data yang belum dapat masuk ke dalam table diperoleh dengan menggunakan hash function lagi. Hash function kedua yang digunakan setelah alamat yang dihasilkan oleh hash function awal telah terisi tentu saja berbeda dengan hash function awal itu sendiri.
Kelemahan dari closed hashing adalah ukuran array yang disediakan harus lebih besar dari jumlah data. Selain itu dibutuhkan memori yang lebih besar untuk meminimalkan collision.

2.   Open hashing (Separate Chaining)
Pada dasarnya separate chaining membuat tabel yang digunakan untuk proses hashing menjadi sebuah array of pointer yang masing-masing pointernya diikuti oleh sebuah linked list, dengan chain (mata rantai) 1 terletak pada array of pointer, sedangkan chain 2 dan seterusnya berhubungan dengan chain 1 secara memanjang.
Kelemahan dari open hashing adalah bila data menumpuk pada satu/sedikit indeks sehingga terjadi linked list yang panjang.
 

Hashing And Binary Tree

A. Hash Table

• 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. Akan tetapi pada kenyataannya sering sekali ditemukan hash table yang record-recordnya mempunyai angka hash yang sama (bertabrakan).

• Pemetaan hash function yang digunakan bukanlah pemetaan satusatu, (antara dua record yang tidak sama dapat dibangkitkan angka hash yang sama) maka dapat terjadi bentrokan (collision) dalam penempatan suatu data record. Untuk mengatasi hal ini, maka perlu diterapkan kebijakan resolusi bentrokan (collision resolution policy) untuk menentukan lokasi record dalam tabel. Umumnya kebijakan resolusi bentrokan adalah dengan mencari lokasi tabel yang masih kosong pada lokasi setelah lokasi yang berbentrokan.

B. Operasi pada hash table

• insert: diberikan sebuah key dan nilai, insert nilai dalam tabel

• find: diberikan sebuah key, temukan nilai yang berhubungan dengan key

• remove: diberikan sebuah key,temukan nilai yang berhubungan dengan key, kemudian hapus nilai tersebut 

• getIterator: mengambalikan iterator,yang memeriksa nilai satu demi satu

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

• Pohon biner dapat juga disimpan sebagai struktur data implisit dalam array, dan jika pohon tersebut merupakan sebuah pohon biner lengkap, metode ini tidak boros tempat. Dalam penyusunan yang rapat ini, jika sebuah simpul memiliki indeks i, anaknya dapat ditemukan pada indeks ke-2i+1 dan 2i+2, meskipun ayahnya (jika ada) ditemukan pada indeks lantai ((i-1)/2) (asumsikan akarnya memiliki indeks kosong).

 D. Operasi pada binary tree
a. Create : Membentuk binary tree baru yang masih kosong. 
b. Clear : Mengosongkan binary tree yang sudah ada.  
c. Empty : Function untuk memeriksa apakah binary tree masih kosong. 
d. Insert : Memasukkan sebuah node ke dalam tree. Ada tiga pilihan insert: sebagai root, left child, atau right child. Khusus insert sebagai root, tree harus dalam keadaan kosong.  
e. Find : Mencari root, parent, left child, atau right child dari suatu node. (Tree tak boleh kosong) 
f. Update : Mengubah isi dari node yang ditunjuk oleh pointer current. (Tree tidak boleh kosong)  
g. Retrieve : Mengetahui isi dari node yang ditunjuk pointer current. (Tree tidak boleh kosong) 
h. DeleteSub : Menghapus sebuah subtree (node beserta seluruh descendant nya) yang ditunjuk current. Tree tak boleh kosong. Setelah itu pointer current akan berpindah ke parent dari node yang dihapus. 
i. Characteristic : Mengetahui karakteristik dari suatu tree.

Stack and Queue

A. Apa yang dimaksud dengan Stack and Queue?

• Stack (Tumpukan) adalah kumpulan elemen-elemen data yang disimpan dalam satu lajur linear.  Elemen-elemen di dalam tumpukan dapat bertipe integer, real, record dalam bentuk sederhana atau terstruktur.
• Konsep utamanya adalah LIFO (Last In First Out), benda yang terakhir masuk dalam stack akan menjadi benda pertama yang dikeluarkan dari stack.
• Queue merupakan suatu struktur data linear. Konsepnya hampir sama dengan Stack, perbedaannya adalah operasi penambahan dan penghapusan pada ujung yang berbeda.  Elemen-elemen di dalam antrian dapat bertipe integer, real, record dalam bentuk sederhana atau terstruktur.
• Sistem pada pengaksesan pada Queue menggunakan sistem FIFO (First In First Out), artinya elemen yang pertama masuk itu yang akan pertama dikeluarkan dari Queue.

B.  Operasi dalam Stack

• Cek posisi Teratas (Peek)

Operasi peek digunakan untuk mengecek posisi teratas dalam stack.

•  Operasi Pop 

Operasi pop dalam stack adalah operasi untuk mengambil/menghapus elemen yang terletak pada posisi paling atas dari sebuah tumpukan.

• Operasi Push 

Operasi push dalam stack adalah operasi yang memasukkan elemen yang akan diletakkan pada posisi teratas dari tumpukan.

•  Cek Stack kosong (Isempty) 

Fungsi yang melakukan pengecekan apakah stack dalam kondisi kosong.

• Cek Stack penuh (full)

Fungsi yang melakukan pengecekan apakah stack dalam kondisi penuh atau tidak.

C. Operasi dalam Queue

• Prosedur enqueue

Prosedur ini digunakan untuk memasukkan sebuah data/ nilai ke dalam queue. Sebelum sebuah data/ nilai dimasukkan ke dalam queue, maka prosedur ini terlebih dahulu melakukan pengecekan terhadap posisi HEAD dan TAIL. Jika posisi HEAD dan TAIL masih berada pada indeks ke-0 (artinya queue masih kosong), maka prosedur ini akan menempatkan HEAD dan TAIL pada indeks ke-1 terlebih dahulu, baru setelah itu memasukkan data/ nilai ke dalam array data queue. Namun, jika posisi HEAD dan TAIL tidak berada pada posisi ke-0, maka posisi TAIL yang akan dinaikkan satu level. Jadi, pada proses enqueue, TAIL-lah yang berjalan seiring masuknya data baru ke dalam antrian, sedangkan HEAD akan tetap pada posisi ke-1.

• Prosedur dequeue

Prosedur ini digunakan untuk mengeluarkan atau membuang sebuah data/ nilai yang paling awal masuk (yang berada pada posisi HEAD, yakni yang paling depan dari antrian) ke dalam queue. Pekerjaan yang dilakukan oleh prosedur ini adalah menaikkan nilai HEAD satu level. Jadi, setiap satu kali data dikeluarkan, maka posisi HEAD naik bertambah satu level.

• Tampil()

Untuk menampilkan nilai-nilai elemen

• Clear()

Untuk menghapus elemen-elemen Antrian

• IsFull

Untuk mengecek apakah Antrian sudah penuh atau belum

• IsEmpty()

Untuk memeriksa apakah Antrian sudah penuh atau belum

• Create()

Untuk menciptakan dan menginisialisasi Queue 

 

D. Prefix, Infix, and Postfix

 

Prefix, infix dan postfix merupakan suatu cara penulisan atau notasi suatu operasi perhitungan / matematika berdasarkan operan dan operatornya. 

• Operan adalah bilangan/angka yang kita akan hitung
• Operator adalah lambang perhitungan yang kita gunakan untuk mengoperasikan operan, misalnya +, -, /, *, ^, dsb.

• Prefix   : Operator diletakan sebelum operan. 
• Infix     : Operator diletakan diantara operan.
• Posfix  : Operator diletakan setelah operan.

berikut contohnya :

E. Mengapa Kita Menggunakan Notasi Prefix / Postfix?

Mungkin banyak orang bertanya mengapa kita memerlukan notasi prefix dan postfix, padahal sudah ada notasi infix yang secara manual lebih mudah untuk dibaca dan digunakan. Berikut manfaat menggunakan notasi prefix/postfix :

• Prefix/Postfix tidak memerlukan bracket/tanda kurung ( ) untuk memprioritaskan presedensi operator.
• Prefix/Postfix lebih mudah dievaluasi komputer.