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:
v
Linear
collection of data elements
v
Store value
in consecutive memory locations
v
Can be
random in accessing of data
Linked List:
v
Linear
collection of nodes
v
Doesn’t
store its nodes in consecutive memory locations
v
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 :
v find(x) : find key x in the BST
v insert(x) : insert new key x into BST
v remove(x) : remove key x from BST
Comments
Post a Comment