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

Basic 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;

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

Specify size and initialise elements
int arr = {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: + 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.

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.

How was the tutorial? Nice. Right?

## What is your Interview Score?

Test your skillset with the curated questions created by experts around the globe.

Book a free test slot. Now !.

It usually takes 30 mins for an online test and this test will be MCQ based. Get detailed analytics based on your test and recommedations with personalised roadmaps.

Book a test slot. Now!

## Have questions about the trial coding class?

Chat with our experts to discuss

Connect on WhatsApp

## Recommended tutorials

#online compiler for c     #python for programming

#dfs and bfs algorithm     #programming with c language

#storageclass in C    #listcomprehension in python