Different data structures with its use cases
I always wanted to have something as quick refresher for data structure. There are lot of material out there to understand any data structure in details and how to implement them. I always felt that if I just need to refresh data structures anytime in 5–10 mins, going through detailed material does not solve the purpose. Hence thought of preparing this for me and sharing in blog to help wider community. I have tried to keep this blog language agnostic.
Arrays: If you are a programmer for any language, arrays needs no introduction. An array is a collection of items stored at contiguous memory locations. Hence being little performant while storing and fetching data. It’s a linear data structure. If you know the size of data list which needs to be stored, arrays can be useful. Because of faster data retrieval through index, arrays more suitable for use case where we need to access data again and again through indexes.
Real world usages
Games: Designing games like chess/checkerboard where size is fixed.
Indexes: Designing indexes, so that location can be retrieved faster. For example, indexes of books, library management system.
Image processing: 2D arrays, commonly known as, matrices, are used in image processing.
Contacts: Contacts on a cell phone.
Array list: Somewhat similar to arrays, but has size flexibility. While creating Arraylist by default size is 15, if not specified. When initial size is full and more elements are added arraylist is moved to different place in memory to occupy growing size. Performance of adding element in arraylist will downgrade if arraylist is very big in size and it’s already full. Because of faster data retrieval through index, arrays more suitable for use case where we need to access data again and again through indexes.
Real world usages
- Resultset: Storing result retrieved from data base.
- Transactions: Keeping track of transactions.
- Will also be useful for other use cases of arrays.
Linked list: Unlike array, data can be stored anywhere in memory and linked through previous element knowing about next element data location. Linked list has good performance while adding data and when we have huge amount of data, but its slower in accessing data through indexing or if we data needs to be accessed in random way. Less memory usage than arrays because it will not block additional memory than actually being used at present.
Real world usages
- Implementing queue data structure
- Message delivery on network
- Kafka topics
Stack: Simple linear data structure with last element inserted is the first element to come out.
Real world usages
- Call stack: Languages use stacks to keep track of what functions are executing at any given point in time during a program. When program runs for infinite loop we get the error Stackoverflow
- To reverse a word: Put all the letters in a stack and pop them out. Because of the LIFO order of stack, you will get the letters in reverse order.
- In compilers: Compilers use the stack to calculate the value of expressions like 2 + 4 / 5 * (7–9) by converting the expression to prefix or postfix form.
- In browsers: The back button in a browser saves all the URLs you have visited previously in a stack. Each time you visit a new page, it is added on top of the stack. When you press the back button, the current URL is removed from the stack, and the previous URL is accessed.
- Word processors: undo\redo operation in word processors
Queues: Unlike stacks, a queue is open at both its ends. One end is always used to insert data (enqueue) and the other is used to remove data (dequeue).
Real world usages
- Message queues
- CPU scheduling, Disk Scheduling
- When data is transferred asynchronously between two processes.The queue is used for synchronisation. For example: IO Buffers, pipes, file IO, etc
- Handling of interrupts in real-time systems.
- Call Center phone systems use Queues to hold people calling them in order.
- Scheduling based on priority
Tree: A tree data structure is a non-linear data structure because it does not store data in a sequential manner. It is a hierarchical structure as elements in a Tree are arranged in multiple levels. Tree is also recursive data structure, where structure repeats itself. There are many types of trees which has different use cases which I will mention separately. Some basic usage of tree is below.
Real world usages
- Storing naturally hierarchical data: Trees are used to store the data in the hierarchical structure. For example, the file system. The file system stored on the disc drive, the file and folder are in the form of the naturally hierarchical data and stored in the form of trees.
- Organize data: It is used to organize data for efficient insertion, deletion and searching. For example, a binary tree has a logN time for searching an element
Binary Tree: The Binary tree means that the node can have maximum two children. Here, binary name itself suggests that ‘two’; therefore, each node can have either 0, 1 or 2 children.
Properties of Binary Tree
- At each level of i, the maximum number of nodes is 2i.
- The minimum number of nodes possible at height h is equal to h+1.
Real world usages
- Faster Searching and sorting because it stores data hierarchically.
- Routing table: A routing table is used to link routers in a network. It is usually implemented with a trie data structure, which is a variation of a binary tree. The tree data structure will store the location of routers based on their IP addresses. Routers with similar addresses are grouped under a single subtree.
- Expression Evaluation: Another useful application of binary trees is in expression evaluation. In mathematics, expressions are statements with operators and operands that evaluate a value. The leaves of the binary tree are the operands while the internal nodes are the operators.
- Data Compression: Huffman coding builds a binary tree and inserts the encodings of characters in the nodes based on their frequency in the text. The encoding for a character is obtained by traversing the tree from its root to the node. Frequently occurring characters will have a shorter path as compared to less occurring characters. This is done to reduce the number of bits for frequent characters and ensure maximum data compression.
Binary search tree: It’s a specialised binary tree where value of left node will always be lesser than value of right node and it also follows the properties of binary tree.
Real world usages
- BSTs are used for indexing and multi-level indexing.
- They are also helpful to implement various searching algorithms.
- It is helpful in maintaining a sorted stream of data.
Binary heap: Binary heap is a type of binary tree data structure where root node stores either maximum or minimum value of the tree. In case of Min binary heap, every child node value will be higher than parent node and vice versa applied to max binary heap. It’s a complete binary tree because all levels are completely filled except leaf nodes and parent node will not have right child without left child. Binary heap allows only root node to be extracted.
Real world usages:
- Priority queues: Designing the priority queues because first element will be always have highest priority.
- To quickly find the smallest and largest element from a collection of items or array.
- In order to overcome the Worst-Case Complexity of Quick Sort algorithm from O(n²) to O( nlog(n) ) in Heap Sort.
AVL Tree: AVL Tree is invented by GM Adelson — Velsky and EM Landis in 1962. The tree is named AVL in honour of its inventors. AVL Tree can be defined as height balanced binary search tree in which each node is associated with a balance factor which is calculated by subtracting the height of its right sub-tree from that of its left sub-tree.
Tree is said to be balanced if balance factor of each node is in between -1 to 1, otherwise, the tree will be unbalanced and need to be balanced.
Real world usages
- AVL trees are mostly used for in-memory sorts of sets and dictionaries.
- AVL trees are also used extensively in database applications in which insertions and deletions are fewer but there are frequent lookups for data required.
- It is used in applications that require improved searching apart from the database applications.
Trie: The word “Trie” is an excerpt from the word “retrieval”. Trie is a sorted tree-based data-structure that stores the set of strings.
Usage:
- Spell checker
- Auto-complete
- Browser history: It is also used to complete the URL in the browser. The browser keeps a history of the URLs of the websites you’ve visited.
Graphs: A graph can be defined as group of vertices and edges that are used to connect these vertices. A graph can be seen as a cyclic tree, where the vertices (Nodes) maintain any complex relationship among them instead of having parent child relationship.
Multiple types of graphs:
- Directed graph: Direction for traversal specified
- Undirected graph: Direction for traversal specified
- Weighted graph: Edge having weight associated with it
- Connected graph: A connected graph is a graph in which a path always exists from a vertex to any other vertex. A graph is connected if we can reach any vertex from any other vertex by following edges in either direction.
There are 2 ways to traverse the graph:
- BFS(Breadth first search):Breadth-first search is a graph traversal algorithm that starts traversing the graph from the root node and explores all the neighboring nodes. Then, it selects the nearest node and explores all the unexplored nodes. While using BFS for traversal, any node in the graph can be considered as the root node. Queue data structure is used to implement BFS algorithm.
Application of BFS:
- BFS can be used to find the neighbouring locations from a given source location.
- In a peer-to-peer network, BFS algorithm can be used as a traversal method to find all the neighboring nodes. Most torrent clients, such as BitTorrent, uTorrent, etc. employ this process to find “seeds” and “peers” in the network.
- BFS can be used in web crawlers to create web page indexes. It is one of the main algorithms that can be used to index web pages. It starts traversing from the source page and follows the links associated with the page. Here, every web page is considered as a node in the graph.
- BFS is used to determine the shortest path and minimum spanning tree.
2. DFS(Depth first search): The depth-first search (DFS) algorithm starts with the initial node of graph G and goes deeper until we find the goal node or the node with no children. Because of the recursive nature, stack data structure can be used to implement the DFS algorithm.
Application of DFS:
- DFS algorithm can be used to implement the topological sorting.
- It can be used to find the paths between two vertices.
- It can also be used to detect cycles in the graph.
Minimum spanning tree: A spanning tree can be defined as the subgraph of an undirected connected graph. It includes all the vertices along with the least possible number of edges. If any vertex is missed, it is not a spanning tree. A minimum spanning tree can be defined as the spanning tree in which the sum of the weights of the edge is minimum.The weight of the spanning tree is the sum of the weights given to the edges of the spanning tree.
Usage:
- Minimum spanning tree can be used to design water-supply networks, telecommunication networks, and electrical grids.
- It can be used to find paths in the map.
If you think there is any other data structure and detail which needs to be added as quick reference material, do let me know in comments section and I will incorporate those.
Reference material:
