HASH TABLE DAN TREE

HASH TABLE

Hash table adalah sebuah struktur data yang terdiri dari sebuah table dan fungsi yang bertujuan untuk memetakan nilai kunci yang unik untuk sebuah record (baris) untuk menjadi sebuah angka (hash) lokasi record tersebut dalam sebuah table.



Keunggulan dari struktur hash table ini yaitu lebih cepat mencari item jika record yang disimpan langsung berada pada angka hash lokasi penyimpanannya.

Tetapi struktur hash memiliki kelemahan, yaitu jika hash table yang record nya memiliki angka hash yang sama sehingga terjadi bentrok (collision).



Benturan tersebut dapat dihindari dengan penerapan resolusi bentrokan (collision resolution policy) untuk menentukan lokasi record dalam table. Umumnya kebijakan tersebut adalah dengan mencari lokasi table yang masih kosong setelah lokasi berbentrokan.



Operasi yang terdapat di hashing table:

Insert                   :               diberikan sebuah key dan nilai, insert nilai dalam table.

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           :               mengembalikan iterator yang memeriksa nilai satu demi satu.



FUNGSI HASH

-          Mid Square : kuadratkan identifier dan gunakan jumlah bit dari tengah kotak untuk mendapatkan hash key.

-          Division : membagi nilai string atau identifier menggunakan operator modulo.

-          Folding : partisi identifier menjadi beberapa bagian lalu tambahkan bagian bersama – sama untuk mendapatkan kunci hash.

-          Digit Extraction : digit yang ditentukan sebelumnya dari nomor yang diberikan maka dianggap sebagai alamat hash.

-          Rotating Hash : fungsi ini hanya membalikkan nilai dari depan ke belakang, berlaku sebaliknya.

TREE

Tree adalah data struktur non linear yang mewakili hubungan hirarki antara objek data. Beberapa hubungan pohon dapat diamati dalam struktur direktori atau hirarki organisasi. Node tidak perlu disimpan secara berdekatan dan disimpan dimana saja yang dihubungkan oleh pointer.



BINARY TREE 


Binary tree terbuat dari node yang setiap node berisi kiri pointer dan kanan pointer. Pointer root menunjuk ke paling atas pohon. Pointer kiri dan kanan menunjuk ke subtree yang lebih kecil dari kedua sisi dengan rekursif.



Jenis jenis binary tree:

a.       Full binary tree

Binary tree yang setiap node nya (kecuali leaf) memiliki dua child dan tiap subtree harus mempunyai panjang path yang sama.

b.       Complete binary search tree

Mirip dengan full binary tree, namun tiap subtree boleh memiliki panjang path yang berbeda. Node kecuali leaf memiliki  0 atau 2 child.



BINARY SEARCH TREE


Binary search tree adalah binary tree dengan sifat bahwa semua left child harus lebih kecil daripada right child dan parent nya. Juga semua right child harus lebih besar dari left child beserta parentnya.



Source: http://muqoddarsrengmadureh.blogspot.com/2013/01/algoritma-dan-sturktur-data-hashing.html?m=1

LINKED LIST

Linked list adalah bagian struktur data yang biasa disebut juga senarai berantai adalah sebuah rangkaian yang terdiri dari data dan alamat elemen record selanjutnya(pointer) yang biasa juga disebut node.  Dalam sebuah linked list terdapat istilah head  dan tail.

·         Head = Elemen yang berada di posisi pertama dalam suatu linked list.

·         Tail = Elemen yang berada di posisi terakhir dalam suatu linked list.

Ada beberapa jenis linked list sebagai berikut:

1.       Single Linked List

Single linked list merupakam suatu linked list yang haya memiliki satu variable pointer saja, diana pointer tersebut menunjuk ke node selanjutnya. Biasanya field pada tail tersebut menunju ke NULL. Pembuatan Single Linked List dapat menggunakan 2 metode:
•     LIFO (Last In First Out), aplikasinya : Stack (Tumpukan)
•     FIFO (First In First Out), aplikasinya : Queue (Antrean)

Contoh:

 struct Mahasiswa{

            char nama[25];

            int usia;

            struct Mahasiswa *next;

}*head,*tail;

2.      Double Linked List

Salah astu kelemahhan single linked list adalah pointer hanya dapat bergerak satu arah saja, maju/mundur atau, kanan/kiri sehingga pencarian data pada single linked list hanya dapat bergerak ke satu arah saja. Double linked list merupakan suatu linked list yang memiliki dua pointer, yaitu pointer yang menunjuk ke node selanjutnya dan pointer yang menunjuk ke node sebelumya, sehingga linked list tersebut dapat menunjuk ke dua arah data. Setiap head dan tailnya juga menunjuk ke NULL.

Contoh:

Struct Mahasiswa{

            char nama[25];

 int usia;

            struct Mahasiswa *next,*prev;

}*head,*tail

3.       Circular Linked List

Dalam circular linked list, node terakhir dalam struktur memiliki pointer yang mengarah ke node pertama(head), jadi tidak ada pointer yang menunjuk ke NULL. Ada dua jenis circular linked list, yaitu:

a.       Circular single linked list

b.       Circular doubly linked list

Circular doubly linked list merupakan double linked list yang node terakhirnya menunjuk ke ke node awal yang menunjuk ke  node terakhir.

Berikut adalah operasi-operasi yang terdapat dalam linked list:

-          Insert : menambahkan sebuah node baru ke dalam suatu linked list

-          IsEmpty : menentukan apakah linked list kosong atau tidak.

-          Find first : mencari elemen pertama pada linked list.

-          Find next : mencari elemen seudah elemen yang ditunjuk now.

-          Retrieve : mengambil elemen yang ditunjuk oleh now, elemen tersebut lalu dikembalikan oleh fungsi.

-          Update : megnubah elemen  yang ditunjuk oleh now dengan isi dari sesuatu.

-          Delete now : menghapus elemen yang ditunjuk oleh now, jika yang diihapus adalah elemen pertama dari linked list(head), head akan berpindah ke elemen berikut.

-          Delete head : menghapus elemen yang ditunjuk head, dan head berpindah ke elemen berikutnya.

-          Clear : menghapus inked list yang sudah ada. Fungsi ini wajib dilakukan bila ingin mengakhiri program yang menggunakan linked list. Jika dilakukan, data data yang dialokasikan ke memori program senelumnya akan tetap tertinggal di dalam memori.

Contoh coding:

                Doubly linked list

                                Struct tnode{

                                Int value;

                                Struct tnonde *next;

                                Struct tnode *prev;

                                };

Struct tnode *head = 0;

Struct tnode *tail = 0;



Implementasi:

                Insert :

                                Code baru dibelakang tail:

                                Struct tnode *node = (struct tnode*) malloc(sizeof(struct tnode));

Node ->value = x;

Node->next = NULL;

Node -> prev = tail;

Tail -> next = node;

Tail -> node;

Code baru diantara head dan tail:

Struct tnode *a = ??;

Struct tnode *b = ??;

//code baru akan ditaro diantara a dan 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;

                Delete:

                                Jika node yang dihapus adalah node satu satunya:

                                Free(head);

                                Head = NULL;

                                Tal = NULL;

                                Jika node yang ingin dihapus adalah head:

                                Head = head -> next;

                                Free(head -> prev);

                                Tail -> next = NULL;

                                Jika node yang ingin dihapus adalah tail:

                                Tail = tail -> prev;

                                Free(tail -> next);

                                Tail -> next = NULL;

                                Jika node yang dihapus bukanlah head atau 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);



Source:

https://zoneblog123.blogspot.com/2018/04/pengertian-linked-list-beserta-jenis.html
alvinstrukturdata.blogspot.com/2016/01/apa-itu-linked-list.html


(approved by mr. henry chong)