Summary
Linked List
Sebelum dimulai, saya ingin memberikan pengertian sedikit apa itu Linked List. Linked List adalah sebuah Data Structure yang bersifat linier. Lalu, apa bedanya dengan Array? Di Array, kita harus memberikan terlebih dahulu constraint untuk me-reserve memory untuk nantinya dimasukkan sebuah variable. Sedangkan di Linked List, kita tidak perlu memberikan constraint karena kita akan memakai memory SESUAI dengan tiap node yang kita masukkan. Sebagai contoh agar lebih mudah dimengerti, kita misalkan seperti kita ingin makan di sebuah restoran, dimana jika kita mengambil contoh Array, itu seperti kita sudah melakukan booking terhadap meja tertentu di hari-hari sebelum kita makan di restoran tersebut. Sedangkan kalau Linked List, kita langsung datang ke restoran untuk makan di saat itu juga. Jika kita melakukan booking terhadap meja tertentu, tentunya kita akan tahu dimana kita akan makan, di meja ke berapa, di bagian mana meja tersebut terletak. Sedangkan jika kita tidak melakukan booking atau langsung datang ke restoran untuk makan, tentu kita akan diberikan meja yang masih kosong, kita tidak tahu di hari itu ada brp pengunjung yang makan disitu, dimana meja yang akan kita pakai, karena kita tidak melakukan booking, kita akan diberikan meja yang kosong pada WAKTU itu.
Dalam pertemuan kali ini, kita mempelajari tentang tiga jenis Linked List :
- Circular Single Linked List
- Doubly Linked List
- Circular Doubly Linked List
1. Circular Single Linked List
Di dalam Linked List, kita memiliki Circular Single dan Circular Doubly. Persamaan diantara keduanya adalah sama sama tidak memiliki nilai NULL diakhir sebuah NODE. Namun, di Circular Single Linked List sendiri, akhiran pada sebuah node akan kembali ke HEAD yang ada di paling depan. Ini bisa diterapkan dengan melakukan loop hingga node terakhir dan jadikan node(terakhir)->next = head.
Pada gambar diatas (source:geekforgeeks), kita bisa lihat bahwa 3 itu sebagai HEAD dan 9 sebagai NODE terakhir. dan di node(9)->next = head(node 3) itu sebagai penyambung agar menjadi Circular Single Linked List.
2. Doubly Linked List
Doubly Linked List memiliki perbedaan yg cukup terlihat dibandingkan dengan Single Linked List. Disini memiliki HEAD dan TAIL. HEAD memiliki fungsi yang sama seperti di Single Linked List, yaitu sebagai awal, dan TAIL sebagai akhir dari sebuah Doubly Linked List. Untuk pointer, disini kita punya NEXT dan PREV, kegunaan PREV akan saya jelaskan nanti di bagian deletion.
didalam Doubly Linked List, kita bisa melakukan INSERT dan DELETE. INSERT sendiri yaitu memasukkan node baru kedalam Linked List. Penulisan coding INSERT dalam bahasa C/C++ bisa ditulis sabagai berikut :
Untuk membuat node baru:
Untuk melakukan pushHead (menjadikan node baru sebagai HEAD):
Untuk melakukan pushTail (menjadikan node baru sebagai TAIL):
Dan sekarang mari kita buat node dengan menulis ini:
Penulissan code DELETE adalah sebagai berikut :
Untuk menghapus HEAD:
Untuk menghapus TAIL:
Untuk menghapus node ke n:
Jika itu adalah node satu satunya:
3. Circular Doubly Linked List
Mirip seperti Circular Single Linked List, namun dalam kasus ini kita tidak hanya menyatukan node->next dengan head namun kita menyatukan head dengan tail. Caranya adalah dengan menjadikan tail->next = head dan head->prev = tail.
Sekian penjelasan saya tentang Circular Single/Doubly Linked List dan Doubly Linked List.
References:
Diktat Algorithm & Programming for New Assistant Recruitment SLC NAR20-1
Diktat Advanced C for New Assistant Recruitment SLC NAR20-1
Single Linked List
Single Linked List adalah jenis linked list yang hanya bisa menunjuk ke node berikutnya, berbeda dengan Double Linked List yang bisa menunjuk sebelumnya.Di dalam Rangkuman ini, kita akan melakukan beberapa fungsi seperti men-insert node baru, men-delete node baru, dan mengeprint semua isi node nya.
1. Insert
Untuk melakukan insert di dalam Single Linked List, kita bisa melakukannya dengan men-insert di depan (pushHead), menginsert di belakang (pushTail).
Membuat fungsi createaccount untuk node baru
Disini kita akan membuat fungsi yang berguna untuk membuat node baru. Di baris pertama, kita ingin mengalokasikan memory yang akan digunakan untuk node baru kita. Caranya adalah dengan syntax malloc. malloc berguna untuk memberi tahu kepada mesin untuk menyediakan memory untuk node yang akan kita buat. Berikutnya kita melakukan strcpy untuk mengcopy email dan password yang kita masukkan kedalam email dan password yang merupakan atribut node. kemudian kita set node->next = NULL untuk memberi tahu mesin bahwa setelah node itu tidak ada apa-apa. Ini berguna untuk melakukan insert. dan terakhir kita return node kita tadi untuk dimasukkan kedalam pushHead.
pushHead
untuk membuat pushHead, dapat dilihat sebagai berikut :
Disini saya membuat fungsi pushHead untuk struct yang memiliki atribut email dan password. Tahap pertama dalam membuat pushHead adalah membuat pointer baru dimana kita mengunakan fungsin createaccount yang sudah di contohkan diatas. setelah kita mendeklarasikan pointer node nya, kita melakukan selection. Jika head == NULL, maka kita akan membuat Head dan Tail yang baru. Tapi jika sudah ada, maka kita akan bilang bahwa node->next = head dan head = node. Ini berguna untuk mendorong head yang lama sehingga node yang baru kita masukkan menjadi head yang baru.
pushTail
untuk membuat pushTail, dapat dilihat sebagai berikut :
Disini saya membuat fungsi pushTail yang berfungsi untuk memasukkan node baru di setelah Tail (node terakhir). ini bisa dilakukan dengan struktur codingan yang sama dengan pushHead namun bedanya di else kita membuat next dari tail sebagai node yang baru, dan node yang baru kita jadikan tail.
2. Delete
Delete dapat dilakukan dengan 3 cara : yaitu popHead, popMid, dan popTail.
popHead
untuk membuat popHead, dapat dilihat sebagai berikut :
popTail
uintuk membuat popTail, dapat dilihat sebagai berikut :
popMid
untuk membuat popMid, dapat dilihat sebagai berikut :
3. Print
untuk membuat fungsi print, dapat dilakukan sebagai berikut :
4. Inisiasi
untuk menggunakan semua fungsi ini, kita dapat memanggilnya di main dengan cara sebagai berikut :
Hash Table
Due to class being a bilingual-language class, I'm going to use English for this point onward. Some may be in Indonesian but mostly it will be in English.
Hash table is one of the several types of Data structures that stores its value in array manner. Usually we use Hash table to store string values. In Hash table, there's a method which called Hashing. In Hash table, we will use the spesific "key" to acquire it's information, so in this type of data structure, you will need a "key". This key can be something like names,code,etc. Every array can be set into certain "key". that array can contain something like attribute and such. For example, if you set your key into names, like "Dave" and you calculate the total amount of their ascii number then modulo it to the amount of array, that way we can tell which array do "Dave" attribute stored at. This way we can search faster than that of the normal linear search for array.
There are 3 basic operations for Hash table: Search, Insert, Delete.
Search
There are several methods on how you do the searching in Hash table, but for the sake of simplicity I will use the division method. What this does is as you can read above in the example, you can convert each character of the string into their ascii numbers. Then you can modulo it to the amount of array or array size. If you formulized it. it can be something like (Ascii) Mod (ArrSize). If you don't know how this can be implemented in C language, then I will show you how :
Insert
Insertion can be as simple as the picture above. As you can see in the last part, you can just use that to put some value into the array that you already have using the previous method. For example: in the last line of the code, we can insert the value into the array that the key has been modulo by the amount of array.
Deletion
Deletion is as the same as insertion, only here you can clear the value inside the array that you want to delete.
Linear Probing
This is one of the solution if you ever have the "Collution" problem. Collution problem is a problem when you already have a value inside a certain array that you want to insert. This will cause a collution between values. This can be avoided using the Linear Probing method. How this works is whenever you find collution, you can always place the same "key" into the next array. This may cause some problem if you have a limited amount of array but a large number of key and its attribute you want to add.
Chaining
This solution is a bit better than Linear Probing. Instead of adding it into the next array, you can make those array into some Linked List where you can store undinifed amount of value that has the same key in the same array.
Binary Tree
Binary tree is the type of data structure that divide the node into some binary node tree. The way it works is you have a root as your base to expand later. then if you want to add another node, you can add it on the left or the right depends on how the value react to the root. If the value is lower than the root, that usually it goes to the left. But if the value is larger than the root, they goes to the right. THE most important part of this tree is that you cannot have more than TWO CHILDS for each node.
The first node or "1" node, is the root of the tree. And the last level of nodes (Such as 8,9,10,11,13,14) is the leaf of the tree.
Types of Binary Tree
There are several types of Binary Tree, some of which are :
Perfect Binary Tree
Complete Binary Tree
Skewed Binary Tree
References :
Binusmaya resource powerpoint
Pictures are from geektogeeks
Binary Search Tree
Binary Search Tree or BST is one of the Data Structure that have the same properties as Binary Tree, but more organized. The difference on BST is they are made for easier and faster search. This is accomplished by seperating the data using the root node. If there's already a root node on the tree, then you need to see whether the new node you want to insert is larger or smaller than the root. If the new node is smaller, then you place it on the left side of the root as the child. If the new node is larger, then it goes to the right. This way the tree will be sorted easily.
Binary Search Tree has the following properties:
- The left subtree of a node contains only nodes with keys lesser than the node’s key.
- The right subtree of a node contains only nodes with keys greater than the node’s key.
- The left and right subtree each must also be a binary search tree.
There are 3 functions that BST has:
Search
If you already have BST, you can proceed by searching the node that you're looking for. You need to pay attention on whether the node that you're looking for is larger or smaller than your current nodes. This mean that everytime you do the search per nodes, check it whether its larger or smaller.
(courtesy of GeeksforGeeks)
Insert
(Courtesy of GeeksforGeeks)
Deletion
As almost the same as insert, you first need to search for the nodes that you want to delete. After you found the nodes that you want to delete, procceed by connecting the childs (If exist) of the node to the parents of the node.
No comments:
Post a Comment