Short Note of Data Structure

 Arrays 

An array is collection of items stored at continuous memory locations. The idea is to declare multiple items of same type together. Array declaration: In C, we can declare an array by specifying its and size or by initializing it or by both.

// Array declaration by specifying size
int arr[10];

// Array declaration by initializing elements
int arr[] = {10, 20, 30, 40};

// Array declaration by specifying size and
// initializing elements
int arr[6] = {10, 20, 30, 40}

Formulas:

  
 Length of Array = UB - LB + 1 

Given the address of first element, address of any other element is calculated using the formula:-

   Loc (arr [k]) = base (arr) + w * k
   w = number of bytes per storage location 
       of for one element 
   k = index of array whose address we want 
       to calculate

Elements of two-dimensional arrays (mXn) are stored in two ways:-

• Column major order: Elements are stored column by column, i.e. all elements of first column are stored, and then all elements of second column stored and so on.

   Loc(arr[i][j]) = base(arr) + w (m *j + i)

• Row major order: Elements are stored row by row, i.e. all elements of first row are stored, and then all elements of second row stored and so on.

   Loc(arr[i][j]) = base(arr) + w (n*i + j)

Stacks

Stack is a linear data structure which follows a particular order in which the operations are performed. The order may be LIFO(Last In First Out) or FILO(First In Last Out).

Basic operations :

Push: Adds an item in the stack. If the stack is full, then it is said to be an Overflow condition. (Top=Top+1) Pop: Removes an item from the stack. The items are popped in the reversed order in which they are pushed. If the stack is empty, then it is said to be an Underflow condition.(Top=Top-1)
Peek: Get the topmost item.

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

Converting between these notations: Click here

Tower of Hanoi is a mathematical puzzle where we have three rods and n disks. The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:

1) Only one disk can be moved at a time.

2) Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.

3) No disk may be placed on top of a smaller disk.

For n disks, total 2n – 1 moves are required 
Time complexity : O(2n) [exponential time]

Queues

Queue is a linear structure which follows a particular order in which the operations are performed. The order is First In First Out (FIFO).  A good example of queue is any queue of consumers for a resource where the consumer that came first is served first. Stack :  Remove the item the most recently added Queue: Remove the item the least recently added Operations on Queue:

Enqueue: Adds an item to the queue. If the queue is full, then it is said to be an Overflow condition.

Dequeue: Removes an item from the queue. The items are popped in the same order in which they are pushed. If the queue is empty, then it is said to be an Underflow condition.

Front: Get the front item from queue.

Rear: Get the last item from queue.

Linked Lists

Linked List is a linear data structure. Unlike arrays, linked list elements are not stored at contiguous location; the elements are linked using pointers.

Advantages over arrays
1) Dynamic size
2) Ease of insertion/deletion
Drawbacks:
1) Random access is not allowed. We have to access elements sequentially starting from the first node. So we cannot do 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 head. If the linked list is empty, then value of head is NULL.
Each node in a list consists of at least two parts:
1) data
2) pointer to the next node In C, we can represent a node using structures. Below is an example of a linked list node with an integer data.

// A linked list node
struct node
{
  int data;
  struct node *next;
};