Final Summary

SUMMARY
Nama saya Rahadi Fauzan Ramadhan dan pada kesempatan kali ini saya akan membagikan rangkuman seluruh materi yang sudah saya pelajari selama ini.

LINKED LIST

1. Circular Singly Linked List
Dalam Circular Singly Linked List, dapat disimpulkan bahwa setiap node pada Linked List mempunyai field yang berisi pointer ke node berikutnya, dan field yang berisi data. Pada akhir Linked List, node terakhir akan menunjuk ke node pertama sehingga Linked List tersebut mengalami pengulangan dan begitu seterusnya.

2. Doubly Linked List

Dalam Doubly Linked List, dapat disimpulkan bahwa setiap node pada Linked List mempunyai field yang berisi data dan pointer ke node berikutnya dan ke node sebelumnya. Untuk pembentukan node baru, pointer dibagi menjadi dua, yaitu next dan prev, next akan menunjuk ke node berikutnya, dan prev akan menunjuk ke node sebelumnya.

3. Circular Doubly Linked List

Dalam Circular Doubly Linked List, dapat disimpulkan bahwa pada dasarnya sama saja dengan Doubly Linked List, tapi pada Circular Doubly Linked List, node akhir akan menunjuk lagi ke node pertama, sehingga Linked List tersebut mengalami pengulangan.

Pada linked list, terdapat istilah push dan pop, dimana push berarti insert data baru pada linked list tersebut, dimana kita bisa push dari depan, belakang, atau dari tengah. Sedangkan pop berarti mendelete data, data dari depan, tengah, dan juga belakang.

Dikarenakan saya belum paham sepenuhnya, berikut 2 contoh sc untuk single linked list yang saya dapat dari pertemuan tadi, namun sebelum membuat push dan pop, pertama-tama kita perlu membuat struct terlebih dahulu:

struct Data
{
    int value;
    struct Data *next,*prev;
}*head,*curr,*tail;

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 pop2()
{
    if(tail == head){
        free(curr);
        tail = head = curr = NULL;
    }
    else
    {
        tail = tail->prev;
        free(tail->next);
        tail->next = NULL;
    }
}

NOTE : free() perlu digunakan untuk pembebasan memory yang tidak dipakai lagi setelah dipesan melalui malloc.

Hashing Table
Hash Table adalah sebuah struktur data yang digunakan untuk menyimpan data sementara. Hash Table menggunakan fungsi untuk memperhitungkan index ke dalam array dimana akan terdapat elemen yang bisa dimasukkan atau dicari.

Binary Tree

Salah satu fitur yang sering digunakan di data struct adalah Tree (Binary Tree). Binary Tree digunakan untuk mewakili struktur data nonlinear

Binary Search Tree 

Binary Search Tree adalah struktur data yang mengambil konsep Binary Tree namun terdapat aturan bahwa setiap child node sebelah kiri selalu lebih kecil nilainya dari pada root node. Begitu pula sebaliknya, setiap child node sebelah kanan selalu lebih besar nilainya daripada root node.

Operasi find

Operasi untuk mencari nilai dalam binary search tree

Memulai Find Dari Root

Jika Root adalah value yang kita cari , maka berhenti

Jika x lebih kecil dari root maka cari kedalam rekrusif tree sebelah kiri

Jika x lebih besar dari root maka cari kedalam rekrusif tree sebelah kanan.

Operasi insert

Operasi untuk mencari nilai dalam binary search tree

Dimulai insert dari root

jika x lebih kecil dari node value(key) kemudian cek dengan sub-tree sebelah kiri lakukan pengecekan secara rekrusif

jika x lebih besar dari node value(key) kemudian cek dengan sub-tree sebelah kanan lakukan pengecekan secara rekrusif

Ulangi sampai menemukan node yang kosong untuk memasukan value X

Operasi remove

Operasi untuk mengapus nilai

Jika nilai yang ingin dihapus adalah Daun atau paling bawah , langsung delete

Jika nilai yang akan dihapus mempunyai satu anak, hapus nodenya dan gabungkan      anaknya ke parent value yang dihapus.

jika nilai yang akan di hapus adalah node yang memiliki 2 anak , maka ada 2 cara , kita bisa cari dari left sub-tree anak kanan paling terakhir(leaf) (kiri,kanan).

AVL TREE

AVL Tree adalah Binary Search Tree yang memiliki perbedaan tinggi/ level maksimal 1 antara subtree kiri dan subtree kanan. AVL Tree muncul untuk menyeimbangkan Binary Search Tree. Dengan AVL Tree, waktu pencarian dan bentuk tree dapat dipersingkat dan disederhanakan

AVL TREE itu mempunyai 2 cara untuk merotasi nodenya yaitu:

A.SINGLE ROTATION

Single rotation dilakukan bila kondisi AVL tree waktu akan ditambahkan node baru dan posisi node baru adalah subtree yang urutannya harus seperti demikian serta height- nya harus sama (≥ 0). Hal ini juga berlaku untuk AVL tree yang merupakan citra cermin .

B.DOUBLE ROTATION

Double rotasi dilakukan apabila searah yaitu right to left atau left to right

HEAP

Hari ini saya akan menyampaikan sebuah rangkuman tentang Heap dan Tries

Heap adalah sebuah Complete Binary Tree yang memenuhi persyaratan heap. Heap mempunyai porperties sebagai berikut:

Min Heap

Setiap node lebih kecil dari masing-masing childnya

Root merupakan node paling kecil, sedangkan node terbesar terletak pada leaf node

Max Heap

Setiap node lebih besar dari masing-masing childnya

Root merupakan node paling besar, sedangkan node terkecil terletak pada leaf node

Min-Max Heap

Heap dengan Min heap pada level ganjil dan Max heap pada level genap

TRIES

Tries adalah tree yang dilakukan untuk menyimpan array asosiatif

Properties pada tries:

Setiap vertex/node merepresentasikan satu huruf

Root merepresentasikan karakter kosong