Rangkuman pembelajaran Data Structure

LINKED LIST

Linked list atau kadang-kadang disebut dengan senarai berantai atau daftar bertaut dalam ilmu komputer merupakan sebuah struktur data yang digunakan untuk menyimpan sejumlah objek data biasanya secara terurut sehingga memungkinkan penambahan, pengurangan, dan pencarian atas elemen data yang tersimpan dalam senarai dilakukan secara lebih efektif. Pada praktiknya sebuah struktur data memiliki elemen yang digunakan untuk saling menyimpan rujukan antara satu dengan lainnya sehingga membentuk sebuah senarai abstrak, tiap-tiap elemen yang terdapat pada senarai abstrak ini seringkali disebut sebagai node. karena mekanisme rujukan yang saling terkait inilah disebut sebagai senarai berantai. linked list juga bisa diartikan sebagai struktur data yang terdiri dari urutan record data dimana setiap record memiliki field yang menyimpan alamat/referensi dari record selanjutnya (dalam urutan). 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

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

• Double Linked List 
• Merupakan suatu linked list yang memiliki dua variabel pointer yang menunjuk ke node selanjutnya dan pointer yang menunjuk ke node sebelumnya. Setiap head dan tail juga menunjuk ke NULL.

• Circular Linked List 
• Merupakan suatu linked list dimana tail(node terakhir) menunjuk ke head (node pertama). Jadi, tidak ada pointer yang menunjuk ke NULL

Single Linked List
Inisialisasi struct yang dibutuhkan seperti dibawah ini
struct data{
int value;
struct data*next;
}*head=NULL,*tail,*curr;

Saya diajarkan fungsi push dan pop yang masing-masing bisa dari depan maupun belakang.
dibawah ini adalah source code untuk masing-masing push dan pop.

Push depan
void pushdepan(int x){
curr = (struct data*)malloc(sizeof(struct data));
curr->value=x; 

if(head==NULL){//linked list kosong
head=tail=curr;
}
else{
curr->next = head;
        head = curr;
    }
    tail->next = NULL;

}

push belakang
void pushbelakang(int x){
curr = (struct data*)malloc(sizeof(struct data));
curr->value=x; 

if(head==NULL){//linked list kosong
head=tail=curr;
}
else{
tail->next = curr;
        tail = curr;
    }
    tail->next = NULL;

}

Pop depan
void popdepan(){
    curr = head;
    
    if(tail == head){
        free(curr);
        tail = head = curr = NULL;
    }
    else
    {
        curr = curr->next;
        free(head);
        head = curr;
    }

}

Pop belakang

void popbelakang(){

    curr = head;

    

    if(tail == head){

        free(curr);

        tail = head = curr = NULL;

    }

    else

    {

        while(curr->next!=tail){

            curr = curr->next;

        }

        free(tail);

        tail = curr;

        tail->next = NULL;

    }

}

Double Linked List
Hampir sama seperti inisialisasi struct pada Single Linked List, pada Double Linked List ditambahkan parameter tambahan yaitu "prev" seperti dibawah ini
struct Data
{
    int value;
    struct Data *next,*prev;
}*head,*curr,*tail;

Saya juga diajarkan fungsi push dan pop. dibawah ini adalah source code untuk masing-masing push dan pop.

Push
void push(int a)
{
    curr = (struct Data*)malloc(sizeof(struct Data));
    curr->value = a;
    
    if(head==NULL){
        head = tail = curr;
    }
    else{
        tail->next = curr;
        curr->prev = tail;
        tail = curr;
    }
    head->prev = tail->next = NULL;

}

Pop
void pop()
{
    if(tail == head){
        free(curr);
        tail = head = curr = NULL;
    }
    else
    {
        tail = tail->prev;
        free(tail->next);
        tail->next = NULL;
    }
}

Hash Table

     Hash Table 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).

    Pemetaan hash function yang digunakan bukanlah pemetaan satusatu, (antara dua record yang tidak sama dapat dibangkitkan angka hash yang sama) maka dapat terjadi bentrokan (collision) dalam penempatan suatu data record. Untuk mengatasi hal ini, maka perlu diterapkan kebijakan resolusi bentrokan (collision resolution policy) untuk menentukan lokasi record dalam tabel. Umumnya kebijakan resolusi bentrokan adalah dengan mencari lokasi tabel yang masih kosong pada lokasi setelah lokasi yang berbentrokan.

    Operasi Pada Hash Tabel

Ø  insert: diberikan sebuah key dan nilai, insert nilai dalam tabel

Ø  find: diberikan sebuah key, temukan nilai yang berhubungan dengan key

Ø  remove: diberikan sebuah key,temukan nilai yang berhubungan dengan key, kemudian hapus nilai tersebut

Ø  getIterator: mengambalikan iterator,yang memeriksa nilai satu demi satu

Binary Tree

     Pohon biner adalah pohon dengan syarat bahwa tiap node hanya memiliki boleh 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 anak/child.

Node pada Binary Tree 
Jumlah maksimum node pada setiap tingkat adalah 2n, Node pada binary tree maksimumnya berjumlah 2n-1.

 

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. Selain itu, terdapat juga aturan dimana anak kiri dari parent selalu memiliki nilai lebih kecil dari nilai parent dan anak kanan selalu memiliki nilai lebih besar dari parent. Pada artikel ini, penulis akan membahas bagaimana cara mengimplementasikan binary search tree di dalam Bahasa C.