Summary Data Structure

LINKED LIST

1.       Circular Single Linked List

Single : field pointernya hanya satu buah dan satu arah

Linked List : node-node nya saling terhubung satu sama lain

Circular : pointer next-nya akan menunjuk pada dirinya sendiri sehingga berputar

 Jadi, single linked list circular adalah single linked list yang pointer nextnya menunjuk kepada dirinya sendiri artinya linked list ini tidak memiliki nilai NULL untuk medan sambungannya.

Setiap nodenya memiliki field yang berisi pointer ke next node, dan juga memiliki field yang berisi data.

Deklarasi Single Linked List Circular:

 Struct tnode  { 

int data;

tnode *next;

 };

void main()  { 

head = new tnode; 

head->next = head; 

}

Node terakhir akan menunjuk ke node paling depan sehingga linked list akan terus berputar.

1.       Double Linked List

Adalah linked list dengan node yang memiliki data dan dua buah pointer (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.

Deklarasi node dibuat dari struct berikut ini :

typedef struct TNode{  

int data;  

Tnode *next;  

Tnode *prev; 

};

Awalnya, 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.

Pointer 1 akan menunjuk Head (node pertama).

Deklarasi pointer penunjuk head pada double linked list :

TNode *head;

Penambahan data di depan

Penambahan node baru akan dikaitkan di node paling depan, namun saat data masih kosong, maka penambahan data dilakukan pada head-nya. Jadi, kita mengkaitkan data baru dengan head, kemudian head akan menunjuk pada data baru tersebut sehingga head akan tetap selalu menjadi data yang paling pertama. Kita juga membutuhkan pointer bantu untuk menghubungkan node terakhir dengan node terdepan.

Contoh code menambah data baru di depan :

int isEmpty(){  //untuk mengecek apakah double linked list nya kosong

if(head == NULL) return 1;

else return 0;

}

void insertDepan(int databaru){  

TNode *baru;  

baru = new TNode;  

baru->data = databaru; 

baru->next = NULL;  

baru->prev = NULL;  

if(isEmpty()==1){

head=baru;

head->next = NULL;

head->prev = NULL;  

}

   else {

baru->next = head;

head->prev = baru;

head = baru;  

}

   Printf(”Data masuk\n”);

} 

Penambahan data di belakang

Penambahan data dilakukan di belakang, namun pada saat pertama kali data langsung ditunjuk pada head-nya. Penambahan di belakang lebih sulit karena kita membutuhkan pointer bantu untuk mengetahui data terbelakang, kemudian dikaitkan dengan data baru. Kita membutuhkan perulangan untuk mengetahui data terbelakang.

Contoh code menambah data baru di belakang :

Void insertBelakang (int databaru){ 

Tnode *baru, *bantu; 

Baru = new Tnode;

baru->data = databaru; 

baru->next = NULL;

baru->prev = NULL; 

if(isEmpty()==1){  

head=baru;  

head->next = NULL;  

head->prev = NULL; 

} 

else{  

bantu=head;  

while(bantu->next!=NULL){  

bantu=bantu->next  

} 

bantu->next = baru;  

baru->prev = bantu;  

}

   Printf(”Data masuk\n”);

}

Menghapus Node Double Linked List

Tidak diperlukan pointer karena pointer hapus sudah bisa menunjuk ke pointer sebelumnya dengan menggunakan elemen prev ke node sebelumnya, yang akan diset agar menunjuk ke NULL setelah penghapusan dilakukan.

Contoh code menghapus data di depan:

void hapusDepan (){

TNode *hapus;

int d;

if (isEmpty()==0){

if(head->next != NULL){

hapus = head;

d = hapus->data;

head = head->next;

head->prev = NULL;

delete hapus;

}

else {

 d = head->data; head = NULL;

}

printf" terhapus\n";

}

else printf"Masih kosong\n";

}

Contoh code menghapus node terbelakang :

void hapusBelakang(){

TNode *hapus;

int d;

if (isEmpty()==0){

if(head->next != NULL){

hapus = head;

while(hapus->next!=NULL){

hapus = hapus->next;

}

d = hapus->data;

hapus->prev->next = NULL;

delete hapus;

}

else {

d = head->data;

head = NULL;

}

Printf “terhapus\n";

}

else printf"Masih kosong\n";

}

Double Linked List Circular

Double Linked List Circular (DLLC) adalah linked list dengan menggunakan pointer, dimana  setiap node memiliki 3 field, yaitu 1 field pointer yang menunjuk next, 1 field menunjuk pointer prev, serta sebuah field yang berisi data untuk node tersebut dengan pointer next dan prev-nya menunjuk ke dirinya sendiri secara circular.

Deklarasi node di double linked list circular:

typedef struct TNode{

int data;

TNode *next;

Tnode *prev;

};

HEAD AND TAIL

Pada linked list, terdapat istilah push, dan pop dimana push berarti insert data baru pada linked list tersebut, dimana kita bisa push dari depan(dimana data yang kita masukkan berada di paling depan linked list kita dan data yang kita masukkan tersebut menjadi head), belakang (dimana data yang kita masukkan akan berada di paling belakang linked list kita dan data yang kita masukkan tersebut menjadi tail). Sedangkan pop berarti mendelete data, data dari depan, tengah dan juga belakang. Pada linked list, head berarti yang paling depan pada linked list tersebut, sedangkan tail berarti data yang terakhir.
Pada linked list digunakan fungsi malloc, untuk memesan sebuah alamat memory. Pada saat penggunaan malloc itu sendiri, mungkin beberapa bertanya-tanya mengapa digunakan sizeof, tidak langsung saja misal int, langsung saja 4, tidak usah pake sizeof(int), jawabannya adalah agar dinamis, karena kita tidak pernah tau program kita akan dicompile di compiler apa, bisa saja 16 ataupun 32 bit, yang mengakibatkan jumlah byte nya berbeda-beda.

Berikut contoh code fungsi untuk push head / menambahkan data dari depan :

Berikut contoh code fungsi untuk push tail / menambahkan data dari belakang :

Berikut contoh code fungsi untuk pop head/ men delete data paling depan :

Berikut contoh code fungsi untuk pop tail / men delete data paling belakang :

Hashing

adalah proses menghasilkan data keluaran (output data) yang panjangnya tetap dan sama, dari data masukan (input data) yang panjangnya berbeda-beda. 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. Itu juga digunakan dalam banyak algoritma enkripsi.

Hash Table

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. Menyimpan data pada memori ke dalam baris-baris dan kolom-kolom sehingga membentuk table yang diakses dengan cepat.

Hash Function

 •       Mid-square

Mid-Square hashing adalah teknik hashing di mana kunci unik dihasilkan. Dalam teknik ini, nilai diambil dan dikuadratkan. Kemudian, beberapa digit dari tengah diekstraksi. Angka-angka yang diekstrak ini membentuk angka yang diambil sebagai nilai baru. Teknik ini dapat menghasilkan kunci dengan keacakan tinggi jika nilai yang cukup besar akan diambil.    •       Division (most common)

Jumlah lokasi memori yang tersedia dihitung, kemudian jumlah tersebut digunakan sebagai pembagi untuk membagi nilai yang asli dan menghasilkan sisa. Sisa tersebut adalah nilai hashnya. Secara umum, rumusnya h(k)= k mod m. Dalam hal ini m adalah jumlah lokasi memori yang tersedia pada array. Fungsi hash tersebut menempatkan record dengan kunci K pada suatu lokasi memori yang beralamat h(k). Metode ini sering menghasilkan nilai hash yang sama dari dua atau lebih nilai aslinya atau disebut dengan bentrokan. Karena itu, dibutuhkan mekanisme khusus untuk menangani bentrokan yang disebut kebijakan resolusi bentrokan.

Contoh: asumsikan ukuran tabel = 11 dan satu file dengan 8 record menggunakan nilai kunci sebagai berikut : 12,21,68.

Maka:

(12 mod 11) + 1 = 1 + 1 = 2 ; simpan 12 dilokasi 2

(21 mod 11) + 1 = 10 + 1 = 11 ; simpan 21 dilokasi 11

(68 mod 11) + 1 = 2 + 1 = 3 ; simpan 68 dilokasi 3

(38 mod 11) + 1 = 5 + 1 = 6 ; simpan 38 dilokasi 6

(52 mod 11) + 1 = 9 + 1 = 10 ; simpan 52 dilokasi 10

(70 mod 11) + 1 = 4 + 1 = 5 ; simpan 70 dilokasi 5

(44 mod 11) + 1 = 0 + 1 = 1 ; simpan 44 dilokasi 1

(18 mod 11) + 1 = 7 + 1 = 8 ; simpan 18 dilokasi 8

Sehingga :

Index 1 2 3 4 5 6 7 8 9 10 11

Nilai Key 44 12 68 – 70 38 – 18 52 – 21

 •       Folding

Untuk mendapatkan alamat relatif, nilai key dibagi menjadi beberapa bagian, setiap bagian (kecuali bagian terakhir) mempunyai jumlah digit yang sama dengan alamat relatif. Bagian-bagian ini kemudian dilipat (seperti kertas) dan dijumlah. Hasilnya, digit yang tertinggi dibuang (bila diperlukan).

Contoh : 

Kunci 123456, 234351, 222456, 321654, dilipat menjadi 2 bagian, setiap 3 digit.
Maka :
123+654 = 777 ; simpan 123456 dilokasi 777
234+153 = 387 ; simpan 234351 dilokasi 387
222+654 = 876 ; simpan 222456 dilokasi 876
321+456 = 777; simpan 321654 dilokasi 777
Dari perhitungan terjadi kolisi untuk nomor 123456 dan 321654.

•  Digit Extraction

Digit yang telah ditetapkan dari nomor yang diberikan dianggap sebagai alamat hash.

Contoh:

Misalkan x = 14.568

Jika kita mengekstrak digit pertama, ketiga, dan kelima, kita akan mendapatkan kode hash: 158.

•   Rotating Hash

Gunakan metode hash (seperti metode division atau Mid-Square). Setelah mendapatkan kode hash/alamat dari metode hash, lakukan rotasi. Rotasi dilakukan dengan menggeser digit untuk mendapatkan alamat hash baru.

Contoh:

Misal alamat hash = 20021

Hasil rotasi: 12002 (membalik angka)

Trees & Binary Tree

Following are the important terms with respect to tree :

·      Path − Path refers to the sequence of nodes along the edges of a tree.

·      Root − The node at the top of the tree is called root. There is only one root per tree and one path from the root node to any node.

·      Parent − Any node except the root node has one edge upward to a node called parent.

·      Child − The node below a given node connected by its edge downward is called its child node.

·      Leaf − The node which does not have any child node is called the leaf node.

·      Subtree − Subtree represents the descendants of a node.

·      Visiting − Visiting refers to checking the value of a node when control is on the node.

·      Traversing − Traversing means passing through nodes in a specific order.

·      Levels − Level of a node represents the generation of a node. If the root node is at level 0, then its next child node is at level 1, its grandchild is at level 2, and so on.

·      keys − Key represents a value of a node based on which a search operation is to be carried out for a node.

Binary Tree

Binary Tree atau Pohon Biner adalah sebuah pohon dalam struktur data yang bersifat hirarkis (hubungan one to many). Tree bisa didefenisikan sebagai kumpulan simpul dengan setiap simpul mempunyai paling banyak dua anak. Secara khusus, anaknya dinamakan kiri dan kanan. Binary tree tidak memiliki lebih dari tiga level dari Root.
Binary tree adalah suatu tree dengan syarat bahawa tiap node (simpul) hanya boleh memiliki maksimal dua subtree dan kedua subtree tersebut harus terpisah. Tiap node dalam binary treee boleh memiliki paling banyak dua child (anak simpul), secara khusus anaknya  dinamakan kiri dan kanan.
Pohon biner dapat juga disimpan sebagai struktur data implisit dalam array, dan jika pohon tersebut merupakan sebuah pohon biner lengkap, metode ini tidak boros tempat. Dalam penyusunan yang rapat ini, jika sebuah simpul memiliki indeks i, anaknya dapat ditemukan pada indeks ke-2i+1 dan 2i+2, meskipun ayahnya (jika ada) ditemukan pada indeks lantai ((i-1)/2) (asumsikan akarnya memiliki indeks kosong).

BINARY SEARCH TREE

Di computer science, binary search trees (BST), disebut sebagai binary tree yang diurutkan, adalah sebuah data structure yang menyimpan "item" tertentu (biasanya angka, nama, dll) di memori. Binary search trees (BST) memungkinkan untuk pencarian cepat, penambahan dan penghapusan item. Pada binary search trees (BST) sendiri menggunakan konsep untuk angka lebih kecil berada di sebelah kiri dan angka lebih besar berada di sebelah kanan.

Binary search tree mempunyai operasi dasar yaitu:

-          find(x)             : mencari kunci x di binary search tree (BST)

Setiap kali data dicari, mulailah mencari dari simpul akar. Kemudian jika data kurang dari nilai kunci, cari elemen di subtree kiri. Jika tidak, cari elemen di subtree kanan. Ikuti algoritma yang sama untuk setiap node.

-          insert(x)          : menambahkan kunci baru x di binary searach tree (BST)

Setiap kali data baru dimasukkan, pertama-tama cari lokasi yang tepat. Mulai mencari darileaf node, kemudian jika data kurang dari nilai kunci, cari lokasi kosong di subtree kiri dan masukkan data. Jika tidak, cari lokasi kosong di subtree kanan dan masukkan data.

-          remove(x)       : menghapus key x dari BST

Ketika kita menghapus sebuah key, maka akan ada 3 kemungkinan :

- Node yang dihapus terletak pada leaf : Maka simple langsung hapus saja data tersebut.

- Node yang dihapus mempunyai satu anak: Maka salin value anak tersebut ke dalam node dan hapus value anak di tempat semula.

- Node yang akan dihapus memiliki dua anak: Temukan penerus inorder dari node. Salin penerus inorder ke node dan hapus penerus inorder. Perhatikan bahwa pendahulu inorder juga dapat digunakan.

Sekian ringkasan yang saya buat, Terimakasih.