Linked List

Nama : Edric Elsen

NIM : 2301859461

Kelas : LO01

Nama Dosen:

(Kelas Besar) Ferdinand Ariandy Luwinda (D4522) & Henry Chong (D4460)

(Kelas Kecil) David (D4498)

Rangkuman Akhir Semester 2

>> Blog ini merupakan kumpulan dari blog-blog sebelumnya

Linked List

Linked list adalah sebuah struktur data yang terdiri dari sebuah tahapan dari rekaman-rekaman data yang setiap datanya itu ada sebuah bidang(field) yang mencakupi suatu referensi mengenai rekaman di tahapan selanjutnya.

Linked list sangatlah berguna khususnya dalam menyelesaikan masalah dalam waktu nyata atau waktu sebenarnya dimana beberapa unsur yang disimpan ialah tidak terprediksi dan juga saat tahapan akses dari unsur unsur itu.

Linked list terdiri dari 2 tipe yaitu, single dan double linked list. Single linked list biasanya ditandai dengan memiliki satu jalur hubungan dari suatu senarai(list) penunjuk ke senarai(list) lainnya. sedangkan double linked list adalah linked list struktur data yang memiliki dua link, link yang satu memiliki referensi ke data selanjutnya dan yang satunya lagi memili referensi ke sata sebelumnya.

Linked List Ilustration

Single Linked list dapat diilustrasikan sebagai suatu rantai data(node), dimana setiap data menunjuk ke data selanjutnya.

Seperti ilustrasi di atas, terdapat beberapa poin yang perlu dipertimbangkan :

Single linked list terdiri dari suatu unsur utama yang disebut Head
Single linked list juga memiliki unsur yang dinamakan dengan First
setiap link membawa suatu field data dan field link yang disebut Next
Setiap link yang terhubung dengan link selanjutnya menggunakan yang namanya Next Link
link terakhir membawa link yang berisi null yang menandakan akhir dari list tersebut yang biasa di sebut Tail

Double Linked list dapat diilustrasikan sebagai suatu rantai data(node), dimana setiap data menunjuk ke data selanjutnya dan juga data sebelumnya.

Seperti ilustrasi di atas, terdapat beberapa poin yang perlu dipertimbangkan :

Double linked list terdiri dari suatu unsur utama yang disebut Head
Double linked list memiliki yang namanya First dan Last
Setiap link membawa field data dan dua field link yang disebut dengan Next dan Prev
Setiap link yang terhubung dengan link selanjutnya menggunakan yang namanya Next Link
Setiap link yang terhubung dengan link seblumnya menggunakan yang namannya Previous Link
Link terakhir biasanya membawa null yang menandakan akhir dari list tersebut yang disebut dengan Tail

Operation pada double linked terdapat operasi dasar yaitu, insert dan delete.

>>> Insert

> Saat ingin menginsert node di belakang tail

//insert link at the last location
void insertLast(int key, int data) {

   //create a link
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key = key;
   link->data = data;
 
   if(isEmpty()) {
      //make it the last link
      last = link;
   } else {
      //make link a new last link
      last->next = link;     
      
      //mark old last node as prev of new link
      link->prev = last;
   }

   //point last to new last node
   last = link;
}

> saat memasukkan node pada posisi setelah suatu node

/* Given a node as prev_node, insert a new node after the given node */

void insertAfter(struct Node* prev_node, int new_data) 

{

    /*1. check if the given prev_node is NULL */

    if (prev_node == NULL) { 

        printf("the given previous node cannot be NULL"); 

        return; 

}

    /* 2. allocate new node */

    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); 

    /* 3. put in the data  */

    new_node->data = new_data; 

    /* 4. Make next of new node as next of prev_node */

    new_node->next = prev_node->next; 

    /* 5. Make the next of prev_node as new_node */

    prev_node->next = new_node; 

    /* 6. Make prev_node as previous of new_node */

    new_node->prev = prev_node; 

    /* 7. Change previous of new_node's next node */

    if (new_node->next != NULL) 

        new_node->next->prev = new_node; 

}

>>> Delete

>Jika node di delete pada bagian head atau yang paling awal maka

head = head->next;

free(head->prev);

head->prev = NULL;

>Jika node di delete pada bagian tail atau yang paling akhir maka

tail = tail->prev;

free(tail->next);

tail->next = NULL;

>Jika node di delete pada bagian yang bukan head atau yang paling awal tail atau yang paling akhir maka

struct tnode *curr = head;

while ( curr->next->value != x ) curr = curr->next;

struct tnode *a = curr;

struct tnode *del = curr->next;

struct tnode *b = curr->next->next;

a->next = b;

b->prev = a;

free(del);

>Jika node yang di delete adalah node yang hanya sendiri

free(head);

head = NULL;

tail = NULL;

Circular Linked List

Ada juga jenis linked list circular yang mencakupi circular single linked list dan circular double linked list.

1. Circular Single Linked List

Dalam circular single linked list, node terakhir berisikan penunjuk ke node pertama. Pada circular linked list tidak ada tempat penyempinan nilai null dalam listnya

Biasanya dapat diilustrasikan sebagai berikut

Singly Linked List as Circular Linked List

2. Circular Double Linked List

Dalam circular double linked list, setiap node memiliki dua pointer. Salah satu pointer itu menunjuk ke node yang selanjutnya dan pointer yang lain menunjuk ke node sebelumnya. Pada circular double linked list tidak terdapat nilai null pada pemnyimpanannya maka circular double linked list ini mirip dengan circular single linked list.

Linked List

Linked List Ilustration

Single Linked list dapat diilustrasikan sebagai suatu rantai data(node), dimana setiap data menunjuk ke data selanjutnya.

Seperti ilustrasi di atas, terdapat beberapa poin yang perlu dipertimbangkan :

Single linked list terdiri dari suatu unsur utama yang disebut Head
Single linked list juga memiliki unsur yang dinamakan dengan First
setiap link membawa suatu field data dan field link yang disebut Next
Setiap link yang terhubung dengan link selanjutnya menggunakan yang namanya Next Link
link terakhir membawa link yang berisi null yang menandakan akhir dari list tersebut yang biasa di sebut Tail

Double Linked list dapat diilustrasikan sebagai suatu rantai data(node), dimana setiap data menunjuk ke data selanjutnya dan juga data sebelumnya.

Seperti ilustrasi di atas, terdapat beberapa poin yang perlu dipertimbangkan :

Double linked list terdiri dari suatu unsur utama yang disebut Head
Double linked list memiliki yang namanya First dan Last
Setiap link membawa field data dan dua field link yang disebut dengan Next dan Prev
Setiap link yang terhubung dengan link selanjutnya menggunakan yang namanya Next Link
Setiap link yang terhubung dengan link seblumnya menggunakan yang namannya Previous Link
Link terakhir biasanya membawa null yang menandakan akhir dari list tersebut yang disebut dengan Tail

Operation pada double linked terdapat operasi dasar yaitu, insert dan delete.

>>> Insert

> Saat ingin menginsert node di belakang tail

//insert link at the last location
void insertLast(int key, int data) {

   //create a link
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key = key;
   link->data = data;
 
   if(isEmpty()) {
      //make it the last link
      last = link;
   } else {
      //make link a new last link
      last->next = link;     
      
      //mark old last node as prev of new link
      link->prev = last;
   }

   //point last to new last node
   last = link;
}

> saat memasukkan node pada posisi setelah suatu node

/* Given a node as prev_node, insert a new node after the given node */

void insertAfter(struct Node* prev_node, int new_data) 

{

    /*1. check if the given prev_node is NULL */

    if (prev_node == NULL) { 

        printf("the given previous node cannot be NULL"); 

        return; 

}

    /* 2. allocate new node */

    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); 

    /* 3. put in the data  */

    new_node->data = new_data; 

    /* 4. Make next of new node as next of prev_node */

    new_node->next = prev_node->next; 

    /* 5. Make the next of prev_node as new_node */

    prev_node->next = new_node; 

    /* 6. Make prev_node as previous of new_node */

    new_node->prev = prev_node; 

    /* 7. Change previous of new_node's next node */

    if (new_node->next != NULL) 

        new_node->next->prev = new_node; 

}

>>> Delete

>Jika node di delete pada bagian head atau yang paling awal maka

head = head->next;

free(head->prev);

head->prev = NULL;

>Jika node di delete pada bagian tail atau yang paling akhir maka

tail = tail->prev;

free(tail->next);

tail->next = NULL;

>Jika node di delete pada bagian yang bukan head atau yang paling awal tail atau yang paling akhir maka

struct tnode *curr = head;

while ( curr->next->value != x ) curr = curr->next;

struct tnode *a = curr;

struct tnode *del = curr->next;

struct tnode *b = curr->next->next;

a->next = b;

b->prev = a;

free(del);

>Jika node yang di delete adalah node yang hanya sendiri

free(head);

head = NULL;

tail = NULL;

Circular Linked List

Ada juga jenis linked list circular yang mencakupi circular single linked list dan circular double linked list.

1. Circular Single Linked List

Dalam circular single linked list, node terakhir berisikan penunjuk ke node pertama. Pada circular linked list tidak ada tempat penyempinan nilai null dalam listnya

Biasanya dapat diilustrasikan sebagai berikut

2. Circular Double Linked List

Linked List (2.0)
Pada penggunaan linked list terdapat 2 cara untuk memasukkan data atau menghapus data yang disebut dengan Push dan Pop.
Push bekerja sebagai pemasukkan data sedangkan Pop digunakan untuk menghapus data.
Push dan Pop ini bekerja pada letak data yang sama yaitu, push depan, push belakang, pop depan dan pop belakang.
Push dan pop ini pun bekerja pada single linked list maupun double linked list.
Penggunaan push dan pop biasanya diikuti dengan Memory Allocation(Malloc).

PUSH(Single Linked List)
Push adalah operasi pada linked list yang digunakan untuk memasukkan atau menambahkan node atau data. push depan biasanya memasukkan data ke yang paling depan sedangkan push belakang memasukkan data ke yang paling belakang.
>>KODING Push Depan

>>KODING Push Belakang

untuk men-Sort datanya diperlukan fungsi lagi seperti ini

POP(Single Linked List)
Pop adalah operasi pada linked list yang digunakan untuk menghapus data-data yang ada atau data yang satu. Pop depan adalah penghapusan data yang berada di depan sedangkan pop belakang adalah penghapusan data yang paling belakang.
>>KODING Pop Depan

>>KODING Pop Belakang

Sort pada pop bisa seperti ini

Ada juga fungsi 1 lagi yaitu, Display. Fungsi ini berfungsi untuk menampilkan data yang telah di sort dari push dan pop.

Hashing Table & Binary Tree

A. Hashing

Hashing adalah suatu teknik yang digunakan untuk menyimpan dan menggunakan kembali kunci kunci dengan cara yang cepat.
Dalam hashing, suatu string karakter dapat diubah menjadi panjang nilai yang lebih pendek atau kunci yang mewakili string yang asli.
Hashing dapat digunakan sebagai index dan mengembaliken barang dalam bentuk database karena lebih cepat untuk mencari barang menggunakan kunci hashed dari pada mencari nilai aslinya.
Hashing dapat juga diartikan sebagai konsep mendistribusikan kunci-kunci dalam suatu array yang disebut hash table dengan menggunakan fungsi tertentu yang disebut hash function.

>>Hash Function digunakan untuk memetakan sebuah nilai yang diberikan dengan sebuah kunci khusus untuk mempercepat akses dari isi-isinya. Efisiensi dari pemetaan tergantung pada efisiensi penggunaan efisiensi hash function.

Sebuah hash function yang bagus biasanya mencakupi, komputasi yang efisien dan secara seragam mendistribusi tiap kuncinya.

>>Hash table adalah suatu array yang menyimpan poimnter ke record yang sesuai ke nomornya. sebuah masukan ke hash table adalah NULL jika tidak ada nomor yang punya hash function yang nilainya sama dengan index masukan.

ukuran dari hash table juga biasanya sesuai dengan beberapa urutan dari besar kecilnya dari jumlah total dari string yang memungkinkan, sehingga beberapa string dapat memiliki hash key yang sama.

B. Binary Tree

Tidak seperti array, linked list, stack dan queues, yaitu data struktur linear, trees ini lebih seperti data struktur hierarki. Sebuah binary tree adalah sebua pohon data struktur yang setiap cabangnya memiliki setidaknya 2 anak, yang di referensi sebagai anak kiri dan anakakanan. Biasanya binary tree dipakai dengan menggunakan Links.

Representasi binary tree biasanya seperti suatu pointer dari cabang bagian paling atas sebuah pohon. Jika tree tersebut kosong, maka nilai dari akarnya adalah NULL, sebuah cabang binary tree daoat berisi data, pointer dari anak kiri dan pointer dari anak kanan.

Binary tree dapat dilalui dari kiri-akar-kanan(inorder), preorder(akar-kiri-kanan) dan postorder(kiri-kanan-akar).

C. Implementation

Hashing table digunakan pada blockchain yang bersangkutan dengan proses memasukkan inpun baranng dari panjang yang merefleksi output dari barang dengan panjang yang sesuai. jika kita ambil contoh dari blockchain yang menggunakan cryptocurrencies, transaksi dari panjang yang berbagai macam, dapat melawati sebuah algoritma hashing dan semua memberikan output dengan panjang yang sesuai.

Binary Search Tree

Sebuah Binary Search Tree atau BST singkatnya adalah suatu struktur data yang mendukung cepatnya pencarian, sorting atau peanataan beruntun dan juga masukan dan penghapusan data yang mudah. BST juga dikenal sebagai bentuk yang lebih berurutan dari Binary tree.

Pada BST terdapat juga hal-hal demikian:

> Subtree kiri dari suatu node biasanya hanya memiliki keys yang lebih sedikit dari pada key pada nodenya

> Subtree kanan dari suatu node biasanya memiliki keys yang lebih banyak atau lebih besar dari pada key pada nodenya.

> Subtree kiri dan kanan,masing-masing harus berbentuk BST dan tidak boleh ada node yang sama.

BST juga memiliki fungsi seperti, find, insert dan remove.

Pada BST biasanya juga disediakan dengan urutannya diantara keys agar dapat memudahkan operasi atau fungsi pencarian seperti mencari nilai minimum dan nilai maksimum. jika tidak ada urutan tersebut maka saat mencari akan dibutuhkan untuk setiap key dicari untuk menemukan kunci yang diperlukan.

Contoh dari BST =

A. Find

Dengan fungsi ini pertama akan dibandingkan key dengan akar dari nodenya, jika key nya terdapat pada akar yang sesuai maka, return akarnya. Jika key nya lebih kecil dari key akarnya, maka kita bisa pindahkan ke subtree bagian kiri. Jika tidak berhasil maka pencarian akan dilemparkan ke bagian sebelah kanan.

B. Insert

>> Dimulai dari awal akarnya

>> Kedua, nilai yang akan ditambahkan akan dibandingkan dengan bagian kiri subtree, dan jika nialinya lebih besar dari bagian kiri subtree maka dimasukkan ke bagian kanan

>> Pengulangan akan terus terjadi hingga terdapat node kosong untuk dimasukkan nilai baru secara rekursif

C. Delete

>> Jika nilainya terdapat di akhir node atau leaf, maka bisa langsung di delete nodenya.

>> Jika key atau nilainya adalah sebuah node maka delete node tersebut dan sambungkan cabang yang berhubungan dengan bagian sebelumnya.

>> Jika key atau nilainya memiliki dua nak cabang maka cari anak paling kiri dari subtree kanan atau juga anak paling kanan dari subtree kiri untuk menggantikannya dan pengulangan terjadi secara rekursif hingga hasil telah didapatkan.

AVL TREE

AVL Tree adalah bentuk dari Binary Search Tree(BST) yang telah dikembangkan untuk dapat menyeiambangkan dirinya sendiri secara otomatis saat memasukkan data didalamnya dan juga masih memiliki semua sifat dan ciri dari BST.

AVL Tree juga memiliki ciri seperti, setiap root pastinya berada di paling atas; setiap root bisa memiliki nol, satu maupun dua child nodes; setiap child node bisa memiliki nol, satu atau lebih dari satu child node lainnya; dan biasanya setiap node yang berada di posisi kanan memiliki nilai yang relatif kecil daripada node yang berada di kanan yang nilainya relatif lebih besar.

Namun AVL Tree memiliki ciri khasnya yaitu, perbedaan kedalaman antara node kiri dan node kanan tidak boleh melebihi satu, dimana dalam pemrograman AVL Tree harus memiliki kode yang dapat mengatur/mengubah/menyeimbangkan tree pada saat nilai yang baru dimasukkan kedalam node yang baru.

Explain insert and delete operations in AVL trees with suitable ...

Explain insert and delete operations in AVL trees with suitable ...

Metode yang ada pada AVL Tree mencakup Insertion dan Deletion

INSERTION

1. Single LEFT Rotation (LL Rotation)
Jika terjadi ketidak seimbangan pada child node kanan pada subtree kanan maka perlu dilakukan sebuah Left Rotation.
Hal ini dapat dilakukan dengan cara mengubah satu posisi tiap node dari posisi awalnya ke bagian kirinya.
Seperti contoh:
Related image

Pada contoh tersebut, diambil node yang berisi nilai 85 dan dijadikan sebagai poros agar semua nodenya dapat melakukan Left Rotation sekali.

2. Single RIGHT Rotation (RR Rotation)
Jika terjadi ketidak seimbangan pada child node kiri pada subtree kiri maka perlu dilakukan sebuah Right Rotation.
Hal ini dapat dilakukan dengan cara mengubah satu posisi tiap node dari posisi awalnya ke bagian kanannya.
Seperti contoh:

Pada contoh tersebut, diambil node yang berisi nilai 44 dan dijadikan sebagai poros agar semua nodenya dapat melakukan Right Rotation sekali.

3. LEFT-RIGHT Rotation (LR Rotation)
Jika terjadi ketidak seimbangan pada child node kiri pada subtree kanan maka perlu dilakukan sebuah Left-Right Rotation.
Hal ini dapat dilakukan dengan cara menggunakan kombinasi dari Left Rotation kemudian Right Rotation. Dengan setiap node bergeser 1 posisi ke sebelah kiri dari posisi awalnya dan kemudian bergeser sekali lagi ke posisi kanannya.
Seperti contoh:

Pada contoh tersebut, diambil node yang berisi nilai 39 menjadi poros kemudian dilakukan Left Rotation dan dilanjutkan dengan mengambil nilai 39 lagi menjadi porosnya dan dilakukan Right Rotation.
4. RIGHT-LEFT Rotation (RL Rotation)
Jika terjadi ketidak seimbangan pada child node kanan pada subtree kiri maka perlu dilakukan sebuah Right-Left Rotation.
Hal ini dapat dilakukan dengan cara menggunakan kombinasi dari Right Rotation kemudian Left Rotation. Dengan setiap node bergeser 1 posisi ke sebelah kanan dari posisi awalnya dan kemudian bergeser sekali lagi ke posisi kirinya.
Seperti contoh:

Pada contoh tersebut, diambil node yang berisi nilai 40 menjadi poros kemudian dilakukan Right Rotation dan dilanjutkan dengan mengambil nilai 40 lagi menjadi porosnya dan dilakukan Left Rotation.

DELETION
Biasanya dalam operasi Deletion dalam AVL Tree memiliki 2 kasus yaitu,
1. Ketika yang akan dihapus adalah node yang tidak memiliki anak, maka dari itu penghapusan dapat segera dilakukan tanpa mengubah Tree-nya.
2. Ketika yang akan dihapus adalah node yang memiliki anak, maka dari itu proses harus dilakukan penyeimbangkan Tree-nya setelah melakukan penghapusan.
Another blog for Assignment :D: Pertemuan 6

Another blog for Assignment :D: Pertemuan 6

HEAPS &TRIES

Heaps & Tries

Heaps adalah sebuah binary tree khusus yang digunakan untuk menyimpan data secara berurutan/sorted. Hal tersebut membuat pencarian menjadi lambat namun mempercepat pemasukan data serta root dari tree tersebut dapat dengan mudah dihapus.

Tries yang dibaca sebagai "Trees" adalah sebuah tree yang tidak mementikan keberadaan dari nodes, namun key/value dapat dikaitkan dengan edges dan node hanya ada untuk mengisi. Value sebenarnya dari tree ini hanya terdapat pada leaves dan sibling memiliki hubungan yang disebuit common prefix.

A. HEAPS

Heaps sangatlah mirip dengan BST, mereka memilki dua valua namun tidak seperti BST, dimana children memiliki nialai yang selalu lebih kecil dibandingkan parentnya (atau nilai yang lebih besar pada min tree). Dalam arti root akan selalu memiliki nilai paling besar
Karena heaps tidak begutu ketet terhadap urutan, maka dari itui memasukkan data lebih cepat daripada memasukkannya pada sorted array dikarenakan [0(log n)].
Heaps juga lebih cepat dalam memasukkan data daripada BST dikarenakan kedalaman atau tinggi dari Tree dan juga dengan mudah Heaps Tree dapat tetap seimbang.
Namun kelemahan dari Heaps adalah saat mencari data.
Kelebihannya yang lain adalah efisiensi dalam penghapusan Root dari Tree-nya

Heaps biasanya memiliki 2 bentuk yaitu, Max Heap dan Min Heap.

Cara kerja Heap :

Heaps biasanya tersimpan pada sebuah array karena heaps adalah sebuah binary tree yang dapat dengan cepat menghitung node children berdasarkan indexnya
Kelemahannya ialah diperlukan memori yang telah dialokasi terlebih dahulu atau membuat ukuran maxnya ataupun membuat array dinamik.
Menambahkan data ke Heap bisa disebut sebagai "up-heap”, “bubble up” dan “trickle up”.

Menambahkan node biasanya ditaruh di yang paling bawah pada nilai pertama yang terbuka
Jika Node barunya bernilai lebih kecil daripada Parent-nya maka lakukan swap dan terus diulang hingga sesuai

Pengurangan data ke Heap bisa disebut sebagai "downheap”, “bubble-down" dan “trickle-down”.

Pindahkan nilai dari yang terakhir diisi menjadi 0.
Jika Node barunya bernilai lebih besar daripada Child-nya maka lakukan swap dan terus diulang hingga sesuai.

Contoh pada MIN Heap

> Insert 12

> Delete Root

B. TRIES

Tries biasanya digunakan sebagai cara cepat untuk sort dan insert data sekaligus sebagai spellchecker, autocomplete dan juga search engines.
Root pada Tries tidak memiliki karakter/("")
Node Tries biasanya berisi karakter.
Kelebihan

Dapat dengan cepat mencari case terburuk daripada hash table yang tidak sempurna
Tidak perlu mementingkan hash yang buruk dan juga collision yang buruk
Dengan mudah membagikan sebuah listing berurutan tanpa struktur data tambahan/

Kekurangan

Pencarian pada Tries dapat lebih lambat daripada Hash, tepatnya jika mesin yang digunakan memiliki waktu random-access yang buruk
Tidak baik digunakan saat ada chains yang tidak berguna
Dapat menggunakan memori ynag lebih banyak daripada hash table

Contoh dari Tries

> Insertion

Kata-kata yang terdapat pada Tries di atas yaitu :

Bean
Bed
Bee
Bell
Brew
Bread
Break

Tuesday, June 9, 2020

Rangkuman Akhir

Linked List Ilustration

Linked List Ilustration