Rangkuman

Rangkuman
Hawinurtama Auliyah-2301925513

Linked list
adalah stuktur data linier dimana adalah koleksi data element juga dikenal sebagai nodes dan dapat memiliki variasi ukuran/sizes. biasanya, item/barang yang terdaftar terkoneksi melalui pointer dimana diketahui sebagai link dan dikurung ini disebut sebagai linked list. Biasanya terdapat istilah head dan tail.

Head = elemen yang berada pada posisi pertama dalam suatu linked list
Tail = elemen yang berada pada posisi terakhir dalam suatu linked list

Macam- macam linked list :
1. Single Linked List
2. Double Linked List
3. Circular Linked List
4. Multiple Linked List

Single Linked List
Single Linked List merupakan suatu linked list yang hanya memiliki satu variabel pointer saja. Dimana pointer tersebut menunjuk ke node selanjutnya. Biasanya field pada tail menunjuk ke null.

contoh kodingannya :
Struct Students{
     char nama[100];
     char nim[100];
     char id[100];
     float ipk;
     struct students *next;
}*head,*tail;

Double Linked List
Double Linked List merupakan suatu linked list yang memiliki dua variabel pointer yaitu pointer yang menunjuk ke node selanjutnya dan pointer yang menunjuk ke node sebelumnya. Setiap head dan tailnya juga menunjuk ke null.

contoh kodingannya :
Struct Students{
     char nama[100];
     char nim[100];
     char id[100];
     float ipk;
     struct students *next,*prev;
}*head,*tail;

Dapat disimpulkan, perbedaan dari Single Linked List dan Double Linked List yaitu, Single Linked list yakni linked ist dengan sebuat pointer terhubung. Sedangkan Double Linked List yakni linked list dengan 2 pointer penunjuk, yaitu ke arah node sebelum(prev) dan node sesudah (next).

Circular Linked List

Circular Linked List merupakan suatu linked list dimana tail (node terakhir) menunjuk ke head (node pertama). Jadi tidak ada pointer yang menunjuk NULL. Ada 2 jenis Circular Linked List, yaitu :

- Circular Linked List

-Circular Double Linked List

Insert dan delete dalam double linked list

Push merupakan operasi insert, terdapat 2 macam yaitu pushDepan dan pushBelakang.

Contoh pushDepan :

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;

}

}

Contoh pushBelakang :

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;

}

}

Pop merupakan operasi delete, terdapat 2 macam yaitu PopDepan dan PopBelakang

Contoh PopDepan :

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

}

}

Contoh PopBelakang : 

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

}

}

Stack dan Queue

Stack adalah struktur data penting yang menyimpan elemen-elemennya secara teratur. Data disimpan di Last In First Out(LIFO). Stack bisa diimplementasikan dengan menggunakan array atau linked list.

Operasi-operasi pada stack dengan Single Linked List :
Push = yaitu memasukkan elemen baru ke dalam stack
       Contoh penggunaan operasi Push : 

void pushHead(char name[]){
 current = (struct book *)malloc(sizeof book);
 strcpy(current->studentname, name);
 current->next = current->prev = NULL;

 if(head==NULL){
  head=tail=current;
 }else{
  head->prev=current;
  current->next=head;
  head=current;
 }

Pop  =  yaitu menghapus elemen teratas dari stack
        Contoh penggunaan operasi Pop : 

void popHead(){
 if(head==NULL){
  printf("No Data");
 }else if(head==tail){
  current=head;
  head=tail=NULL;
  free(current);
 }else{
  current=head;
  head=head->next;
  head->prev=NULL;
  free(current);
 }
}

Top  = biasa disebut juga dengan peek. Yaitu melihat data paling atas dari stack
      Contoh penggunaan operasi Top : 

public void peek()

System.out.print("Posisi Atas= ");

if(posisi != 0)

System.out.print(isistack[posisi]);

System.out.println();

Queue dalah struktur data penting yang menyimpan elemen-elemennya secara teratur. Data disimpan di Fast In First Out(FIFO).

Operasi-operasi pada Stack : 

push = untuk menambah item ke belakang dari queue

     contoh penggunannya : 

void enqueue(int x)

{

if ((antrian.HEAD == 0) && (antrian.TAIL == 0))

{

antrian.HEAD = 1;

antrian.TAIL = 1;

}

else

{

antrian.TAIL = antrian.TAIL + 1;

}

antrian.data[antrian.TAIL] = x;

}

pop = untuk menghapus salah satu item dari depan queue tsb

     contoh penggunannya : 

void Dequeue(){

if (q.head > q.tail) {

q.head = 0;

q.tail = 0;

}

q.head = q.head + 1;

}

front = untuk mengembalikan item paling depan dari queue

    contoh penggunannya : 

 int peekQueue(){

      return front->data;

}

Hashing and Hash Table
Tabel hash adalah tabel tempat kita menyimpan string asli. Indeks tabel adalah kunci hash, sementara nilainya adalah string asli. Ukuran tabel hash biasanya beberapa kali lipat lebih rendah dari jumlah total string yang mungkin Jadi, beberapa string mungkin memiliki kunci yang sama.

Contoh :
kita mempunyai 3 string dengan isi "nama","jurusan",dan "idsiswa" dengan size 20. Maka, fungsi hash yang akan kita gunakan adalah mengubah karakter pertama dari setiap string menjadi angka antara 0..19.


h[ ]

Value


0

idsiswa


1




2

jurusan


3




4
nama
sampai size 19




maka, idsiswa disimpan di h[0] karena i terdapat di index 0.

jurusan disimpan di h[2] karena j terdapat di index 2, dan seterusnya.

Fungsi Hash yang biasa digunakan : 

1. Division



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.

2. Mid-Square
adalah teknik hashing di mana kunci unik dihasilkan. Dalam teknik ini, nilai benih diambil dan dikuadratkan. Kemudian, beberapa digit dari tengah diekstraksi. Angka-angka yang diekstrak ini membentuk angka yang diambil sebagai benih baru. Teknik ini dapat menghasilkan kunci dengan keacakan tinggi jika nilai benih yang cukup besar diambil. Namun, itu memiliki batasan. Saat bijinya dikuadratkan, jika angka 6-digit diambil, maka persegi akan memiliki 12-digit. Ini melebihi kisaran tipe data int. Jadi, overflow harus diurus.

3. 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).



Tree dan Binary Tree




Tree merupakan kumpulan dari satu node atau lebih. 

Di dalam Tree terdapat : 


Prodecessor : node yang berada diatas node tertentu.
Successor : node yang berada di bawah node tertentu.
Ancestor : seluruh node yang terletak sebelum node tertentu dan terletak pada jalur yang sama.
Descendant : seluruh node yang terletak sesudah node tertentu dan terletak pada jalur yang sama.
Parent : predecssor satu level di atas suatu node.
Child : successor satu level di bawah suatu node.
Sibling : node-node yang memiliki parent yang sama dengan suatu node.
Subtree : bagian dari tree yang berupa suatu node beserta descendantnya dan memiliki semua karakteristik dari tree tersebut.
Size : banyaknya node dalam suatu tree.
Height : banyaknya tingkatan/level dalam suatu tree.
Root : satu-satunya node khusus dalam tree yang tak punya predecssor.
Leaf : node-node dalam tree yang tak memiliki seccessor.
Degree : banyaknya child yang dimiliki suatu node


Binary Tree merupakan struktur data potoh yang di rootnya memiliki paling banyak dua child.





contoh implementasi binary tree 


#include <stdio.h>

#include <malloc.h>

 

struct node {

    struct node * left;

    char data;

    struct node * right;

};

 

struct node *constructTree( int );

void inorder(struct node *);

 

char array[ ] = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', '\0', '\0', 'H' };

int leftcount[ ] = {  1,   3,   5,   -1,   9,  -1,  -1,   -1,   -1,  -1 };

int rightcount[ ] = {  2,   4,   6,   -1,  -1,  -1,  -1,   -1,   -1,  -1 };

 

void main() {

    struct node *root;

    root = constructTree( 0 );

    printf("In-order Traversal: \n");

    inorder(root);

}

 

struct node * constructTree( int index ) {

    struct node *temp = NULL;

    if (index != -1) {

        temp = (struct node *)malloc( sizeof ( struct node ) );

        temp->left = constructTree( leftcount[index] );

        temp->data = array[index];

        temp->right = constructTree( rightcount[index] );

    }

    return temp;

}

 

void inorder( struct node *root ) {

    if (root != NULL) {

        inorder(root->left);

        printf("%c\t", root->data);

        inorder(root->right);

    }

}






Binary Search Tree

Binary Search Tree adalah salah satu struktur data yang membantu pencarian, sorting lebih cepat. Serta penyisipan dan penghapusan yang mudah. Unruk node BST, bagian sub tree kiri  x berisi elemen yang lebih kecil daripada yang disimpan dalam x. Unuk baagian sub tree kanan x berisi elemen yang lebih besar daripada yang disimpan di dalam x.

Operasi-operasi yang dapat digunakan di dalam BST

- Create : Membentuk binary tree
- Clear : Mengosongkan binary tree
- Insert : Memasukkan sebuah node ke dalam tree
- Find : Mencari suatu node
- Update : Memperbarui isi dari node


Insert BST 
= Penyisipan sebuah node baru, didahului dengan operasi pencarian posisi yang sesuai. Dalam hal ini, node baru tersebut akan menjadi leaf.

Delete BST
= Operasi delete memiliki 3 kemungkinan :



-   Delete terhadap node tanpa anak/child (leaf/daun) : node dapat langsung dihapus

-     Delete terhadap node dengan satu anak/child : maka node anak akan menggantikan posisinya.

-   Delete terhadap node dengan dua anak/child : maka node akan digantikan oleh node paling kiri dari Sub Tree Kanan atau dapat juga digantikan oleh anak paling kanan dari Sub Tree Kiri.




AVL TREE

AVL Tree adalah Binary Search Tree yang memiliki perbedaan tinggi/ level maksimal 1 antara subtree kiri dan subtree kanan. AVL Tree muncul untuk menyeimbangkan Binary Search Tree.

Ketinggian subtree kosong adalah 0. Tinggi daun adalah 1. Ketinggian simpul internal adalah ketinggian maksimum anak-anaknya ditambah 1. Faktor keseimbangan semua node di pohon AVL harus paling banyak 1. 

Operasi pada AVL :
- insertion 



insert node baru pada bst, dimana node baru diposisikan sebagai leaf. Setelah itu, dilakukan penyeimbangan pada path dari node yang baru diinsert.









- deletion

node yang dihapus digantikan oleh node terbesar pada subtree kiri atau node terkecil pada subtree kanan.















Selain itu, terdapat single rotation dan double rotation. Single rotation merupakan rotasi sekali left ke left atau right ke right. Sedangkan double rotation merupakan dua kali rotasi dengan left-right ataupun sebaliknya.




Heaps and Tries

Heap merupakan struktur data berbasis pohon biner lengkap yang memenuhi properti heap. Heap dapat diimplementasikan dengan menggunakan linked-list, tetapi lebih mudah untuk menggunakan array. Heap dibagi menjadi dua macam yaitu :

-Max Heap
yang dimana node rootnya memiliki nilai paling besar di antara semua childrennya.
contoh max heap :



-Min Heap
yaitu node rootnya memiliki nilai paling kecil di antara semua childrennya.
contoh min heap :







insertion and deletion in Heap




deletion di heap merupakan penghapusan pada simpul root. Jika itu max heap maka yang dihapus adalah node yang mempunyai nilai paling besar. Sedangkan deletion di min heap adalah penghapusan node yang memiliki nilai paling kecil.



untuk insertion dalam heap, yaitu dengan :

1. menambahkan elemen baru di akhir array

2. lalu membandingkan nilai node tersebut dengan nilai parent, jika mereka salah urutan tukar mereka.



Tries adalah dtruktur data yang digunakan untuk menyimpan array asosiatif. tries adalah struktur data yang simpulnya menyimpan huruf-huruf alfabet.