Summary

Linked list II

Linked List adalah koleksi data item yang tersusun dalam sebuah barisan secara linear, dengan penyisipan dan pemindahan dapat dilakukan dalam semua tempat Linked List tersebut.

Single Linked List adalah sebuah Linked List yang menggunakan sebuah variable pointer saja untuk menyimpan banyak data dengan metode Linked List, suatu daftar isi yang saling berhubungan. Contoh :

Pada gambar diatas, data terletak pada sebuah lokasi dalam sebuah memory, tempat yang disediakan memory untuk menyimpang data disebut node, setiap node memiliki pointer yang menunjuk ke node berikutnya sehingga membentuk suatu untaian yang disebut single Linked List. Bila dalam single Linked List pointer hanya dapat bergerak ke satu arah saja, maju / mundur, kanan / kiri, sehingga pencarian datanya juga hanya satu arah saja.

Single Linked List Circular adalah Single Linked List yang pointer nextnya menunjuk pada dirinya sendiri. Jika Single Linked List tersebut terdiri dari beberapa node, maka pointer next pada node akhir akan menunjuk ke node terdepannya.
Ilustrasi Single Linked List Circular :
1. Setiap node pada linked list mempunyai field yang berisi pointer ke node berikutnya, dan juga memiliki field yang berisi data.
2. pada akhir Linked List, node terakhir akan menunjuk ke node terdepan sehingga Linked List tersebut berputar. Node terakhir akan menunjuk lagi ke head.

Double Linked List merupakan suatu Linked List yang memiliki 2 variable pointer. yaitu pointer yang menunjuk ke node selanjutnya dan pointer yang menunjuk ke node sebelumnya. setiap head dan tail juga menunjuk ke NULL.

Dalam double Linked List, dapat mengatasi kelemahan-kelemahan single Linked List.

Double Linked List Circular adalah Linked List yang menggunakan 3 pointer, dimana setiap node mempunyai 3 field. Yaitu:
1. Field pointer yang menunjuk pointer berikutnya "next".
2. Field menunjuk pointer sebelumnya "prev".
3. Field yang berisi data untuk node tersebut.
Double Linked List Circular pointer next dan prev nya menunjuk kedirinya sendiri secara circular. Setiap node pada Linked List mempunya field yang berisi data dan pointer ke node berikutnya dan ke node sebelumnya. Untuk pembentukan node baru, mulanya pointer next dan prev akan menunjuk ke nilai NULL. Selanjutnya pointer prev akan menunjuk ke node sebelumnya, dan pointer next akan menunjuk ke node selanjutnya pada list.

Demikianlah rangkuman materi mengenai Linked List II. Semoga rangkuman ini dapat membantu teman-teman dalam mempelajari materi Linked List. Terima Kasih!

Stack and Queue in Data Structures

Stack adalah struktur data linear di mana elemen dapat dimasukkan dan dihapus hanya dari 1 sisi daftar, yang disebut bagian atas. Tumpukan elemen Stack mengikuti prinsip LIFO (Last In First Out), yaitu elemen yang dimasukkan terakhir adalah elemen yang pertama keluar. Proses memasukkan elemen ke sebuah stack disebut operasi push, dan proses penghapusan elemen dari stack disebut operasi pop. Dalam stack, kita selalu melacak elemen terakhir yang ada dalam daftar dengan pointer yang disebut top.

Ilustrasi cara kerja dari stack seperti di bawah ini:

Queue seperti bahasa indonesianya yaitu antri, queue adalah struktur data linear di mana elemen yang disisipkan hanya dari 1 sisi daftar yang disebut belakang, dan elemen dapat dihapus hanya dari sisi lain yang disebut depan. Struktur data queue mengikuti prinsip FIFO (First In First Out), yaitu elemen yang dimasukkan pertama kali dalam daftar, adalah elemen pertama yang akan dihapus dari daftar. Proses memasukkan elemen ke dalam queue disebut operasi enqueue, dan proses penghapusan sebuah elemen disebut dequeue. Berbeda dengan stack, di dalam queue kita selalu mempertahankan 2 pointer, 1 menunjuk ke elemen yang disisipkan di pertama dan masih ada dalam daftar dengan pointer depan dan pointer ke-2 menunjuk ke elemen yang dimasukkan terakhir dengan pointer belakang.

Ilustrasi cara kerja dari queue seperti dibawah ini:

Perbedaan antara Stack and Queue adalah:

Stack	Queue
Menggunakan prinsip LIFO	Menggunakan prinsip FIFO
Proses memasukkan dan menghapus elemen di stack hanya terjadi di satu ujung daftar yang disebut top	Proses memasukkan terjadi di bagian belakang dan proses menghapus dilakukan dari bagian depan daftar
Proses memasukkan sebuah elemen disebut push	Proses memasukkan sebuah elemen disebut enqueue
Proses penghapusan sebuah elemen disebut pop	Proses penghapusan sebuah elemen disebut dequeue
Di dalam stack, hanya mempertahankan 1 pointer, yang namanya top, yang selalu menunjuk ke elemen terakhir	Di dalam queue, mempertahankan 2 pointer. 1 pointer untuk elemen pertama dan 1 pointer lagi untuk elemen terakhir

Binary Tree
Binary tree adalah data struktur berpohon di mana setiap simpul memiliki paling banyak 2 anak, yang disebut kiri dan kanan. Binary tree diimplementasikan terutama menggunakan link. Sebuah Tree diwakili oleh pointer ke simpul paling atas di Tree. Jika Tree tersebut kosong, maka nilai sebuah Root kosong. Binary Tree terdapat beberapa node seperti :

Data
Pointer ke anak kiri
Pointer ke anak kanan

Binary Tree dapat dilalui dengan 2 cara. Yang pertama adalah Depth First Traversal dan yang kedua adalah Breadth First Traversal. Depth First Traversal terdiri dari :

Inorder (Kiri-Root-Kanan)
Preorder (Root-Kiri-Kanan)
Postorder (Kiri-Kanan-Root).

Breadth First Traversal terdiri dari : Level order Traversal.

Properti dari Binary Tree :

Angka maksimum node ada di level '1' = 2^1-1.
Angka maksimum node adalah = 2^{h + 1} - 1. h adalah tinggi sebuah Tree.
Ketinggian minimum adalah = Ceil(Log₂(n+1)) – 1.
Di dalam binary tree, jumlah node leaf selalu lebih banyak 1 dari node 2 anak.
Kompleksitas Waktu Traversal Tree : 0(n).

Salah satu alasan menggunakan Binary Tree atau Tree adalah untuk hal-hal yang membentuk hierarki. Mereka sangat berguna dalam struktur File dimana setiap file terletak di direktori tertentu dan ada hierarki spesifik yang terkait dengan file dan direktori.

Binary Heap

adalah Binary Tree dengan :

Isi pohon lengkap (semua level terisi penuh kecuali mungkin level terakhir dan level terakhir memiliki semua kunci yang tersisa) Properti Binary Heap ini membuatnya cocok untuk disimpan dalam array.
Binary Heap adalah Min Heap atau Max Heap. dalam Min Binary Heap, kunci pada root harus minimum di antara semua kunci yang ada di Binary Heap.Properti yang sama harus benar secara rekursif untuk semua node di Binary Tree. Max Binary Heap mirip dengan Min Heap. Max Binary Heap diimplementasikan menggunakan array.

Dapatkan Minimum di Min Heap: O (1) [Atau Dapatkan Max di Max Heap]
Ekstrak Minimum Min Heap: O (Log n) [Atau Ekstrak Max di Max Heap]
Kurangi Kunci di Tumpukan Min: O (Log n) [Atau Kurangi Kunci di Tumpukan Max]
Sisipkan: O (Log n)
Hapus: O (Log n)

Struktur data Heap dapat digunakan untuk secara efisien menemukan elemen k terkecil (atau terbesar) dalam sebuah array, menggabungkan array yang diurutkan k, median aliran, dll.

Heap adalah struktur data khusus dan tidak dapat digunakan untuk mencari elemen tertentu.

Hashing Hash Function

Suatu fungsi yang mengubah kunci input besar yang diberikan ke nilai integer praktis kecil. Nilai integer yang dipetakan digunakan sebagai indeks dalam hash table. Fungsi hash yang baik harus memiliki properti berikut :

Dihitung secara efisien.
Sebaiknya mendistribusikan kunci secara seragam (Setiap posisi meja memiliki kemungkinan yang sama untuk setiap kunci)

Hash Table: Array yang menyimpan pointer ke catatan yang sesuai dengan nomor telepon tertentu. Entri dalam hash table adalah NIL jika tidak ada nomor telepon yang memiliki nilai fungsi hash sama dengan indeks untuk entri.

Collision Handling: Karena fungsi hash memberi kita sejumlah kecil untuk kunci yang merupakan bilangan bulat besar atau string, ada kemungkinan bahwa dua kunci menghasilkan nilai yang sama. Situasi di mana peta kunci yang baru dimasukkan ke slot yang sudah ditempati di hash table disebut tabrakan dan harus ditangani menggunakan beberapa teknik penanganan tabrakan. Berikut ini adalah cara untuk menangani tabrakan:

Chaining --> Idenya adalah untuk membuat setiap sel tabel hash menunjuk ke daftar catatan terkait yang memiliki nilai fungsi hash yang sama. Rantai itu sederhana, tetapi membutuhkan memori tambahan di luar meja.
Open Addressing --> Dalam pengalamatan terbuka, semua elemen disimpan dalam hash table itu sendiri. Setiap entri tabel berisi catatan atau NIL. Saat mencari elemen, kita satu per satu memeriksa slot tabel hingga elemen yang diinginkan ditemukan atau jelas bahwa elemen tersebut tidak ada dalam tabel.

Hashing Data Structure

Hashing adalah Struktur Data penting yang dirancang untuk menggunakan fungsi khusus yang disebut fungsi Hash yang digunakan untuk memetakan nilai yang diberikan dengan kunci tertentu untuk akses elemen yang lebih cepat. Efisiensi pemetaan tergantung pada efisiensi fungsi hash yang digunakan.

Biarkan fungsi hash H (x) memetakan nilai x pada indeks x% 10 dalam sebuah array. Sebagai contoh jika daftar nilai adalah [11,12,13,14,15] itu akan disimpan di posisi {1,2,3,4,5} masing-masing dalam array atau tabel hash.

Binary Search Tree

Kemarin kita sudah membahas mengenai Hash Table, Hashing dan Binary Tree. Pada hari ini, saya akan menjelaskan tentang Binary Search Tree.

Binary Search Tree adalahadalah Binary Tree dengan :

Subtree kiri dari sebuah node hanya berisi node dengan kunci kurang dari kunci node.
Subtree kanan dari sebuah node hanya berisi node dengan kunci lebih besar dari kunci node.
Subtree kiri dan kanan masing-masing juga harus berupa pohon pencarian biner.

Properti di atas dariBST menyediakan pemesanan antar tombol sehingga operasi seperti pencarian, minimum dan maksimum dapat dilakukan dengan cepat. Jika tidak ada pemesanan, maka BST mungkin harus membandingkan setiap kunci untuk mencari kunci yang diberikan.

BST mempunya Basic Operations yang terdiri dari :

Search - untuk mencari elemen dalam tree
Insert - untuk memasukkan data ke dalam tree
Pre-order Traversal - melintasi tree dengan cara pre-order
In-order Traversal - melintasi tree dengan cara in-order
Post-order Traversal - melintasi tree dengan cara post-order

Search Algorithm :

struct node* search(int data){
   struct node *current = root;
   printf("Visiting elements: ");
 
   while(current->data != data){
 
      if(current != NULL) {
         printf("%d ",current->data);
   
         //go to left tree
         if(current->data > data){
            current = current->leftChild;
         }  //else go to right tree
         else {                
            current = current->rightChild;
         }
   
         //not found
         if(current == NULL){
            return NULL;
         }
      }   
   }
   
   return current;
}

Insert Algorithm :

void insert(int data) {
   struct node *tempNode = (struct node*) malloc(sizeof(struct node));
   struct node *current;
   struct node *parent;

   tempNode->data = data;
   tempNode->leftChild = NULL;
   tempNode->rightChild = NULL;

   //if tree is empty
   if(root == NULL) {
      root = tempNode;
   } else {
      current = root;
      parent = NULL;

      while(1) {                
         parent = current;
   
         //go to left of the tree
         if(data < parent->data) {
            current = current->leftChild;                
            //insert to the left
    
            if(current == NULL) {
               parent->leftChild = tempNode;
               return;
            }
         }  //go to right of the tree
         else {
            current = current->rightChild;
            
            //insert to the right
            if(current == NULL) {
               parent->rightChild = tempNode;
               return;
            }
         }
      }            
   }
}

Kasus terburuk BST yang dapat terjadi adalah Kompleksitas Waktu. Kompleksitas waktu kasus terburuk dari operasi pencarian dan penyisipan adalah 0 (h) di mana h adalah ketinggian BST. Dalam kasus terburuk, kita mungkin harus melakukan perjalanan dari root ke simpul daun terdalam. Ketinggian pohon miring dapat menjadi n dan kompleksitas waktu pencarian dan operasi memasukkan bisa menjadi 0 (n).

Beberapa fakta mengenai BST :

In-order traversal dalam BST selalu menghasilkan output yang berurutan.
Kita dapat membuat BST dengan hanya Preorder atau Postorder atau traversal Level Order. Tetapi harus diingat bahwa kita selalu bisa mendapatkan inorder traversal dengan mengurutkan satu-satunya traversal yang diberikan.
Jumlah BST unik dengan n kunci yang berbeda adalah nomor Catalan.

Sumber :

1. https://kuliahinformatika.wordpress.com/2010/01/21/linked-list-definisi-node-linked-list-single-linked-list-double-linked-list-circular-linked-list/

2. http://brawlyvonfabre.blogspot.com/p/single-linked-list.html

3. http://brawlyvonfabre.blogspot.com/p/double-linked-list.html

4. https://suciantinovi.blogspot.com/2014/03/linked-list-i_14.html

5. https://www.geeksforgeeks.org/difference-between-stack-and-queue-data-structures/

6. https://www.geeksforgeeks.org/overview-of-data-structures-set-2-binary-tree-bst-heap-and-hash/

7. https://www.geeksforgeeks.org/hashing-data-structure/

8. https://www.geeksforgeeks.org/binary-search-tree-data-structure/

9. https://en.wikipedia.org/wiki/Binary_search_tree