Single Linked List Circular
Single Linked List Circular adalah Single Linked List yang pointer selanjutnya menunjuk ke dirinya sendiri. Jika terdiri dari beberapa node, maka pointer next pada node terakhir akan menunjuk ke pointer terdepan.
Single : artinya field pointer-nya hanya satu buah saja dan satu arah.
Circular : artinya pointer next-nya akan menunjuk ke dirinya sendiri sehingga akan membuat sebuah sirkuit atau sirkular
Ilustrasi
- Setiap node pada linked list mempunyai field yang berisi pointer ke node berikutnya yang juga memiliki field yang berisi data
- Pada akhir linked list, node terakhir akan menunjuk ke node terdepan sehingga linked list tersebut berputar. Node terakhir akan menunjuk lagi ke head.
Rangkaian Single Linked List tersebut diawali dengan sebuah head untuk menyimpan alamat awal dan diakhiri dengan node yang mengarah ke pointer null yang akan menunjuk ke salah satu node kembali.
Double Linked List
Pengertian Double Linked List adalah sekumpulan node data yang terurut linear atau sekuensial dengan dua buah pointer yaitu next dan prev. Dimana pointer next menunjuk ke node setelah dan node prev menunjuk ke node.
Pointer pembantu di dalam Double Linked List adalah head dan tail. Pointer ini akan digunakan dalam menunjuk elemen lain.
Property of Binary Tree
Untuk node x = 8
Ilustrasi
Pointer head akan menunjuk pada node pertama di dalam linked list dan pointer tail akan menunjuk pada node paling akhir di dalam linked list. Sebuah linked list dikatakan kosong apabila isi pointer head-nya adalah NULL. Pointer prev dari head akan selalu menunjuk NULL karena merupakan data pertama. Begitu pula dengan pointer next dari tail yang akan selalu NULL sebagai penanda data terakhir.
Beberapa operasi yang biasanya ada di dalam sebuah double linked list di antara lain :
1 1) Push
Push merupakan operasi sebuah insert dimana di dalam linked list akan terdapat tiga jenis insert, yaitu insert melalui depan (pushDepan), insert melalui belakang (pushBelakang), ataupun insert melalui mid atau tengah dari linked list (pushTengah). Operasi pushDepan berarti data yang paling baru dimasukkan akan berada di depan data lainnya dan pushBelakang berarti sebaliknya, dimana data yang paling baru dimasukkan akan berada di belakang data lainnya.
Representasinya :
o pushDepan : 3,6,7,10 maka hasilnya adalah 10,7,6,3
o pushBelakang : 3,6,7,10 maka hasilnya adalah 3,6,7,10.
Push Depan
void pushHead(int age, char name[]){
//membuat blok data baru
current = (struct human *)malloc(sizeof human);
//mengisi data
strcpy(current->name, name);
current->age=age;
//membuat penunjuk data lain menjadi NULL terlebih dahulu
current->next = current->prev=NULL;
//jika tidak ada data
if(head==NULL){
//maka akan jadi data pertama, head dan tail akan sama dengan data baru
head=tail=current;
//jika ada data
}else{
//pergantian head menjadi data terbaru
head->prev=current;
current->next=head;
head=current;
}
}
Push Belakang
void pushTail(int age, char name[]){
//membuat blok data baru
current = (struct human *)malloc(sizeof human);
//mengisi data
strcpy(current->name, name);
current->age = age;
//membuat penunjuk data lain menjadi NULL terlebih dahulu
current->prev = current->next = NULL;
//jika tidak ada data
if(head==NULL){
//maka akan jadi data pertama, head dan tail akan sama dengan data baru
head=tail=current;
//jika ada data
}else{
//pergantian tail menjadi data terbaru
current->prev = tail;
tail->next = current;
tail = current;
}
}
Push Tengah
void PushMid(int age, char name[]){
//jika tidak ada data
if(head==NULL){
//pushHead
pushHead(age,name);
//jika umur yang akan dimasukkan lebih kecil dari umur data ke head
}else if(age < head->age){
//pushHead
pushHead(age,name);
//jika umur yang akan dimasukkan lebih kecil dari umur data ke tail
}else if(age > tail->age){
//pushTail
pushTail(age,name);
}else{
//buat blok data
current = (struct human *)malloc(sizeof human);
//mengisi data
strcpy(current->name, name);
current->age = age;
//buat penunjuk data sebelum/sesudahnya menjadi NULL terlebih dahulu
current->next = current->prev = NULL;
struct human *temp=head;
//mencari posisi dimana data akan dimasukkan
while(temp!=NULL && temp->age < current->age){
temp=temp->next;
}
//memasukkan data dan menunjuk alamat-alamat data selanjutnya/sebelumnya
current->prev=temp->prev;
current->next=temp;
temp->prev->next=current;
temp->prev=current;
}
}
22) Pop
Pop, kebalikan dari push, merupakan operasi delete, dimana di dalam linked list memiliki dua kemungkinan delete, yaitu melalui depan (popDepan) dan melalui belakang (popBelakang). PopDepan berarti data yang akan dihapus adalah data paling belakang (akhir).
Pop Head
void popHead(){
//jika tidak ada data
if(head==NULL){
printf("No Data\n");
//jika hanya ada 1 data
}else if(head==tail){
current=head;
head=tail=NULL;
free(current);
//jika lebih dari 1 data
}else{
current=head;
head=head->next;
head->prev=NULL;
free(current);
}
}
Pop Belakang
void popTail(){
//jika tidak ada data
if(head==NULL){
printf("No Data\n");
//jika hanya ada 1 data
}else if(head==tail){
current=tail;
head=tail=NULL;
free(current);
//jika lebih dari 1 data
}else{
current=tail;
tail=tail->prev;
tail->next=NULL;
free(current);
}
}
Pop Tengah
void popMid(int age){
//inisialisasi flag sebagai penanda eksistensi data
int temu=0;
//jika tidak ada data
if(head==NULL){
printf("No Data\n");
//jika ada data
}else{
current=head;
//mencari posisi data
while(current!=NULL){
//pengecekan data,jika sesuai, ubah flag dan langsung break looping
if(current->age==age){
temu=1;
break;
}
current=current->next;
}
//jika data ketemu
if(temu==1){
//jika hanya data yang ditemukan adalah Head
if(current==head){
popHead();
//jika hanya data yang ditemukan adalah Tail
}else if(current==tail){
popTail();
//jika hanya data yang ditemukan bukan Head dan bukan Tail
}else{
current->prev->next=current->next;
current->next->prev=current->prev;
free(current);
}
}else{
printf("Data Not Found\n");
}
}
}
Circular Double Linked List
Memiliki kesamaan dengan Doubly Linked List, namun jumlah pointer di setiap node berjumlah 2 (dua) pointer.
Stack
Stack adalah kumpulan elemen data yang disimpan dalam satu laju linear. Kumpulan elemen-elemen data hanya boleh diatas pada posisi atas (top) tumpukan. Tumpukan digunakan dalam parsing, evaluation, dan backtrack. Elemen-elemen di dalam tumpukan dapat bertipe integer, real, record dalam bentuk sederhana ataupun terstruktur.
Konsep utama dari stack yaitu LIFO (Last in First Out), benda yang terakhir masuk ke dalam stack akan menjadi benda pertama yang dikeluarkan dari stack. Tumpukan atau stack mempunyai istilah pop dan push. Pop adalah penambahan elemen baru ke dalam tumpukan, sedangkan Push adalah penarikan atau penghapusan elemen yang paling atas dari tumpukan. Baik penambahan elemen maupun penghapusan elemen akan selalu dilakukan pada bagian akhir data yang selalu disebut top of stack ( karena data terakhir selalu terletak di bagian atas tumpukan ).
Terdapat beberapa operasi yang sering digunakan dalam struktur data stack. Operasi yang paling umum digunakan adalah push dan pop. Beberapa operasi yang sering digunakan yaitu :
1. Push digunakan untuk menambah item pada tumpukan paling atas
2. Pop digunakan untuk mengambil item pada tumpukan paling atas
3. Clear digunakan untuk mengosongkan stack
4. Create stack digunakan untuk membuat tumpukan baru dengan jumlah elemen kosong
5. MakeNull digunakan untuk mengosongkan tumpukan dan menghapus semua elemen ( jika terdapat elemen)
6. IsEmpty untuk mengecek apakah stack sudah kosong
7. IsFull untuk mengecek apakah stack sudah penuh
Terdapat juga istilah overflow dan underflow, dimana overflow adalah keadaan dimana stack tidak bisa menampung elemen baru karena jumlah elemen sudah mencapai maksimum, sedangkan underflow adalah keadaan dimana terdapat stack kosong dan tidak ada elemen yang bisa diambil lagi.
Macam – Macam Stack
1) Stack dengan Array
Sesuai dengan sifat stack, pengambilan ataupun penghapusan elemen dalam stack harus dimulai dari elemen teratas
2) Double Stack dengan Array
Teknik khusus untuk menghemat pemakaian memori dalam pembuatan dua stack dengan array. Intinya adalah penggunaan hanya sebuah array untuk menampung dua stack
Queue
Queue merupan struktur data linear. Konsepnya hamper sama dengan stack, perbedaannya adalah operasi penambahan dan penghapusan pada ujung yang berbeda. Penghapusan dilakukan pada bagian depan (front), sedangkan penambahan dilakukan pada bagian belakang (rear). Elemen-elemen di dalam antrian dapat bertipe integer, real, record dalam bentuk sederhana atau terstruktur.
Queue juga disebut waiting line yaitu penambahan elemen baru dilakukan pada bagian belakang dan penghapusan elemn dilakukan pada bagian depan. Sistem pengaksesan queue menggunakan sistem FIFO (First in First Out), artinya elemen pertama yang masuk itu yang akan pertama dikeluarkan dari queue . Queue juga merupakan salah satu contoh dari double linked list.
Istilah yang dipakai apabila seseorang masuk ke dalam antrian disebut enqueue, sedangkan apabiala sesorang keluar dari antrian disebut dequeue
Beberapa operasi dalam queue :
§ Create Queue : membuat antrian baru Q, dengan jumlah elemen kosong
§ Make Null : mengosongkan antrian Q, dengan jumlah elemen kosong
§ Enqueue : berfungsi untuk memasukkan data baru ke belakang antrian
§ Dequeue : berfungsi untuk mengeluarkan data terdepan dari antrian
§ Clear : menghapus semua antrian
§ IsEmpty : memeriksa apakah barisan kosong
§ IsFull : memeriksa apakah barisan penuh
Hash Table
Hashing
Hashing adalah transformasi aritmatik sebuah string atau karakter menjadi nilai yang merepresentasikan string aslinya.
Hashing digunakan sebagai metode untuk menyimpan data di dalam sebuah array agar penyimpanan, penambahan, dan pencarian data dapat dilakukan dengan benar.
Hash Table
Hash table adalah table (array) dimana kita menyimpan suatu string asli, dimana index dari array adalah suatu kunci yang dienkripsi (hashed key ), namun nilainya adalah string yang asli.
Ukuran dari hash table biasanya terdiri dari berbagai macam urutan, namun biasanya lebih sedikit dari berbagai kemungkinan string. Jadi, beberapa string kemungkinan mempunyai hashed key yang sama.
Hash Function
Hashing adalah salah satu bagian penting dari data structure dimana didesain oleh suatu fungsi yang dinamakan hash function yang digunakan untuk memetakan suatu nilai dengan suatu ciri yang spesifik untuk akses elemen yang lebih cepat.
Misalkan untuk fungsi H(x) akan memetakan nilai x yang disimpan di
index x%10, maka data {11,13,15,17,19 } akan disimpan secara berturut-turut akan disimpan di index { 1,3,5,7,9 } di dalam array.
Beberapa metode untuk membuat Hash Function :
Ø Mid – Square
Ø Division
Ø Folding
Ø Digit Extraction
Ø Rotating Hash
Mid-Square
Function: h(k) = s
k = key
s = hash key yang diperoleh dari nilai tengah kuadrat k
· kuadratkan string/identifier (k), lalu kita ambil angka tengah dari kuadrat string/identifier untuk dijadikan hash key (s)
Division
Function: h(z) = z mod M
z = key
M = angka yang digunakan untuk membagi key
· ketika ingin memunculkan index dan meletakkan key di index hasil function division
Folding
· bagi key menjadi beberapa bagian
· jumlahkan bagian individualnya
Digit Extraction
· beberapa bagian digit dari key akan dijadikan hash address
· contoh :
x = 12350. Jika kita mengambil angka ke 1, 2, dan 4, maka kita akan mendapatkan hashcode : 125.
Rotating Hash
· gunakan metode apa saja, lalu urutan angka akan dibalik ( misalkan division atau mid-square )
· setelah mendapatkan hash code dari hash method, lakukan rotation
· rotation adalah dijalankan dengan menggeser digit untuk mendapatkan hash address yang baru.
· contoh :
hash address awal = 27201
hasil rotation = 10272
Collision
· ketika kita ingin menyimpan string menggunakan hash function sebelumnya ( menggunakan karakter pertama dari setiap string )
· misalkan kita ingin mendeklarasikan tipe data float, exp, char, atan, ceil, acos, floor
· maka kita akan menemukan kesamaan di tipe data float dan floor, serta tipe data char dan ceil. Ini terjadi karena kedua pasang tipe data memiliki awalan karakter yang sama, sehingga mempunyai hash key yang sama.
· disinilah terjadi collision
Ada dua solusi umum untuk mengatasi collision :
1. Linear Probing
mencari tempat selanjutnya yang kosong dan meletakkan string di tempat tersebut
2. Chaining
meletakkan string sebagai linked list
Trees and Binary Tree
Tree Introduction
· Tree adalah non-linear data structure yang merepresentasikan relasi antara objek atau data
· Beberapa tree bisa dilihat di dalam directory structure ataupun organizational hierarchies
· Node dari tree harus disimpan terus menerus dan bisa disimpan dimana saja, serta dihubungkan oleh pointer
Tree Concept
· node di posisi paling atas disebut root
· garis yang menghubungkan parent dan child disebut edge
· node yang tidak mempunyai children disebut leaf
· node yang mempunyai parent yang sama disebut sibling
· degree adalah total sub tree dari sebuah node ( jumlah descendant )
· height / depth adalah degree maksimum dari sebuah node di dalam tree
· jika ada garis yang menghubungkan p dengan q, maka p disebut ancestor dari q, serta q disebut descendant dari p
Binary Tree Concept
· binary tree adalah tree di dalam data structure yang mempunyai paling banyak dua children
· kedua children tersebut biasa disebut left child dan right child
· node yang tidak mempunyai children disebut leaf
Types of Binary Tree
· Perfect Binary Tree adalah binary tree dengan level yang berjumlah sama dengan height/depth
· Complete Binary Tree adalah binary tree dengan level yang berjumlah sama dengan height/depth, namun hampir terisi sempurna
· Skewed Binary Tree adalah binary tree yang setiap nodenya mempunyai paling banyak satu child
· Balanced Binary Tree adalah binary tree dimana tidak ada leaf yang garisnya lebih Panjang dari leaf lainnya
Property of Binary Tree
maksimum jumlah node dari level k adalah
· beberapa sumber menyebutkan bahwa level dari binary tree dimulai dari 1 (root)
· height dari sebuah tree adalah total dari level diluar dari root
· gambar di atas memiliki height sebanyak 3 ( dimana level 0 tidak dihitung karena mengandung root )
· height minimum dari binary tree dengan n node adalah
· height maksimum dari binary tree dengan n node adalah n-1
Binary Search Tree
Binary Search Tree adalah salah satu bentuk data structure yang mendukung searching secara lebih cepat, sorting lebih cepat, dan mempermudah insertion dan deletion.
Binary Search Tree juga dikenal sebagai versi sorting dari Binary Tree
Untuk node x = 8
- Elemen di sebelah kiri dari node x harus bernilai lebih kecil dari x
- Elemen di sebelah kanan dari node x harus bernilai lebih besar dari x
( dengan asumsi dimana setiap elemen / node bernilai berbeda satu dengan yang lain )
Basic Operation
- find(x) : find the key x
- insert(x) : insert new key x
- remove(x) : remove key x
Search
- karena kelebihan BST dimana searching sangat mudah dengan menggunakan BST
- misalkan kita ingin mencari x
- kita akan mulai dari root
- jika di root ditemukan nilai x ( root = x ), maka search akan dihentikan
- jika nilai x lebih kecil dari root, maka pencarian akan dilakukan secara rekursif di sub tree kiri dari root.
- Jika nilai x lebih besar dari roor, maka pencarian akan dilakukan secara rekursif di sub tree kanan dari root.
Insertion
- Insertion dilakukan secara rekursif
- Misalkan new key adalah x
- dimulai dari root
- Jika nilai x lebih kecil dari new key, maka nilai x akan dimasukkan ke daerah sub tree sebelah kiri.
- Jika nilai x lebih besar dari new key, maka nilai x akan dimasukkan ke daerah sub tree sebelah kanan.
- Dilakukan secara rekursif sampai terdapat node kosong untuk meletakkan (dimana x akan selalu menjadi new leaf )
Berikut adalah contoh insertion dimana merupakan pencarian tempat untuk node key baru.
Deletion
Terdapat tiga kondisi yang perlu dipertimbangkan :
- Jika key adalah leaf, maka node tersebut akan dihapus
- Jika key adalah node yang mempunyai satu child, maka node tersebut dihapus dan child akan dihubungkan dengan parent-nya
- Jika key adalah node yang mempunyai dua children, maka temukan
Berikut adalah contoh deletion yang merupakan penghapusan node key.
Comments
Post a Comment