Data Structures : Explained

Data structures are the most essential tools when we talk of computer programming. They are used to store and organise data in a way that makes their retrieval, manipulation and deletion easier.

There is a plethora of data structures used while solving complex problems. In this article, we will cover basic data structures like Arrays, linked lists and stacks as well as more complex and advanced data structures like Graphs and tries.

Note: C++ is the language used for reference in this article.

ARRAYS

An array is a linear and static data structure which is used to store elements in a sequential order.

To declare an array, we need to specify it’s size beforehand and it cannot be changed afterwards. This is why an array is a static data structure

Example: int arr1[5]={1,2,3,4,5};

In the above example, an array of size 5 is declared.

Some in-built functions used with arrays are:

1. sort()- This function is pre-defined in the C++ libraries and is used to sort the elements of the array in increasing order by default.
2. *min_element()- It is used to return the minimum element in the array
3. *max_element()- It is used to return the maximum element in the array
4. size()- It returns the size of the array
5. swap()- it is used to swap two elements of the array

Arrays are used in the implementation of various other data structures like stacks and queues. It is the simplest data structure with it’s own unique use-cases.

STRINGS

A string is also a linear data structure which consists of an arrangement of characters. A string can contain both alphanumeric and special characters.

Example: string str1=”CoinCodeCap”;

Some STL functions available with strings are as follows:

1. length()- It gives the length of the string
2. reverse()- It is used to reverse the string
3. clear()- removes all the characters from the string
4. empty()- checks if the string is empty or not

Also Read: Top 10 Best Tools for Data Scientists

STACKS

A stack is a linear and dynamic data structure that follows a unique rule for insertion and deletion of elements called the LIFO rule. LIFO stands for Last-In First-Out and the element that was inserted last int he stack is the first one to be removed.

LIFO rule is followed in real life too. Let’s say that the last person to hop on to a crowded bus is the first one to hop off.

The following STL functions are available with stacks:

1. push() – this is used to insert elements to the top of the stack
2. pop() – this is used to remove the topmost element of the stack
3. isEmpty() – this checks if the stack is empty or not
4. isFull() – this checks whether the stack is full
5. size() – it returns the size of the stack

QUEUES

Similar to a stack, a queue is a linear data structure but it follows the FIFO(First-In First-Out) rule. It means that insertions are done at the rear end and deletions are done at the front end. A good example of a queue is any queue of consumers for a resource where the consumer that came first is served first.

A queue is an important data structure that is used in Breadth First Search traversals. We will read more about BFS later in this article.

The following operations are present with queues:

1. push() – it is used to push new elements to the rear end of the queue.
2. pop() – it is used to delete elements from the front end of the queue.
3. isEmpty()- returns true if the queue is empty, otherwise it returns false.
4. isFull() – returns true if the queue is full
5. size() – returns the size of the queue

LINKED LISTS

A linked list is also a linear and dynamic data structure but it also allows non-contiguous memory allocation unlike arrays. A linked list consists of a linear arrangement of nodes wherein each node has a data and a pointer which points to the next node. Linked lists allows for efficient insertion and deletion of elements as nodes are not stored contiguously in the memory.

The head node in a linked list points is the first node in the sequence and the tail is the last node which points to null pointer.

1. There is no concept of indexing in a linked list and elements can be accessed sequentially unlike arrays where random access was also possible.
2. node→next is the operation that is used to move to the next node in the linked list
3. node→val returns the value of the data element present in a node

The following are the types of linked lists-

a) Singly linked list – Each node is connected only to its next node using a pointer

b) Doubly linked list – A doubly linked list is a type of a linked list that contains pointers to the previous node as well as the next node in the sequence. A doubly linked list provides bidirectional traversal.

For example, node→prev is used to access the node on the immediate left of the current node and node→next is used to access the right node.The previous of the first node and next of the last node will point to null, indicating end of the linked list in each direction .

c) Circular linked list – It is a type of linked list where the last node and the first node are connected with pointers giving the list a cyclic nature.

d) Circular doubly linked list – It is a type of linked list where a doubly linked list forms a cycle. Each node has a prev and a next pointer. The next of the last node points to the first node and the prev of the first node points to the last node.

TREES

Trees are very important data structures which consists of nodes wherein each node has a value, a left pointer and a right pointer. Trees are a non linear and dynamically-growing data structure. Each node has a left child and a right child and the starting node of the tree is called the root.

Let us learn some terminology associated with trees

1. Root – Topmost node of the tree
2. Degree – The degree of a node is the total number of children it has.
3. Leaf node – The node which do not have left and right children.
4. Height – The height of a tree is the total number of edges encountered in the longest path from the root to the leaf node.

Binary trees and Binary Search trees are the two most important type of trees that we will discuss in detail.

A) Binary Trees

A binary tree is a tree data structure in which each node has at most two children called the left child and the right child.

The following operations are possible on a binary tree:

1. Insertion – We can insert a node in a binary tree either by making it the left node or the right node of any existing node.
2. Deletion – Deleting a node from a binary tree can be easily done by replacing the node with it’s left or right child.
3. Traversal – We can traverse a binary tree using BFS (Breadth First Search) or DFS( Depth First Search) traversal methods which include preorder, postorder, inorder traversals and level order traversal respectively.

• Preorder traversal : Node → Left → Right sequence is followed, it means the node is traversed first followed by the left subtree and then the right subtree.
• Postorder traversal : Left → Right → Node sequence is followed, it means the left subtree is visited followed by the right subtree and finally the node is visited.
• Inorder traversal : Left → Node → Right sequence is followed, the left subtree is traversed followed by the node and then the right subtree is traversed.
• Level order traversal : It is a type of BFS traversal wherein the nodes at each level of the tree are visited from the left to right direction.

Some types of binary trees are as follows :

1. Complete binary tree – it is a special type of binary tree in which all the levels of the tree are filled completely except the lowest level which may or may not be completely filled.
2. Perfect binary tree – it is a binary tree in which all the non-leaf nodes have exactly two children and the leaf nodes are at the same level. A perfect binary tree with a depth n has 2^(n+1)-1 nodes in total.
3. Balanced binary tree – The difference between the heights of the left subtree and right subtree is -1 , 0 or 1.

One important application of binary trees is a priority queue which is used to search for maximum and minimum elements present in O(1) time complexity.

B) Binary Search Trees

Binary search tree is also a binary tree with the condition that the left child has a value less than the parent node and the right child has a value greater than the parent node. The left subtree and the right subtree are also binary search trees.

This property provides easy access to elements in a B.S.T. Also, it is interesting to note that the inorder traversal of a binary search tree sorts the nodes in non-decreasing order.

GRAPHS

A graph is a non linear data structure that consists of vertices and edges. It is a collection of vertices(V) and edges(E). A graph G is denoted by G(V, E).

There are two most common ways to represent a graph – Adjacency list and adjacency matrix. An adjacency list stores all the vertices that are connected to a given vertex through an edge whereas an adjacency matrix is a binary matrix which holds a value of 1 if an edge exists between two vertices, otherwise it holds 0.

Operations that can be applied on a graph data structure are insertion , deletion and searching. Two traversal algorithms that can be applied on graphs are Breadth first search and Depth first search .

Some famous graph-based algorithms include Djikstra’s algorithm to find the shortest distance between two nodes in a graph and topological sort algorithm which is used to order the vertices in a Directed Acyclic Graph (DAG).

Property BFS DFS
1. Traversal Explores all nodes at the Explores nodes till the end current level before moving of each level. to the next.
2. Structure Queue data structure is used A stack is used for used
3. Time O(V+E) is the time complexity O(V+E) is the time used
4. Approach Used for searching vertices Used for searching nodes closest to a given node far from a given node

Graphs have widespread applications in the real world. Graphs are used in neural networks to study the human brain, in transportation networks such as airline traffic routes, in computer networking and topology and in social networking sites to cite a few examples.

TRIES

A trie is a tree-like data structure which is used to store a set of strings such that each node represents a character in the string.

The root node of a trie is an empty or null string. The rest of the nodes are characters which when combined in a sequence form a string. Each node in a trie can consist of multiple children nodes to provide a large number of string combinations.

Tries are used for prefix-matching as each node consists of a common prefix of some set of strings. Other applications of tries include dictionaries, autocomplete and lexicographic ordering.