Data Structures Cookbook
References:
https://www.geeksforgeeks.org/real-time-application-of-data-structures/
https://www.programiz.com/dsa
Arrays:
Single Dimensional or Linear Arrays:
Applications:
a) For sorting data elements.
b) Implement Stacks and Queues
Multi Dimensional Arrays:
Applications:
a) Used for plotting graphs, and statistics and also to do scientific studies and research in almost different fields
b) Best representation methods for plotting surveys
c) Matrix Calculations.
LinkedList:
Applications:
a) Web pages can be accessed using the previous and the next URL links which are linked using a linked list.
b) Train coaches are connected to one another in a doubly-linked list fashion.
c) Social media content “feeds”.
Stacks: First in Last Out
Applications:
a) Message logs and all messages you get are arranged in a stack.
b) History of visited websites.
c) Syntaxes in languages are parsed using stacks.
d) Call stacks in programming run times.
Queues: First in First Out
Applications:
a) For job scheduling.
b) Sending an e-mail, it will be queued.
c) Data packets in communication are arranged in queue format
Priority Queue:
Reference: https://www.programiz.com/dsa/priority-queue
A priority queue is a special type of queue in which each element is associated with a priority value. And, elements are served on the basis of their priority. That is, higher priority elements are served first.
Note: If elements with the same priority occur, they are served according to their order in the queue.
Difference between Priority Queue and Normal Queue
In a queue, the first-in-first-out rule is implemented whereas, in a priority queue, the values are removed on the basis of priority. The element with the highest priority is removed first.
Applications:
1) Premium user requests
2) VVIP,VIP tickets, requests etc.
Graph:
Data structure where data is stored in a collection of interconnected vertices (nodes) and edges (paths).
Applications:
a) Recommendation Engines.
b) The GPS navigation system also uses shortest path APIs.
c) GraphQL queries.
Trees:
It is a graph without cyclic paths.
Applications:
a) Domain Name Server(DNS) also uses tree structures.
b) XML structure
c) File explorer/my computer of mobile/any computer
Binary Search Tree:
Reference: https://www.programiz.com/dsa/binary-search-tree
Each node has a maximum of two children.
It is called a search tree because it can be used to search for the presence of a number in O(log(n)) time.
The properties that separate a binary search tree from a regular binary tree is
- All nodes of left subtree are less than the root node
- All nodes of right subtree are more than the root node
- Both subtrees of each node are also BSTs i.e. they have the above two properties
Applications:
a) Used for indexing and multi-level indexing.
b) Computer Graphics Rendering
Trie:
Applications:
1) Dictionary
2) Autocomplete
Hash Tables:
The Hash table data structure stores elements in key-value pairs where
- Key- unique integer that is used for indexing the values
- Value — data that are associated with keys.
Note: Since Hash of of 2 input string can be same, we shouldn’t replace the existing key, value pair, and this is called as Collusion Resolution.
Chaining: Value is a doubly linked-list. Each data is stored as a node in this doubly linked list.
Applications:
a) Indexing data
b) Constant time lookup and insertion is required
c) Cryptographic applications
Heaps:
min heap: the key of the parent is less than or equal to those of its children max heap: the key of the parent is greater than or equal to those of its children
Applications:
a) Implementing a priority queue.
b) Dijkstra’s Algorithm
c) Heap Sort
