Review I

Review Semester 1

Linked List

Linked List (senarai berantai) adalah suatu struktur data linier yang dibentuk secara dinamik.

Terdapat tipe – tipe dari linked list, yaitu Single Linked List, Doubly Linked List, dan Circular Linked List.

• Singly Linked List

Singly linked list merupakan linked list yang memiliki 1 penghubung ke node lain. Setiap node memiliki data dan pointer ke node selanjutnya. Terdapat bagian awal yaitu head dan akhir yaitu tail dan tail memiliki pointer yang menunjukka NULL.

• Doubly Linked List

Doubly linked list merupakan linked list yang setiap nodenya memiliki 2 penghubung / pointer. 1 pointer menunjuk pada node selanjutnya dan 1 pointer lagi menunjuk pada node sebelumnya. Seperti gambar diatas terdapat node head yang pointer prevnya menunjuk NULL. Sama juga dengan tail.

• Circular Linked List

Sebenarnya terdapat 2 tipe circular linked list, yaitu circular singly linked list dan circular doubly linked list. Circular linked list sendiri merupakan variasi linked list yang akhir elemenya atau node tail berhubungan dengan node head sehingga menggambarkan suatu loop.

Method - Method pada linked list

• Push()

Push digunakan untuk menginsert value baru kepada suatu linked list. Dalam push dapat dilakukan dengan 3 cara yaitu pushHead, pushTail, dan pushMiddle. Contoh : Data = 1 2 3, jika dilakukan ingin mengisi 4 dengan pushHead data akan menjadi 4 1 2 3. Jika mengisi 4 dengan pushTail maka menjadi 1 2 3 4. Jika dilakukan pushMiddle 2.5 maka akann menjadi 1 2 2.5 3 4.
Contoh pengkodingan push head single linked list dan push head double linked list:
Push Head (SLL)

curr = newNode(value);

if(head == NULL)
head = tail = curr;
else
{
curr->next = head;
head = curr;
}

Push Head(DLL)
curr = (struct data*)malloc(sizeof(struct data));
curr->value = value;
curr->next = curr->prev = NULL;
if(head == NULL)
head = tail = curr;
else
{
curr->next = head;
head->prev = curr;
head = curr;
}

• Pop()

Pop digunakan untuk menghapus suatu value dari linked list. Contoh : Data = 1 2 3, jika dilakukan popHead dan popTail data akan menjadi 2.
Contoh pengkodingan pop head single linked list dan pop head double linked list:
Pop Head (SLL)
if(head == tail)
{
free(head);
head = tail = NULL;
}
else
{
curr = head;
head = head->next;
free(curr);

}

Pop Head (DLL)

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

Untuk pengkodingan lebih mendetail pada push dan pop terhadap linked list terdapat pada link berikut

https://kctdatastructure.blogspot.com/2020/02/linked-list.html (Double Linked List)

https://kctdatastructure.blogspot.com/2020/03/linked-list-ii.html (Single Linked List)

Hashing Table & Binary Tree

• Hashing Table

Hash table adalah suatu data struktur yang menyimpan data secara teratur yang saling berhubungan. Pada sebuah hash table, data disimpan dalam bentuk array, dimana setiap value dari suatu data memiliki index value uniknya sendiri. Pengaksesan data menjadi lebih cepat jika kita mengetahui index dari data tersebut.

Hashing adalah teknik untuk mengconvert value key - key menjadi index - index array. Contohnya jika terdapat hash table dengan size 20 maka berlaku rumus H(x) = [ x % 20 ]. Jika list yang ingin diconvert adalah List = [ 21, 22, 23, 24, 25 ].

Maka pada hash table akan berisi seperti berikut :

Pada hashing table terdapat 2 metode yaitu insert dan delete. Contoh kodingan insert:

Insert

int idx = hashCode(id);  <Function ini untuk mengconvert value key menjadi index array>

curr = create(id, name);

if(head[idx] == NULL)

head[idx] = tail[idx] = curr;

else

{

curr->prev = tail[idx];

tail[idx]->next = curr;

tail[idx] = curr;

}

• Binary Tree

Binary tree adalah suatu data struktur yang digunakan untuk menyimpan data. Suatu binary tree memiliki kondisi dimana setiap node paling maksimum memiliki 2 anak.

Terdapat 3 jenis binary tree yaitu:

• Full Binary Tree:
  Binary Tree yang tiap nodenya (kecuali leaf) memiliki dua child dan tiap subtree harus mempunyai panjang path yang sama.
• Complete Binary Tree:
  Mirip dengan Full Binary Tree, namun tiap subtree boleh memiliki panjang path yang berbeda. Node kecuali leaf memiliki 0 atau 2 child.
• Skewed Binary Tree:
  yakni Binary Tree yang semua nodenya (kecuali leaf) hanya memiliki satu child.

Untuk pengkodingan pada hashing table dapat dilihat pada link berikut:

https://kctdatastructure.blogspot.com/2020/03/hashing-table-binary-tree.html

Binary Search Tree

Binary search tree dpt dimengertikan sebagai sebuah struktur data yang dapat kita gunakan untuk mengurutkan angka - angka. BST juga dapat dimengertikan sebagai binary tree yang dimana setiap node hanya memiliki value terkecil pada subtree kiri dan value yang terbesar pada subtree kanan serta node dari kedua subtree juga merupakan BST. Contohnya seperti yang berikut ini :

Binary tree kanan salah dikarenakan node dengan value 3 lebih kecil dari pada node key utama.

Akan dikatakan sebagai binary tree jika setiap node dari tree memiliki maksmimal 2 anak. Akan dikatakan sebagai search tree jika tree tersebut dapat mencari value dari 0(log(n)) kali.

Terdapat 3 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.

Pada BST juga terdapat 2 metode yaitu insertion dan deletion. 

• Insertion untuk menambah data pada binary tree
• Deletion untuk menghapus data dari binary tree dan biasanya terdapat 3 kemungkinan yang bisa terjadi, yaitu:
• Jika node yang dihapus adalah leaf (Langsung hapus dari tree).

• Jika node yang dihapus memiliki 1 anak (Copy anak tersebut pada node yang akan dihapus dan hapus nodeny)

• Jika node yang dihapus memiliki 2 anak (Cari inorder successor, yaitu value yang lebih besar daripada value node dan memiliki selisih paling kecil, lalu copy isi inorder successor pada node dan hapus node tersebut)

Untuk pengkodingan dan penjelasan lebih detail dapat dilihat melalui link ini:

https://kctdatastructure.blogspot.com/2020/03/binary-search-tree.html