REVIEW DATA STRUCTURE

LINKED LIST

Linked list adalah salah satu data structure yang terdiri dari urutan record data dimana setiap record punya field yang berisikan alamat/referensi ke record data berikutnya dalam sebuah urutan.

SINGLE LINKED LIST

Sebuah Single Linked List hanya memiliki 1 penghubung ke node lain.

Sebuah Linked List dikatakan kosong apabila isi pointer head adalah NULL.

Single Linked List hanya memiliki beberapa operasi yaitu PUSH dan POP.

Contoh

PUSH DEPAN 2,4,6,8 maka hasilnya angka paling depan akan ada dipaling belakang maka urutannya 8-6-4-2-NULL.

PUSH BELAKANG 2,4,6,8 maka hasilnya akan sama 2-4-6-8-NULL.

cara coding single linked list

pertama buat dulu struct data misal untuk nama dan score.

struct data{ char name[51]; int score; struct data *next; }*head=NULL, *tail=NULL;

kedua buat nodenya

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; return node; }

setelah itu bisa buat program pushnya. seperti push depan, belakang atau tengah

Push Depan

void pushHead(struct data **head, struct data **tail, char name[], int score){ //1. reserve memory & 2. assign value struct data *node = newNode(name, score); //3. connect if(*head == NULL) //list masih kosong *head = *tail = node; else{ node->next = *head; *head = node; } }

Push Belakang

void pushTail(struct data **head, struct data **tail, char name[], int score) { //1. reserve memory & 2. assign value struct data *node = newNode(name, score); //3. connect if(*head == NULL) //list masih kosong *head = *tail = node; else { (*tail)->next = node; *tail = node; } }

Push Tengah

void pushMiddle(struct data **head, struct data **tail, char name[], int score){ //1. reserve memory & 2. assign value struct data *node = newNode(name, score); //3. connect if(*head == NULL) //list masih kosong *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; } }

setelah membuat program maka kita akan membuat program pop yaitu delete.

Pop Depan

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

Pop Belakang

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

Pop Tengah

void popMiddle(struct data **head, struct data **tail){ int count=2; struct data *curr = *head; if(*head == NULL){ printf("No Data to Delete\n"); } else if(*head == *tail){ free(*head); *head = *tail = NULL; } else{ while(curr->next!=NULL){ curr=curr->next; count++; } curr=*head; if(count%2==0){ count=count/2; } else{ count=(count/2)+1; } int dex=1; while(dex!=count-1){ curr=curr->next; dex++; } struct data *depan = *head; struct data *belakang = *head; struct data *prev; while(depan!=NULL && depan->next!=NULL){ depan=depan->next->next; prev=belakang; belakang=belakang->next; } prev->next=belakang->next; free(belakang); } }

Pop All

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

cara deklarasinya

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

//lalu masukkan function push yang diinginkan misal push middle atau pop

pushMiddle(&head, &tail, "michael", 19);

//perlu diingat function pop tidak akan berjalan jika data yang tersisa tinggal 1

}

LINKED LIST II

CIRCULAR SINGLE LINKED LIST

Circular Single Linked List adalah sebuah Linked List dimana semua node terhubung untuk membentuk sebuah loop.

Pada Circular Single Linked List tidak memiliki NULL pada bagian akhirnya.

Cara Deklarasi Node Circular Single Linked List

typedef struct TNode{

int data;

TNode *next;

};

DOUBLY LINKED LIST

Doubly Linked List adalah Linked List dua arah dimana yang satu berisi refrensi kedata berikutnya dan yang satunya lagi berisi data refrensi berikutnya.

deklarasi Doubly Linked List

struct tnode {

int value;

struct tnode *next;

struct tnode *prev;

};

struct tnode *head = 0;

struct tnode *tail = 0;

HASHING TABLE & BINARY TREE

Hashing adalah teknik yang digunakan untuk menyimpan dan mengambil key dengan cepat.

Dalam Hashing character string dapat ditransform menjadi sebuah nilai yang datanya pendek atau sebuah key yang mewakili string asli.

Hash Table adalah tabel (array) tempat dimana menyimpan string asli. Indeks tabel adalah Hashed Key sementara nilainya adalah string asli.

Ukuran table hash berbeda-beda biasanya beberapa urutan besarnya lebih rendah dari jumlah total string yang mungkin ada, sehingga beberapa string mungkin memiliki hash key yang sama.

HASH FUNCTION

MID-Square

Mid-Square merupakan fungsi hashing dengan cara mengkuadratkan nilai string/indentifier yang kemudian digunakan dalam jumlah bit sesuai dengan tengah kotak untuk mendapatkan hash key.

Sebagai contoh

Nilai = 1003

Nilai 1003 dipangkatkan menjadi 1.006.009‬ nilai tersebut merupakan square value

Setelah itu ambil nilai tengah dari squre value yaitu 606 ini merupakan hasil dari Mid-Square Hashing.

Division

Division merupakan fungsi hashing dengan cara membagi nilai string/indentifier menggunakan operator modulus.

Sebagai contoh

Misalnya table menyimpan string. Fungsi hash yang sangat sederhana adalah menambahkan nilai ASCII dari semua karakter dalam string dan mengambil modulo ukuran tabel, misalnya 97.

Misalnya data "ABCD" maka ( 64+1 + 64+2 + 64+3 + 64+4) % 97 = 76 oleh karena itu data "ABCD" akan disimpan di 76.

Folding

Folding merupakan fungsi hashing dengan cara mempartisi string/indentifier menjadi beberapa bagian lalu ditambahkan bersama-sama untuk mendapatkan hash key

Sebagai contoh

Nilai = 1234

maka akan dipecah menjadi 2 part yaitu 12 dan 34

setelah itu ditambahkan 12+34 maka menjadi 46

maka hash keynya 46

Digit Extraction

Digit Extraction merupakan fungsi hashing dengan cara digit yang ditentukan sebelumnya dari nomor yang diberikan dianggap sebagai alamat hash.

Sebagai contoh

Nilai = 123456

jika kita hanya mengambil digit ke 1, 3 dan 5 maka kita akan mendapatkan

hash code = 135

Rotating Hash

Rotating Hash merupakan fungsi hashing dengan cara metode hash (seperti metode pembagian atau mid-square)

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

Rotasi dilakukan dengan menggeser digit untuk mendapatkan alamat hash baru.

Sebagai contoh

diberikan hash address 12345

maka hasil dari rotating hashnya 54321

COLLISION

Collision terjadi jika kita ingin menyimpan string ini menggunakan fungsi hash sebelumnya (gunakan karakter pertama dari setiap string).

Cara untuk menyelesaikan collision ada 2 yaitu

1. Linear Probing

Cari slot kosong berikutnya dan letakkan string tersebut di sana.

2. Chaining

Masukkan string ke dalam slot sebagai chained list(linked list).

TREE & BINARY TREE

Tree adalah struktur data non-linear yang mewakili hubungan hierarkis di antara objek data.

Beberapa hubungan tree dapat diamati dalam struktur direktori atau hierarki organisasi.

Node di tree tidak perlu disimpan secara berdekatan dan dapat disimpan di mana saja dan dihubungkan oleh pointer.

BINARY TREE CONCEPT

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

Kedua anak itu biasanya dibedakan sebagai anak kiri dan anak kanan.

Node yang tidak memiliki anak disebut leaf.

TIPE-TIPE BINARY TREE

Perfect Binary Tree

PERFECT binary tree adalah binary tree di mana setiap level berada pada kedalaman yang sama.

Complete Binary Tree

Complete Binary Tree adalah binary tree di mana setiap level, kecuali mungkin yang terakhir, terisi penuh, dan semua node sejauh mungkin dibiarkan. Perfect Binary Tree adalah Complete Binary Tree.

Skewed Binary Tree

Skewed Binary Tree adalah binary tree di mana setiap node memiliki paling banyak satu anak.

Balanced Binary Tree

Balanced Binary Tree adalah binary tree di mana tidak ada daun yang jauh lebih jauh dari root daripada leaf lainnya (skema penyeimbangan yang berbeda memungkinkan definisi yang berbeda dari "jauh lebih jauh").

TRANSVERSAL

misal ekspresi pada tree concept

struct tnode {

char chr;

struct tnode *left;

struct tnode *right;

};

lalu buat ekspresi pada tree dari prefix

Bisa dideklarasikan dengan cara rekursif

char s[MAXN];

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 transversal

void prefix(struct tnode *curr){

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

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

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

}

Postfix transversal

void postfix(struct tnode *curr) {

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

if ( curr->right != 0 ) postfix(curr->right); printf( “%c“, curr->chr );

}

Infix transversal

void infix(struct tnode *curr) {

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

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

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

}

Binary Search Tree

Binary search tree adalah salah satu struktur data yang faster searching, rapid sorting, and easy insertion and deletion. Binary search tree juga dikenal sebagai versi binary tree yang disort.

INSERTION OPERATION

Dimulai dari root. jika x kurang dari node maka insert x ke sub tree, atau masukkan x ke sub tree kanan ulang terus sampai menemukan empty node untuk meletakkan X (X akan selalu menjadi leaf baru)

DELETION

jika key hanya leaf tinggal delete saja nodenya

jika key memiliki 1 child delete node dan connect child ke parentnya

Jika key ada dinode yang memiliki dua child, temukan child paling kanan dari sub tree kirinya (simpul P), ganti kuncinya dengan kunci P dan hapus P secara rekursif. (atau secara bergantian Anda dapat memilih anak paling kiri dari sub tree kanannya)