Singly Linked List:
Singly Linked list adalah linked list yang hanya memiliki
satu pointer yang mengarah ke node berikutnya.
Berikut
adalah gambaran Singly Linked List:
Circular Singly Linked List
Selain itu juga terdapat Circular Singly Linked List yaitu
Singly Linked List yang node tailnnya memiliki pointer yang mengarah ke head
nodenya.
Berikut
adalah gambaran Circular Singly Linked List:
Membuat Singly Linked List:
Source
code:
struct data
{
int value;
struct data
*next; // Pada single linked list hanya ada
penunjuk untuk node berikutnya.
}*head,*curr,*tail;
//head adalah node paling depan
//tail adalah node paling belakang
//curr adalah penunjuk yang akan gerak antar node untuk operasi insert dan deletenya
nanti.
Operasi pada singly linked list:
1. Insert/Push:
operasi untuk memasukkan node atau data baru pada
linked list. Terdapat dua macam insert yaitu insert(head) dan insert(tail).
a. Insert(head):
memasuki node barunya di depan linked listnya yaitu sebelum head, sehingga
node
baru tersebut menjadi head.
Source
Code Insert(head):
void
insert_before_head(int nilai)
{
curr=(struct data*)malloc(sizeof(struct data)); //alokasi
memori untuk node baru
curr->value = nilai;
if(head==NULL)
{
head=tail=curr;
}
else
{
curr->next=head; //next dari node baru akan
menunjuk pada head dr linked list
head=curr; //Kemudian head akan pindah ke curr atau node baru tadi.
}
}
b. Insert(tail): memasuki
node barunya di belakang linked list yaitu setelah tail, sehingga node
baru
tersebut menjadi tailnya.
Source code
Insert(tail):
void insert_after_tail(int nilai)
void insert_after_tail(int nilai)
{
curr=(struct data*)malloc(sizeof(struct data));
// mengalokasikan memori untuk node barunya
curr->value = nilai;
if(head==NULL) //jika head kosong maka list baru tersebut adalah head,
tail dan juga currnya
{
head=tail=curr;
}
else{
tail->next=curr; //next dari tail akan menunjukkan
node baru yaitu curr.
tail=curr; //Lalu tailnya pindah ke node baru tersebut.
}
tail->next=NULL;
}
2. Delete/Pop: operasi
untuk menghapus sebuah node atau data dalam linked list. Terdapat 2 macam delete yaitu delete(head) dan delete(tail):
a. Delete(head): menghapus node paling depan linked list atau head dari linked list tersebut.
Source code
Delete(head):
void
delete_head()
{
if(tail==head)
{
free(curr);
tail=head=curr=NULL;
}
else
{
curr=head; //currnya akan memulai di head.
head=head->next; //kemudian head akan berpindah ke node
nextnya/berikutnya.
free(curr); //kemudian curr yang di paling depan tadi akan dihapus
curr=NULL;
}
b. Delete(tail): menghapus node paling belakang linked list atau tail dari linked list tersebut.
void delete_tail()
{
curr=head; //karena single linked list hanya memiliki ponter pada node berikutnya maka kita
{
curr=head; //karena single linked list hanya memiliki ponter pada node berikutnya maka kita
memulai dari node paling awal yaitu head.
if(tail==head)
{
free(curr);
tail = head = curr = NULL;
}
else
{
while(curr->next!=tail)
{
curr=curr->next; //pada looping ini curr akan berpindah sampai pointer nextnya adalah tail
{
free(curr);
tail = head = curr = NULL;
}
else
{
while(curr->next!=tail)
{
curr=curr->next; //pada looping ini curr akan berpindah sampai pointer nextnya adalah tail
}
free(tail); //lalu tail dihapus
free(tail); //lalu tail dihapus
tail=curr; //kemudian
curr sebelum tail tadi akan menjadi tail baru linked list tersebut.
tail->next=NULL;
}
}
}
}
adalah Linked List ynang memiliki dua pointer dimana yang pertama mengarah ke node berikutnya dan satunya lgi mengarah ke node sebelumnya.
Berikut adalah gambaran doubly Linked List:
Selain itu juga terdapat Circular Doubly Linked List dimana pointer next pada tail mengarah ke head dan ponter prev pada head mengarah ke tail.
Berikut adalah gambaran Circular Doubly Linked List:
Source Codenya:
struct data
{
int value;
struct data *next,*prev; //pada doubly linked list terdapat penunjuk pada node sebelum dan
berikutnya
}*head,*curr,*tail;
Operasi pada Doubly Linked List:
1. Insert/Push:
Insert/Push pada Doubly Linked List terdapat tiga yaitu: insert head, insert tail, dan insert setelah node
spesifik.
a. Insert(head): memasuki node barunya di depan linked listnya yaitu sebelum head, sehingga
node
baru tersebut menjadi head.
Source Codenya:
void insert_before_head(int nilai)
{
curr = (struct data*)malloc(sizeof(struct data));
curr->value = nilai;
if(head==NULL)
{
head=tail=curr;
}
else
{
head->prev=curr; //prev pada head akan menunjuk pada curr/node baru
curr->next=head; //lalu next pada node baru/curr akan menunjuk pada head
head=curr; //kemudian head akan pindah ke node baru/curr.
}
head->prev=NULL;
tail->next=NULL;
}
b. Insert(tail): memasuki node barunya di belakang linked list yaitu setelah tail, sehingga node
Source Codenya:
void insert_before_head(int nilai)
{
curr = (struct data*)malloc(sizeof(struct data));
curr->value = nilai;
if(head==NULL)
{
head=tail=curr;
}
else
{
head->prev=curr; //prev pada head akan menunjuk pada curr/node baru
curr->next=head; //lalu next pada node baru/curr akan menunjuk pada head
head=curr; //kemudian head akan pindah ke node baru/curr.
}
head->prev=NULL;
tail->next=NULL;
}
b. Insert(tail): memasuki node barunya di belakang linked list yaitu setelah tail, sehingga node
baru
tersebut menjadi tailnya.
Source codenya:
void insert_after_tail(int nilai)
{
curr = (struct data*)malloc(sizeof(struct data));
curr->value = nilai;
if(head==NULL)
{
head=tail=curr;
}
else {
tail->next=curr; //next pada tail akan menunjuk curr atau node baru.
curr->prev=tail; //prev pada curr/node baru akan menunjuk pada tail
tail=curr; //lalu tail akan pindah ke curr atau node baru tadi.
}
head->prev=NULL;
tail->next=NULL;
}
c. Insert(after_node): Memasuki node barunya setelah node yang ditentukan.
Source code:
void insert_after_node(struct data* prev_node, int nilai) //disini akan menerima node yg mau
dimasukkan node baru sesudahnya
dan data/nilainya juga.
{
curr = (struct data*)malloc(sizeof(struct data));
curr->value = nilai;
if(prev_node==NULL)
{
printf("prev_nodenya tidak boleh NULL\n");
}
else
{
curr->next=prev_node->next; //next pada node baru akan menunjuk next pada prev_node
prev_node->next=curr; //next pada prev_node akan menunjuk pada curr
curr->prev=prev_node; //kemudian prev pada node baru/curr akan menunjuk prev_node.
if(curr->next!=NULL)
{
curr->next->prev=curr;
}
}
}
Source codenya:
void insert_after_tail(int nilai)
{
curr = (struct data*)malloc(sizeof(struct data));
curr->value = nilai;
if(head==NULL)
{
head=tail=curr;
}
else {
tail->next=curr; //next pada tail akan menunjuk curr atau node baru.
curr->prev=tail; //prev pada curr/node baru akan menunjuk pada tail
tail=curr; //lalu tail akan pindah ke curr atau node baru tadi.
}
head->prev=NULL;
tail->next=NULL;
}
c. Insert(after_node): Memasuki node barunya setelah node yang ditentukan.
Source code:
void insert_after_node(struct data* prev_node, int nilai) //disini akan menerima node yg mau
dimasukkan node baru sesudahnya
dan data/nilainya juga.
{
curr = (struct data*)malloc(sizeof(struct data));
curr->value = nilai;
if(prev_node==NULL)
{
printf("prev_nodenya tidak boleh NULL\n");
}
else
{
curr->next=prev_node->next; //next pada node baru akan menunjuk next pada prev_node
prev_node->next=curr; //next pada prev_node akan menunjuk pada curr
curr->prev=prev_node; //kemudian prev pada node baru/curr akan menunjuk prev_node.
if(curr->next!=NULL)
{
curr->next->prev=curr;
}
}
}
2. Delete/Pop:
Delete/Pop pada Doubly Linked List terdapat 2 yaitu: Delete(head) ,dan Delete(tail).
a. Delete(head): Menghapus node paling depan atau head dari Doubly Linked List.
Source code:
void delete_head()
{
curr=head;
if(tail==head)
{
free(curr);
tail=head=curr=NULL;
}
else
{
head=curr->next; //head akan pindah ke next dari curr
free(curr); //lalu curr akan di hapus
head->prev=NULL;
}
}
b. Delete(tail): Menghapus node paling akhir atau tail dari Doubly Linked List.
Source code:
void delete_tail()
{
curr=tail; //karena doubly linked list memiliki pointer ke node sebelumnya kita dpt memulai dr tail
if(tail==head)
{
free(curr);
tail = head = curr = NULL;
}
else
{
tail=curr->prev; //tail akan pindah ke prev dari curr
free(curr); //lalu curr akan di hapus
tail->next=NULL;
}
}
Hashing
Hashing adalah sebuah teknik untuk mengubah sebuah string
karakter menjadi sebuah key yang mempresentasikan string karakter aslinya
tersebut.
Tujuannya adalah untuk mempercepat pencarian dan pengambilan
item dari sebuah database, karena mencari dengan hash key yang sudah
disingkatkan lebih cepat dibandingkan mencari dengan string karakter aslinya.
Hash Table
Hash table adalah array dimana kita menyimpan string kita.
Index dari array hash table adalah hash key yang disingkatkan dari string
sedangkan value yang disimpan adalah string tersebut.
Hash Function
Hash function adalah teknik-teknik untuk membuat hash kay.
1. Mid Square
Mendapatkan hash key dengan cara
mengkuadratkan string lalu mengambil tengah nya untuk menjadi key.
Contoh: terdapat nilai 675248 maka akan di kuadratkan terlebih dahulu, kemudian diambil tengahnya.
675248->455959861504-> 959861(hash keynya)
Mendapatkan hash key dengan cara memodulus
stringnya. Hasil modulusnya adalah hash key.
Contoh:
asumsikan ukuran tabel = 11 dan satu file dengan 8 record
menggunakan nilai kunci sebagai berikut : 12,21,68,38,52,70,44,18.
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
Mendapatkan hash key dengan cara mempartisi
string menjadi beberapa bagian lalu menjumlahkannya (tanpa carry).
Contoh :
Kunci 123456, 234351, 222456 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
Maka :
123+654 = 777 ; simpan 123456 dilokasi 777
234+153 = 387 ; simpan 234351 dilokasi 387
222+654 = 876 ; simpan 222456 dilokasi 876
4. Digit Extraction
Mendapatkan hash key dengan cara mengambil
digit-digit tertentu dari sebuah string untuk dijadikan
hash keynya.
Contoh: terdapat string yaitu 123456
jika kita mengambil digit ke-1 , ke-4 dan ke-6 maka hash keynya adalah 146
5. Rotating hash
Mendapatkan hash key dengan cara merotasikan
hash key yang didapatkan dengan function-function diatas.
Contoh: terdapat hashkey 146 dari digit extraction tadi maka rotating hash akan merotate hash key tersebut menjadi 641.
Collision
Collision adalah ketika beberapa string memiliki hash key
yang sama. Untuk menyelesaikannya terdapat 2 teknik yaitu Linear Probing dan
Chaining.
1. Linear Probing
Menyelesaikan collision dengan mencari slot
yang kosong di array lalu menyimpan string tersebut disana.
Pada
contoh dibawah ceil dan char memiliki hash key sama sehingga saat mau
menyimpan ceil sudah terdapat char di h[2] oleh karena itu ceil
dimasukkan ke tempat yg kosong yaitu h[6].
Menyelesaikan collison dengan cara menaruh string tersebut sebagai chained list/linked list dari slot hash key yang sama.
Pada contoh dibawah acos dan atan memiliki hash key yang sama sehingga saat mau menyimpan acos di h[0] terdapat atan. Jadi dibuatlah linked list dari atan yang menunjuk pada acos.
Binary Tree
Binary tree adalah sebuah data structure tree yang setiap
node nya memiliki paling banyak 2 child.
Node yang tidak memiliki child disebut leaf.
Jenis-jenis Binary
Tree
1. Perfect Binary Tree
Binary tree dimana setiap level berada di
depth yang sama.
2. Complete Binary TreeBinary tree dimana semua level kecuali yang terakhir terisi penuh dan semua node berada di kiri. Sebuah perfect binary tree adalah complete binary tree.
Binary tree dimana semua node memiliki
paling banyak 1 child.
Binary tree dimana tidak ada leaf yang paling
jauh dari root dari semua leaf.
Sifat-sifat binary
tree
1. Jumlah node maksimal dalam sebuah level adalah
2^level;
2. Jumlah node maksimal dalam sebuah binary tree
adalah 2height+1 – 1
3. Height dari sebuah tree adalah jumlah level atau
level tertinggi di tree tersebut.
4. Minimum height tree yang memiliki n nodes adalah
2log(n).
5. Maximum height tree yang memiliki n nodes adalah
n - 1.
Berikut adalah gambaran binary tree untuk mempermudah:
Source code Binary tree:
struct node {
struct node {
int data;
struct node *left; //Pointer mengarah ke child leftnya
struct node *right; //Pointer mengarah ke child rightnya
struct node *parent; //Pointer mengarah ke parentnya
};
struct node
*root = NULL;Expression Tree
Expression tree adalah binary tree dimana setiap node internal adalah operator dan node leaf adalah operand.
Contoh Expression tree dari 3 + ((5+9)*2)
1. Infix (InOrder Traversal) adalah notasi yang membentuk atas operator dengan operand,dimana operator berada diantara operand. Contoh Infix diatas: 3+(5+9)*2
2. Prefix (Preorder Traversal) adalah notasi yang terbentuk atas operator dengan operand, dimana operator didepan operand. Contoh Prefix diatas: +3*+592
3. Postfix (Postorder Traversal) adalah notasi yang membentuk atas operator dengan operand, dimana operator berada dibelakang operand. Contoh Postfix diatas adalah 3+59+2*
Binary Search Tree
Binary
Search tree adalah data structure Binary Tree yang sudah di sort sehingga
mendukung searching yang lebih cepat dan juga insertion dan deletion yang lebih
mudah.
Diatas adalah contoh binary search tree. Dapat dilihat
binary search tree sudah di sort. Elemen di kiri selalu yang lebih kecil dan
elemen yang dikanan selalu lebih besar.
Dalam binary search tree terdapat 3 operasi dasar yaitu:
1. Find atau Search: yaitu mencari sebuah elemen
dalam binary search tree
2. Insert atau Push: Yaitu memasukkan sebuah elemen
ke dalam binary search tree.
3. Remove atau Pop: yaitu menghapus sebuah elemen
dalam binary search tree.
Operasi Find:
Karena Binary search tree sudah di sort maka pencarian sebuah elemen menjadi lebih mudah dan cepat.
Karena Binary search tree sudah di sort maka pencarian sebuah elemen menjadi lebih mudah dan cepat.
Langkah-langkah operasi Find:
1. Operasi find dimulai dari node berada di akar
binary search tree
2. Lalu memeriksa apakah elemen pada node adalah
elemen yang dicari, jika iya maka operasI
find berakhir jika tidak maka akan
lanjut ke langkah berikutnya.
3. Jika elemen lebih kecil dari pada elemen pada
node maka akan mencari secara rekursif pada
subtree bagian kiri. Jika elemen
lebih besar maka akan mencari secara rekursif pada subtree
bagian kanan.
Operasi Insert:
Insert pada binary search tree dilakukan secara rekursif
karena insert elemen baru yang lebih kecil harus dikiri dan harus kosong
nodenya sedangkan yang lebih besar harus di kanan dan juga harus kosong.
Langkah-langkah operasi Insert:
1. Operasi Insert dimulai dari node berada di akar
binary search tree
2. Jika elemen yang ingin dimasukkan lebih kecil
daripada elemen pada node maka nodeakan
ke subtree kiri secara rekursif, jika
lebih besar maka node akan ke subtree kanan secara
rekursif.
3. Hal tersebut dilakukan sampai menemukan node
yang kosong. Lalu memasukkan elemennya
disana.
Berikut adalah ilustrasi insert pada Binary Search Tree
Insert 1
Insert 2
Insert 3
Insert 4
Insert 1: Node dimulai dari akar karena elemen yang ingin
dimasukkan lebih besar maka ke subtree kanan.
Insert 2: Karena
node yang sekarang elemennya lebih besar dari pada elemen yang ingin dimasukkan
maka ke subtree kiri.
Insert 3: Karena
node yang sekarang elemennya lebih kecil dari pada elemen yang ingin dimasukkan
maka ke subtree kanan.
Insert 4: Karena
nodenya kosong maka dimasukkan disana elemennya.
Operasi Delete:
Delete pada binary search tree terdapat 3 kasus yaitu:
J 1. Jika node yang ingin didelete adalah daun dari
binary search tree tersebut. Maka bisa langsung didelete.
2. Jika node yang ingin didelete memiliki 1 child
maka child tersebut harus dihubungkan ke
pada parent node yang ingin didelete.
Lalu baru mengdelete node tersebut.
3. Jika node
yang ingin didelete memiliki 2 child maka kita harus mencari elemen terbesar
pada
subtree kiri atau elemen terkecil pada subtree kanan (yang akan kita akan
sebut elemen X)
lalu mengantikan elemen node yang ingin didelete tersebut
dengan elemen X dan menghapus
node X.
Berikut adalah ilustrasi Delete pada binary search tree
Delete 1
Delete 2
Delete 1: Node
yang ingin didelete memiliki 2 child maka pada kasus tersebut ia memilih elemen
terbesar pada subtree kiri (elemen X).
Delete 2: Lalu
node yang ingin didelete diberikan elemen X kemudian Node X dihapus
No comments:
Post a Comment