Last minute notes on Data Structures | GATE Preparation | All In One

Article by: Manish Methani

Last Updated: October 3, 2021 at 2:04pm IST

In this article, you will find the last-minute notes of Data Structures useful in the preparation of the GATE CSE exam.
Easy to remember Short formulas used for solving the problems is the bonus for you.

Arrays 

An array is a data structure used to store values of the same type.

Syntax:

Array declaration by specifying its size

int arr[10];
 

Initialise elements in an array
int arr[] = {2,4,6,7};

Specify size and initialise elements
int arr[5] = {2,4,6,8,10};

Formula:

Length of Array = UB - LB + 1

How to find the address of any element with the given address of the first element in an array,

Formula:

Loc (arr [i]) = base (arr) + size * i
size = size is the number of bytes required to store a single element of the array arr.

i = index of an array whose address we want to calculate

Elements of two-dimensional arrays (m X n) are stored in two ways:

Column Major order Storage

Column major order: If an array is declared by a[m][n] where m is the number of rows while n is the number of columns, then the address of an element a[i][j] of the array stored in column-major order is calculated as,

The formula is:

LOC (arr [i, j]) = Base Address + [(i - Lr) + nr(j - Lc)]*datatype size

Here,

LOC (arr [i,j]): is the location of the element in the ith row and jth column.

Base (arr): is the base address of the array arr.

nc => number of columns in the main array.

nr => number of rows in the main array.

Lr => Lower bound of base array row.

Lc => Lower bound of base array column.

Row Major order Storage

Row major order: If the array is declared by a[m][n] where m is the number of rows while n is the number of columns, then the address of an element a[i][j] of the array stored in row-major order is calculated as,

LOC (arr [i, j]) = Base Address + [nc(i - Lr) + (j - Lc)]*datatype size

Here,

LOC (arr [i,j]): is the location of the element in the ith row and jth column.

Base (arr): is the base address of the array arr.

nc => number of columns in the main array.

nr => number of rows in the main array.

Lr => Lower bound of base array row.

Lc => Lower bound of base array column.

Stack

Stack is a linear data structure in which operations are performed in two ways.

1) LIFO (Last In First Out)

2) FILO (fIRST INLAST OUT) 

Basic operations :

1. Push: push() function is used to insert new elements into the Stack and pop() function is used to remove an element from the stack. Both insertion and removal are allowed at only one end of Stack called Top.
2. Stack is said to be in an Overflow state when it is full and is said to be in an Underflow state if it is empty.

Infix, prefix, Postfix notations

Infix notation: X + Y Operators are written in-between their operands. This is the usual way we write expressions. An expression such as

A * ( B + C ) / D

Postfix notation (also known as “Reverse Polish notation”): X Y + Operators are written after their operands. The infix expression given above is equivalent to

A B C + * D/

Prefix notation (also known as “Polish notation”): + X Y Operators are written before their operands. The expressions given above are equivalent to

/ * A + B C D

Tower of Hanoi

1. It is a classic problem where you try to move all the disks from one peg to another peg using only three pegs.

2. Only one disk will be shifted at a time.

3.Smaller disk can be placed on the larger disk.

The time complexity to find the order of moves of discs in the Tower of Hanoi problem is O(2^n).

Queue

A queue is a linear structure in which the first element is inserted from one end called the REAR(also called the tail), and the removal of the existing element takes place from the other end called FRONT(also called the head).

 The order which queue follows is First In First Out (FIFO).

Enqueue: Adds an item to the queue. 

Algorithm for ENQUEUE operation

1. Check if the queue is full or not.
2. If the queue is full, then print the overflow error and exit the program.
3. If the queue is not full, then increment the tail and add the element.

Dequeue: Removes an item from the queue.

Algorithm for DEQUEUE operation

1. Check if the queue is empty or not.
2. If the queue is empty, then print underflow error and exit the program.
3. If the queue is not empty, then print the element at the head and increment the head.

Linked List

The linked list is a linear data Structure used to store elements dynamically. No need to know the actual size. In the case of arrays, you must know the size of an array. Linked List in Data Structure gives better advantages than arrays.

ArrayList vs Linked List

The difference between Array and the Linked list is explained here by the advantages of Linked List over Arrays.

1) Dynamic size 

2) Insertion/Deletion is easy in Linked List.

Drawbacks:

1) Random access is not allowed. We have to access elements sequentially starting from the first node. So we cannot do a binary search with linked lists.

2) Extra memory space for a pointer is required with each element of the list.

Representation in C: A linked list is represented by a pointer to the first node of the linked list. The first node is called the head. If the linked list is empty, then the value of the head is NULL.