8 Data Structures every programmer must know

Algorithms and data structures are one of the most important key skills for every programmer. Knowing about them is not enough, but being good at them can give a good leap in a programmer's productivity and career.

There are plenty of resources are available on data structures, but here we shall explore them in a simplified way. Before that, one must know a little more about data structures.

What is a Data Structure?

Imagine, if you want to organize things at home, so that you can find them or use them quickly, you follow some methods to arrange them, like stacking them according to colors, or arranging them with some labels, etc., in the same way, data structures are methods of organizing and storing data in a computer system so that operations can be performed more efficiently.
As there are different types and forms of data, data structures also take the form of different layouts, each of which can be efficient for some operations and inefficient for others. To solve the problem more effectively and efficiently, the programmer has to decide which data structure is suitable for a given set of data.

I have explained each data structure quickly in the following template

data structure name
< definition >
< structure >
< allocation type - static or dynamic, homogenous or heterogeneous >
< example >
< insertion / access / deletion / traversal criteria >
< usecase >

1. Array

• Array is the collection of similar data stored sequentially.
• Stored in contiguous memory locations linearly, the items stored inside the array are called elements.
• Homogeneous and static, once initialized, their size remains the same.
• Best example of an array is the weekly medication box, which consists of small containers indicating memory blocks or array indices, whereas medicines stored inside it indicate elements.
• Can be accessed sequentially or randomly by its index value, the initial element of the array always has an index of 0 (zero).
• Cannot reduce or expand the array size by deletion or addition of elements respectively.
• Generally used for building complex data structures and sorting algorithms.

2. Stack

• Stack is an ordered list of data that stacks elements inside a container.
• Stored in Last-in-First-out (LIFO) structure, where the last element removed first which is called top.
• Homogeneous and dynamic, size can be increased or decreased according to the data dynamically.
• Best example of a stack is the pile of plates, where we add plates one over the other and can only remove the plate at the top.
• Adding a new element (insertion) called push and removing the top element (deletion) called pop.
• Commonly used for parsing and evaluating mathematical expressions, to implement function calls in recursion programming, also in undo-redo operation.

3. Queue

• Queue is an ordered list of data in which arrange elements inside a container sequentially.
• Stored in First-in-First-out (FIFO) structure, where the first element removed first.
• Homogeneous and dynamic, size can be increased or decreased according to the data dynamically.
• Best example of a queue is a line of people waiting to enter a bus, where the person at the beginning of the line will enter first while the person at the end will enter last.
• Adding a new element at the end (insertion) called enqueue and removing the element at the beginning (deletion) called dequeue.
• Often used to manage threads in multithreading, and used to implement priority queuing systems, like printer spool.

4. Linked List

• Linked list is a sequence of data arranged in a linear order, and stores data in nodes that are connected to each other.
• Node contains the data (key) and the reference to the next node to it (pointer), this pointer is also called next.
• Homogeneous and dynamic, size depends on insertion or deletion of nodes, but cannot be accessed randomly.
• Best example of a linked list is the train, where the engine is connected to the next car, and it always has to start from the engine, if you want to remove a car, you have to identify the car and then detach the car from the cars both ahead and behind it.
• The first node of a linked list is always called head, whereas the last node is called tail.
• The direction of access of any node is always from head to tail. Doubly linked list can be accessed in both directions.
• Circular linked list is another type in which the head and tail are connected to each other.
• Used for the symbol table management in switching between program windows in operating systems by pressing alt+tab, forward-backward functionality in the browser.

5. Tree

• Tree is an advanced version of a linked list where nodes are linked to another in a tree-like structure (root at the top and leaves are at the bottom).
• Nodes are arranged in a hierarchical structure, like a family tree or organization tree.
• Homogeneous and dynamic, size is totally dependent on insertion and deletion of nodes, but cannot be accessed randomly.
• Best example of a tree is itself, to reach the particular leaf we have to start from the root and to its adjacent and respective branch and sub-branch.
• The first node of a tree is always called root and nodes can be denoted as node, the node under the other node is called child node. Each node consists of a value (key), a pointer to the left child node (left), a pointer to the right child node (right), and a pointer to the parent node (p).
• Binary Search Trees (BST) are one of the applications used for different types of search applications, especially used for searching files in the directory structure, or in wireless networking.
• Tree is also used for developing chess algorithms to store the possible moves.

6. Graph

• Graph is a network of interconnected items.
• It is abstract, non-linear made of a finite set of nodes that are connected to each other.
• Homogeneous and dynamic, size is dependent on a finite set of nodes
• Best example of a graph is google map where each location is considered as edges and to find the shortest path between these nodes, graph algorithms are used.
• Each node is called vertex and the connection between the nodes is called edge, nodes are predefined along with their edges.
• Often used to represent networks such as paths in a city, they are also used in social media to represent each node as a person's profile and their connection to the other profiles or nodes.

7. Hash Table

• Hash table is a tabular two-column based like structure, in which the first column entry know as key and the second column entry known as value.
• Structure associates each value with a key and then stores them, this makes it easy to look up values efficiently using a key.
• Heterogeneous and dynamic, size depends on total entries of key and value pair.
• Best example of a hash table is college students' record, where each student is identified by the unique ID number, and by accessing the ID number can give the information about the respective student.
• Uses hash function to map a data set of any size to one of a fixed size table. Values are returned by hash function are known as hash values.
• Often used to store a set of fixed keywords that are referenced very frequently, to create databases indices, to create associative arrays to store some real-time data, to social media feeds section.

8. Heap

• Heap is a type of binary tree, which can also be represented as binary arrays.
• In a heap, parent nodes are compared to their children, this allows the values within the nodes to be arranged accordingly.
• Same as tree, homogeneous and dynamic.
• Best example of a heap is the tree whose parent leaves that are greener than the child leaves, or vice versa, where the green color is the node value.
• There are two types of heaps. In a min heap, the parent's key is less than or equal to the keys of its children, In a max heap, the parent's key is greater than or equal to the keys of its children.
• Often used in algorithms used to create priority queues, and find the smallest or largest value in an array for sorting algorithms, and implement Dijkstra's algorithm.