DATA STRUCTURE
Data structure is a set of algorithm that we can use in any programming language such as: C, Python, Java, C++, Ruby, Swift, etc.
Example: Let we have data which have (student name–Ramesh) and (age-24). Here, Ramesh is a string data type and 24 is an integer data type. We can organize these data as record like student record, which will have both name and age. Now, we can collect and store the student record in a database as a data structure. In a simple language, it should be designed and implemented in a way that it reduce the complexity of program and increase efficiency.
| Name | Age |
| Ramesh | 24 |
Here, Name and Age are attributes/fields and Ramesh and 24 are row/tuple.
Classification of Data Structure
Primitive Data Structure
This type of data structure is directly operated by machine instruction.
It can be further classified as:-
Integer: This data type is used to store integer value.
Float: This data type is used to store decimal number with single precision. It takes 4 byte memory space. example: 4.5, 23.9, etc.
Double: It is used to store decimal number with double precision. It takes 8 byte memory space.
Pointer: It is a variable which is used to hold the address of another variable.
Non-Primitive Data Structure
This is complex data structure which is derived from primitive data structure.
It is classified into two categories:-Linear & Non-linear data structures
i) Linear Data Structures
It consists of data elements arranged in sequential manner where every element is connected to its previous and next elements.
Some of them are:-
Array: Array is a collection of similar data types. It is a collection of multiple values in a single variable stored in a contiguous memory location. We can access the element of array by using its index. Array can’t contain dissimilar type of data. Its size always begins with zero index.
Syntax : data type array-name[array-size];
TYPES OF ARRAY
1) single dimensional array
Its dimension is classified by one subscript [ ]. It is also called 1D array.
Syntax : data type array-name[array-size];
2) multi-dimensional array
Its dimension is classified by two or more subscript. Most common multi-dimensional array is two dimensional array (2D array).
Syntax : data type array-name[row-size] [column-size];
Stack: A stack is a fundamental data structure in computer science that follows the Last In, First Out (LIFO) principle. In a stack, elements are added and removed from the top only. This means that the most recently added item is the first one to be removed.
Operations on a stack typically include:
Push: Adds an element to the top of the stack. For every new element added in the stack, top is incremented by 1. If the stack array is filled and no new elements can be added in the stack, it is called stack overflow.
Algorithm for push operation
STEP 1 : START.
STEP 2 : Store the element to push into array.
STEP 3: Check if top== (MAXSIZE-1) then stack is full else go to step 4.
STEP 4 : increment top as top = top+1.
STEP 5 : Add element to the position stack[top]=num.
STEP 6 : STOP.
POP: Removes the top element from the stack. After every POP operation, top of the stack is decremented by 1. If the POP operation is performed when there is no element in the stack, it is called stack underflow.
Algorithm for POP operation
STEP 1 : START.
STEP 2 : Check if top== (-1) then stack is empty else go to step 4.
STEP 3 : Access the element top is pointing number = stack[top];
STEP 4 : Decrease the top by 1 top = top-1;
STEP 6 : STOP.
Queue: A queue is fundamental data structure in computer science, which follows the First In, First Out (FIFO) principle. In a queue, elements are added at the rear (also called enqueue) and removed from the front (also called dequeue). This ensures that the oldest elements are processed first.
Operations on a queue typically include:
Enqueue: Adds an element to the rear of the queue.
Algorithm for Enqueue
Step 1: START
Step 2: Check if the queue is full.
Step 3: If the queue is full, produce an overflow error and exit.
Step 4: If the queue is not full, increment the rear pointer to point to the next space.
Step 5: Add a data element to the queue location, where the rear is pointing.
Step 6: End the process and exit.
Dequeue: Removes the element from the front of the queue.
Algorithm for Dequeue
Step 1: START
Step 2: Check if the queue is empty.
Step 3: If the queue is empty, print underflow and exit.
Step 4: If the queue is not empty, access the data where the front is pointing.
Step 5: Increment the front pointer to point to the next available data element.
Step 6: Set the front and rear as -1 for the last element.
Step 7: End the process and exit.
Linked List
A linked list is a linear data structure consisting of a sequence of elements, called nodes, where each node contains two parts: the data and a reference (or pointer) to the next node in the sequence. Unlike arrays, linked lists do not have a fixed size in memory, and the elements are not stored in contiguous memory locations. Instead, each element (node) points to the next one, forming a chain-like structure.
There are two main types of linked list:-
Singly linked list: In this linked list each node contains data and a single pointer that points to the next node in the sequence. The last node typically points to null to signify the end of the list. We can only access next node in this linked list.
figure : Single linked list
Doubly linked list: Each node contains data and two pointers: one pointing to the next node and another pointing to the previous node. This allows traversal in both forward and backward directions.
fig: doubly linked list
Some operation in linked list are:-
1) Inserting a node at the beginning of the linked list
Algorithm:
Step 1: Create a new node with the given data:
newNode = CreateNode(newData)
Step 2:Set the next pointer of the new node to point to the current head node:
newNode.next = head
Step 3: Update the head pointer to point to the new node:
head = newNode
Step 4: Return the updated head pointer.
2) Inserting a node at the end of the linked list
Algorithm:
Step 1:Create a new node with the given data:
newNode = Node(newData)
Step 2: If the linked list is empty (head is null):
Set head to point to the new node.
Return head.
Step 3: Otherwise, traverse the list until the last node is reached:
Set currentNode to head.
While currentNode.next is not null: Set currentNode to currentNode.next.
Step 4: Set the next pointer of the last node to point to the new node:
currentNode.next = newNode
Step 5: Return the head pointer.
3) Deleting the first node of linked list
Algorithm:
Step 1:If head is null:
Return null , as there is nothing to delete.
Step 2: Set temp to point to the node after the head (head.next).
Step 3: Set head to point to temp.
Step 4: Optionally, free the memory occupied by the original head node.
Step 5: Return the updated head pointer.
4) Deleting the last node of linked list
Algorithm:
Step 1: If head is null or head.next is null (list has 0 or 1 node):
Set head to null and return.
Step 2: Set current-Node to head.
Step 3: While current-Node.next.next is not null: Set current-Node to current-Node.next.
Step 4: Set current-Node.next to null.
Step 5: Optionally, free the memory occupied by the last node.
Step 6: Return the head pointer.
ii) Non-linear data structures
Non-linear data structures are those where each element can be connected to more than one adjacent element, unlike linear data structures where elements are arranged sequentially.
Common examples of non-linear data structures include trees and graphs.
TREE: Trees are hierarchical data structures consisting of nodes connected by edges. Each node contains data. The first node of the tree is called root node.
Basic Terminologies of Tree:-
Path: A path in a tree is a sequence of nodes where each node is connected to its adjacent node by an edge. It starts from a particular node and ends at another node.
Root: The root of a tree is the topmost node. It is the starting point of the tree and hasno parent.
Node: A node is a fundamental unit of a tree. It contains data and may have zero or more child nodes.
Parent Node: A parent node is a node that has one or more child nodes.
Child Node: A child node is a node that is directly connected to another node when moving away from the root.
Leaf Node: A leaf node is a node that does not have any child nodes. It is located at the end of a branch.
Non-leaf Node (Internal Node): A non-leaf node is a node that has one or more child nodes. It is not a leaf node.
Siblings: Siblings are nodes that share the same parent node. They are at the same level in the tree.
Sub-tree: A sub-tree is a portion of a tree that consists of a node and all its descendants. In other words, it is a smaller tree within the larger tree.
Ancestors: Ancestors of a node are the nodes that lie on the path from the root to that node, excluding the node itself.
Descendants: Descendants of a node are all the nodes that are reachable from that node by following its children and their children, recursively.
Degree of a Node: The degree of a node is the number of children it has.
Degree of a Tree: The degree of a tree is the maximum degree of any node in the tree.
Level of a Node: The level of a node is its distance from the root. The root is at level 0, its children are at level 1, and so on.
Depth of a Node: The depth of a node is the length of the path from the root to that node.
Traversing In Tree:
It is the process of accessing or operating on each node in a data collection.
We can traverse tree in 3 orders:-
i) Pre-order (VLR)
Algorithm:
Step 1: visit the Root node (V)
Step 2: Traverse left sub-tree using pre-order(L)
Step 3: Traverse right sub-tree using pre-order(R)
ii) In-order(LVR)
Algorithm:
Step 1: Traverse left sub-tree using In-order(L)
Step 2: visit the root node(V)
Step 3: Traverse right sub-tree using In-order(R)
iii)Post-order(LRV)
Algorithm:
Step 1: Traverse left sub-tree using post-order(L)
Step 2: Traverse right sub-tree using post-order(R)
Step 3: Visit the root node(V)
Traverse the given tree in PRE, IN and POST order
PRE-ORDER: 8, 3, 1, 6, 4, 7 , 10, 13, 14
IN-ORDER: 1, 3, 4, 6, 7 , 8, 10, 13, 14
POST-ORDER: 1, 4, 7, 6, 3, 13, 14, 10, 8
Construct a binary tree using given traversal
Pre-order: 1, 2, 4, 8, 9, 10, 11, 5, 3, 6, 7
IN-order: 8, 4, 10, 9, 11, 2, 5, 1, 6, 3, 7
Binary Search Tree: In this tree, small elements are stored in the left side with the respect of root node and bigger elements with the respect of root node are stored on the right side of the tree.
Figure: Binary search Tree
Graph: It is the pictorial representation of edges and vertices. It is used to represent the relation between objects.
Terminologies of Graph:-
Vertex (Node): A vertex, often referred to as a node, is a fundamental unit of a graph. It represents an entity or an element. In a network diagram, a vertex can represent anything from a person to a city or a website.
Edge: An edge is a connection between two vertices. It can represent a relationship, interaction, or some other connection between the entities represented by the vertices. In a directed graph, edges have a direction indicating the flow or relationship between the vertices.
Adjacent Vertices: Two vertices are adjacent if they are connected by an edge. In an undirected graph, this relationship is symmetric, meaning if vertex A is adjacent to vertex B, then vertex B is also adjacent to vertex A. In a directed graph, adjacency is directional.
Path: A path in a graph is a sequence of vertices where each adjacent pair is connected by an edge. The length of a path is the number of edges it contains. Paths are often discussed in the context of finding routes or connections between different vertices in a graph.
Degree of a Node: The degree of a node in a graph is the number of edges incident to that node. In simple terms, it’s the number of connections or neighbors that a node has. In a directed graph, there are typically separate measures for the in-degree (number of incoming edges) and the out-degree (number of outgoing edges) of a node.
Types of Graph:-
i) Un-directed Graph: In an undirected graph, the edges have no direction associated with them. This means that if vertex A is connected to vertex B, then vertex B is also connected to vertex A. Undirected graphs are often used to represent relationships where the connection between two entities is symmetric, such as friendships in a social network or roads between cities on a map.
ii) Directed Graph: In a directed graph, also known as a digraph, each edge has a direction associated with it. This means that the connection between two vertices is one-way. Directed graphs are used to represent relationships where the connection between two entities is asymmetric or directional, such as following relationships on social media or the flow of traffic in a transportation network.
Operations in Data structure:
Inserting: Insertion involves adding a new element into a data structure at a specified position. Depending on the data structure, insertion might involve simply adding an element at the end (like in a dynamic array), or it might require maintaining certain properties (like in a binary search tree).
Example: Adding a new node to the end of a linked list.
Deleting: Deleting involves removing an existing element from a data structure .Similar to insertion, deletion might require adjusting the structure to maintain its integrity or properties.
Example: Removing a node from a binary search tree while maintaining the binary search tree property.
Searching: Searching of a specific element within a data structure. The efficiency of searching depends on the data structures used. For example: Searching in a sorted array can be done efficiently using binary search.
Example: Searching for a specific value in a hash table or searching for a key in a binary search tree.
Sorting: Sorting is the process of arranging the elements of a data structures in a particular order, either in ascending or descending order. There are various sorting algorithms, each with its advantages and disadvantages in terms of efficiency and space complexity.
Example: Sorting an array using algorithms like bubble sort , insertion sort, merge sort, quicksort, etc.
Traversing: Traversing involves visiting and processing each element of a data structures exactly once. Traversal is often used to perform operations on every element of the data structure, such as printing all elements, calculating the sum of elements, etc.
Example: Traversing a binary tree in preorder, in-order, or post-order.
Merging: Merging involves combining two or more data structures into a single data structure .The process of merging depends on the type of data structures being merged and the desired outcome.
Example: Merging two sorted arrays into a single sorted array, or merging two binary search trees into a single binary search tree.
Advantages of Data Structure:
i) Easier processing of Data
ii) Efficient storage
iii) Efficient designing of Algorithm
iv) Secure way of data storing
v) Accessing of data anytime and anywhere
vi) Graph models real life problems
Applications of Data Structure:
i) Used to store data in computer and other electronic devices
ii) Used to organize data efficiently for easier processing
iii) Traversing of large data becomes easier and effective
iv) Used while making video games
v) Used to store data in the memory before they are permanently saved
vi) Used to provide abstract view of data
vii) Essential for problem solving and developing effective algorithms, etc.