Pre-UTS Summary Semester 2

Rangkuman Pertemuan Kelas Besar Data Struktur

Semester 2 Pre UTS

Pengertian Linked List

Linked list merupakan suatu struktur data linear, namun linear disni tidak secara harafiah mengartikan data yang disusun secara linear seperti array, melainkan sebuah struktur data dimana satu data mengacu ke data lainnya secara berurut. Linked list merupakan koleksi nodes yang mengacu pada nodes lainnya dan dapat membentuk sekuensial tanpa batas. Berbeda dengan array yang slotnya harus dibooking terlebih dahulu dan melimit isi dari array tersebut, linked list merupakan struktur data yang membooking sebuah slot hanya ketika diperlukan sehingga tidak membuang-buang tempat dan data yang dimasukkan bisa saja tidak terbatas, maka dari itu array sering disebut sebagai struktur data statis sedangkan linked list merupakan struktur data dinamis.

Single Linear Linked List

Single linear linked list merupakan jenis linked list yang paling sederhana. Setiap node memiliki pointer yang menunjuk ke node berikutnya sehingga terbentuk satu untaian linear yang terus berlanjut.

Double Linear Linked List

Salah satu kelemahan single linear linked list adalah pointer yang hanya dapat bergerak satu arah saja, sehingga pencarian data pada single linear linked list hanya dapat bergerak dalam satu arah saja. Double linear linked list merupakan jenis linked list yang memiliki 2 buah pointer, yaitu pointer terhadap elemen selanjutnya dan juga pointer terhadap elemen sebelumnya sehingga pointer bisa bergerak maju maupun mundur secara efisien.

Single Circular Linked List

Sama halnya dengan single linear linked list, single circular linked list merupakan jenis linked list yang memiliki 1 buah pointer terhadap node selanjutnya, namun pada linked list jenis ini node terakhir pada list memiliki pointer menuju node pertama dari list tersebut (tail bertemu head), sehingga terjadi susunan elemen yang melingkar dan tidak ada elemen yang bernilai null.

Double Circular Linked List

Sama seperti double linear linked list, double circular linked list merupakan jenis linked list yang memiliki 2 buah pointer terhadap node selanjutnya dan sebelumnya dan pointer bisa bergerak maju ataupun mundur, namun pada linked list jenis ini node terakhir pada list memiliki pointer menuju node pertama dari list tersebut (tail bertemu head)

, sehingga terjadi susunan elemen yang melingkar dari dua arah dan tidak ada elemen yang bernilai null.

Stacks

Stacks merupakan sebuah struktur data berbentuk tumpukan yang hanya bisa dioperasikan dari salah satu sisi (biasanya dari head atau top) dan mengikuti aturan LIFO (Last In First Out), yang artinya data yang masuk terakhir akan dioperasikan atau keluar duluan. Memasukkan data kedalam Stacks disebut PUSH dan mengeluarkan data disebut POP. Contoh nyata sehari-hari implementasi Stacks adalah tombol Ctrl + Z atau undo di PC.

Queue

Queue merupakan sebuah struktur data berbentuk antrian yang memiliki awal dan akhir (biasanya disebut front dan back) dimana Front biasa merupakan awal antrian yang dioperasikan terlebih dahulu, dan Back merupakan penambah antrian yang dioperasikan sesuai urutannya. Oleh karena itu, Queue berkebalikan dengan Stacks mengikuti aturan FIFO (First In First Out), yang artinya data yang masuk duluan akan dioperasikan sesuai urutannya. Sama seperti Stacks, memasukkan data kedalam Queue juga disebut PUSH dan mengeluarkan data disebut POP. Contoh nyata sehari-hari implementasi Queue adalah antrian pada bank.

Circular Queue

Queue yang awal dan akhirnya bertemu dan seolah-olah membentuk sebuah lingkaran dinamakan CIrcular Queue. Struktur data jenis ini bisa mengakali "kelemahan" menggunakan sebuah array sebagai dasar implementasi Queue, karena pada sebuah array ada limit data yang di input sehingga data yang dapat ditampung pasti akan mencapai limitnya. Dengan menggunakan Circular Queue, limit tersebut bisa diakali dengan mempertemukan Front dan Back dari Queue dan mengoverwrite data yang telah di POP.

Apa itu Hash Table?

Hash Table merupakan sebuah struktur data yang menyimpan data secara asosiatif dan berupa sebuah array, dimana setiap data memiliki indexnya masing-masing. Index sangatlah penting, karena dengan mengetahui index sebuah data, kita bisa mengakses data dengan lebih cepat. Maka dari itu, sangatlah mudah untuk memasukkan ataupun mencari sebuah data dalam Hash Table tanpa memperdulikan banyaknya data dalam array tersebut.

Hashing

Hashing merupakan teknik yang digunakan untuk memasukkan dan mencari data dengan cepat, dan biasanya data yang dicari diubaha kedalam kode yang lebih pendek dan mudah dicari bersamaan dengan indexnya. Hashing juga merupakan teknik mendasar dalam blockchain dan masih digunakan dalam teknologi sekarang karena hashing merupakan salah satu teknik yang paling mudah dipelajari oleh pemula dan efektif untuk melakukan blockchain. Konsep mendasar dari hashing dan hash table sendiri jugalah penting, maka dari itu banyak yang masih menggunakan hashing dalam block chain.

Tree

Tree merupakan sebuah struktur data non liner yang melambangkan hubungan hirarki antar objek data yang satu dengan lainnya. Nodes dalam tree sangatlah dinamis dan bisa disimpan maupun dihubungkan dengan menggunakan linked list.

Binary Tree

Binary Tree merupakan sebuah tree yang memiliki paling banyak hanya 2 cabang atau anak. Biasanya dinamai "right" dan "left". Sebuah node yang tidak memiliki cabang atau anakan disebut leaf.

Jenis-jenis Binary Tree:

- PERFECT / FULL Binary Tree merupakan sebuah binary tree dimana semua childnya berada di level atau kedalaman yang sama.

- COMPLETE Binary Tree merupakan sebuah binary tree dimana semua child yang paling bawah berada di sebelah kiri.

- SKEWED / DEGENERATE Binary Tree merupakan sebuah binary tree yang hanya memiliki 1 cabang atau anak per node.

- BALANCED Binary Tree merupakan sebuah binary tree dimana semua leafnya tidak ada yang lebih jauh satu sama lain dari rootnya (seimbang).

Binary Search Tree

Binary Search Tree merupakan sebuah binary tree dalam struktur data dimana node subtree bagian kiri hanya tersusun dari nodes yang besarnya masing-masing kurang dari parent nodenya, dan subtree bagian kanannya hanya tersusun dari nodes yang besarnya masing-masing lebih dari parent nodenya. Masing-masing subtree bagian kiri dan kanan harus merupakan binary tree juga yang artinya hanya memiliki 2 cabang atau keturunan.

Dalam binary search tree, terdapat 3 operasi mendasar:

1. Search

Ketika kita ingin mencari suatu nilai dalam binary sarch tree, kita selalu memulai dari root. Jika data yang diinginkan kurang dari key value rootnya, maka kita cari hanya di bagian kiri subtreenya. Jika lebih besar maka kita cari di bagian kanan subtree.

Whenever an element is to be searched, start searching from the root node. Then if the data is less than the key value, search for the element in the left subtree. Otherwise, search for the element in the right subtree. Follow the same algorithm for each node.

2. Insert

Ketika kita ingin memasukkan data baru dalam tree, pertama kita mulai dari rootnya. JIka data lebih kecil dari root maka carilah bagian atau cabang kosong di subtree kiri, jika data lebih besar maka masukkan di bagian kanan.

3. Delete

Untuk mendelete sebuah data dalam binary search tree, ada 3 kondisi yang perlu dipertimbangkan:

a. Jika data yang ingin dihapus merupakan leaf, maka langsung hapus data tersebut.

b. Jika data memiliki 1 cabang atau anak, maka hapus data dan hubungkan anak dari data yang dihapus ke parent node data yang dihapus.

c. Jika data memiliki 2 cabang atau anak, cari cabang paling kanan data tersebut dan gantikan dengan data yang ingin dihapus, kemudian hapus data tersebut.

Credits to:

https://www.tutorialspoint.com/data_structures_algorithms/binary_search_tree.htm

https://www.programiz.com/dsa/binary-search-tree

https://www.tutorialspoint.com/data_structures_algorithms/hash_data_structure.htm

https://www.geeksforgeeks.org/difference-between-stack-and-queue-data-structures/

https://www.tutorialspoint.com/data_structures_algorithms/dsa_queue.htm

https://www.tutorialspoint.com/data_structures_algorithms/stack_algorithm.htm

https://www.academia.edu/32350910/MAKALAH_STRUKTUR_DATA_VARIASI_LINKED_LIST

https://en.wikipedia.org/wiki/Linked_list

https://www.tutorialspoint.com/data_structures_algorithms/linked_list_algorithms.htm

https://www.tutorialspoint.com/data_structures_algorithms/doubly_linked_list_algorithm.htm

https://www.tutorialspoint.com/data_structures_algorithms/circular_linked_list_algorithm.htm

http://apriliyatiwen.blogspot.com/2013/04/linked-list.html

Dreamer's Market Code

#include<stdio.h> #include<stdlib.h> #include<string.h> #include<ctype.h> struct data{ char produk[31]; int qty; int price; struct data *next; struct data *prev; }*head = NULL, *tail = NULL; void push(char produk[31], int qty, int price){ struct data *node = (struct data*) malloc(sizeof(struct data)); struct data *curr = head; strcpy(node->produk, produk); node->qty = qty; node->price = price; node->next = NULL; node->prev = NULL; if (head == NULL){ head = tail = node; } else if (strcmp(produk, head->produk) <= -1){ node->next = head; head->prev = node; head = node; } else if (strcmp(produk, tail->produk) >= 0){ if (strcmp(produk, tail->produk) !=0){ tail->next = node; node->prev = tail; tail = node; } else{ tail->qty += node->qty; } } else{ while (strcmp(produk, curr->next->produk) >= 0){ curr = curr->next; } if (strcmp(produk, curr->produk) != 0){ node->prev = curr; node->next = curr->next; curr->next->prev = node; curr->next = node; } else{ curr->qty += node->qty; } } } void pop(char produk[31]){ struct data *curr = head; if (head == tail && strcmp(head->produk, produk) == 0){ head = tail = NULL; free(curr); printf("Product has successfully been removed!"); } else if (strcmp(head->produk, produk) == 0){ head = head->next; head->prev = NULL; free(head->prev); printf("Product has successfully been removed!"); } else if (strcmp(tail->produk, produk) == 0){ tail = tail->prev; tail->next = NULL; free(tail->next); printf("Product has successfully been removed!"); } else{ while (strcmp(curr->produk, produk) != 0){ if (curr->next != NULL){ curr = curr->next; } else{ break; } } if (strcmp(produk, curr->produk) == 0){ curr->prev->next = curr->next; curr->next->prev = curr->prev; free(curr); printf("Product has successfully been removed!"); } else{ printf("ERROR, Product not found!\n"); } } } void edit(char produk[31], int newQty){ struct data *node = (struct data*) malloc(sizeof(struct data)); struct data *curr = head; strcpy(node->produk, produk); node->qty = newQty; node->next = NULL; node->prev = NULL; if (head != NULL){ while (strcmp(produk, curr->produk) != 0){ if (curr->next != NULL){ curr = curr->next; } else{ break; } } if (strcmp(produk, curr->produk) == 0){ curr->qty = node->qty; printf("Product quantity has successfully changed!\n"); } else{ printf("ERROR, Product not found!\n"); } } else{ return; } } void view(){ struct data *curr = head; int number = 1; if (head != NULL){ printf("==================================================================================\n"); printf("******************************** Dreamer's Market ********************************\n"); printf("==================================================================================\n"); printf("| No. | Product Name | Quantity | Price | Total Price |\n"); printf("==================================================================================\n"); while (curr != NULL){ printf("| %-4d| %-25s| %-9d| Rp. %-10d| Rp. %-15d|\n" ,number, curr->produk, curr->qty, curr->price, (curr->qty * curr->price)); curr = curr->next; number++; } printf("==================================================================================\n\n"); } else{ return; } } void bill(){ struct data *curr = head; int number = 1, sum = 0; if (head != NULL){ printf("==================================================================================\n"); printf("******************************** Dreamer's Market ********************************\n"); printf("==================================================================================\n"); printf("| No. | Product Name | Quantity | Price | Total Price |\n"); printf("==================================================================================\n"); while (curr != NULL){ printf("| %-4d| %-25s| %-9d| Rp. %-10d| Rp. %-15d|\n" ,number, curr->produk, curr->qty, curr->price, (curr->qty * curr->price)); sum = sum + (curr->qty * curr->price); curr = curr->next; number++; } printf("----------------------------------------------------------------------------------\n"); printf("| Total: | Rp. %-15d|\n", sum); printf("==================================================================================\n\n"); printf("Thank You\n"); printf("Kindness is Free\n"); } else{ return; } } int main(){ struct data *curr = head; char item[31]; int choose = 0, quantity = 0; int pricing = 0, randomMin = 10000, randomMax = 100000; do{ system("cls"); printf("===========================\n"); printf("Welcome to Dreamer's Market\n"); printf("===========================\n\n"); printf("1. Add item\n"); printf("2. View Item\n"); printf("3. Edit item's quantity\n"); printf("4. Delete item\n"); printf("5. Pay\n"); printf("6. Exit Market\n"); printf(" Choose: "); scanf("%d", &choose); getchar(); switch(choose){ case 1: printf("Input item's name [1 - 30 char]: "); scanf("%[^\n]", &item); getchar(); printf("Input item's quantity: "); scanf("%d", &quantity); getchar(); pricing = ((rand() % (randomMax - randomMin + 1)) + randomMin); push(item, quantity, pricing); printf("Item successfully added!\n"); printf("Press Enter to continue . . . "); getchar(); break; case 2: system("cls"); if (head != NULL){ view(); } else{ printf("No data found, please add items first!\n"); } printf("Press Enter to continue . . . "); getchar(); break; case 3: system("cls"); if (head != NULL){ view(); printf("Input item's name: "); scanf("%[^\n]", &item); getchar(); printf("Input the changed quantity: "); scanf("%d", &quantity); getchar(); edit(item, quantity); } else{ printf("No data found, please add items first!\n"); } printf("Press Enter to continue . . . "); getchar(); break; case 4: system("cls"); if (head != NULL){ view(); printf("Input item's name: "); scanf("%[^\n]", &item); getchar(); pop(item); } else{ printf("No data found, please add items first!\n"); } printf("Press Enter to continue . . . "); getchar(); break; case 5: system("cls"); if (head != NULL){ bill(); return 0; } else{ printf("No data found, please add items first!\n"); } break; } }while (choose != 6); return 0; }