RANGKUMAN

Review materi data struktur di semester 2 

 

 Pada saat ini saya akan merangkum apa yang saya dapat di Semester 2 ini, mulai dari Linked list sampai Binary Search Tree. Langsung saja kita bahas dengak singkat satu per satu.

  Linked List

Ada beberapa macam Linked List yang telah kita pelajari yaitu:

1.            Single Linked List

Single Linked List adalah sekumpulan dari node yang saling terhubung dengan node lain melalui sebuah pointer. Rangkaian single linked list tersebut diawali dengan sebuah head untuk menyimpan alamat awal dan di akhiri dengan node yang mengarah pointer ke null.

2.            Double Linked List

 Double Linked List adalah sekumpulan node data yang terurut linear atau sekuensial dengan dua buah pointer yaitu prev dan next. Double Linked List adalah linked list dengan node yang memiliki data dan dua buah reference link (biasanya disebut next dan prev) yang menunjuk ke node sebelum dan node sesudahnya. Pada implementasinya, terdapat dua variasi double linked list yaitu circular dan non-circular layaknya pada single linked list.
Elemen double link list terdiri dari tiga bagian:
- Bagian data informasi
- Pointer next yang menunjuk ke elemen berikutnya
- Pointer prev yang menunjuk ke elemen sebelumnya


Materi yang Kedua ialah:
Stack dan Queue. 

 Perbedaan STACK dan QUEUE :
Stack memakai sistem LIFO atau last in first out (yang pertama masuk akan keluar terakhir, begitu pula yang terakhir masuk akan keluar pertama kali) yang apabila kita mengahapus/ keluar data, maka data yang terakhirlah yang akan terhapus/ keluar terlebih dahulu.

Sementara queue memakai sistem FIFO atau first in first out (yang pertama masuk akan keluar pertama, begitu pula yang masuk terakhir akan keluar terakhir) yang apabila kita menghapus / mengeluarkan data, maka data yang pertamalah yang akan terhapus/ keluar terdahulu dan data yang terakhir akan terhapus/ keluar terakhir.

Guna counter pada rangkaian stack dan queue adalah untuk menentukan apakah stack atau queue tersebut sudah full atau masih empty.

Malloc merupakan fungsi standart untuk mengalokasinkan memori
Banyaknya byte yaang akan dipesan dinyatakan sebagai parameter fungsi. Untuk return value dari fungsi ini adalah sebuah pointer yang tak bertipe ( pointer to void) yang menunjuk ke buffer(tempat penyimpanan sementara) yang dialokasikan .
Pointer harus dikonversi pada tipe data yang sesuai ( dengan menggunakan type cast) agar bisa mengakses data yang disimpan dalam buffer.
Kegunaan dari malloc adalah mengembalikan pointer kesejumlah n byte ruang memori yang belum di inisialisasi. Apabila tidak terpenuhi akan mengembalikan ke nilai NULL.

Fungsi dari free adalah untuk membebaskan memori yang telah dipakai dalam fungsi malloc() , calloc().
sintak : void *free (void *memblock)
fungsi ini untuk menghindari adanya pemborosan memori atau terjadi kebocoran memori ( memori leak ) maka harus melakukan dealokasi terhadap ruang-ruang memori yang sebelumnya dialokasikan .

Materi yang Ketiga ialah:

Hashing 

Hashing adalah teknik yang digunakan untuk menyimpan dan mengambil kunci dengan cepat.
Dalam hashing, string karakter ditransformasikan menjadi nilai panjang yang biasanya lebih 

pendek atau kunci yang mewakili string asli.
Hashing digunakan untuk mengindeks dan mengambil item dalam database karena lebih cepat 

menemukan item menggunakan kunci hash yang lebih pendek daripada menemukannya 

menggunakan nilai asli.
Hashing juga dapat didefinisikan sebagai konsep mendistribusikan kunci dalam array yang 

disebut tabel hash menggunakan fungsi yang telah ditentukan yang disebut fungsi hash.

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

Materi yang Keempat ialah:

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.

Operasi-operasi pada Binary Tree :

v Create : Membentuk binary tree baru yang masih kosong.

v Clear : Mengosongkan binary tree yang sudah ada.

v Empty : Function untuk memeriksa apakah binary tree masih kosong.

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

v Find : Mencari root, parent, left child, atau right child dari suatu node. (Tree tak boleh kosong)

v Update : Mengubah isi dari node yang ditunjuk oleh pointer current. (Tree tidak boleh kosong)

v Retrieve : Mengetahui isi dari node yang ditunjuk pointer current. (Tree tidak boleh kosong)

v DeleteSub : Menghapus sebuah subtree (node beserta seluruh descendantnya) yang ditunjuk current. Tree tak boleh kosong. Setelah itu pointer current akan berpindah ke parent dari node yang dihapus.

v Characteristic : Mengetahui karakteristik dari suatu tree, yakni : size, height, serta average lengthnya. Tree tidak boleh kosong. (Average Length = [jumlahNodeLvl1*1+jmlNodeLvl2*2+…+jmlNodeLvln*n]/Size)

v Traverse : Mengunjungi seluruh node-node pada tree, masing-masing sekali. Hasilnya adalah urutan informasi secara linier yang tersimpan dalam tree. Adatiga cara traverse : Pre Order, In Order, dan Post Order.

Langkah-Langkahnya Traverse :

Ø PreOrder : Cetak isi node yang dikunjungi, kunjungi Left Child, kunjungi Right Child.

Ø InOrder : Kunjungi Left Child, Cetak isi node yang dikunjungi, kunjungi Right Child.

Ø PostOrder : Kunjungi Left Child, Kunjungi Right Child, cetak isi node yang dikunjungi.

Binary Search Tree(BST)

biasanya memiliki ciri-ciri seperti berikut :

• 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 dalam contoh di atas setiap node memiliki value yang berbeda , dan sesuai dengan ciri-ciri yang di sebutkan di atas Binary Search Tree memiliki 3 oprasi dasar ,  hampir mirip dengan array keliatannya jadi ada 3 yaitu :

1. Find(x)     : find value x didalam BST ( Search )
2. Insert(x)   : memasukan value baru x ke BST ( Push )
3. Remove(x)  : menghapus key x dari BST ( Delete )

Oprasi: Search BST dengan adanya ciri” atau syarat di dalam BST , maka untuk finding/searching didalam BST menjadi lebih mudah.
Bayangkan kita akan mencari value X.

• Memulai Pencarian Dari Root
• Jika Root adalah value yang kita cari , maka berhenti
• Jika x lebih kecil dari root maka cari kedalam rekrusif tree sebelah kiri
• Jika x lebih besar dari root maka cari kedalam rekrusif tree sebelah kanan.