Summary Data Structure


Summary of Data Structure study material for half Semester

Data Struktur  adalah format organisasi , menejemen dan penyimpanan data yang memberikan akses dan modifikasi yang lebih efisien. Struktur data adalah koleksi dari nilai data, hubungan antar data, dan fungsi dan operasi yang bisa diterapkan kedalam data. Dalam pembelajaran selama setengah semester ini struktur data yang dipelajari ada 3 bentuk yaitu Linked-list, Hash table, dan Binary Search Tree
1.      Linked-List
Linked-list adalah struktur data yang yang memberikan data tambahan berupa pointer pada setiap satuan data  untuk menunjukkan hubungan antar data. Untuk menunjukkan posisi setiap data biasanya diberi penunjuk tambahan untuk menunjukkan awal dan akhir dari kumpulan data yang biasa kita menamakannya pointer head dan tail. Untuk penunjuk pada data yang pertama atau terakhir biasa nya akan diberikan penunjuk berupa NULL(linked-list biasa) atau penunjuk ke data awalnya (circular linked-list) dikarenakan jika pointer pada data terakhir tidak diberi nilai maka pointer tersebut dapat menunjuk nilai secara sembarang yang membuat struktur data kita rusak.
Linked-List yang dipelajari ada 2 yaitu Single linked-list dan double linked-list bedanya hanya terletak pada pointer yang setiap data miliki . Jika Single linked-list memiliki satu pointer yang menunjuk ke data yang selanjut. Jika double linked-list menunjuk ke data yang sebelum dan setelahnya. Selain kedua linked list tersebut juga bisa juga linked list kita memiliki lebih dari 2 pointer contohnya untuk membuat jalur pada peta diperlukan data dengan 4 pointer untuk menunjuk ke arah mata angin. Konsep linked-list juga bisa diimplementasikan dalam bentuk struktur data stack dan queue.
Contoh kodingan Double Linked-Listed
#include<stdio.h>
#include <stdlib.h>

struct Node{
               int value;
               struct Node *next,*prev;
}*head=NULL,*tail=NULL,*curr=NULL;

struct Node* createNode(int value){
               struct Node* curr = (struct Node*) malloc (sizeof(struct Node));
               curr->value = value;
               curr->next = NULL;
               curr->prev = NULL;
               return curr;
}

void pushHead(int value){
               curr= createNode(value);
               if(head==NULL){
                              head=tail=curr;
               }
               else{
                              head->prev=curr;
                              curr->next=head;
                              head=curr;
               }
}

void pushTail(int value){
               curr = createNode(value);
               if(head==NULL){
                              head=tail=curr;
               }
               else{
                              curr->prev=tail;
                              tail->next=curr;
                              tail=curr;
               }
}

void popHead(){
               if(head==NULL){
                              return;
               }
               else if(head==tail){
                              head=tail=NULL;
               }
               else{
                              head=head->next;
                              curr=head->prev;
                              curr->next=NULL;
                              curr->prev=NULL;
                              head->prev=NULL;
                              free(curr);
               }
}

void popTail(){
               if(head==NULL){
                              return;
               }
               else if(head==tail){
                              head=tail=NULL;
               }
               else{
                              tail=tail->prev;
                              curr=tail->next;
                              curr->next=NULL;
                              curr->prev=NULL;
                              tail->next=NULL;
                              free(curr);
               }
}

void print(){
               curr=head;
               if(curr==NULL){
                              printf("no Node");
               }
               while(curr!=NULL){
                              printf("%d ",curr->value);
                              curr=curr->next;
               }
}


2.      Hash-Table
Data Struktur yang berbentuk seperti tabel. Penempatan data pada setiap sel tabel memiliki fungsinya tersendiri. Suatu data pasti memiliki property yang bisa dijadikan key untuk penempatan data. Proses mengambil key yang terdapat pada data disebut hashing. Setiap data menempati tempat yang unik pada hash table. Jika data dalam hash table mempunyai key yang sama itu disebut data collision dimana data tersebut memiliki nilai key yang sama cara mengatasinya adalah dengan linear probing yaitu menempatkan data pada baris selanjutnya dari tabel yang kosong atau  dengan chaining yaitu membuat linked list lagi didalam sel tabel sehingga penambahan data lebih dinamis dan tidak kehabisan tempat.
Untuk kodingan Hash Table silahkan kunjungi ; https://william081.blogspot.com/2020/03/hash-table.html
3.      Binary Search Tree
Data struktur yang berbentuk seperti pohon pada matematika. Properti yang dimiliki BST ini pada umumnya adalah:
a.      Subtree bagian kiri memiliki data yang key-nya kurang dari key data sebelumnya.
b.      Subtree bagian kanan memiliki  data yang key-nya lebih dari key data sebelumnya
c.      Subtree bagian kanan dan kiri juga harus memiliki propertinya yang sama dengan data diatasnya sehingga membentuk binary search tree.
Untuk kodingan Binary Search Tree silahkan kunjungi: https://william081.blogspot.com/2020/03/binary-search-tree-bst.html



Komentar

Posting Komentar

Postingan populer dari blog ini

Heap

Heap dibagi 2 yaitu max heap(elemen anak dari node lebih kecil) dan min heap (elemen anak dari node lebih besar) . Heap bisa diimplementasi dengan menggunakan array. Penggunaan heap bisa dalam selection algorithm, Djikstra’s algorithm dan Prim algorithm. Untuk sorting juga ada Heap Sort. Elemen dari heap disimpan secara sekuensial dalam array dari atas ke bawah, kiri ke kanan. Root selalu ditempatkan di index ke 1 untuk memudahkan perhitungan. Cara menentukan node relasi dari node x. Parent= x/2, left-child = 2 * x, right-child = 2*x+1. Insert dalam Min-Heap 1.       Taruh node pada index terahir dari array 2.       Upheap node tersebut untuk memperbaiki property heap *Upheap : mencari elemen atas nya, jika elemen parentnya lebih besar maka elemen tersebut akan ditukar. Proses ini terjadi secara rekursif sampai kondisi tidak memenuhi(mencapai root atau elemen parent lebih kecil). Delete dalam Min-Heap 1.   ...
Baca selengkapnya

Hash Table

1. Hash Table •  Hashing adalah teknik yang digunkan untuk menyimpan dan mengambil kunci dalam jangka waktu  yang cepat.  •  Dalam hashing, sebuah data misalnya string dapat diambil bagiannya(karakter) kemudian dijadikan key untuk disimpan pada table •  Hashing menggunakan indek untuk mengambil data pada penyimpanan untuk mempercepat pencaharian menggunakan hashed yang lebih pendek daripada nilai yang sebenarnya(lebih panjang). •  Hashing juga bisa disebut konsep mendistribusikan indeks kedalam sebuah  hash table menggunakan fungsi yang disebut  hash function . 2. Hash Function Ada banyak cara hashing string menjadi key. - Mid-Square - Division - Digit Extraction - Rotating Hash -Mid-Square     Key yang didapat dikudratkan kemudian diambil bagian tengah dari key     contohnya: key 3121 di kuadratkan menjadi 9740641 sehingga diambil bagian tengahnya 406    Penggunaan kuadrat agar address y...
Baca selengkapnya

Binary Search Tree (BST)

Struktur data binary search tree memberikan fitur searching dan sorting yang lebih cepat. insert dan delete yang lebih mudah juga.  Aturan penempatan node :  1. Untuk node yang lebih kecil dari node yang dibandingkan maka node tersebut ditempatkan dikiri 2. Untuk node yang lebih besar dari node yang dibandingkan maka node tersebut ditempatkan dikanan 3. Setiap node nilainya berbeda 4. Perbandingan mulai dari root, terus turun sampai dapat tempat kosong Operasi pada BST 1. search(x) 2. insert(x) 3. remove(x) 1. Search Misalnya nilai yang mau kita cari adalah x  - Mulai dari root  - Jika root mengandung x maka proses selesai  - Jika x < nilai root cari secara rekursif pada subtree kiri, Jika tidak maka cari  secara rekursif pada subtree kanan 2. Insert  Misalnya nilai yang ingin kita masukkan adalah x  - Proses mulai dari root  -  Jika x < nilai root cari secara rekursif pada subtree kiri, Jika tidak maka cari...
Baca selengkapnya