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.