CODING ASSIGNMENT GSLC SHOPPING SIMULATOR :
Linked List
Linked list sendiri merupakan seperangkat node yang dialokasikan secara dinamis, disusun sedemikian rupa sehingga setiap node berisi satu nilai dan satu pointer. Pointer selalu menunjuk ke anggota berikutnya dari daftar. Jika penunjuknya adalah NULL, maka itu adalah simpul terakhir dalam daftar. Namun, memahami pointer sangat penting untuk memahami cara kerja daftar yang ditautkan. Pada dasarnya, Linked List berfungsi sebagai array yang dapat tumbuh dan menyusut sesuai kebutuhan, dari titik mana pun dalam array.
Linked list diperlukan alokasi dan pointer memori dinamis, yang memperumit kode dan meningkatkan risiko kebocoran memori dan kesalahan segmen. Linked List memiliki overhead yang lebih besar daripada array, karena item linked list dialokasikan secara dinamis (kurang efisien) dan setiap item dalam daftar juga harus menyimpan pointer tambahan.
Linked list sendiri merupakan seperangkat node yang dialokasikan secara dinamis, disusun sedemikian rupa sehingga setiap node berisi satu nilai dan satu pointer. Pointer selalu menunjuk ke anggota berikutnya dari daftar. Jika penunjuknya adalah NULL, maka itu adalah simpul terakhir dalam daftar. Namun, memahami pointer sangat penting untuk memahami cara kerja daftar yang ditautkan. Pada dasarnya, Linked List berfungsi sebagai array yang dapat tumbuh dan menyusut sesuai kebutuhan, dari titik mana pun dalam array.
Linked list diperlukan alokasi dan pointer memori dinamis, yang memperumit kode dan meningkatkan risiko kebocoran memori dan kesalahan segmen. Linked List memiliki overhead yang lebih besar daripada array, karena item linked list dialokasikan secara dinamis (kurang efisien) dan setiap item dalam daftar juga harus menyimpan pointer tambahan.
Stack and Queue
Stack adalah struktur data FILO (First In Last Out) atau LIFO (Last In First Out) yang dapat diimplementasikan menggunakan array, linked list, atau bentuk lainnya. Pertimbangkan riwayat peramban. Anda menavigasi ke Situs A -> lalu B -> lalu C -> D. Ketika pengguna bergerak maju, Anda pertama-tama push tail daftar situs web. Ini memastikan bahwa situs saat ini selalu di bagian atas tumpukan.
Stack adalah struktur data FILO (First In Last Out) atau LIFO (Last In First Out) yang dapat diimplementasikan menggunakan array, linked list, atau bentuk lainnya. Pertimbangkan riwayat peramban. Anda menavigasi ke Situs A -> lalu B -> lalu C -> D. Ketika pengguna bergerak maju, Anda pertama-tama push tail daftar situs web. Ini memastikan bahwa situs saat ini selalu di bagian atas tumpukan.
Kemudian ketika pengguna menekan tombol kembali, Anda pop satu di bagian atas yang memberikan situs yang terakhir dikunjungi - C. Dengan demikian konsep First In dan Terakhir Keluar. Serupa bisa dikatakan untuk antrian yaitu FIFO (First In First Out). Perhatikan contoh antrian pekerjaan. Saat melakukan pekerjaan, Anda akan yang melayani yang lebih dulu tiba. Hal ini menjadikan antrian sebagai struktur data yang sangat baik untuk memproses pekerjaan berdasarkan sistem siapa cepat dia dapat.
Dalam kedua kasus, Anda tidak ingin penghapusan atau penyisipan elemen secara sewenang-wenang pada indeks apa pun. Tidak, itu akan menghasilkan perilaku yang tidak diinginkan. Oleh karena itu, perlu tumpukan / antrian.
Hashing Table and Binary Tree
Hash Table
- Tidak semua hashing menggunakan linked list sebagai array. Alternatif yang populer adalah menggunakan array "lebih baik", misalnya binary tree, atau tabel hashing lainnya.
- Beberapa tabel hash sama sekali tidak menggunakan kotak: lihat Buka Mengatasi (mereka datang dengan masalah lain, jelas)
- Ada sesuatu yang disebut Linear re-hashing, yang menghindari perangkap "stop-the-world-and-rehash". Pada dasarnya selama fase migrasi Anda hanya memasukkan tabel "baru", dan juga memindahkan satu entri "lama" ke tabel "baru".
Binary Tree
- Re-balancing mahal, Anda dapat mempertimbangkan Skip-List atau Splay Tree.
- Pengalokasi yang baik dapat "mengemas" node bersama dalam memori, meskipun hal ini tidak mengurangi masalah penunjuk penunjuk.
Hash Table
- Tidak semua hashing menggunakan linked list sebagai array. Alternatif yang populer adalah menggunakan array "lebih baik", misalnya binary tree, atau tabel hashing lainnya.
- Beberapa tabel hash sama sekali tidak menggunakan kotak: lihat Buka Mengatasi (mereka datang dengan masalah lain, jelas)
- Ada sesuatu yang disebut Linear re-hashing, yang menghindari perangkap "stop-the-world-and-rehash". Pada dasarnya selama fase migrasi Anda hanya memasukkan tabel "baru", dan juga memindahkan satu entri "lama" ke tabel "baru".
Binary Tree
- Re-balancing mahal, Anda dapat mempertimbangkan Skip-List atau Splay Tree.
- Pengalokasi yang baik dapat "mengemas" node bersama dalam memori, meskipun hal ini tidak mengurangi masalah penunjuk penunjuk.
binary search tree
Binary Search Tree (BST) is one such data structures that supports faster searching, rapid sorting, and easy insertion and deletion
BST is a node-based binary tree data structure which has the following properties:
BST also have multiple basic operations such as find, insert, and remove. Which all of them have their own unique commands.
- Search
o We begin at root
- Insertion
- Deletion
Binary Search Tree (BST) is one such data structures that supports faster searching, rapid sorting, and easy insertion and deletion
BST is also known as sorted versions of binary tree.
BST is a node-based binary tree data structure which 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.
BST also have multiple basic operations such as find, insert, and remove. Which all of them have their own unique commands.
- Search
Because of the property of BST, finding/searching in BST is easy.
Let the key that we want to search is X.
o We begin at root
o If the root contains X then search terminates successfully.
o If X is less than root’s key then search recursively on left sub tree, otherwise search recursively on right sub tree.
- Insertion
Inserting into BST is done recursively.
Let the new node’s key be X,
o Begin at root
o If X is less than node’s key then insert X into left sub tree, otherwise insert X into right sub tree
o Repeat until we found an empty node to put X (X will always be a new leaf)
- Deletion
There are 3 cases which should be considered:
o If the key is in a leaf, just delete that node
o If the key is in a node which has one child, delete that node and connect its child to its parent
o If the key is in a node which has two children, find the right most child of its left sub tree (node P), replace its key with P’s key and remove P recursively. (or alternately you can choose the left most child of its right sub tree)
