Data Structures

Data Structures (DS) tutorial provides basic and advanced concepts of Data Structure. Our Data Structure tutorial is designed for beginners and professionals.

Data Structure is a way to store and organize data so that it can be used efficiently.

Our Data Structure tutorial includes all topics of Data Structure such as Array, Pointer, Structure, Linked List, Stack, Queue, Graph, Searching, Sorting, Programs, etc.

What is Data Structure?

The data structure name indicates itself that organizing the data in memory. There are many ways of organizing the data in the memory as we have already seen one of the data structures, i.e., array in C language. Array is a collection of memory elements in which data is stored sequentially, i.e., one after another. In other words, we can say that array stores the elements in a continuous manner. This organization of data is done with the help of an array of data structures. There are also other ways to organize the data in memory. Let’s see the different types of data structures.PauseNextMute

Duration 18:10

Loaded: 4.04%Fullscreen

The data structure is not any programming language like C, C++, java, etc. It is a set of algorithms that we can use in any programming language to structure the data in the memory.

To structure the data in memory, ‘n’ number of algorithms were proposed, and all these algorithms are known as Abstract data types. These abstract data types are the set of rules.

Types of Data Structures

There are two types of data structures:

• Primitive data structure
• Non-primitive data structure

Primitive Data structure

https://techzone360.shop/data-structures-tutorial/

The primitive data structures are primitive data types. The int, char, float, double, and pointer are the primitive data structures that can hold a single value.

Non-Primitive Data structure

The non-primitive data structure is divided into two types:

• Linear data structure
• Non-linear data structure

Linear Data Structure

The arrangement of data in a sequential manner is known as a linear data structure. The data structures used for this purpose are Arrays, Linked list, Stacks, and Queues. In these data structures, one element is connected to only one another element in a linear form.

When one element is connected to the ‘n’ number of elements known as a non-linear data structure. The best example is trees and graphs. In this case, the elements are arranged in a random manner.

We will discuss the above data structures in brief in the coming topics. Now, we will see the common operations that we can perform on these data structures.

Data structures can also be classified as:

• Static data structure: It is a type of data structure where the size is allocated at the compile time. Therefore, the maximum size is fixed.
• Dynamic data structure: It is a type of data structure where the size is allocated at the run time. Therefore, the maximum size is flexible.

Major Operations

The major or the common operations that can be performed on the data structures are:

• Searching: We can search for any element in a data structure.
• Sorting: We can sort the elements of a data structure either in an ascending or descending order.
• Insertion: We can also insert the new element in a data structure.
• Updation: We can also update the element, i.e., we can replace the element with another element.
• Deletion: We can also perform the delete operation to remove the element from the data structure.

Which Data Structure?

A data structure is a way of organizing the data so that it can be used efficiently. Here, we have used the word efficiently, which in terms of both the space and time. For example, a stack is an ADT (Abstract data type) which uses either arrays or linked list data structure for the implementation. Therefore, we conclude that we require some data structure to implement a particular ADT.

An ADT tells what is to be done and data structure tells how it is to be done. In other words, we can say that ADT gives us the blueprint while data structure provides the implementation part. Now the question arises: how can one get to know which data structure to be used for a particular ADT?.

As the different data structures can be implemented in a particular ADT, but the different implementations are compared for time and space. For example, the Stack ADT can be implemented by both Arrays and linked list. Suppose the array is providing time efficiency while the linked list is providing space efficiency, so the one which is the best suited for the current user’s requirements will be selected.

Advantages of Data structures

The following are the advantages of a data structure:

• Efficiency: If the choice of a data structure for implementing a particular ADT is proper, it makes the program very efficient in terms of time and space.
• Reusability: The data structure provides reusability means that multiple client programs can use the data structure.

Queue

1. A queue can be defined as an ordered list which enables insert operations to be performed at one end called REAR and delete operations to be performed at another end called FRONT.

2. Queue is referred to be as First In First Out list.

3. For example, people waiting in line for a rail ticket form a queue.

Applications of Queue

Due to the fact that queue performs actions on first in first out basis which is quite fair for the ordering of actions. There are various applications of queues discussed as below.PlayNextMute

Current Time 0:11

/

Duration 18:10

Loaded: 5.14%FullscreenBackward Skip 10sPlay VideoForward Skip 10s

1. Queues are widely used as waiting lists for a single shared resource like printer, disk, CPU.
2. Queues are used in asynchronous transfer of data (where data is not being transferred at the same rate between two processes) for eg. pipes, file IO, sockets.
3. Queues are used as buffers in most of the applications like MP3 media player, CD player, etc.
4. Queue are used to maintain the play list in media players in order to add and remove the songs from the play-list.
5. Queues are used in operating systems for handling interrupts.

Complexity

Data Structuree	Time Complexitys								Space Compleity
	Average				Worst				Worst
	Access	Search	Insertion	Deletion	Access	Search	Insertion	Deletion
Queue	θ(n)	θ(n)	θ(1)	θ(1)	O(n)	O(n)	O(1)	O(1)	O(n)

Tree Data Structuree

Introduction:

We read the linear data structures like an array, linked list, stack and queue in which all the elements are arranged in a sequential manner. Some data organizations require data to be categorized into groups and subgroups. The different data structures are used for different kinds of data

Some factors are considered for choosing the data structure:

• What type of data needs to be stored?: It might be a possibility that a certain data structure can be the best fit for some kind of data.
• Cost of operations: If we want to minimize the cost for the operations for the most frequently performed operations. For example, we have a simple list on which we have to perform the search operation; then, we can create an array in which elements are stored in sorted order to perform the binary search. The binary search works very fast for the simple list as it divides the search space into half.
• Memory usage: Sometimes, we want a data structure that utilizes less memory.

What is Tree Data Structure?

A tree is a finite set of nodes in which there is a special node called the root form which the remaining nodes can be portioned into zero, one or more disjoint subsets each of which itself is a tree known as sub tree of T

Suppose we want to show the employees and their positions in the hierarchical form then it can be represented as shown below:PauseNextMute

Current Time 0:16

/

Duration 18:10

Loaded: 5.87%Fullscreen

The above tree shows the organization hierarchy of some company. In the above structure, john is the CEO of the company, and John has two direct reports named as Steve and Rohan. Steve has three direct reports named Lee, Bob, Ella where Steve is a manager. Bob has two direct reports named Sal and Emma. Emma has two direct reports named Tom and Raj. Tom has one direct report named Bill. This particular logical structure is known as a Tree. Its structure is similar to the real tree, so it is named a Tree. In this structure, the root is at the top, and its branches are moving in a downward direction. Therefore, we can say that the Tree data structure is an efficient way of storing the data in a hierarchical way.

Let’s understand some key points of the Tree data structure.

• A tree data structure is defined as a collection of objects or entities known as nodes that are linked together to represent or simulate hierarchy.
• A tree data structure is a non-linear data structure because it does not store in a sequential manner. It is a hierarchical structure as elements in a Tree are arranged in multiple levels.
• In the Tree data structure, the topmost node is known as a root node. Each node contains some data, and data can be of any type. In the above tree structure, the node contains the name of the employee, so the type of data would be a string.
• Each node contains some data and the link or reference of other nodes that can be called children.
• In Tree data structure node does not have any cycles.

Some basic terms used in Tree data structure.

Let’s consider the tree structure, which is shown below:

In the above structure, each node is labeled with alphabets. Each arrow shown in the above figure is known as a link between the two nodes.

• Root: The root node is the topmost node in the tree hierarchy. In other words, the root node is the one that doesn’t have any parent. In the above structure, node numbered A is the root node of the tree. If a node is directly linked to some other node, it would be called a parent-child relationship.
• Node: The node of a tree that stores the data element and may have zero, one, or more links to other descendant nodes for connectivity. It can be a parent, a child, or both.

In the above example, A, B, C etc are the Nodes of a Tree.

• Edge: The link between any of the two nodes is known as Edge. A directed line from one node to another successor node is called an edge of the tree. A tree with ‘N’ number of vertices can have maximum number of edges which we can denote as ‘N-1’.

In the above diagrammatic representation it shows various edges between the nodes. For Example: An edge between vertex A and Vertex C, An edge between vertex B and Vertex D etc.

• Child node: If the node is a descendant of any node, then the node is known as a child node. A parent node can have any number of child nodes. Each node in a tree can have zero or more child nodes.

In the above example, descendants of any node show that child node. For example: node G, node K are children of node D and children of node B. G and H are the left and right child of node C.

• Parent: A parent node can also be denoted as “The node that has child”. If the node contains any sub-node, then that node is said to be the parent of that sub-node.

In the above example, the predecessor of any node shows that Parent node For example: node A, node B and node G etc. are parent nodes.

• Sibling: The nodes that have the same parent are known as siblings.

In the above example, it shows that nodes which have the same Parent are known as siblings. For example: node G node H are siblings.

• Leaf Node:- The node of the tree, which doesn’t have any child node, is called a leaf node. A leaf node is the bottom-most node of the tree. There can be any number of leaf nodes present in a general tree. Leaf nodes can also be called external nodes and Terminal nodes.

In the above example, it shows the various leaf nodes such as node D, F, K etc.

• Internal nodes: A node has atleast one child node known as an internal node and non-terminal nodes in tree data structure.

In the above example, it shows the various internal nodes such as node A, B, C, G etc.

• Ancestor node:- An ancestor of a node is any predecessor node on a path from the root to that node. The root node doesn’t have any ancestors. In the tree shown in the above image, nodes 1, 2, and 5 are the ancestors of node 10.
• Descendant: The immediate successor of the given node is known as a descendant of a node. In the above figure, 10 is the descendant of node 5.
• Degree: The total number of node’s children is called the degree of that node in tree data structure.

In the above diagrammatic representation, we have seen the degree of the various nodes from its starting point to end point. For Example: The degree of node K is 0 and node E is 1 etc.

• Subtree: If a tree is further divided into smaller trees it is called a subtree in the tree data structure. A subtree is a part of a tree that can be viewed as a complete tree in that each child node forms a subtree on its parent node. The following example shows the different subtrees.

• Level: The node’s level is an integer value that measures the node’s distance from the root. For example: the root node is at level 0 and the children of the root node are at its next level (level 1) and so on.

Above diagrammatic representation represents the level 3 starts from the root node i.e. level 0.

• Path: The path is a sequence of consecutive edges and nodes from the source node to another node i.e. destination.

In the above example, the path from node A to node J is “A – B – E – J” and the path has a length of 4.

Properties of Tree data structure

• Recursive data structure: The tree is also known as a recursive data structure. A tree can be defined as recursively because the distinguished node in a tree data structure is known as a root node. The root node of the tree contains a link to all the roots of its subtrees. The left subtree is shown in the yellow color in the below figure, and the right subtree is shown in the red color. The left subtree can be further split into subtrees shown in three different colors. Recursion means reducing something in a self-similar manner. So, this recursive property of the tree data structure is implemented in various applications.
  
• Number of edges: If there are n nodes, then there would n-1 edges. Each arrow in the structure represents the link or path. Each node, except the root node, will have atleast one incoming link known as an edge. There would be one link for the parent-child relationship.
• Depth of node x: The depth of node x can be defined as the length of the path from the root to the node x. One edge contributes one-unit length in the path. So, the depth of node x can also be defined as the number of edges between the root node and the node x. The root node has 0 depth.
  
• Height of node x: The height of node x can be defined as the longest path from the node x to the leaf node.
  

Based on the properties of the Tree data structure, trees are classified into various categories.

Implementation of Tree

The tree data structure can be created by creating the nodes dynamically with the help of the pointers. The tree in the memory can be represented as shown below:

The above figure shows the representation of the tree data structure in the memory. In the above structure, the node contains three fields. The second field stores the data; the first field stores the address of the left child, and the third field stores the address of the right child.

In programming, the structure of a node can be defined as:

1. struct node  
2. {  
3.   int data;  
4. struct node *left;  
5. struct node *right;   
6. }  

The above structure can only be defined for the binary trees because the binary tree can have utmost two children, and generic trees can have more than two children. The structure of the node for generic trees would be different as compared to the binary tree.

Applications of trees

The following are the applications of trees:

• 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.
• Trie: It is a special kind of tree that is used to store the dictionary. It is a fast and efficient way for dynamic spell checking.
• Heap: It is also a tree data structure implemented using arrays. It is used to implement priority queues.
• B-Tree and B+Tree: B-Tree and B+Tree are the tree data structures used to implement indexing in databases.
• Routing table: The tree data structure is also used to store the data in routing tables in the routers.
• Parse Trees: The tree data structure useful in creating parse tree for evaluating arithmetic expressions.

Types of Tree data structure

The following are the types of a tree data structure:

• General tree: The general tree is one of the types of tree data structure. In the general tree, a node can have either 0 or maximum n number of nodes. There is no restriction imposed on the degree of the node (the number of nodes that a node can contain). The topmost node in a general tree is known as a root node. The children of the parent node are known as subtrees.
  
  There can be n number of subtrees in a general tree. In the general tree, the subtrees are unordered as the nodes in the subtree cannot be ordered.
  Every non-empty tree has a downward edge, and these edges are connected to the nodes known as child nodes. The root node is labeled with level 0. The nodes that have the same parent are known as siblings.
• Binary tree: Here, binary name itself suggests two numbers, i.e., 0 and 1. In a binary tree, each node in a tree can have utmost two child nodes. Here, utmost means whether the node has 0 nodes, 1 node or 2 nodes.
  
  To know more about the binary tree, click on the link given below:
  
• Binary Search tree: Binary search tree is a non-linear data structure in which one node is connected to n number of nodes. It is a node-based data structure. A node can be represented in a binary search tree with three fields, i.e., data part, left-child, and right-child. A node can be connected to the utmost two child nodes in a binary search tree, so the node contains two pointers (left child and right child pointer).
  Every node in the left subtree must contain a value less than the value of the root node, and the value of each node in the right subtree must be bigger than the value of the root node.

A node can be created with the help of a user-defined data type known as struct, as shown below:

1. struct node  
2. {  
3.     int data;  
4.     struct node *left;  
5. struct node *right;   
6. }  

The above is the node structure with three fields: data field, the second field is the left pointer of the node type, and the third field is the right pointer of the node type.

To know more about the binary search tree, click on the link given below:

• AVL tree

It is one of the types of the binary tree, or we can say that it is a variant of the binary search tree. AVL tree satisfies the property of the binary tree as well as of the binary search tree. It is a self-balancing binary search tree that was invented by Adelson Velsky Lindas. Here, self-balancing means that balancing the heights of left subtree and right subtree. This balancing is measured in terms of the balancing factor.

We can consider a tree as an AVL tree if the tree obeys the binary search tree as well as a balancing factor. The balancing factor can be defined as the difference between the height of the left subtree and the height of the right subtree. The balancing factor’s value must be either 0, -1, or 1; therefore, each node in the AVL tree should have the value of the balancing factor either as 0, -1, or 1.

To know more about the AVL tree, click on the link given below:

• Red-Black Tree

The red-Black tree is the binary search tree. The prerequisite of the Red-Black tree is that we should know about the binary search tree. In a binary search tree, the value of the left-subtree should be less than the value of that node, and the value of the right-subtree should be greater than the value of that node. As we know that the time complexity of binary search in the average case is log₂n, the best case is O(1), and the worst case is O(n).

When any operation is performed on the tree, we want our tree to be balanced so that all the operations like searching, insertion, deletion, etc., take less time, and all these operations will have the time complexity of log₂n.

The red-black tree is a self-balancing binary search tree. AVL tree is also a height balancing binary search tree then why do we require a Red-Black tree. In the AVL tree, we do not know how many rotations would be required to balance the tree, but in the Red-black tree, a maximum of 2 rotations are required to balance the tree. It contains one extra bit that represents either the red or black color of a node to ensure the balancing of the tree.

• Splay tree

The splay tree data structure is also binary search tree in which recently accessed element is placed at the root position of tree by performing some rotation operations. Here, splaying means the recently accessed node. It is a self-balancing binary search tree having no explicit balance condition like AVL tree.

It might be a possibility that height of the splay tree is not balanced, i.e., height of both left and right subtrees may differ, but the operations in splay tree takes order of logN time where n is the number of nodes.

Splay tree is a balanced tree but it cannot be considered as a height balanced tree because after each operation, rotation is performed which leads to a balanced tree.

• Treap

Treap data structure came from the Tree and Heap data structure. So, it comprises the properties of both Tree and Heap data structures. In Binary search tree, each node on the left subtree must be equal or less than the value of the root node and each node on the right subtree must be equal or greater than the value of the root node. In heap data structure, both right and left subtrees contain larger keys than the root; therefore, we can say that the root node contains the lowest value.

In treap data structure, each node has both key and priority where key is derived from the Binary search tree and priority is derived from the heap data structure.

The Treap data structure follows two properties which are given below:

• Right child of a node>=current node and left child of a node <=current node (binary tree)
• Children of any subtree must be greater than the node (heap)
• B-tree

B-tree is a balanced m-way tree where m defines the order of the tree. Till now, we read that the node contains only one key but b-tree can have more than one key, and more than 2 children. It always maintains the sorted data. In binary tree, it is possible that leaf nodes can be at different levels, but in b-tree, all the leaf nodes must be at the same level.

Graph

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.

Definition

A graph G can be defined as an ordered set G(V, E) where V(G) represents the set of vertices and E(G) represents the set of edges which are used to connect these vertices.

A Graph G(V, E) with 5 vertices (A, B, C, D, E) and six edges ((A,B), (B,C), (C,E), (E,D), (D,B), (D,A)) is shown in the following figure.

Directed and Undirected Graph

A graph can be directed or undirected. However, in an undirected graph, edges are not associated with the directions with them. An undirected graph is shown in the above figure since its edges are not attached with any of the directions. If an edge exists between vertex A and B then the vertices can be traversed from B to A as well as A to B.PauseNextMute

Current Time 0:06

/

Duration 18:10

Loaded: 4.04%Fullscreen

In a directed graph, edges form an ordered pair. Edges represent a specific path from some vertex A to another vertex B. Node A is called initial node while node B is called terminal node.

A directed graph is shown in the following figure.

Graph Terminology

Path

A path can be defined as the sequence of nodes that are followed in order to reach some terminal node V from the initial node U.

Closed Path

A path will be called as closed path if the initial node is same as terminal node. A path will be closed path if V₀=V_N.

Simple Path

If all the nodes of the graph are distinct with an exception V₀=V_N, then such path P is called as closed simple path.

Cycle

A cycle can be defined as the path which has no repeated edges or vertices except the first and last vertices.

Connected Graph

A connected graph is the one in which some path exists between every two vertices (u, v) in V. There are no isolated nodes in connected graph.

Complete Graph

A complete graph is the one in which every node is connected with all other nodes. A complete graph contain n(n-1)/2 edges where n is the number of nodes in the graph.

Weighted Graph

In a weighted graph, each edge is assigned with some data such as length or weight. The weight of an edge e can be given as w(e) which must be a positive (+) value indicating the cost of traversing the edge.

Digraph

A digraph is a directed graph in which each edge of the graph is associated with some direction and the traversing can be done only in the specified direction.

Loop

An edge that is associated with the similar end points can be called as Loop.

Bubble sort Algorithm

In this article, we will discuss the Bubble sort Algorithm. The working procedure of bubble sort is simplest. This article will be very helpful and interesting to students as they might face bubble sort as a question in their examinations. So, it is important to discuss the topic.

Bubble sort works on the repeatedly swapping of adjacent elements until they are not in the intended order. It is called bubble sort because the movement of array elements is just like the movement of air bubbles in the water. Bubbles in water rise up to the surface; similarly, the array elements in bubble sort move to the end in each iteration.

Although it is simple to use, it is primarily used as an educational tool because the performance of bubble sort is poor in the real world. It is not suitable for large data sets. The average and worst-case complexity of Bubble sort is O(n²), where n is a number of items.

Bubble short is majorly used where -PauseNextMute

Current Time 0:05

/

Duration 18:10

Loaded: 3.67%Fullscreen

• complexity does not matter
• simple and shortcode is preferred

Algorithm

In the algorithm given below, suppose arr is an array of n elements. The assumed swap function in the algorithm will swap the values of given array elements.

1. begin BubbleSort(arr)  
2.    for all array elements  
3.       if arr[i] > arr[i+1]  
4.          swap(arr[i], arr[i+1])  
5.       end if  
6.    end for     
7.    return arr     
8. end BubbleSort  

Working of Bubble sort Algorithm

Now, let’s see the working of Bubble sort Algorithm.

To understand the working of bubble sort algorithm, let’s take an unsorted array. We are taking a short and accurate array, as we know the complexity of bubble sort is O(n²).

Let the elements of array are –

First Pass

Sorting will start from the initial two elements. Let compare them to check which is greater.

Here, 32 is greater than 13 (32 > 13), so it is already sorted. Now, compare 32 with 26.

Here, 26 is smaller than 36. So, swapping is required. After swapping new array will look like –

Now, compare 32 and 35.

Here, 35 is greater than 32. So, there is no swapping required as they are already sorted.

Now, the comparison will be in between 35 and 10.

Here, 10 is smaller than 35 that are not sorted. So, swapping is required. Now, we reach at the end of the array. After first pass, the array will be –

Now, move to the second iteration.

Second Pass

The same process will be followed for second iteration.

Here, 10 is smaller than 32. So, swapping is required. After swapping, the array will be –

Now, move to the third iteration.

Third Pass

The same process will be followed for third iteration.

Here, 10 is smaller than 26. So, swapping is required. After swapping, the array will be –

Now, move to the fourth iteration.

Fourth pass

Similarly, after the fourth iteration, the array will be –

Hence, there is no swapping required, so the array is completely sorted.

Bubble sort complexity

Now, let’s see the time complexity of bubble sort in the best case, average case, and worst case. We will also see the space complexity of bubble sort.

1. Time Complexity

Case	Time Complexity
Best Case	O(n)
Average Case	O(n2)
Worst Case	O(n2)

• Best Case Complexity – It occurs when there is no sorting required, i.e. the array is already sorted. The best-case time complexity of bubble sort is O(n).
• Average Case Complexity – It occurs when the array elements are in jumbled order that is not properly ascending and not properly descending. The average case time complexity of bubble sort is O(n²).
• Worst Case Complexity – It occurs when the array elements are required to be sorted in reverse order. That means suppose you have to sort the array elements in ascending order, but its elements are in descending order. The worst-case time complexity of bubble sort is O(n²).

Linear vs Non-Linear data structure

What is Data structure?

A data structure is a technique of storing and organizing the data in such a way that the data can be utilized in an efficient manner. In computer science, a data structure is designed in such a way that it can work with various algorithms. A data structure is classified into two categories:

• Linear data structure
• Non-linear data structure

Now let’s have a brief look at both these data structures.

What is the Linear data structure?

A linear data structure is a structure in which the elements are stored sequentially, and the elements are connected to the previous and the next element. As the elements are stored sequentially, so they can be traversed or accessed in a single run. The implementation of linear data structures is easier as the elements are sequentially organized in memory. The data elements in an array are traversed one after another and can access only one element at a time.

The types of linear data structures are Array, Queue, Stack, Linked List.PauseNextMute

Current Time 0:15

/

Duration 18:10

Loaded: 5.87%Fullscreen

Let’s discuss each linear data structure in detail.

• Array: An array consists of data elements of a same data type. For example, if we want to store the roll numbers of 10 students, so instead of creating 10 integer type variables, we will create an array having size 10. Therefore, we can say that an array saves a lot of memory and reduces the length of the code.
• Stack: It is linear data structure that uses the LIFO (Last In-First Out) rule in which the data added last will be removed first. The addition of data element in a stack is known as a push operation, and the deletion of data element form the list is known as pop operation.
• Queue: It is a data structure that uses the FIFO rule (First In-First Out). In this rule, the element which is added first will be removed first. There are two terms used in the queue front end and rear The insertion operation performed at the back end is known ad enqueue, and the deletion operation performed at the front end is known as dequeue.
• Linked list: It is a collection of nodes that are made up of two parts, i.e., data element and reference to the next node in the sequence.

What is a Non-linear data structure?

A non-linear data structure is also another type of data structure in which the data elements are not arranged in a contiguous manner. As the arrangement is nonsequential, so the data elements cannot be traversed or accessed in a single run. In the case of linear data structure, element is connected to two elements (previous and the next element), whereas, in the non-linear data structure, an element can be connected to more than two elements.

Trees and Graphs are the types of non-linear data structure.

Let’s discuss both the data structures in detail.

• Tree

It is a non-linear data structure that consists of various linked nodes. It has a hierarchical tree structure that forms a parent-child relationship. The diagrammatic representation of a tree data structure is shown below:

For example, the posts of employees are arranged in a tree data structure like managers, officers, clerk. In the above figure, A represents a manager, B and C represent the officers, and other nodes represent the clerks.

• Graph

A graph is a non-linear data structure that has a finite number of vertices and edges, and these edges are used to connect the vertices. The vertices are used to store the data elements, while the edges represent the relationship between the vertices. A graph is used in various real-world problems like telephone networks, circuit networks, social networks like LinkedIn, Facebook. In the case of facebook, a single user can be considered as a node, and the connection of a user with others is known as edges.

Differences between the Linear data structure and non-linear data structure.

	Linear Data structure	Non-Linear Data structure
Basic	In this structure, the elements are arranged sequentially or linearly and attached to one another.	In this structure, the elements are arranged hierarchically or non-linear manner.
Types	Arrays, linked list, stack, queue are the types of a linear data structure.	Trees and graphs are the types of a non-linear data structure.
implementation	Due to the linear organization, they are easy to implement.	Due to the non-linear organization, they are difficult to implement.
Traversal	As linear data structure is a single level, so it requires a single run to traverse each data item.	The data items in a non-linear data structure cannot be accessed in a single run. It requires multiple runs to be traversed.
Arrangement	Each data item is attached to the previous and next items.	Each item is attached to many other items.
Levels	This data structure does not contain any hierarchy, and all the data elements are organized in a single level.	In this, the data elements are arranged in multiple levels.
Memory utilization	In this, the memory utilization is not efficient.	In this, memory is utilized in a very efficient manner.
Time complexity	The time complexity of linear data structure increases with the increase in the input size.	The time complexity of non-linear data structure often remains same with the increase in the input size.
Applications	Linear data structures are mainly used for developing the software.	Non-linear data structures are used in image processing and Artificial Intelligence.
Insertion and Deletion Complexity	In the linear data structure, if we want to insert or delete any element, then there is a need to shift or reorganize subsequent elements, resulting in higher time complexity.	In non-linear data structures, insertion and deletion algorithms are hierarchical in nature. So, they have better performance in comparison to non-linear data structures.
Search Efficiency	The linear data structure is more efficient in accessing the elements based on their index or position.	In the non-linear data structure, it is very difficult to search the elements based on their index or position. So, they have some complex algorithms like depth-first search or breadth-first search, depending on the structure of the data, which can impact search efficiency.
Memory overhead	All the linear data structures need some extra memory to maintain pointers or references between elements, especially in linked lists.	All the non-linear data structures may need some extra memory to store additional structural information, such as parent-child relationships in trees or adjacency lists in graphs.
Parallelism and Concurrency	All the linear data structure some time face some difficulties to avail the optimal parallelism, especially when the data access pattern is sequential or dependent on previous operations.	All the non-linear data structures sometimes become more efficient for parallel processing or concurrent operations due to their hierarchical or interconnected nature, allowing for efficient parallel traversal or computation.
Scalability	All the linear data structures have less limitation in scalability in some scenarios, like when the data organization needs to evolve beyond a simple sequential arrangement.	All the non-linear data structures have better scalability in some scenarios, like when dealing with complex relationships or large datasets, as they can represent intricate connections more naturally.
Traversal Patterns	All the linear data structures provide traversal patterns, such as sequential or LIFO/FIFO traversal in arrays, stacks, and queues.	All the non-linear data structures have different traversal patterns depending on the specific structure, requiring different algorithms for depth-first, breadth-first, or other traversal strategies.

What is a Trie data structure?

The word “Trie” is an excerpt from the word “retrieval“. Trie is a sorted tree-based data-structure that stores the set of strings. It has the number of pointers equal to the number of characters of the alphabet in each node. It can search a word in the dictionary with the help of the word’s prefix. For example, if we assume that all strings are formed from the letters ‘a‘ to ‘z‘ in the English alphabet, each trie node can have a maximum of 26 points.

Trie is also known as the digital tree or prefix tree. The position of a node in the Trie determines the key with which that node is connected.

Properties of the Trie for a set of the string:

1. The root node of the trie always represents the null node.
2. Each child of nodes is sorted alphabetically.
3. Each node can have a maximum of 26 children (A to Z).
4. Each node (except the root) can store one letter of the alphabet.

The diagram below depicts a trie representation for the bell, bear, bore, bat, ball, stop, stock, and stack.

Basic operations of Trie

There are three operations in the Trie:PauseNextMute

Current Time 0:09

/

Duration 18:10

Loaded: 4.77%Fullscreen

1. Insertion of a node
2. Searching a node
3. Deletion of a node

Insert of a node in the Trie

The first operation is to insert a new node into the trie. Before we start the implementation, it is important to understand some points:

1. Every letter of the input key (word) is inserted as an individual in the Trie_node. Note that children point to the next level of Trie nodes.
2. The key character array acts as an index of children.
3. If the present node already has a reference to the present letter, set the present node to that referenced node. Otherwise, create a new node, set the letter to be equal to the present letter, and even start the present node with this new node.
4. The character length determines the depth of the trie.

Implementation of insert a new node in the Trie

1. public class Data_Trie {  
2.     private Node_Trie root;  
3.     public Data_Trie(){  
4.         this.root = new Node_Trie();  
5.     }  
6.     public void insert(String word){  
7.         Node_Trie current = root;  
8.         int length = word.length();  
9.         for (int x = 0; x < length; x++){  
10.             char L = word.charAt(x);  
11.             Node_Trie node = current.getNode().get(L);  
12.             if (node == null){  
13.                 node = new Node_Trie ();  
14.                 current.getNode().put(L, node);  
15.             }  
16.             current = node;  
17.         }  
18.         current.setWord(true);  
19.     }  
20. }  

Searching a node in Trie

The second operation is to search for a node in a Trie. The searching operation is similar to the insertion operation. The search operation is used to search a key in the trie. The implementation of the searching operation is shown below.

Implementation of search a node in the Trie

1. class Search_Trie {  
2.   
3.     private Node_Trie Prefix_Search(String W) {  
4.         Node_Trie node = R;  
5.         for (int x = 0; x < W.length(); x++) {  
6.            char curLetter = W.charAt(x);  
7.            if (node.containsKey(curLetter))   
8.              {  
9.                node = node.get(curLetter);  
10.               }   
11.            else {  
12.                return null;  
13.            }  
14.         }  
15.         return node;  
16.     }  
17.   
18.     public boolean search(String W) {  
19.        Node_Trie node = Prefix_Search(W);  
20.        return node != null && node.isEnd();  
21.     }  
22. }  

Deletion of a node in the Trie

The Third operation is the deletion of a node in the Trie. Before we begin the implementation, it is important to understand some points:

1. If the key is not found in the trie, the delete operation will stop and exit it.
2. If the key is found in the trie, delete it from the trie.

Implementation of delete a node in the Trie

1. public void Node_delete(String W)   
2. {  
3.     Node_delete(R, W, 0);  
4. }  
5.    
6. private boolean Node_delete(Node_Trie current, String W, int Node_index) {  
7.     if (Node_index == W.length()) {  
8.         if (!current.isEndOfWord()) {  
9.             return false;  
10.         }  
11.         current.setEndOfWord(false);  
12.         return current.getChildren().isEmpty();  
13.     }  
14.     char A = W.charAt(Node_index);  
15.     Node_Trie node = current.getChildren().get(A);  
16.     if (node == null) {  
17.         return false;  
18.     }  
19.     boolean Current_Node_Delete = Node_delete(node, W, Node_index + 1) && !node.isEndOfWord();  
20.    
21.     if (Current_Node_Delete) {  
22.         current.getChildren().remove(A);  
23.         return current.getChildren().isEmpty();  
24.     }  
25.     return false;  
26. }  

Applications of Trie

1. Spell Checker

Spell checking is a three-step process. First, look for that word in a dictionary, generate possible suggestions, and then sort the suggestion words with the desired word at the top.

Trie is used to store the word in dictionaries. The spell checker can easily be applied in the most efficient way by searching for words on a data structure. Using trie not only makes it easy to see the word in the dictionary, but it is also simple to build an algorithm to include a collection of relevant words or suggestions.

2. Auto-complete

Auto-complete functionality is widely used on text editors, mobile applications, and the Internet. It provides a simple way to find an alternative word to complete the word for the following reasons.

• It provides an alphabetical filter of entries by the key of the node.
• We trace pointers only to get the node that represents the string entered by the user.
• As soon as you start typing, it tries to complete your input.

3. 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.

Advantages of Trie

1. It can be insert faster and search the string than hash tables and binary search trees.
2. It provides an alphabetical filter of entries by the key of the node.

Disadvantages of Trie

1. It requires more memory to store the strings.
2. It is slower than the hash table.