Rangkuman Data Structure

Warren

2301858093

Kelas: CB01-CL

Lecturer: Ferdinand Ariandy Luwinda (D4522), Henry Chong (D4460)

Linked List

Linked list adalah struktur data yang terdiri dari urutan – urutan data yang memilki referensi untuk data selanjutnya. Linked list bisa melakukan insertion dan deletion tipe apapun dan dimanapun. Linked list biasa digunakan untuk “solving real-time problems”, saat jumlah data yang ingin disimpan tidak dapat diprediksi. Ada dua tipe linked list yaitu single linked list dan double linked list.

Single Linked List

Single linked list ditandai dengan memiliki link satu arah dari list yang menunjuk ke list lain. Systemnya berjalan dengan pointer dari Head lalu next sampai NULL.

Doubly Linked List

Systemnya seperti single linked list, tetapi sekarang dia dapat jalan mundur juga (previous).

Circular Linked List

“previous” pointer dari node pertama (head) akan “points” ke node terakhir (tail) membuatnya tidak bernilai null.

pointer “next” di node terakhir (tail) akan “points” ke node pertama (head) membuatnya tidak bernilai null juga.

Linked List vs Array

Array:

· Linear collection of data elements

· Store value in consecutive memory locations

· Can be random in accessing of data

Linked List:

· Linear collection of nodes

· Doesn’t store its nodes in consecutive memory locations

· Can be accessed only in a sequential manner

Stack & Queue

Stack concept. Stack is an important data structure which stores its elements in an ordered manner. Example, You must have seen a pile of plates where one plate is placed on top of another. When you want to remove a plate, you remove the topmost plate first. Hence, you can add and remove an element (i.e. the plate) only at/from one position which is the topmost position. Stack is a linear data structure which can be implemented by either using an array or a linked list, The elements in a stack are added and removed only from one end (top), and the data are stored in Last In First Out (LIFO) way.

Queue concept. Queue can be implemented by either using arrays or linked lists. The elements in a queue are added at one end called the rear and removed from the other one end called front. The data are stored in First In First Out (FIFO) way, this is the main difference between stack and queue.

Infix, Postfix, and Prefix Notation

Prefix is an operator written before operands, infix is an operator written between operands, and postfix is an operator written after operands. Why do we need prefix or postfix notation? Because prefix and postfix notations don’t need brackets to prioritize operator precedence. Prefix and postfix is much easier for computer to evaluate.

Hashing and Hash Tables, Trees & Binary Tree

Hashing

Hashing is a technique used for storing and retrieving keys in a rapid manner.

In hashing, a string of characters are transformed into a usually shorter length value or key that represents the original string.

Hashing is used to index and retrieve items in a database because it is faster to find item using shorter hashed key than to find it using the original value.

Hashing can also be defined as a concept of distributing keys in an array called a hash table using a predetermined function called hash function.

Binary Tree

A binary tree is a tree with the condition that each node only has a maximum of two subtree and the two subtree must be separate. In accordance with this definition, each node in the binary tree must only have at most two children / children.

Implementation in Blockchain

In a blockchain, each node of the network stores the full data. So it is absolutely not the same idea as the DHT in which data are divided among nodes. Every new entry in the blockchain must be validated by a process called mining whose details are out of the scope of this answer but this process insure consensus of the data.

Advantages

• It enables linear traversal of elements in the tree

• Linear traversal eliminates the use of stacks which in turn consume a lot of memory space and computer time

• It enables to find the parent of a given element without explicit use of parent pointers

• Since nodes contain pointers to in-order predecessor and successor, the threaded tree enables forward and backward traversal of the nodes as given by in-order fashion

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 also known as sorted versions of binary tree

Binary Search Tree operations. Binary search tree has the following basic operations:

· find(x) : find key x in the BST

· insert(x) : insert new key x into BST

· remove(x) : remove key x from BST

AVL TREE

AVL tree adalah nama berasal dari dua penciptannya yaitu, G.M. Adelson-Veleskii and E.M. Landis. AVL tree adalah self-balancing binary search tree pertama yang pernah diciptakan. AVL tree digunakan untuk menyeimbangkan Binary Search Tree, untuk mempersingkat pencarian dan menyederhanakan bentuk tree.

Contoh:

Insertion di AVL Tree

Insertion pada AVL tree adalah insertion biasa seperti yang digunakan pada binary search tree. Tetapi ini dapat menyebabkan pelanggaran pada properti AVL Tree. Setelah melakukan insertion biasa maka kita harus benarkan menjadi kondisi yang seimbang.

Selanjutnya, kembalikan kondisi keseimbangan. Pertama, lacak jalur dari kunci baru menuju root. Untuk setiap node yang A lewati, periksa apakah ketinggian kiri A dan kanan A berbeda pada paling banyak 1. Jika ya, lanjutkan ke parent A. Jika Tidak, perbaiki sub pohon A baik dengan single rotation atau double rotation.

Single Rotation

Single rotation dilakukan jika searah (left-left atau right-right)

Double Rotation

Double rotation dilakukan jika tidak searah (left-right atau right left)

Rotasi pertama

Rotasi kedua

Delete di AVL tree

Hapus node seperti pada Binary Search Tree biasa. Node yang dihapus akan berupa leaf atau node dengan satu child. Lacak jalur dari parent dari leaf yang dihapus ke arah root. Untuk setiap node yang A lewati, periksa apakah ketinggian kiri A dan kanan A berbeda paling banyak 1. Jika ya, lanjutkan ke parent A. Jika tidak, perbaiki sub pohon A dengan single rotation atau double rotation. Setelah kita melakukan rotasi pada A, kita mungkin harus melakukan rotasi pada beberapa ancestor A. Jadi, kita harus terus melacak jalan sampai kita mencapai root.

Heap & Tries

Heap adalah struktur data “complete binary tree based” yang memenuhi heap property.
Property tersebut adalah:

Min Heap
Max Heap

Min Heap

Setiap elemen node lebih kecil dari elemen children-nya.
Ini menyiratkan bahwa elemen terkecil terletak di root tree.
Elemen terbesar terletak di suatu tempat di salah satu leaves node.
Heap dapat diimplementasikan menggunakan linked-list, tetapi jauh lebih mudah untuk mengimplementasikan heap using array.