Table of Contents
DATA STRUCTURE IMPORTANT SHORT NOTES
What is Data Structure?
Data Structure is a process to store and organize data in a well-defined manner so that it can be used efficiently.
Types of Data Structures
There are two types of data structures:
- Primitive data structure
- Non-primitive data structure
Primitive Data structure:
The primitive data structures are primitive data types. Such as int, char, float, double, and pointer are the primitive data structures that can hold a single value.
Non-Primitive Data structure:
Non-primitive data structures are the data structures that are created using primitive data structures.
Some of the Non-primitive data structures are linked lists, stacks, trees, and graphs.
The non-primitive data structure is divided into two types:
- Linear data structure
- Non-linear data structure
Linear Data Structure:
Linear Data Structure is Data Structure where data elements are arranged sequentially, each element is attached to its previous and next adjacent.
Example: Array, Stack, Queue, and Linked List
1. ARRAY:
The array is a linear data structure that stores similar data elements at contiguous memory locations.
2. STACK:
Stack is another linear data structure where elements stored in data structure follows LIFO(Last in first out) means last data which added get removed first.
In Stack, only one end allows the insertion and deletion of data.
Example: Book Stacked Together. In order to access the last book, we have to remove all books placed over it.
3. QUEUE:
The queue is also a Linear data structure that is similar to Stack but it follows FIFO(First in First out) means Data added first is to remove first.
In Queue both ends are used for insertion and deletion of data.
There are two terms in Queue FRONT(head) and REAR(tail).
Two main operations of Queue are:
Enqueue: Process to add an element in Queue.
Dequeue: Process to remove an element from Queue.
NOTE: Enqueue(insertion) always occur at rear(tail) side while Dequeue(deletion/removal) always occurs at Front(head) side.
Algorithm for Enqueue :
- Check if Queue is full or not.
- If Queue is full then print Overflow and Exit.
- If Queue is not full then , increment tail and add elements.
Algorithm for Dequeue:
- Check if Queue is empty or not.
- If Queue is empty then print underflow error and Exit.
- If Queue is not empty then ,print element at head and increment head
4.LINKED LIST:
Linked list is linear data structure in which data is stored in forms of Nodes and each nodes is connected to next
data via – pointer and formed a chain.
NODE: A node in a linked list holds data value and pointer which points to the location of next node in linked list.
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.
Example: Tree and Graph
1. TREE:
Tree Data structure consist of various nodes linked together.
Structure of a Tree is hierarchical that forms a relationship like that of a parent and child.
Example: AVL, Binary, Binary search
2. GRAPH:
Graph are those types of non-linear data structures that consist of a definite quantity of vertices and edges.
NOTE: Difference between Graph to a Tree is that in Graph there are no specific rules for the connection of nodes.
SOME BASIC TERMS RELATED TO DATA STRUCTURE
Algorithm: An algorithm is a set of instructions or logic for solving a problem step by step.
Space Complexity: Space complexity is defined as amount of memory used by an algorithm to execute and produce output.
Time Complexity: Time complexity is defined as the amount of time taken by an algorithm to execute and return output.
SORTING
Sorting arranges data in a sequence manner which make searching of data easier.
It can be done in ascending or descending order.
TYPES OF SORTING
BUBBLE SORT: Bubble sort compares all element one by one and sort them based on their values.
INSERTION SORT: In Insertion Sort array is sorted by shifting elements one by one according to their values.
SELECTION SORT: In this sorting technique first find the smallest element in the array and exchange it with the first element of the array then find the second smallest and replace it with the 2nd element and so on until the array gets sorted.
QUICK SORT:
Based on the Divide and Conquer rule.
This algo divide the list into three parts:
- Element less than Pivot Element.
- Pivot Element(which is selected first by an algorithm to do certain calculations).
- Element greater than pivot element
MERGE SORT: In merge sort, the unsorted list is divided into N sublists each having one element.
Then, repeatedly merge these sublists to produce a new sorted sublist.
HEAP SORT: Similar to selection sort but here we have to find the greatest element in the array and replace it with the first element and again find the second greatest element and replace it with the second element and so on until the array gets sorted.
Graph Representations
In graph theory, a graph representation is a technique to store graphs into the memory of the computer.
To represent a graph, we just need the set of vertices, and for each vertex the neighbours of the vertex (vertices which are directly connected to it by an edge).
If it is a weighted graph, then the weight will be associated with each edge.
There are two ways to store Graphs into the computer’s memory.
1. Sequential Representation
In sequential representation, we use an adjacency matrix to store the mapping represented by vertices and edges.
Adjacency Matrix:
- Adjacency matrix is a sequential representation.
- It is used to represent which nodes are adjacent to each other. i.e. is there any edge connecting nodes to a graph.
- In this representation, we have to construct a nXn matrix A. If there is any edge from a vertex i to vertex j, then the corresponding element of A, ai,j = 1, otherwise ai,j= 0.
- If there is any weighted graph then instead of 1s and 0s, we can store the weight of the edge.
2. Linked Representation
In the linked representation, an adjacency list is used to store the Graph in the computer’s memory.
Adjacency List:
- Adjacency list is a linked representation.
- In this representation, for each vertex in the graph, we maintain the list of its neighbors. It means, every vertex of the graph contains list of its adjacent vertices.
- We have an array of vertices which is indexed by the vertex number and for each vertex v, the corresponding array element points to a singly linked list of neighbors of v.
For more info GRAPH REPRESENTATION
DEPTH FIRST SEARCH(DFS):
DFS is an edge-based technique.
It uses a stack data structure that follows LIFO.
It performs two stages :
- first visited ones are pushed into stack and
- second if there is no vertices then visited are popped out.
BREADTH FIRST SEARCH(BFS):
BFS is a vertex-based technique for finding the shortest path in the graph.
It uses a Queue Data structure that follows FIFO.
In BFS :
- one vertex is selected at a time when it is visited and marked then
- its adjacent are visited and stored in queue.
SPANNING TREE:
Spanning Tree is a subset of Graph G1 which has all vertices covered with the minimum possible number of edges.
Minimum Spanning Tree:
A minimum spanning tree is a spanning tree that has minimum weight than all other spanning trees of the same graph.
Application of Minimum spanning tree: Cluster analysis, Handwriting recognition and image segmentation
Prim’s Algo:
Prim’s algo uses the greedy approach as in this algo we grow a spanning tree from a starting position and add a vertex to the growing spanning tree.
Time Complexity: O(V+E)logV
Kruskal’s Algo :
This algo follow the greedy approach as in each iteration it finds an edge which has the least weight and adds it to growing spanning tree.
Time Complexity: O(E logV)
Binary Tree :
A binary tree is a special type of data structure in which every node can have a maximum of 2 children, which are known as Left child and Right Child.
Binary Traversal :
Binary traversal is the process of accessing every node of a tree and exactly once.
There are three techniques of traversal:
- Preorder Traversal
- Postorder Traversal
- Inorder Traversal
1. Preorder Traversal
Algorithm for preorder traversal
Step 1 : Start from the Root.
Step 2 : Then, go to the Left Subtree.
Step 3 : Then, go to the Right Subtree.
2. Postorder Traversal
Algorithm for postorder traversal
Step 1 : Start from the Left Subtree (Last Leaf).
Step 2 : Then, go to the Right Subtree.
Step 3 : Then, go to the Root.
3. Inorder Traversal
Algorithm for inorder traversal
Step 1 : Start from the Left Subtree.
Step 2 : Then, visit the Root.
Step 3 : Then, go to the Right Subtree.
AVL TREE
AVL tree is a binary search tree in which the difference of heights of left and right subtrees of any node is less than or equal to one.
The technique of balancing the height of binary trees was developed by Adelson, Velskii, and Landi and hence given the short form as AVL tree or Balanced Binary Tree.
Representation of AVL Trees:
Struct AVLNode
{
int data;
struct AVLNode *left, *right;
int balfactor;
};
Hash table
A hash table is a type of data structure that stores key-value pairs. The key is sent to a hash function that performs arithmetic operations on it. The result (commonly called the hash value or hash) is the index of the key-value pair in the hash table.
For more info about HASH TABLE
BASIC TERMONOLOGY OF TREE IN DATA STRUCTURE:
Root node:
The root node R is the topmost node in the tree. If R = NULL, then it means the tree is empty.
Edge:
- The connecting link between any two nodes is called as an edge.
- In a tree with n number of nodes, there are exactly (n-1) number of edges.
Parent:
- The node which has a branch from it to any other node is called as a parent node.
- In other words, the node which has one or more children is called as a parent node.
- In a tree, a parent node can have any number of child nodes.
Child:
- The node which is a descendant of some node is called as a child node.
- All the nodes except root node are child nodes.
Siblings:
- Nodes which belong to the same parent are called as siblings.
- In other words, nodes with the same parent are sibling nodes.
Degree:
- Degree of a node is the total number of children of that node.
- Degree of a tree is the highest degree of a node among all the nodes in the tree.
Internal Node/Non-Terminal Node:
- The node which has at least one child is called as an internal node.
- Internal nodes are also called as non-terminal nodes.
- Every non-leaf node is an internal node.
Leaf Node/Terminal Node:
- The node which does not have any child is called as a leaf node.
- Leaf nodes are also called as external nodes or terminal nodes.
Level:
- In a tree, each step from top to bottom is called as level of a tree.
- The level count starts with 0 and increments by 1 at each level or step.
Height:
- Total number of edges that lies on the longest path from any leaf node to a particular node is called as height of that node.
- Height of a tree is the height of root node.
- Height of all leaf nodes = 0
Depth:
- Total number of edges from root node to a particular node is called as depth of that node.
- Depth of a tree is the total number of edges from root node to a leaf node in the longest path.
- Depth of the root node = 0
- The terms “level” and “depth” are used interchangeably.
Subtree:
- In a tree, each child from a node forms a subtree recursively.
- Every child node forms a subtree on its parent node.
Forest:
A forest is a set of disjoint trees.
Leave a comment