Review Data Struct

Linked List

Linked List atau senarai berantai adalah struktur data yang terdiri dari urutan record data dimana setiap record memiliki field yang menyimpan alamat/referensi dari record selanjutnya. Elemen data yang dihubungkan dengan dengan link pada Linked List disebut Node. Di dalam Linked List, biasanya terdapat Head yang merupakan elemen yang berada pada posisi pertama dalam suatu Linked List dan Tail yang merupakan elemen yang berada pada posisi terakhir dalam suatu Llinked List.

Macam-macam Linked List: 

1. Circular Single Linked List

    Single Linked List Circular adalah Single Linked List yang pointer nextnya menunjuk pada dirinya sendiri. Jika Single Linked List tersebut terdiri dari beberapa node,  maka pointer next pada node terakhir akan menunjuk ke node terdepannya. Circular  artinya pointer nextnya akan menunjuk pada dirinya sendiri sehingga berbentuk seperti berputar. 

2. Doubly Linked List

  Doubly Linked List adalah sekumpulan node data yang terurut linear atau sekuensial dengan dua buah pointer yaitu prev dan next. Doubly Linked List memiliki data dan dua buah reference link (biasanya disebut next dan prev) yang menunjuk ke node sebelum dan node sesudahnya. Pada implementasinya, terdapat dua variasi double linked list yaitu circular dan non-circular layaknya pada single linked list. 

3. Circular Doubly Linked List

   Circular Doubly Linked List mirip dengan Single Linked List, namun jumlah pointer pada setiap node adalah 2. Setiap node pada linked list mempunyai field yang berisi data dan pointer ke node berikutnya & ke node sebelumnya. Untuk pembentukan node baru , mulanya pointer next dan prev akan menunjuk ke nilai NULL. Selanjutnya pointer prev akan menunjuk ke node sebelumnya , dan pointer next akan menunjuk ke node selanjutnya pada list.

4. Multiple Linked List

    Multiple linked list merupakan senarai berantai yang memiliki link atau pointer lebih darisatu. Untuk multiple linked list yang memiliki dua link biasanya disebut sebagai doublylinked list (senarai berantai ganda). Senarai berantai ganda memiliki dua buah pointer yang biasanya masing-masing menunjuk ke simpul sebelumnya dan ke simipul sesudahnya. 

Operasi dalam Linked List:

1. Push

   Push merupakan operasi untuk memasukkan data pada linked list atau insert. Memasukkan data dapat dari depan(PushDepan) atau dari belakang(PushBelakang) atau juga bisa pada data yang diinginkan.

2. Pop

    Pop merupakan operasi untuk menghapus data pada linked list atau delete. Menghapus data dapat dilakukan dari depan(PopDepan) atau dari belakang(PopBelakang) atau juga bisa pada data yang diinginkan.

Hashing & Binary Tree

Hashing adalah teknik yang digunakan untuk menyimpan dan mengambil kunci dengan cepat. Hashing digunakan untuk mengindeks dan mengambil item dalam database karena lebih cepat menemukan item menggunakan kunci hash yang lebih pendek daripada menemukannya menggunakan nilai asli.

Hash Table

Tabel hash adalah tabel tempat menyimpan string asli. Indeks tabel adalah kunci hash dan nilainya adalah string asli. Ukuran tabel hash biasanya berupa urutan yang besarnya lebih rendah dari jumlah total string yang mungkin

Hash Function

Ada beberapa cara untuk membuat fungsi hash. 

1. Mid-Square

a. Kuadratkan string / identifier dan kemudian gunakan jumlah bit yang sesuai dari tengah kotak untuk mendapatkan hash-key.

b. Jika kuncinya adalah string, maka akan dikonversi ke angka.

2.Division

a. Membagi string / pengidentifikasi dengan menggunakan operator modulus.

b. Divison merupakan metode hashing integer yang paling sederhana.

3.Folding

Cara melakukan folding yaitu, buat string / identifier menjadi beberapa bagian, lalu tambahkan bagian bersama-sama untuk mendapatkan kunci hash.

4.Digit Extraction

Pada metode ini, Digit yang ditentukan sebelumnya dari nomor yang diberikan dianggap sebagai alamat hash.

5.Rotating Hash

a. Gunakan metode hash mid-square.

b. Setelah mendapatkan kode / alamat hash dari metode hash, lakukan rotasi.

c. Rotasi dilakukan dengan menggeser digit untuk mendapatkan alamat hash baru.

Tree

Tree merupakan struktur data non-linear yang mewakili hubungan hierarkis(one to many) di antara objek data. Tree bisa didefinisikan sebagai kumpulan simpul/node dengan satu elemen khusus yang disebut Root dan node lainnya.

Binary Tree

Binary tree adalah struktur data rooted tree di mana setiap node memiliki paling banyak dua anak.

Terdapat 4 macam binary tree antara lain : Perfect binary tree, Complete Binary Tree, Skewed binary tree, Balanced binary tree.

Expression Tree

Pohon ekspresi adalah pohon biner di mana setiap node internal sesuai dengan operator dan setiap node leaf sesuai dengan operand.

Prefix  : *+ab/-cde

Postfix : ab+cd-e/*

Infix  : (a+b)*((c-d)/e)

Hashing Table & Binary Tree

Hashing

Hashing adalah teknik yang digunakan untuk menyimpan dan mengambil kunci dengan cepat. Hashing digunakan untuk mengindeks dan mengambil item dalam database karena lebih cepat menemukan item menggunakan kunci hash yang lebih pendek daripada menemukannya menggunakan nilai asli.

Hashing juga dapat didefinisikan sebagai konsep mendistribusikan kunci dalam array yang disebut hash table menggunakan fungsi yang telah ditentukan yang disebut hash function.

Hash Table

Tabel hash adalah tabel tempat menyimpan string asli. Indeks tabel adalah kunci hash dan nilainya adalah string asli. Ukuran tabel hash biasanya berupa urutan yang besarnya lebih rendah dari jumlah total string yang mungkin, sehingga beberapa string mungkin memiliki kunci hash yang sama.

Hash Function

Ada beberapa cara untuk membuat fungsi hash. 

1. Mid-Square

a. Kuadratkan string / identifier dan kemudian gunakan jumlah bit yang sesuai dari tengah kotak untuk mendapatkan hash-key.

b. Jika kuncinya adalah string, maka akan dikonversi ke angka.

2.Division

a. Membagi string / pengidentifikasi dengan menggunakan operator modulus.

b. Divison merupakan metode hashing integer yang paling sederhana.

3.Folding

Cara melakukan folding yaitu, buat string / identifier menjadi beberapa bagian, lalu tambahkan bagian bersama-sama untuk mendapatkan kunci hash.

4.Digit Extraction

Pada metode ini, Digit yang ditentukan sebelumnya dari nomor yang diberikan dianggap sebagai alamat hash.

5.Rotating Hash

a. Gunakan metode hash mid-square.

b. Setelah mendapatkan kode / alamat hash dari metode hash, lakukan rotasi.

c. Rotasi dilakukan dengan menggeser digit untuk mendapatkan alamat hash baru.

Tree

Tree merupakan struktur data non-linear yang mewakili hubungan hierarkis(one to many) di antara objek data. Tree bisa didefinisikan sebagai kumpulan simpul/node dengan satu elemen khusus yang disebut Root dan node lainnya. Tree juga adalah suatu graph yang acyclic, simple, connected yang tidak mengandung loop. Contoh:

1. Node di atas disebut sebagai root.
2. Garis yang menghubungkan induk ke anak adalah edge.
3. Node yang tidak memiliki anak disebut leaf.
4. Node yang memiliki orang tua yang sama disebut sibling.
5. Degree dari simpul adalah total sub tree dari simpul.
6. Height/Depth adalah tingkat maksimum node dalam tree.
7. Jika ada garis yang menghubungkan p ke q, maka p disebut ancestor dari q, dan q adalah descendant dari p.

Binary Tree

Binary tree adalah struktur data rooted tree di mana setiap node memiliki paling banyak dua anak.

Macam-macam binary tree:

1. Perfect binary tree adalah pohon biner di mana setiap level berada pada depth yang sama.
2. Complete adalah pohon biner di mana setiap level kecuali yang terakhir terisi penuh dan semua node diletakkan sejauh mungkin. Perfect binary tree juga merupakan Complete binary tree.
3. Skewed binary tree adalah pohon biner di mana setiap node memiliki paling banyak satu anak.
4. Balanced binary tree adalah pohon biner dimana tidak ada leaf yang lebih jauh dari root daripada leaf lainnya.

Konsep binary tree

• Jumlah maksimum node pada level k dari pohon biner adalah 2k.
• Jumlah maksimum node pada pohon biner dengan tinggi h adalah 2^h+1 - 1.
• Ketinggian pohon adalah jumlah level atau level tertinggi h.
• Tinggi minimum pohon biner dari n node adalah 2log (n).
• Tinggi maksimum pohon biner dari n node adalah n - 1.

Expression Tree

Prefix  : *+ab/-cde

Postfix : ab+cd-e/*

Infix  : (a+b)*((c-d)/e)

Expression tree dapat dibuat dari prefix dengan rekursif.

Struktur Tree yang digunakan:

struct tnode {

  char chr;

  struct tnode *left;

  struct tnode *right;
};

main function

struct tnode *root = newnode(s[0]);

f(root);

char s[MAX];

int  p = 0;

void f(struct tnode *curr) {

if ( is_operator(s[p]) ) {

   p++; curr->left  = newnode(s[p]);

   f(curr-->left);

   p++; curr->right = newnode(s[p]);

   f(curr-->right);}}

Prefix Traversal

void prefix(struct tnode *curr) {

printf( “%c “, curr->chr );

if ( curr->left  != 0 ) prefix(curr->left);

if ( curr->right != 0 ) prefix(curr->right);}

Postfix Traversal

void postfix(struct tnode *curr) {

if ( curr->left  != 0 ) postfix(curr->left);

if ( curr->right != 0 ) postfix(curr->right);

printf( “%c“, curr->chr ); }

Infix Traversal

void infix(tnode *curr) {

if ( is_operator(curr->chr) ) putchar( '(' );

if ( curr->left != 0 ) infix(curr->left);

printf( "%c", curr->chr );

if ( curr->right != 0 ) infix(curr->right);

if ( is_operator(curr->chr) ) putchar( ')' );}

Threaded Binary Tree

Threaded Binary Tree hampir sama dengan pohon biner, namun berbeda dalam menyimpan pointer NULL. Jika thread muncul di bidang kiri disebut left threaded binary tree. Sebaliknya, jika thread muncul di bidang kanan disebut right threaded binary tree. Selain itu, ada juga two way threaded binary tree dimana setiap node di-threaded ke arah pendahulu dan penggantinya secara berurutan (kiri dan kanan) berarti semua pointer nol kanan akan mengarah ke penerus inorder DAN semua pointer nol kiri akan menunjuk ke inorder pendahulu.

Kelebihan Threaded Binary Tree

1. memungkinkan lintasan linier elemen pada pohon.
2. menghilangkan penggunaan tumpukan yang menghabiskan banyak ruang memori dan waktu komputer.
3. memungkinkan untuk menemukan induk dari elemen yang diberikan tanpa menggunakan pointer orangtua secara eksplisit.

Linked List II

Single Linked List

Pendeklarasian struct dari sebuah node single linked list:

struct tnode {
int value;
struct tnode* next;
};

struct tnode* create_node(int value){
struct tnode* node = (struct tnode*)malloc(sizeof(struct tnode));
node->next = NULL;
node->value = value;

return node;
}
Dari single linked list di atas, dapat dilakukan beberapa operasi, yaitu:
1. Push Head
struct tnode* insert_head(struct tnode* head, int value){
struct tnode* new_node = create_node(value);
new_node->next = head;
head = new_node;
return head;

}
function di atas berfungsi untuk menginsert node baru sebagai head atau node awal.


2.Push Tail
struct tnode* insert_tail(struct tnode* head, int value){
if(head==NULL){
head = insert_head(head, value);
} else {
struct tnode* new_node = create_node(value);
struct tnode* temp = head;

while(temp->next!=NULL){
temp = temp->next;
}
temp->next = new_node;
}
return head;

}
function di atas berfungsi untuk menginsert node baru sebagai tail atau node akhir.


3.Pop Head
struct tnode* delete_head(struct tnode* head){
struct tnode* temp = head;
head = head->next;
free(temp);

return head;

}
function di atas berfungsi untuk mendelete node head.


4.Pop Tail
struct tnode* delete_tail(struct tnode* head){
struct tnode* temp = head;
struct tnode* temp2 = head->next;

if(temp2==NULL){
head = NULL;
free(temp);
} else {
while(temp2->next!=NULL){
temp = temp->next;
temp2 = temp2->next;
}
temp->next = NULL;
free(temp2);
}
return head;

}
function di atas berfungsi untuk mendelete note tail.

DATA STRUCTURES

Linked List

Linked List atau senarai berantai adalah struktur data yang terdiri dari urutan record data dimana setiap record memiliki field yang menyimpan alamat/referensi dari record selanjutnya. Elemen data yang dihubungkan dengan dengan link pada Linked List disebut Node. Di dalam Linked List, biasanya terdapat Head yang merupakan elemen yang berada pada posisi pertama dalam suatu Linked List dan Tail yang merupakan elemen yang berada pada posisi terakhir dalam suatu Llinked List.

Meski memiliki konsep yang mirip dengan Array, Linked List memiliki keuntungan dalam penyisipan dan pembuangan data dibandingkan Array. Hanya saja, kelemahannya terletak pada cara mengakses data didalamnya. Pada konsep Linked List, pengaksesan data didalamnya harus secara berurutan dari awal, hal ini dikarenakan linked list tidak mengenal indeks seperti Array.

Jika pada Array dikenal istilah index (indeks), maka Linked List mengenal istilah nodes atau titik. Hal ini terjadi karena Linked List menggunakan alokasi memori yang selalu berbeda dan menghubungkannya dengan memory address yang lain, sehingga kita akan lebih mudah memahaminya dengan nodes.

Macam-macam Linked List: 

1. Circular Single Linked List

Single Linked List Circular adalah Single Linked List yang pointer nextnya menunjuk pada dirinya sendiri. Jika Single Linked List tersebut terdiri dari beberapa node,  maka pointer next pada node terakhir akan menunjuk ke node terdepannya. Circular  artinya pointer nextnya akan menunjuk pada dirinya sendiri sehingga berbentuk seperti berputar. Single Linked List hanya memiliki satu variabel pointer saja. Biasanya field pada tail menunjuk ke NULL. Contoh:

typedef struct TNode{ 

int data; 

TNode *next; 

};

2. Doubly Linked List

Doubly Linked List adalah sekumpulan node data yang terurut linear atau sekuensial dengan dua buah pointer yaitu prev dan next. Doubly Linked List memiliki data dan dua buah reference link (biasanya disebut next dan prev) yang menunjuk ke node sebelum dan node sesudahnya. Pada implementasinya, terdapat dua variasi double linked list yaitu circular dan non-circular layaknya pada single linked list. Operasi pada Doubly Linked List: 

        1. Insert

struct tnode *a = ??;

struct tnode *b = ??;

// the new node will be inserted between a and b

struct tnode *node =

    (struct tnode*) malloc(sizeof(struct tnode));

node->value  = x;

node->next  = b;

node->prev  = a;

a->next  = node;

b->prev  = node;

2. Delete

          -   If the node to be deleted is the only node:

         free(head);

     head = NULL;

     tail = NULL;

    -    If the node to be deleted is head:

     head = head->next;

     free(head->prev);

     head->prev = NULL;

    -   If the node to be deleted is tail:

            tail = tail->prev;

      free(tail->next);

      tail->next = NULL;

         -   If the node to be deleted is not in head or tail:

     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);

 Contoh:

struct tnode {

  int value;

  struct tnode *next;

  struct tnode *prev;

  };

struct tnode *head = 0;

struct tnode *tail = 0;

3. Circular Doubly Linked List

Circular Doubly Linked List mirip dengan Single Linked List, namun jumlah pointer pada setiap node adalah 2. Setiap node pada linked list mempunyai field yang berisi data dan pointer ke node berikutnya & ke node sebelumnya. Untuk pembentukan node baru , mulanya pointer next dan prev akan menunjuk ke nilai NULL. Selanjutnya pointer prev akan menunjuk ke node sebelumnya , dan pointer next akan menunjuk ke node selanjutnya pada list.

Contoh: 
#include <stdio.h>
struct TNode{
char data[30];
TNode *next;
TNode *prev;
};

4.Multiple Linked List

Multiple linked list merupakan senarai berantai yang memiliki link atau pointer lebih darisatu. Untuk multiple linked list yang memiliki dua link biasanya disebut sebagai doublylinked list (senarai berantai ganda). Senarai berantai ganda memiliki dua buah pointer yang biasanya masing-masing menunjuk ke simpul sebelumnya dan ke simipul sesudahnya.