Review

Materi Review :

1. Linked List
2. Stack & Queue
3. Hashing & Hash Tables
4. Trees & Binary Tree
5. Binary Search Tree

1. Linked List

Linked list atau senarai berantai adalah struktur data yang terdiri dari urutan record data dimana 

setiap record memiliki field yang menyimpan alamat atau referensi dari record selanjutnya. Elemen data yang dihubungkan dengan link pada linked list disebut Node. Biasanya didalam suatu linked list, terdapat istilah head dan tail.

• Head adalah elemen yang berada pada posisi pertama dalam suatu linked list
• Tail adalah elemen yang berada pada posisi terakhir dalam suatu linked list

Ada beberapa macam linked list, yaitu :
1. Single Linked List

Single Linked List merupakan suatu linked list yang hanya memiliki satu variabel pointer saja. dimana pointer tersebut menunjuk ke node selanjutnya. Biasanya field pada tail menunjuk ke NULL.

Pembuatan Single Linked List dapat menggunakan 2 metode:

• LIFO (Last In First Out), aplikasinya : stack (tumpukan) 

• FIFO (First In First Out), aplikasinya : queue (antrean)

Contoh Codingannya:

struct Mahasiswa{

    char nama[31];

    int NIM;

struct Mahasiswa *next;

}*head,*tail;

      2. Double Linked List

Salah satu kelemahan single linked list adalah pointer (penunjuk) hanya dapat bergerak satu arah saja, maju/mundur, atau kanan/kiri sehingga pencarian data pada single linked list hanya dapat bergerak dalam satu arah saja. Untuk mengatasi kelemahan tersebut, dapat menggunakan metode double linked list.

Double linked list merupakan suatu linked list yang memiliki dua variabel pointer yaitu pointer yang menunjuk ke node selanjutnya dan pointer yang menunjuk ke node sebelumnya. Setiap head dan tailnya juga menunjuk ke NULL.

Contoh Codingannya:

struct Dosen{
    char Nama[35];
    int kode_dosen;
struct Dosen *next,*prev;
}*head,*tail;

3. Circular Linked List

Circular Linked List merupakan suatu linked list dimana tail (node terakhir) menunjuk ke head (node pertama). Jadi tidak ada pointer yang menunjuk NULL. Ada 2 jenis circular linked list, yaitu :

• Circular Single Linked List

• Circular Double Linked List

Contoh:

4. Multiple Linked List

Multiple Linked List merupakan suatu linked list yang memiliki lebih dar 2 buat variabel pointer.

Operasi-Operasi yang ada pada linked list :

• Insert

Istilah Insert berarti menambahkan sebuah simpul baru ke dalam suatu linked list.

• IsEmpty

Fungsi ini menentukan apakah linked list kosong atau tidak.

• Find First

Fungsi ini mencari elemen pertama dari linked list

• Find Next

Fungsi ini mencari elemen sesudah elemen yang ditunjuk now

• Retrieve

Fungsi ini mengambil elemen yang ditunjuk oleh now. Elemen tersebut lalu dikembalikan oleh fungsi.

• Update

Fungsi ini mengubah elemen yang ditunjuk oleh now dengan isi dari sesuatu

• Delete Now

Fungsi ini menghapus elemen yang ditunjuk oleh now. Jika yang dihapus adalah elemen pertama dari linked list (head), head akan berpindah ke elemen berikut.

• Delete Head

Fungsi ini menghapus elemen yang ditunjuk head. Head berpindah ke elemen sesudahnya.

• Clear

Fungsi ini menghapus linked list yang sudah ada. Fungsi ini wajib dilakukan bila anda ingin mengakhiri program yang menggunakan linked list. Jika anda melakukannya, data-data yang dialokasikan ke memori pada program sebelumnya akan tetap tertinggal di dalam memori.

2. Stack & Queue

• Stack 

Stack atau tumpukan dapat diartikan sebagai suatu kumpulan data yang seolah-olah terlihat seperti ada data yang diletakkan di atas data yang lain. Kaidah utama dalam konsep stack adalah LIFO yang merupakan singkatan dari Last In First Out, artinya adalah data yang terakhir kali dimasukkan atau disimpan, maka data tersebut adalah yang pertama kali akan diakses atau dikeluarkan.

Sebuah struktur data dari sebuah stack setidaknya harus mengandung dua buah variabel, misalnya variabel top yang akan berguna sebagai penanda bagian atas tumpukan dan array data dari yang akan menyimpan data-data yang dimasukkan ke dalam stack tersebut.

Operasi-operasi dasar dalam stack ada 2 yaitu operasi push dan pop:

• Operasi push, berfungsi untuk memasukkan sebuah nilai atau data ke dalam stack. Sebelum sebuah nilai atau data dimasukkan ke dalamstack, prosedur ini terlebih dahulu akan menaikkan posisi top satu level ke atas. 

• Operasi pop, berfungsi untuk mengeluarkan atau menghapus nilai terakhir (yang berada pada posisi paling atas) dari stack, dengan cara menurunkan nilai top satu level ke bawah.

• Queue

Queue atau antrian merupakan struktur data linear dimana penambahan komponen dilakukan disatu ujung, sementara pengurangan dilakukan diujung lain. Kaidah utama dalam konsep queue adalah FIFO yang merupakan singkatan dari First In First Out, artinya adalah data yang pertama kali dimasukkan atau disimpan, maka data tersebut adalah yang pertama kali akan diakses atau dikeluarkan.

Sebuah queue di dalam program komputer dideklarasikan sebagai sebuah tipe bentukan baru. Sebuah struktur data dari sebuah queue setidaknya harus mengandung dua tiga variabel, yakni variabel head yang akan berguna sebagai penanda bagian depan antrian, variabeltail yang akan berguna sebagai penanda bagian belakang antrian danarray dari yang akan menyimpan data-data yang dimasukkan ke dalam queue tersebut.

Operasi-operasi dasar dalam queque ada 2 yaitu operasi enqueue dan dequeue:

• Operasi enqueue, digunakan untuk memasukkan sebuah data atau nilai ke dalam queue. Pada proses enqueue, tail -lah yang berjalan seiring masuknya data baru ke dalam antrian, sedangkan head akan tetap pada posisi pertama. 

• Operasi dequeue, digunakan untuk menghapuskan sebuah data atau nilai yang paling awal masuk ke dalam queue. Operasi ini menaikkan nilai head satu level.

3. Hashing & Hash Tables

• Hashing

Anda mungkin menyadari bahwa tabel T pada contoh sebelumnya bekerja seperti array. Kita seakan-akan dapat melakukan operasi:

T["gozali"] = 3;printf("%d\n", T["gozali"]);

Pada ilmu komputer, tabel seperti ini disebut sebagai hash table. Struktur data ini erat kaitannya dengan konsep "key value". Key adalah hal yang menjadi indeks, dan value adalah nilai yang berasosiasi dengannya. Pada contoh permasalahan sebelumnya, nama mahasiswa merupakan key, dan IPK merupakan value.
Perhatikan bahwa key tidak harus berupa string. Tipe data apapun dapat didukung, asalkan didefinisikan fungsi hash-nya. Kalau untuk value, tentu saja datanya bisa bertipe apapun.
Operasi minimal yang perlu didukung oleh hash table adalah:

• Diberikan key X dan value Y, catat bahwa value dari X adalah Y. Operasi ini dapat dianggap "T[X] = Y".

• Diberikan key X, cari value-nya. Operasi ini dapat dianggap seperti mengakses "T[X]".

Dapat diartikan sebagai aktivitas untuk mengubah suatu objek menjadi serangkaian angka/karakter/sejenisnya. Pada contoh sebelumnya, kita melakukan hash pada string menjadi bilangan.

Kedua operasi ini disebut sebagai update dan read. Kompleksitas operasi-operasi ini adalah O(K), dengan O(K) adalah kompleksitas melakukan hash pada suatu key.

Fungsi Hashing

Pada dasarnya fungsi hashing itu bebas, terserah Anda ingin mendefinisikannya seperti apa. Namun, diharapkan fungsi hashing memiliki kriteria sebagai berikut:

1. Untuk dua buah key yang sama, hasil hashing-nya selalu sama.
2. Memiliki kompleksitas rendah.
3. Meminimalkan collision.

Pada kebanyakan kasus, kompleksitas fungsi hash dapat dianggap O(1).  Sehingga operasi update dan read bekerja dalam O(1).

Hash Tables 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. Keunggulan dari struktur hash table ini adalah waktu aksesnya yang cukup cepat, jika record yang dicari langsung berada pada angka hash lokasi penyimpanannya. Akan tetapi pada kenyataannya sering sekali ditemukan hash table yang record-recordnya mempunyai angka hash yang sama (bertabrakan).

🔺operasi pada hash table:

1. insert: diberikan sebuah key dan nilai, insert nilai dalam tabel
2. find: diberikan sebuah key, temukan nilai yang berhubungan dengan key
3. remove: diberikan sebuah key,temukan nilai yang berhubungan dengan key, kemudian hapus nilai tersebut
4. getIterator: mengambalikan iterator,yang memeriksa nilai satu demi satu

➢contoh :

struct hashnode_s {

char *key;

void *data;

struct hashnode_s *next;

};

4. Tree & Binary Tree

• Tree 

Tree adalah salah satu bentuk struktur data yang menggambarkan hubungan hierarki antar elemen-elemennya (seperti relasi one to many). Sebuah node dalam tree biasanya bisa memiliki beberapa node lagi sebagai percabangan atas dirinya.

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

➢contoh :

struct node {
  int data;
  struct node *left;
  struct node *right;

};

5. Binary Search Tree

Binary Search Tree adalah sebuah konsep penyimpanan data, dimana data disimpan dalam bentuk tree yang setiap node dapat memiliki anak maksimal 2 node.

Aturan main Binary Search Tree :

• Setiap child node sebelah kiri harus lebih kecil nilainya daripada root nodenya.

• Setiap child node sebelah kanan harus lebih besar nilainya daripada root nodenya.

Lalu, ada 3 jenis cara untuk melakukan penelusuran data (traversal) pada BST :

• PreOrder : Print data, telusur ke kiri, telusur ke kanan

• InOrder : Telusur ke kiri, print data, telusur ke kanan

• Post Order : Telusur ke kiri, telusur ke kanan, print data

Berikut adalah contoh Binary Search Tree (BST) pada C :

//
// Created by Hanry Ham on 2019-04-02.
//

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

char stakeholder[][10]={"Lecturer", "Student"};
bool isShow = false;

struct node{
    int binusianID;
    char binusianName[26];
    char type[15];
    struct node *left;
    struct node *right;
}*root = NULL, *curr;

struct node *newNode(int binusianID, char *binusianName, char *type){
    curr = (struct node *) malloc (sizeof(struct node));
    curr->binusianID = binusianID;
    strcpy(curr->binusianName, binusianName);
    strcpy(curr->type, type);
    curr->left = NULL;
    curr->right = NULL;
    return curr;
}

struct node *insert(struct node *ptr, int binusianID, char *binusianName, char *type){
    if(ptr == NULL){
        ptr = newNode(binusianID, binusianName, type);
    }else{
        if(binusianID < ptr->binusianID)
            ptr->left = insert(ptr->left, binusianID, binusianName, type);
        else if(binusianID > ptr->binusianID)
            ptr->right = insert(ptr->right, binusianID, binusianName, type);
        else
            printf("Value should be unique!\n");
    }
    return ptr;
}

struct node *successor(struct node *ptr){
    //right subtree, get the smallest
    curr = ptr->right;
    while(curr->left){
        curr = curr->left;
    }
    return curr;
}

struct node *remove(struct node * ptr, int binusianID){
    if(ptr == NULL) return NULL;

    if(binusianID < ptr->binusianID){
        ptr->left = remove(ptr->left, binusianID);
    }else if(binusianID > ptr->binusianID){
        ptr->right = remove(ptr->right, binusianID);
    }else{
        if((ptr->left == NULL) || (ptr->right == NULL)){

            struct node *temp = NULL;
            if(ptr->left != NULL) temp = ptr->left;
            else temp = ptr->right;

            if(temp == NULL){
                temp = ptr;
                ptr = NULL;
            }else{
                *ptr = *temp;
            }
            free(temp);
        }else{
            // have 2 children
            struct node *temp = successor(ptr);
            //*ptr = *temp;
            ptr->binusianID = temp->binusianID;
            strcpy(ptr->binusianName, temp->binusianName);
            strcpy(ptr->type, temp->type);
            
            ptr->right = remove(ptr->right, temp->binusianID);
        }
    }
    return ptr;
}

struct node *removeAll(struct node *ptr){
    if(ptr){
        ptr->left = removeAll(ptr->left);
        ptr->right = removeAll(ptr->right);
        free(ptr);
        ptr = NULL;
    }
    return ptr;
}

struct node *search(struct node *ptr, int binusianID){
    if(ptr == NULL)
        return NULL;
    if(binusianID == ptr->binusianID)
        return ptr;
    if(binusianID < ptr->binusianID)
        return search(ptr->left, binusianID);
    if(binusianID > ptr->binusianID)
        return search(ptr->right, binusianID);
}

void preOrder(struct node *root){
    if(root){
        printf("||%15d || %15s || %15s ||\n", root->binusianID, root->binusianName, root->type);
        preOrder(root->left);
        preOrder(root->right);
    }
}

void print(struct node *root){
    if(root && isShow==true){
        printf("=========================================================\n");
        printf("||%15s || %15s || %15s ||\n", "Binusian ID", "Binusian Name", "Position");
        printf("=========================================================\n");
        preOrder(root);
        printf("=========================================================\n\n");
    }else{
        printf("No data ...\n");
    }
}

void validatePrintFlag(int checker){
    if(checker % 2 == 1) isShow = true;
    else isShow = false;
}

int getMenu(){
    int choice;
    printf("--------------------------------------------------\n");
    printf("|School of Computer Science Stakeholders Database|\n");
    printf("--------------------------------------------------\n");
    printf("1. Insert\n");
    if(!isShow)
        printf("2. Show View (Pre-Order)\n");
    else
        printf("2. Close View (Pre-Order)\n");
    printf("3. Delete\n");
    printf("4. Exit\n");
    printf("Choice : ");
    scanf("%d", &choice);
    fflush(stdin);
    return choice;
}

void insertMenu(){
    int binusianID;
    char binusianName[26];
    char type[15];
    struct node* tmpSearch;

    do{
        printf("\n\nBinusian ID [1..999] : ");
        scanf("%d", &binusianID);
        fflush(stdin);
    }while(binusianID<1 || binusianID>999);
    tmpSearch = search(root, binusianID);

    if(!tmpSearch){
        do{
            printf("Binusian Name [5..25] : ");
            scanf("%[^\n]", binusianName);
            fflush(stdin);
        }while(strlen(binusianName)<5 || strlen(binusianName)>25);

        do{
            printf("Binusian type [Student / Lecturer] : ");
            scanf("%s", type);
            fflush(stdin);
        }while(strcmpi(stakeholder[0], type)!=0 && strcmpi(stakeholder[1], type)!=0);

        root = insert(root, binusianID, binusianName, type);
        printf("Successfully added ...");
    }else{
        printf("%d is existed, data can not be added", binusianID);
    }
    getchar();
}

void removeMenu(){
    struct node *tmp;
    int binusianID;
    printf("Binusian ID to delete : ");
    scanf("%d", &binusianID);
    fflush(stdin);

    tmp = search(root, binusianID);
    if(tmp){
        root = remove(root, binusianID);
        printf("%d has been removed\n", binusianID);
    }
    else{
        printf("%d can not be found in the system\n", binusianID);
    }
}

int main(){
    int choice;
    int checkerShow = 0;
    do{
        system("cls");
        if(isShow)
            print(root);
        choice = getMenu();
        switch(choice){
            case 1:
                insertMenu();
                break;
            case 2:
                checkerShow++;
                validatePrintFlag(checkerShow);
                break;
            case 3:
                removeMenu();
                getchar();
                break;
            case 4:
                removeAll(root);
                printf("Thank you");
                getchar();
                break;
        }
    }while(choice!=4);

    return 0;
}