Linked List
Linked list adalah struktur data linier dimana elemen tidak di simpan di lokasi memori yang berdekatan.
1. Circular Single Linked List
Circular single linked list adalah suatu linked list yang tidak memiliki nilai NULL untuk medan sambungnya, node yang ada pada akhir circular single linked list akan berisi pointer yang akan menunjuk kepada node yang ada di awal/node pertama. Circular single linked list juga hanya memiliki pointer.
Pada gambar di atas, node paling akhir dari linked list tersebut memiliki pointer yang menunjuk dari dirinya sendiri (node terakhir) ke node awal/node pertama kembali.
2. Doubly Linked List
Doubly linked list adalah salah satu jenis linked list yang memiliki pointer 2 arah dan memiliki struktur data yang saling terkait. Linked list ini memiliki 2 pointer penunjuk, 1 pointer menunjuk ke arah node sebelumnya dan yang 1 lagi ke arah node setelahnya.
Dari gambar di atas, doubly linked list terdapat nilai NULL yang berada pada data terakhir/pada tail yang berguna sebagai pertanda data terakhir yang ada di linked tersebut. Doubly linked list berbeda dengan circular single linked list yang tidak memiliki nilai NULL di dalamnya.
Insertion
Ada 4 cara menambahkan node :
- Pada bagian depan Doubly Linked List
- Setelah node yang di berikan
- Pada akhir Doubly Linked List
- Sebelum node di berikan
Deletion
4 kondisi yang harus diperhatikan saat deleting node :
- Node yang akan di delete adalah node satu-satunya di linked list
- Node yang akan di delete adalah awalan/head
- Node yang akan di delete adalah akhiran/tail
- Node yang akan di delete bukan head/tail
Kita harus memperhatikan kondisi mana yang diinginkan saat kita ingin melakukan deleting pada Doubly Linked List.
Contoh :
(gambar linked list sebelum dilakukan tahap deleting)
(gambar linked list setelah dilakukan tahap deleting)
3. Circular Doubly Linked List
Umumnya, Circular Doubly Linked List itu sama dengan Circular Single Linked List, bedanya terletak pada total pointer pada setiap node yang ada di Circular Doubly Linked List berjumlah 2 pointer.
Dari gambar di atas, kita dapat melihat perbedaan antara Circular Doubly Linked List dengan Circular Single Linked List.
Contoh Codingan Deklarasi Node :
struct Node {
int data;
struct Node* next; // Pointer to next node in Doubly Linked List
struct Node* prev; // Pointer to previous node in Doubly Linked List
};
Contoh Codingan Insertion pada Depan (Head) Doubly Linked List :
void push(struct Node* head_ref, int new_data)
{
/* 1. allocate node */
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
/* 2. put in the data */
new_node->data = new_data;
/* 3. Make next of new node as head and previous as NULL */
new_node->next = (*head_ref);
new_node->prev = NULL;
/* 4. change prev of head node to new node */
if ((*head_ref) != NULL)
(*head_ref)->prev = new_node;
/* 5. move the head to point to the new node */
(*head_ref) = new_node;
}
Stack and Queue
Stack
Stack merupakan sebuah koleksi objek yang menggunakan LIFO (Last In Last Out). Artinya data yang terakhir kali masuk adalah data yang pertama kali/terlebih dahulu keluar.
Istilah-istilah yang ada dalam program stack :
- Push : berfungsi untuk menambah elemen pada suatu stack
- Pop : berfungsi untuk mengambil/menghapus elemen pada suatu stack
- Clear : berfungsi untuk mengosongkan stack
- IsEmpty : berfungsi untuk mengecek apakah stack sudah kosong atau belum
- IsFull : berfungsi untuk mengecek apakah stack sudah penuh
Queue
Queue dapat diartikan sebagai antrian. . Prinsip yang digunakan pada queue adalah FIFO (First In First Out). Artinya, elemen yang pertama kali dimasukkan ke dalam daftar adalah elemen yang pertama kali akan di hapus dari daftar/keluar dari daftar. Pada queue terdapat satu buah pintu masuk di ujung dan satu buah pintu keluar di ujung yang lain. Oleh sebab itu, queue membutuhkan variabel Head dan Tail.
Operasi-operasi yang dapat digunakan pada queue :
- push() : menambahkan suatu item/elemen pada bagian belakang queue
- pop() : menghapus suatu item/elemen pada bagian depan queue
- front() : mengungkapkan/mengembalikan item paling depan dari queue
Aplikasi-aplikasi yang menggunakan queue :
- Deques
- Priority Queues
- Breadth First Search
Contoh Coding Push pada Stack:
struct Data
{
int value;
struct Data *next,*prev;
}*head,*curr,*tail;
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;
}
void cetak()
{
curr = head;
while(curr!=NULL){
printf("%d\n",curr->value);
curr = curr->next;
}
}
int main()
{
push(10);
push(20);
push(30);
push(40);
cetak();
return 0;
}
Contoh Coding Queue :
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX 6
int intArray[MAX];
int front = 0;
int rear = -1;
int itemCount = 0;
int peek() {
return intArray[front];
}
bool isEmpty() {
return itemCount == 0;
}
bool isFull() {
return itemCount == MAX;
}
int size() {
return itemCount;
}
void insert(int data) {
if(!isFull()) {
if(rear == MAX-1) {
rear = -1;
}
intArray[++rear] = data;
itemCount++;
}
}
int removeData() {
int data = intArray[front++];
if(front == MAX) {
front = 0;
}
itemCount--;
return data;
}
int main() {
/* insert 5 items */
insert(3);
insert(5);
insert(9);
insert(1);
insert(12);
// front : 0
// rear : 4
// ------------------
// index : 0 1 2 3 4
// ------------------
// queue : 3 5 9 1 12
insert(15);
// front : 0
// rear : 5
// ---------------------
// index : 0 1 2 3 4 5
// ---------------------
// queue : 3 5 9 1 12 15
if(isFull()) {
printf("Queue is full!\n");
}
// remove one item
int num = removeData();
printf("Element removed: %d\n",num);
// front : 1
// rear : 5
// -------------------
// index : 1 2 3 4 5
// -------------------
// queue : 5 9 1 12 15
// insert more items
insert(16);
// front : 1
// rear : -1
// ----------------------
// index : 0 1 2 3 4 5
// ----------------------
// queue : 16 5 9 1 12 15
// As queue is full, elements will not be inserted.
insert(17);
insert(18);
// ----------------------
// index : 0 1 2 3 4 5
// ----------------------
// queue : 16 5 9 1 12 15
printf("Element at front: %d\n",peek());
printf("----------------------\n");
printf("index : 5 4 3 2 1 0\n");
printf("----------------------\n");
printf("Queue: ");
while(!isEmpty()) {
int n = removeData();
printf("%d ",n);
}
return 0;
}
Hashing and Hash Table, Trees, and Binary Tree
Hashing and Hash Table
Hashing
Hashing adalah suatu teknik yang di gunakan untuk mengidentifikasi objek tertentu dari sekelompok objek yang serupa dengan cara yang unik. Hashing merupakan struktur data penting yang dirancang untuk menggunakan suatu fungsi khusus yang di panggil "The Hash Function" yang digunakan untuk memetakan nilai yang telah diberikan dengan kunci tertentu untuk akses ke elemen yang lebih cepat. Efisiensi dari pemetaan ini tergantung dari efisiensi dari "The Hash Function" yang digunakan.
Hashing di implementasikan ke dalam 2 langkah, yaitu :
1. Elemen dikonversikan kedalam suatu integer dengan menggunakan "Hash Function". Elemen ini dapat digunakan sebagai suatu index untuk menyimpan elemen asli yang jatuh ke hash table.
2. Elemen ini disimpan di hash table dimana dia bisa diambil dengan cepat menggunakan hashed key.
hash = hashfunc(key)
index = hash%array_size
Pada metode ini, hash tidak tergantung pada ukuran array dan kemudian dia akan dikecilkan menjadi suatu index (angka antara 0 dan array_size - 1) dengan menggunakan operator modulo (%).
Hash Table
Hash table adalah suatu struktur data yang digunakan untuk menyimpan keys/value pairs. Hash table menggunakan suatu hash function (fungsi hash) untuk menghitung suatu index ke dalam suatu array dimana suatu elemennya akan dimasukkan atau dicari.
Hash table adalah sebuah tabel yang berbetuk array dimana di dalamnya kita menyimpan string asli. Indeks dari tabelnya adalah hashed key sementara nilainya adalah nilai dari string asli.
Ukuran dari hash table biasanya beberapa urutan yang besarannya lebih rendah daripada jumlah total dari string yang memungkinkan. Jadi, beberapa string mungkin akan memiliki kunci hash (hashed key) yang sama.
Operasi dasar yang ada dalam hash table :
Deklarasi Data Item yang Akan Digunakan dalam Hash Table :
struct DataItem {
int data;
int key;
};
Contoh Coding Search Operation :
struct DataItem *search(int key) {
//get the hash
int hashIndex = hashCode(key);
//move in array until an empty
while(hashArray[hashIndex] != NULL) {
if(hashArray[hashIndex]->key == key)
return hashArray[hashIndex];
//go to next cell
++hashIndex;
//wrap around the table
hashIndex %= SIZE;
}
return NULL;
}
Contoh Coding Insert Operation :
void insert(int key,int data) {
struct DataItem *item = (struct DataItem*) malloc(sizeof(struct DataItem));
item->data = data;
item->key = key;
//get the hash
int hashIndex = hashCode(key);
//move in array until an empty or deleted cell
while(hashArray[hashIndex] != NULL && hashArray[hashIndex]->key != -1) {
//go to next cell
++hashIndex;
//wrap around the table
hashIndex %= SIZE;
}
hashArray[hashIndex] = item;
}
Contoh Coding Delete Operation :
struct DataItem* delete(struct DataItem* item) {
int key = item->key;
//get the hash
int hashIndex = hashCode(key);
//move in array until an empty
while(hashArray[hashIndex] !=NULL) {
if(hashArray[hashIndex]->key == key) {
struct DataItem* temp = hashArray[hashIndex];
//assign a dummy item at deleted position
hashArray[hashIndex] = dummyItem;
return temp;
}
//go to next cell
++hashIndex;
//wrap around the table
hashIndex %= SIZE;
}
return NULL;
}
Hash Function
Hash function adalah suatu fungsi yang mengubah nomor telepon yang besar menjadi nilai integer praktis yang kecil. Suatu hash function memetakan sejumlah angka atau string yang besar kedalam suatu integer yang kecil yang dapat digunakan sebagai index di dalam hash table.
Hash function yang baik harus memiliki properti sebagai berikut :
- Dihitung secara efisien
- Harus mendistribusikan kunci(keys) secara seragam (setiap posisi tabel memiliki kemungkinan yang sama untuk setiap kunci)
Ada banyak cara untuk meng-hash suatu string ke dalam suatu key. Berikut ini adalah beberapa method-method penting untuk membangun fungsi hash, yaitu :
- Mid-square
- Division (paling umum)
- Folding
- Digit Extraction
- Rotating Hash
Collision
Dalam bahasa indonesia, collision dikenal sebagai tabrakan. Dikarenakan fungsi hash memberikan kita sebuah angka kecil untuk sebuah kunci(key) yang merupakan bilangan integer besar atau string. Ada kemungkinan bahwa dua kunci(key) menghasilkan nilai yang sama.
Ada 2 cara untuk menangani Collision, yaitu :
- Linear Probing
- Chaining
Linear Probing
Dilakukan dengan mencari slot yang kosong yang terletak setelah slot yang terisi dan menaruh string nya disana. Dia akan mencari terus hingga mendapatkan slot yang kosong.
Chaining
Dilakukan dengan menaruh string di dalam sebuat slot sebagai sebuah chained list(linked list).
Contoh Coding Liner Probing :
struct { ... } node;
node Table[M]; int Free;
/* insert K */
addr = Hash(K);
if (IsEmpty(addr)) Insert(K,addr);
else {
/* see if already stored */
test:
if (Table[addr].key == K) return;
else {
addr = Table[addr].link; goto test;}
/* find free cell */
Free = addr;
do { Free--; if (Free<0) Free=M-1; }
while (!IsEmpty(Free) && Free!=addr);
if (!IsEmpty(Free)) abort;
else {
Insert(K,Free); Table[addr].link = Free;
}
}
Tree and Binary Tree
Tree
Tree merupakan struktur data yang tidak linear yang digunakan untuk merepresentasikan data yang bersifat hirarki antara elemen-elemennya. Definisi tree yaitu kumpulan elemen yang salah satu elemennya disebut root(akar) dan elemen yang lain disebut simpul(node) yang terpecah menjadi sejumlah kumpulan yang tidak saling berhubungan satu dengan yang lain yang disebut sub-tree atau cabang.
Binary Tree
Tree yang unsurnya paling banyak 2 anak disebut Binary Tree. Karena setiap elemen dalam pohon biner hanya dapat emiliki 2 anak, biasanya anak tersebut akan dinamakan left dan right child.
Node dari Binary Tree berisi dari beberapa bagian, yaitu :
- Data
- Pointer to left child
- Pointer to right child
Node yang tidak memiliki anak disebut leaf.
Jenis-jenis Binary Tree
Binary tree yang tiap node-nya(kecuali leaf) memiliki 2 anak dan tiap sub-tree harus mempunyai panjang path yang sama.
Mirip dengan Full Binary Tree, namun setiap sub-tree boleh memiliki panjang path yang berbeda. Node kecuali leaf memiliki 0 atau 2 child.
Binary tree yang semua nodenya (kecuali leaf) memiliki 1 child.
Jenis pohon terurut yang digunakan unruk menyimpan data sehingga memudahkan pencarian kembali data tersebut.
Operasi Pada Tree
Digunakan untuk membentuk binary tree baru yang masih kosong.
Digunakan untuk mengosongkan binary tree yang sudah ada.
Diguakan untuk memeriksa apakah binary tree masih kosong.
Digunakan untuk memasukkan sebuah node ke dalam tree.
Digunakan untuk mencari root, parent, left child, atau right child dari suatu node dengan syarat tree tidak boleh kosong.
Digunakan untuk mengubah isi dari node yang ditunjuk oleh pointer cureent dengan syarat tree tidak boleh kosong.
Digunakan untuk mengetahui isi dari node yang ditunjuk pointer current dengan syarat tree tidak boleh kosong.
Digunakan untuk menghapus sebuah sub-tree (node beserta seluruh descendant-nya) yang ditunjuk pointer current dengan syarat tree tidak oleh kosong.
Digunakan untuk mengetahui karakteristik dari suatu tree (size, height, serta everage length-nya).
Digunakan untuk mengunjungi seluruh node-node pada tree, masing-masing sekali.
Threaded Binary Tree Example
Keuntungan
- Memungkinkan lintasan linear elemen di tree
- Tranversal linear menghilangkan penggunaan tumpukan yang pada gilirannya akan mengkonsumsi banyak ruang memori dan waktu komputer
- Memungkinkan untuk menemukan induk dari elemen yang diberikan tanpa menggunakan pointer parent secara eksplisit
- Karena node berisi pointer ke pendahulu dan penerus di in-order, tree berulir memungkinkan traversal maju dan mundur dari node seperti yang diberikan oleh mode in-order.
Contoh Coding Binary Tree
#include <stdio.h>
#include <stdlib.h>
//inisialisasi struct
struct data{
int number;
//pointer untuk menampung percabangan kiri dan kanan
data *left, *right;
}*root;
//fungsi push untuk menambah data
void push(data **current, int number){
//jika pointer current kosong maka akan membuat blok data baru
if((*current)==NULL){
(*current) = (struct data *)malloc(sizeof data);
//mengisi data
(*current)->number=number;
(*current)->left = (*current)->right = NULL;
//jika tidak kosong, maka akan dibandingkan apakah angka yang
//ingin dimasukkan lebih kecil dari pada root
//kalau iya, maka belok ke kiri dan lakukan rekursif
//terus menerus hingga kosong
}else if(number < (*current)->number){
push(&(*current)->left, number);
//jika lebih besar, belok ke kanan
}else if(number >= (*current)->number){
push(&(*current)->right, number);
}
}
//preOrder : cetak, kiri, kanan
void preOrder(data **current){
if((*current)!=NULL){
printf("%d -> ", (*current)->number);
preOrder(&(*current)->left);
preOrder(&(*current)->right);
}
}
//inOrder : kiri, cetak, kanan
void inOrder(data **current){
if((*current)!=NULL){
inOrder(&(*current)->left);
printf("%d -> ", (*current)->number);
inOrder(&(*current)->right);
}
}
//postOrder : kiri, kanan, cetak
void postOrder(data **current){
if((*current)!=NULL){
postOrder(&(*current)->left);
postOrder(&(*current)->right);
printf("%d -> ", (*current)->number);
}
}
//searching data
void search(data **current, int number){
//jika pointer current memiliki data
if((*current)!=NULL){
//cek, apakah datanya lebih kecil. Jika iya, belok ke kiri
if(number<(*current)->number){
search(&(*current)->left,number);
//jika lebih besar, maka belok ke kanan
}else if(number>(*current)->number){
search(&(*current)->right,number);
//jika sama dengan, maka angka ketemu
}else{
printf("Found : %d", (*current)->number);
}
//jika tidak ada data lagi (not found)
}else{
printf("Not Found.");
}
}
void main(){
push(&root, 11);
push(&root, 22);
push(&root, 13);
push(&root, 15);
push(&root, 9);
inOrder(&root);
printf("\n");
preOrder(&root);
printf("\n");
postOrder(&root);
printf("\n");
search(&root,91);
getchar();
}
Binary Search Tree
Binary Search Tree atau BST adalah suatu struktur data binary tree (pohon biner) yang berbasis simpul. binary Search Tree memiliki beberapa properti, seperti :
- Subtree kiri dari suatu node hanya berisi node-node dengan kunci yang lebih rendah daripada kunci node (node key).
- Subtree kanan dari suatu node hanya berisi node-node dengan kunci yang lebih besar daripada kunci node (node key).
- Subtree kiri dan kanan masing-masing juga harus berupa sebuah Binary Search Tree.
*dengan asumsi kunci berbeda.
Binary Search Tree (BST) adalah salah satu struktur data yang mendukung pencarian yang lebih cepat, penyortiran yang cepat, dan penyisipan (insertion) dan penghapusan (deletion) yang lebih mudah. Binary Search Tree (BST) juga dikenal sebagai Sorted Version of Binary Tree.
Basic operation yang ada pada Binary Search Tree (BST), yaitu :
- Search
- Insert
- Deletion
- Pre-Order Traversal
- In-Order Traversal
- Post-Order Traversal
Yang akan dibahas ada 3, yaitu :
- Insertion
- Searching
- Deletion
Contoh Codingan :
struct node* search(struct node* root, int key)
{
// Base Cases: root is null or key is present at root
if (root == NULL || root->key == key)
return root;
// Key is greater than root's key
if (root->key < key)
return search(root->right, key);
// Key is smaller than root's key
return search(root->left, key);
}
Insertion
Kunci (key) baru akan selalu dimasukkan (di insert) di daun. Kita memulai untuk mencari sebuah kunci (key) dari root/akar sampai menyentuh sebuah leaf node. Sekali sebuah leaf node ditemukan, node baru akan ditambahkan sebagai anak dari leaf node.
Contoh Codingan :
/* A utility function to insert a new node with given key in BST */
struct node* insert(struct node* node, int key)
{
/* If the tree is empty, return a new node */
if (node == NULL) return newNode(key);
/* Otherwise, recur down the tree */
if (key < node->key)
node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);
/* return the (unchanged) node pointer */
return node;
}
Deletion
Ada 3 kasus yang harus di pertimbangkan :
- Jika kunci (key) berada di leaf, hapus saja node itu.
- Jika kunci (key) ada di sebuah node yang tidak memiliki chid, hapus node tersebut dan hubungkan child dengan parent nya.
- Jika kunci (key) ada di node yang memiliki 2 children (anak), temukan child yang paling kanan dari sub-tree (simpul P), ganti kuncinya dengan kunci P dan delete P secara rekursif. Atau bisa secara bergantian memilih child paling kiri dari sub-tree kanan.
Contoh Codingan :
/* Given a binary search tree and a key, this function deletes the key
and returns the new root */
struct node* deleteNode(struct node* root, int key)
{
// base case
if (root == NULL) return root;
// If the key to be deleted is smaller than the root's key,
// then it lies in left subtree
if (key < root->key)
root->left = deleteNode(root->left, key);
// If the key to be deleted is greater than the root's key,
// then it lies in right subtree
else if (key > root->key)
root->right = deleteNode(root->right, key);
// if key is same as root's key, then This is the node
// to be deleted
else
{
// node with only one child or no child
if (root->left == NULL)
{
struct node *temp = root->right;
free(root);
return temp;
}
else if (root->right == NULL)
{
struct node *temp = root->left;
free(root);
return temp;
}
// node with two children: Get the inorder successor (smallest
// in the right subtree)
struct node* temp = minValueNode(root->right);
// Copy the inorder successor's content to this node
root->key = temp->key;
// Delete the inorder successor
root->right = deleteNode(root->right, temp->key);
}
return root;
}
Contoh Coding Deklarasi Awal
struct node* search(int data){
struct node *current = root;
printf("Visiting elements: ");
while(current->data != data){
if(current != NULL) {
printf("%d ",current->data);
//go to left tree
if(current->data > data){
current = current->leftChild;
}
//else go to right tree
else {
current = current->rightChild;
}
//not found
if(current == NULL){
return NULL;
}
}
}
return current;
}
Contoh Codingan untuk Insert Operation
void insert(int data) {
struct node *tempNode = (struct node*) malloc(sizeof(struct node));
struct node *current;
struct node *parent;
tempNode->data = data;
tempNode->leftChild = NULL;
tempNode->rightChild = NULL;
//if tree is empty
if(root == NULL) {
root = tempNode;
} else {
current = root;
parent = NULL;
while(1) {
parent = current;
//go to left of the tree
if(data < parent->data) {
current = current->leftChild;
//insert to the left
if(current == NULL) {
parent->leftChild = tempNode;
return;
}
}
//go to right of the tree
else {
current = current->rightChild;
//insert to the right
if(current == NULL) {
parent->rightChild = tempNode;
return;
}
}
}
}
}
Referensi :
- https://computerscience4lyfe.blogspot.com/2020/02/linked-list.html
- https://computerscience4lyfe.blogspot.com/2020/03/stack-and-queue.html
- https://computerscience4lyfe.blogspot.com/2020/03/hashing-and-hash-table-trees-binary-tree.html
- https://computerscience4lyfe.blogspot.com/2020/03/binary-search-tree.html
