Rangkuman

Kali ini saya akan membahas kembali tentang apa yang sudah dipelajari di semester ini. Yang pertama adalah Linked list dan macam-macamnya. Lalu saya mempelejari apa itu stack, queue, hash table, dan juga tree terutama binary search tree. Berikut adalah penjelasannya dimulai dari linked list.

Linked List

Linked list adalah cara menyimpan suatu data secara lurus. Linked list ini sering di bandingkan dengan array karena sama-sama menyimpan data secara lurus. Data di linked list hanya diketahui headnya saja dan data selanjutnya hanya bisa ditemukan dengan cara iterasi satu persatu. Pertama, untuk membuat sebuah linked list adalah dengan membuat struct yang akan dijadikan linked list.

Struct linked list simpel:

template<class T>

struct llist{

    T val;

    llist *next = NULL;

};

Setelah dibuat struct-nya harus dibuat pointer untuk menentukan awal dan akhir untuk linked list tersebut. Barulah dibuat fungsi untuk memasukkan dan menghapus nilai di dalam sebuah linked list.

Mendeklarasi awal dan akhir linked list dengan tipe data int:

llist<int> *start = NULL, *end = NULL;

Tipe data bisa diganti dengan apa saja, tetapi untuk contoh menggunakan int dulu.

Fungsi insert untuk memasukkan data ke dalam linked list:

template<class T>

void insert(T val, llist<T> *&start, llist<T> *&end){

    if(start == NULL){

        llist<T> *newstart = new llist<T>;

        newstart->val = val;

        start = newstart;

        end = start;

    }

    else{

        llist<T> *newnode = new llist<T>;

        newnode->val = val;

        

        end->next = newnode;

        end = newnode;

    }

}

jika awal dari linked list masih kosong, maka node awal akan dibuat. Selain dari itu node baru akan dimasukkan di akhir dari linked list.

Fungsi remove untuk menghapus data dari linked list.

template<class T>

void remove(T val, llist<T> *start){

    llist<T> *cur = start, *prevcur = NULL;

    

    while(cur != NULL){

        if(cur->val == val){

            prevcur->next = cur->next;

            delete cur;

            cur = prevcur;

        }

        prevcur = cur;

        cur = cur->next;

    }

}

 Nilai yang ingin dihapus dicari lebih dulu dengan looping, kemudian node tersebut dihapus dan node sebelum dan sesudahnya disambung. 

 Fungsi untuk mem-print isi dari linked list:

template<class T>

void showlist(llist<T> *start){

    if(start == NULL) return;

    llist<T> *cur = start;

    while(cur != NULL){

        std::cout << cur->val << " ";

        cur = cur->next;

    }

    std::cout << std::endl;

}

Print isi dari linked list dengan men-loop seluruh node-nya hingga ketemu NULL.

 Contoh program untuk menggunakan semua fungsi diatas:

#include<iostream>

template<class T>

struct llist{

    T val;

    llist *next = NULL;

};

template<class T>

void insert(T val, llist<T> *&start, llist<T> *&end){

    if(start == NULL){

        llist<T> *newstart = new llist<T>;

        newstart->val = val;

        start = newstart;

        end = start;

    }

    else{

        llist<T> *newnode = new llist<T>;

        newnode->val = val;

        

        end->next = newnode;

        end = newnode;

    }

}

template<class T>

void remove(T val, llist<T> *start){

    llist<T> *cur = start, *prevcur = NULL;

    

    while(cur != NULL){

        if(cur->val == val){

            prevcur->next = cur->next;

            delete cur;

            cur = prevcur;

        }

        prevcur = cur;

        cur = cur->next;

    }

}

template<class T>

void showlist(llist<T> *start){

    if(start == NULL) return;

    llist<T> *cur = start;

    while(cur != NULL){

        std::cout << cur->val << " ";

        cur = cur->next;

    }

    std::cout << std::endl;

}

int main(){

    llist<int> *start = NULL, *end = NULL;

    insert<int>(1, start, end);

    insert<int>(4, start, end);

    insert<int>(6, start, end);

    insert<int>(4, start, end);

    remove<int>(4, start);

    showlist<int>(start);

    return 0;

}

          Output:

1 6

 Circular Single Linked List
Circular single linked list adalah single linked list yang node terakhirnya bukan menunjuk ke NULL, melainkan menunjuk kearah node pertama. Cara membuatnya adalah sama dengan single linked list biasa tetapi setiap menambahkan node baru, pointer selanjutnya dari node tersebut mengarah ke node pertama.

Contoh penggunaan circular single linked list adalah untuk algoritma first in first out atau algoritma round-robin. Circular single linked list juga bisa dipakai untuk mengakses data yang membutuhkan mengakses node awal lagi setelah mencapai node terakhir. Contoh lainnya adalah game monopoli dimana bentuk permainannya hanya bisa pergi ke kota selanjutnya dan ketika mencapai kota terakhir maka akan mengulang lagi dari kota pertama. Circular single linked list akan dapat mempermudah proses tersebut.


Doubly Linked List
Doubly linked list adalah tipe linked list dimana setiap node mempunyai dua pointer, ke arah node selanjutnya dan ke arah node sebelumnya. Dengan begitu saat melakukan traversal di suatu linked list, bisa kembali ke node sebelumnya dibanding dengan single linked list yang hanya bisa sekali jalan. Cara membuat doubly linked list adalah dengan menambahkan satu pointer lagi pada struct node nya. Pointer ini harus menunjuk ke arah node sebelumnya. Kecuali untuk node pertama, maka pointer ke arah sebelumnya diisi dengan NULL dan untuk node terakhir, pointer ke arah selanjutnya diisi dengan NULL.

Contoh penggunaan dari doubly linked list adalah sistem undo dan redo. Dimana kita harus mengakses data yang sekarang dan bisa kembali ke sebelum dan sesudahnya dengan cepat. Jika sistem undo dan redo dilakukan dengan single linked list, maka dia harus mengulang lagi dari node pertama untuk kembali ke node sebelumnya.


Circular Doubly Linked List
Circular double linked list adalah gabungan antara doubly linked list dan circular linked list. Bentuknya adalah seperti doubly linked list biasa, tetapi hanya berbeda pada node awal dan akhirnya saja. Untuk node awal, pointer yang menunjuk node sebelumnya diisi dengan address dari node akhir bukan NULL seperti pada doubly linked list biasa. Pada node akhir pointer yang menunjuk node selanjutnya diisi dengan address dari node pertama yang seharusnya diisi dengan NULL juga pada doubly linked list. Dengan begitu seseorang bisa melakukan traversal ke depan dan kebelakang.

Contoh penggunan doubly linked list adalah seperti playback musik dimana kita bisa melakukan mengulang dari awal, memutar kedepan, dan memutar kebelakang. Dengan menggunakan doubly linked list, proses tersebut bisa dilakukan dengan mudah. Karena data tersebut memiliki insformasi ke dua arah dan mempunyai informasi untuk kembali ke awal setelah mencapai akhir. Data tersebut juga bisa diputar terbalik karena node awal memiliki informasi untuk ke node terakhir tanpa perlu adanya pointer tambahan.

Stack dan Queue
Setelah itu saya mempelajari apa itu stack dan queue. Secara singkat, stack itu adalah tipe penyimpanan data yang menggunakan sistem "first in, last out" yang artinya data yang paling bawah dimasukkan akan keluar paling terakhir. Sedangkan queue adalah yang menggunakan sistem "first in, first out" yang artinya data yang paling pertama dimasukkan akan dikeluarkan pertama.

Hash Table
Hash Table adalah sebuah struktur data yang menggunakan array sebagai media penyimpanannya. Sebuah data diproses melalui suatu fungsi yang akan menentukan index dari array untuk menyimpannya. Fungsi tersebut dinamakan hash function dan isi dari sebuah hash function bermacam-macam. Collision terjadi ketika sebuah data dimasukkan ke hash function dan menghasilkan index yang sama dengan data yang berbeda.

Suatu hash function yang bagus adalah ketika jarang terjadinya collision dengan data yang bermacam-macam. Maka dari itu hash function yang bagus memiliki sifat pseudo-random yaitu acak tetapi terkontrol. Artinya output yang dikeluarkan hanya mengeluarkan 1 jenis untuk 1 tipe data. Itulah alasannya mengapa hash table biasanya digunakan dalam pengenkripsian data.

Contoh penggunaan hash table untuk meginput data:

int hash_table[100];   // Deklarasi hash table sebesar 100

hash_table[hash_function(10)] = 10; // Menaruh data ke index dari suatu hash function

Lalu ketika memprint hanya tinggal mendapatkan indeks array dari hash functionnya lagi

cout << hash_table[hash_function(10)];

Output:

10

Karena indeks dari hash table bisa didapatkan hanya dengan perantara hash function maka waktu untuk insert, delete, dan searching dalam hash table adalah O(1). Tetapi tentu saja itu hash table hanya akan O(1) jika tidak terjadi collision sama sekali.

Binary Search Tree
Binary Search Tree adalah sebuah struktur data yang terdiri dari node yang memiliki cabang paling banyak 2 cabang. Cabang tersebut biasa dinamakan node kanan dan node kiri. Node kiri selalu berisi data yang nilainya lebih kecil dari node sebelumnya, sedangkan node kanan selalu berisi data yang nilainya lebih besar dari node sebelumnya. Node utama yang berada paling atas dinamakan root. Sedangkan node yang paling luar yang tidak memiliki children dinamakan leaf. Ilustrasi dari sebuah binary search tree adalah seperti berikut:

Contoh sebuah struct untuk node binary tree dengan C++:

struct bst{

    int value;

    bst *parent;

    bst *left;

    bst *right;

    bst(int val){

        value = val;

        parent = nullptr;

        left = nullptr;

        right = nullptr;

    }

} *root = nullptr;

value di didalam struct ini adalah untuk menyimpan datanya. Lalu ada 3 pointer, pointer parent menunjuk ke arah parent atau node diatasnya, pointer left menunjuk ke arah data yang nilainya lebih kecil, pointer right menunjuk ke arah data yang nilainya lebih besar.


Ada 3 operasi dasar pada binary search tree yaitu insert(), find(), dan remove().
Operasi yang pertama adalah find().Operasi ini adalah operasi untuk mencari apakah suatu nilai ada di dalam tree-nya. Contoh fungsi find():

bst* find(int val){

    if(root == nullptr) return nullptr;

    bst *cur = root;

    while(true){

        if(val == cur->value)

            return cur;

        else if(val > cur->value){

            if(cur->right == nullptr)

                break;

            else

                cur = cur->right;

        }

        else if(val < cur->value){

            if(cur->left == nullptr)

                break;

            else

                cur = cur->left;

        }   

    }

    return nullptr;

}

Fungsi ini akan mengembalikan pointer dari nilai yang dicari jika ketemu dan mengembalikan pointer kosong (nullpointer) jika tidak ketemu. Karena fungsi ini mengembalikan pointer ke struct yang dicari, maka perlu dibuat fungsi lain yang gunanya untuk mengecek jika nilai tersebut ada atau tidak.

bool exist(int val){

    if(find(val) != nullptr)

        return true;

    else

        return false;

}

 Fungsi exist() ini adalah fungsi boolean yang akan mengembalikan true apabila nilai yang dicari ada dan false bila tidak ada. Fungsi ini dibuat untuk mempermudah melakukan pengecekan nilai karena tidak perlu mengecek dari adanya data atau nullpointer.


Operasi yang kedua adalah operasi insert(). Operasi ini berfungsi untuk memasukkan nilai baru kedalam sebuah binary search tree. Contoh operasi insert():

void insert(int val){

    if(root == nullptr) // If root is empty, create root

        root = new bst(val);

    else{

        bst *cur = root;

        while(true){

            if(val > cur->value){   // If value is bigger traverse left

                if(cur->right == nullptr){

                    bst *newnode = new bst(val);

                    cur->right = newnode;

                    newnode->parent = cur;

                    break;

                }

                else

                    cur = cur->right;

            }

            else if(val < cur->value){  // If value is smaller traverse left

                if(cur->left == nullptr){

                    bst *newnode = new bst(val);

                    cur->left = newnode;

                    newnode->parent = cur;

                    break;

                }

                else

                    cur = cur->left;

            }

            else break; // If value already exist, break

        }

    }

}

Fungsi insert() hanya akan boleh berjalan apabila nilai yang ingin dimasukkan belum ada pada tree-nya. Jika rootnya belum ada maka node baru akan dibuat di root. Jika root sudah ada maka node tersebut akan ditempatkan sesuai dengan aturan binary search tree yaitu kiri lebih kecil, kanan lebih besar.

Operasi dasar terakhir adalah operasi remove(). Operasi ini berguna untuk menghapus data yang sudah ada. Contoh operasi remove():

void remove(int val){

    bst* cur = find(val);   // Find the value to be deleted

    if(cur == nullptr) return;  // If value is not found

    // Check the position if the data is on the right or left node

    bool isroot = false, isleft = false;

    if(cur->parent == nullptr)  // If the is a root

        isroot = true;

    else if(cur->parent->left == cur)

        isleft = true;

    else if(cur->parent->right == cur)

        isleft = false;

    if(cur->left == nullptr && cur->right == nullptr){  // If node has no children

        if(!isroot){

            if(isleft)

                cur->parent->left = nullptr;

            else

                cur->parent->right = nullptr;

        }

        delete cur;

    }

    else if(cur->left != nullptr && cur->right == nullptr){ // If node only has one children on left

        if(isroot){

            root = cur->left;

        }

        else{

            if(isleft)

                cur->parent->left = cur->left;

            else

                cur->parent->right = cur->left;

        }

        delete cur;

    }

    else if(cur->left == nullptr && cur->right != nullptr){ // If node only has one children on right

        if(isroot){

            root = cur->right;

        }

        else{

            if(isleft)

                cur->parent->left = cur->right;

            else

                cur->parent->right = cur->right;

        }

        delete cur;

    }

    else{   // If node has two childrens

       bst *successor = cur->right;

        // Finding successor

        while(true){

            if(successor->left != nullptr)

                successor = successor->left;

            else

                break;

        }

        // Put the node's successor as replacement

        if(isroot){

            // Check if successor is the first node after 

            if(successor->parent == cur){

                successor->left = root->left;

                successor->parent = nullptr;

            }

            else{

                // Put the right side of successor (if there's any) to it's parent

                successor->parent->left = successor->right;

                

                // replacing the root with successor

                successor->left = root->left;

                successor->right = root->right;

                successor->parent = nullptr;

            }

            root = successor;

        }

        else{

            // Check if successor is the first node after 

            if(successor->parent == cur){

                successor->left = cur->left;

                successor->parent = cur->parent;

                if(isleft)

                    cur->parent->left = successor;

                else

                    cur->parent->right = successor;

            }

            else{

                // Put the right side of successor (if there's any) to it's parent

                successor->parent->left = successor->right;

                

                // replacing the root with successor

                successor->left = cur->left;

                successor->right = cur->right;

                successor->parent = cur->parent;

                

                if(isleft)

                    cur->parent->left = successor;

                else

                    cur->parent->right = successor;

            }

        }

        delete cur;

    }

}

Pertama fungsi nilai yang ingin di delete dicari lebih dulu dengan menggunakan fungsi find(). Lalu fungsi remove() dibagi menjadi 2 kondisi yaitu ketika dia root atau bukan dan dibagi lagi menjadi 3 kondisi yaitu ketika dia memiliki satu children, dua children, dan tidak ada children. Cara untuk menghapus untuk setiap kondisi berbeda-beda yang dapat dilihat dari kode diatas.

Setelah membuat ketiga fungsi diatas, tentu saja perlu suatu fungsi untuk memprint angka untuk mengecek hasilnya. Contoh fungsi yang memprint angka dari kecil ke besar (secara inorder):

void printinorder(bst *node){

    if(node->left != nullptr)

        printinorder(node->left);

    cout << node->value << " ";

    if(node->right != nullptr)

        printinorder(node->right);

}

Lalu contoh program untuk mengetes semua fungsi diatas:

int main(){

    // Adding numbers to the tree

    insert(5);

    insert(3);

    insert(9);

    insert(6);

    insert(1);

    cout << "All numbers in ascending order:" << endl;

    printinorder(root);

    cout << endl;

    if(exist(3))

        cout << "3 exist in the tree" << endl;

    else

        cout << "3 not exist in the tree" << endl;

    cout << endl;

    // Removing 3 from the tree

    remove(3);

    cout << "After removal:" << endl;

    printinorder(root);

    cout << endl;

    if(exist(3))

        cout << "3 exist in the tree" << endl;

    else

        cout << "3 not exist in the tree" << endl;

    

    return 0;

}

Output:

    All numbers in ascending order:

1 3 5 6 9

    3 exist in the tree

    After removal:

    1 5 6 9

    3 not exist in the tree