Review

Review

STRUKTUR DATA - Linked List

Linked List
Linked List adalah struktur data yang terdiri dari urutan record data dimana setiap record memiliki field yang menyimpan alamat/referensi dari record selanjutnya (dalam urutan). Elemen data yang dihubungkan dengan link pada Linked List disebut Node. Biasanya didalam suatu linked list, terdapat istilah head dan tail.
Head adalah elemen yang berada pada posisi pertama dalam suatu linked list atau kepala
Tail adalah elemen yang berada pada posisi terakhir dalam suatu linked list atau ekor

Ada beberapa macam Linked List, yaitu :
1. Single Linked List
2. Double Linked List
3. Circular Linked List
4. Multiple Linked List

Single Linked List
Single Linked List merupakan suatu linked list yang hanya memiliki satu variabel pointer saja. Dimana pointer tersebut menunjuk ke node selanjutnya. Biasanya field pada tail menunjuk ke NULL.
contoh :

Contoh codingannya :

struct Mahasiswa{
char nama[25];
int usia;
struct Mahasiswa *next;
}*head,*tail;

Double Linked List
Double Linked List merupakan suatu linked list yang memiliki dua variabel pointer yaitu pointer yang menunjuk ke node selanjutnya dan pointer yang menunjuk ke node sebelumnya. Setiap head dan tailnya juga menunjuk ke NULL.

Contoh :

contoh codingannya :

struct Mahasiwa{
char nama[25];
int usia;
struct Mahasiswa *next,*prev;
}*head,*tail;

Circular Linked List
Circular Linked List merupakan suatu linked list dimana tail (node terakhir) menunjuk ke head (node pertama). Jadi tidak ada pointer yang menunjuk NULL. Ada 2 jenis Circular Linked List, yaitu :
Circular Single Linked List 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.

Multiple Linked List
Multiple Linked List merupakan suatu linked list yang memiliki lebih dar 2 buat variabel pointer. contoh :

Memory Allocation
Dalam C/C++, alokasi memory dapat dilakukan dengan menggunakan malloc , sedangkan untuk dealokasi dapat menggunakan free. Fungsi free hanya membebaskan memory tetapi tidak menghapus isi dari memory tersebut.

Contoh penggunaan malloc:

int *px = (int *) malloc(sizeof(int));
char *pc = (char *) malloc(sizeof(char));
struct Facebook *curr = (struct Facebook*) malloc(sizeof(struct Facebook));

Contoh penggunaan free:

free(curr);

Insert dan Delete Node dalam Single Linked List
Insert (push) dan delete (pop) node pada linked list dapat dilakukan pada posisi depan (head), tengah (mid) dan belakang (tail)

Insert (push)
Contoh codingan push depan :

Contoh codingan push belakang :

Delete (Pop)
Contoh codingan pop depan :

Contoh codingan pop belakang :

Insert dan Delete Node dalam Double Linked List
Insert (push) dan delete (pop) node pada linked list dapat dilakukan pada posisi depan (head), tengah (mid) dan belakang (tail)

Insert (Push)
Contoh codingan push depan :

Contoh codingan push belakang :

Delete (Pop)
Contoh codingan pop depan :

Contoh codingan pop belakang :

Single Linked List
Single Linked List merupakan suatu linked list yang hanya memiliki satu variabel pointer saja. Dimana pointer tersebut menunjuk ke node selanjutnya. Biasanya field pada tail menunjuk ke NULL.

Head adalah elemen yang berada pada posisi pertama dalam suatu linked list atau kepala
Tail adalah elemen yang berada pada posisi terakhir dalam suatu linked list atau ekor

Contoh koding:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// tipe local

struct Data
{
char name[51];
int score;
struct Data *next, *prev;
};//*head=NULL, *tail=NULL, *curr;

struct Data* newNode (char name[], int score){
// 1. Reserve Memory
struct Data *node = (struct Data*) malloc(sizeof(struct Data));

// 2. Assign Value
strcpy(node->name, name);
(*node).score = score;
node->next = NULL;
}


void pushHead(struct Data **head, struct Data **tail, char name[], int score)
{

struct Data *node = newNode(name, score);


if (head == NULL) // list masih kosong
{
*head = *tail = node;
}
else
{
node->next = *head;
*head = node;
}

}

void pushTail(struct Data **head, struct Data **tail, char name[], int score)
{



struct Data *node = newNode(name, score);


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

}

void pushMiddle(struct Data **head, struct Data **tail, char name[], int score)
{

struct Data *node = newNode(name, score);


if(*head == NULL)
*head = *tail = node;

else if (score < (*head)->score)
{
//pushHead
node->next = *head;
*head = node;
}
else if (score >= (*tail)->score)
{
//pushTail
(*tail)->next = node;
*tail = node;
}
else
{
struct Data *curr = *head;
while(score >= curr->next->score)
{
curr = curr->next;
}
node->next = curr->next;
curr->next = node; 
}
}

void popHead(struct Data **head, struct Data **tail)
{
if (*head == NULL)
printf ("No Data to Delete!\n");
else if (*head == *tail)
{
free(*head);
*head = *tail = NULL;
}
else
{
struct Data *curr = *head;
*head = (*head)->next;
free(curr);
}
}

void popTail (struct Data **head, struct Data **tail)
{
if (*head == NULL)
printf ("No Data to Delete!\n");
else if (*head == *tail)
{
free(*head);
*head = *tail = NULL;
}
else
{
struct Data *curr = *head;
while(curr->next != *tail)
{
curr = curr->next;
}
free(*tail);
*tail = curr;
(*tail)->next = NULL;
}
}

void popAll(struct Data **head, struct Data **tail)
{
if (*head == NULL)
printf("No Data to Delete!\n");
else
{
struct Data *curr = *head;
while (curr != NULL)
{
*head = (*head)->next;
free(curr);
curr = *head;
}
}
}


void cetak(struct Data *head)
{
if(head == NULL)
printf("No Data!\n");
else
{
struct Data *curr = head;
while(curr != NULL)
{
printf("%s %d\n", curr->name, curr->score);
curr = curr->next;
}
}
}

int main ()
{
struct Data *head=NULL;
struct Data *tail=NULL;

cetak(head);

pushHead(&head, &tail, "Agus Budiman", 22);
pushTail(&head, &tail, "Adel Wijaya", 22);
pushMiddle(&head, &tail, "Harris Setiawan", 53);
pushMiddle(&head, &tail, "Dinda Agustina", 45);
pushMiddle(&head, &tail, "Marie Ayunda", 37);
cetak(head);

popHead(&head, &tail);
popAll(&head, &tail);
cetak(head);

return 0;
}


HASHING

Secara sederhana, hashing berarti mengambil string input dengan panjang berapa pun dan memberikan output dengan panjang tetap
Contoh:

Output	Hash
Triv	A3B56C052D0CB495237B951B77D1271BE03E09E775E28FB6AA11465F77C129E8
t	E3B98A4DA31A127D4BDE6E43033F66BA274CAB0EB7EB1C70EC41402BF6273DD8
T	E632B7095B0BF32C260FA4C539E9FD7B852D0DE454E9BE26F24D0D6F91D069D3
Hash	A91069147F9BD9245CDACAEF8EAD4C3578ED44F179D7EB6BD4690E62BA4658F2
Bitcoin	B4056DF6691F8DC72E56302DDAD345D65FEAD3EAD9299609A826E2344EB63AA4

Jika ingin mencobanya dapat dilakukan disini https://passwordsgenerator.net/sha256-hash-generator/

1.      Pengertian Hash Tabel
Hash Table adalah sebuah struktur data yang terdiri atas sebuah tabel dan fungsi yang bertujuan untuk memetakan nilai kunci yang unik untuk setiap record (baris) menjadi angka (hash) lokasi record tersebut dalam sebuah tabel.
Keunggulan dari struktur hash table ini adalah waktu aksesnya yang cukup cepat, jika record yang dicari langsung berada pada angka hash lokasi penyimpanannya. Akan tetapi pada kenyataannya sering sekali ditemukan hash table yang record-recordnya mempunyai angka hash yang sama (bertabrakan).
Pemetaan hash function yang digunakan bukanlah pemetaan satusatu, (antara dua record yang tidak sama dapat dibangkitkan angka hash yang sama) maka dapat terjadi bentrokan (collision) dalam penempatan suatu data record. Untuk mengatasi hal ini, maka perlu diterapkan kebijakan resolusi bentrokan (collision resolution policy) untuk menentukan lokasi record dalam tabel. Umumnya kebijakan resolusi bentrokan adalah dengan mencari lokasi tabel yang masih kosong pada lokasi setelah lokasi yang berbentrokan.

2.      Operasi Pada Hash Tabel
Ø  insert: diberikan sebuah key dan nilai, insert nilai dalam tabel
Ø  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: mengambalikan iterator,yang memeriksa nilai satu demi satu

BINARY TREE

Binary Tree

Binary Tree adalah tree dengan syarat bahwa tiap node hanya boleh memiliki maksimal dua subtree dan kedua subtree tersebut harus terpisah. Sesuai dengan definisi tersebut, maka tiap node dalam binary tree hanya boleh memiliki paling banyak dua child.

a) Full Binary Tree

Binary Tree yang tiap nodenya (kecuali leaf) memiliki dua child dan tiap subtree harus mempunyai panjang path yang sama.

b) 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.

c) Skewed Binary Tree

akni Binary Tree yang semua nodenya (kecuali leaf) hanya memiliki satu child.

Implementasi Binary Tree

Binary Tree dapat diimplemntasikan dalam Pascal dengan menggunakan double Linked List. Untuk nodenya, bisa dideklarasikan sbb :

Type Tree = ^node;

Node = record

Isi : TipeData;

Left,Right : Tree;

end;

Contoh ilustrasi Tree yang disusun dengan double linked list :

Operasi-operasi pada Binary Tree :

v Create : Membentuk binary tree baru yang masih kosong.

v Clear : Mengosongkan binary tree yang sudah ada.

v Empty : Function untuk memeriksa apakah binary tree masih kosong.

v Insert : Memasukkan sebuah node ke dalam tree. Ada tiga pilihan insert: sebagai root, left child, atau right child. Khusus insert sebagai root, tree harus dalam keadaan kosong.

v Find : Mencari root, parent, left child, atau right child dari suatu node. (Tree tak boleh kosong)

v Update : Mengubah isi dari node yang ditunjuk oleh pointer current. (Tree tidak boleh kosong)

v Retrieve : Mengetahui isi dari node yang ditunjuk pointer current. (Tree tidak boleh kosong)

v DeleteSub : Menghapus sebuah subtree (node beserta seluruh descendantnya) yang ditunjuk current. Tree tak boleh kosong. Setelah itu pointer current akan berpindah ke parent dari node yang dihapus.

v Characteristic : Mengetahui karakteristik dari suatu tree, yakni : size, height, serta average lengthnya. Tree tidak boleh kosong. (Average Length = [jumlahNodeLvl1*1+jmlNodeLvl2*2+…+jmlNodeLvln*n]/Size)

v Traverse : Mengunjungi seluruh node-node pada tree, masing-masing sekali. Hasilnya adalah urutan informasi secara linier yang tersimpan dalam tree. Adatiga cara traverse : Pre Order, In Order, dan Post Order.

Langkah-Langkahnya Traverse :

Ø PreOrder : Cetak isi node yang dikunjungi, kunjungi Left Child, kunjungi Right Child.

Ø InOrder : Kunjungi Left Child, Cetak isi node yang dikunjungi, kunjungi Right Child.

Ø PostOrder : Kunjungi Left Child, Kunjungi Right Child, cetak isi node yang dikunjungi.