Rangkuman

Pengertian single serta double linked list

            Single linked list merupakan linked list yang memiliki satu tautan saja. Sedangkan double linked list merupakan linked list dengan dua tautan, dimana tautan yang pertama bereferensi pada data selanjutnya sedangkan tautan selanjutnya bereferensi pada tautan sebelumnya. Pada single maupun double linked list (referensi ppt bimay) terdapat 2 fungsi, yaitu insert dan delete. Insert dan delete dapat juga kita sebut dengan istilah push dan pop, dimana push berarti insert dan pop berarti delete. Perbedaan diantara mereka adalah hadirnya fungsi pop mid dan push mid yang mana mewajibkan linked list harus memiliki 2 tautan.

            Fungsi push sendiri berfungsi untuk menambah nilai node (data) dari barisan paling awal, tengah dan akhir. Berikut macam – macam fungsi push pada linked list.

·         Push head

Merupakan fungsi push yang bertujuan menambah data melalui barisan awal.

·         Push Mid(double linked list)

Merupakan fungsi push yang bertujuan menambah data melalui barisan tengah

·         Push tail

Merupakan fungsi push yang bertujuan menambah data dari barisan belakang

Merupakan kebalikan dari fungsi push, fungsi pop sendiri berfungsi untuk menghapus nilai node (data) dari barisan paling awal, tengah dan akhir. Berikut macam – macam fungsi pop pada linked list.

·         Pop head

Merupakan fungsi pop yang bertujuan menghapus data melalui barisan awal.

·         Pop Mid(double linked list)

Merupakan fungsi pop yang bertujuan menghapus data melalui barisan tengah

·         Pop tail

Merupakan fungsi pop yang bertujuan menghapus data dari barisan belakang

Pengertian Hash Table

            Jadi, apa itu hash table? hash table merupakan sebuah fungsi dalam 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 yaitu memiliki waktu pengaksesan data yang cepat. Namun kekurangannya ialah sering sekali ditemukan hash table yang record-recordnya mempunyai angka hash yang sama (collision).Maka dari itu perlu diterapkan kebijakan resolusi bentrokan (collision resolution policy) untuk menentukan lokasi record dalam table agar angka – angka hash tidak saling bertabrakan (collision). Berikut hal – hal yang dapat dilakukan untuk menghindari collision :

           

·         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 :

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

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

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

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

Pengertian Binary Search Tree

Lalu, apa itu binary search tree? Binary search tree merupakan sebuah fungsi pada data structure (sama seperti hash table) namun memiliki konsep yang berbeda. Seperti Namanya, binary search tree merupakan salat Satu bentuk Struktur Data tidak linier 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 tak saling berhubungan Satu sama lainnya (disebut subtree). 

            Contoh Code :

               while(current->data != data){

                if(current != NULL) {

                printf("%d ",current->data);

                if(current->data > data){  

                  current = current->leftChild;

                 }

                 else {       

                    current = current->rightChild;

                 }

                 if(current == NULL){

                    return NULL;

                           }

                      }  

                 }

  

               return current;