Data structure:

Module 1:

Data structure:

Data structure is the representation of logical relationship existing between individual

elements of data.
Data structure normally divided into two broad categories.
1. Primitive data structure
2. Non-primitive data structure

Primitive data structure:

Data structures that are directly operated up on the machine level instructions are known as
primitive data structures.
Its types are:
1. Integer
2. Floating point
3. Character
4. Pointer
The most commonly used operations in primitive data structures are:
 Create
 Selection
 Update
 Destroy or delete

Non-primitive data structures:

The data structures that are derived from the primitive data structures are called non-
primitive data structures.
Their commonly known types are:
1. Array
2. List – linear and non-linear
3. Files
Array:

An array is defined as a set of finite number homogeneous data elements.

It means an array can contain one type of data only, either all integers or all characters.
Declaration of an array can be written as: int a[10];
 In the declaration the ‘int’ specifies the data structure,
 ‘a’ is the name of the array and
 The number specified in the square bracket is the number of elements array can
store, this is also called the length or size of the array.
The first element of the array has index 0, it means the first element and last element of an
array with size 10 will be specified as a[0] and a[9] respectively.
Syntax for reading and writing an array is:
1. For reading an array:
for(i=0;i<=9;i++)
{
Cin>>a[i];
}

2. For writing an array:

for(i=0;i<=9;i++);
{
Cout<<a[i];
}

Lists:
A list can be defined as a collection of variable number of data items
It has two fields, one for storing data and other for storing the address of the next element.
Each element is referred to as a node.
They’re categorised into two types:
1. Linear
2. Non-linear
In the case of a linear data structure, the data items are stored in a linear order. Every
element is linked to the first and next elements in the sequence.
In the case of a non-linear data structure, the data pieces are ordered non-linearly and
attached hierarchically. The data elements are linked to several items.
A linear data structure can be a stack or a queue.
Stack:
It is a storage device in which the data that is stored last is the first one to be retrieved.
Queue:
Queues are first-in first-out type of data structure. The first element to be inserted is the
one to the retrieved first.
Non-linear data structures include trees and graphs.
Trees:
A tree can be defined as finite set of data items or nodes. They represent a hierarchical
relationship between the elements.
Graphs:
A graph has vertices and edges. They’re a type of mathematical data structure.

Files:
A file is a collection of related data that a computer treats as a single unit.
A file is a sequence of records.

Sorting:

Sorting of an array is the technique pf arranging the array elements in the specified order.
That is either in ascending order or descending order.
There are four types of sorting:
1. Bubble sorting
2. Selection sort
3. Quick sort
4. Insertion sort

Bubble sorting:
It compares the adjacent elements and swaps them if they are in the wrong order.
Selection sorting:
It selects the smallest or largest element from the array in the beginning of the array, this
process continues until it is sorted.
Quick sorting:
It divides the array into 2 subparts by finding a pivot element.
One part has elements smaller than the pivot element and the other part of it has numbers
larger than it.
Insertion sorting:
When inserting, the elements are inserted one by one, swaps the elements after comparing
to sort them.

Searching:

Searching is used to find the location where element is available or not.

There are two types of searching:
1. Linear searching
2. Binary searching

Linear searching:
In linear search we access each element of an array one by one sequentially and see
whether it is desired or not.
A search will be unsuccessful if the desired element is not found on the array.
Binary searching:
To do binary search, first we need to sort the array elements. (we use quick sorting)
 First find the middle element of the array.
 Compare the middle element with an item.
 There are 3 cases:
 If the desired element is found then the search is successful.
 If the element is smaller than the desired element, then search only the
first half of the array.
 If the element is greater than the desired element, then search the
second half of the array.

Module 2:

Stack:
A stack is an ordered collection of elements like arrays but it has special features such as
deletion of elements and insertion of elements can be done only from one end called top of
the stack.
It is called LIFO due to this feature.
The stack organization has two operations:
1. Push: to insert an element onto the top of the stack. This operation of pushing an
element on top of the stack is called push.
2. Pop: to delete the topmost element.
They can be implemented in 2 ways, static implementation and dynamic implementation,
using arrays and pointers.
Stack underflow is when the stack is empty when we try to call an element and overflow is
when the stack is full and we cannot push more elements into it.

Applications of stack:
 Expression evaluation:
Stack is used to evaluate prefix, postfix and infix expressions.
 Expression conversion:
Stack can be used to convert prefix, postfix and infix expressions.
 Syntax parsing
 String reversal
 Function call
 Backtracking

Notations:

The ways to write arithmetical expressions is known as notations.

They are of three types:
1. Infix notation:
The operator is written in the middle of the operands. For example, A+B.
2. Prefix notation:
The operator is written before the operands. For example, +AB.
3. Postfix notation:
The operator is written after the operands. For example, AB+.
Infix notation to postfix notation (conversion):

The equation to be converted: Q = (A+(B/C+D^E))

Character Contents Postfix

scanned of the expression
from Q stack
( ( -
A ( A
+ (+ A
( (+( A
B (+( AB
/ (+(/ AB
C (+(/ ABC
+ (+(+ ABC/
D (+(+ ABC/D
^ (+(+^ ABC/D
E (+(+^ ABC/DE
) (+ ABC/DE^+
) - ABC/DE^++

Evaluation of a postfix expression:

Evaluating the expression AB+C* if A=2, B=3 and C=4.

 Step 1: First element is operand A, push A to the stack
 Step 2: Second element is operand B, push B also into the stack.
 Step 3: Third element is ‘+’ operator, then pop the two operands A and B and
evaluate the expression A+B = 2+3 = 5.
 Step 4: push the result ‘5’ onto the stack.
 Step 5: next element is C, push it into the stack.
 Step 6: it is ‘*’ operator. Push C and 5 from the stack and evaluate the expression
5*C = 5*4 = 20.
 Step 7: end of the expression, the result is 20.

Queue:

A queue is a non-primitive data structure.

It is a homogeneous collection of elements in which new elements are inserted at one end
called the rear end and the existing elements are deleted from the other end called front
end.
FRONT END 0 1 2 3 4 REAR END

R = -1 and F = -1

10
R = 0 and F = 0

10 20
R = 1 and F = 0

10 20 30
R = 2 and F = 0

10 20 30 40
R = 3 and F = 0

10 20 30 40 50
R = 4 and F = 0

30 40 50
R = 4 and F = 2

40 50
R = 4 and F = 3

50
R = 4 and F = 4

R = 4 and F = 5

Whenever we insert an element into the queue, the value of the rear is incremented by 1,
that is, rear = rear + 1.
During the insertion of the first element both the rear end and the front end increments by
1 from -1 to 0.
After that, the front will not change until an element is deleted.
Whenever we remove an element from the queue, the value of the front is incremented by
1, that is, front = front + 1.

Queue implementation:
1. Static implementation: representation using array.
2. Dynamic implementation: representation using pointers.

Limitations of linear queue:

 Space utilization: Linear queues can be inefficient with memory space because
they don't use empty spaces in the front of the queue until the queue is empty.
 Traversal: Once an element is deleted from a linear queue, it can't be replaced.
 Insertion and deletion: Insertion is done at the rear end, and deletion is done at
the front end

Variations in a queue:

1. Circular queue
2. Double ended queue
3. Priority queue

Circular queue:
To overcome linear queue limitations, the concept of the circular queue was introduced.
A circular queue is similar to a linear queue as it is also based on the FIFO (First In First Out)
principle except that the last position is connected to the first position in a circular queue
that forms a circle. It is also known as a Ring Buffer.

The following are assumptions:

 Front will be always pointing to the first element.
 If front = rear then the queue will be empty.
 Each time a new element is inserted into the queue, the rear end increments by one.
i.e, rear = rear +1
 Each time a new element is removed from the queue, the front end increments by
one.
i.e front = front + 1

Double ended queue:

This contains both insertion and deletion operation are performed at both the ends.
That is it can insert element from the rear end and also from the front end, same goes for
deletion.
There are two types of DE queues:
1. Output restricted
2. Input restricted
There are four operations done in DE queue. Insertion and deletion at the rear end and at
the front end.

Application of queue:
 Round robin scheduling
 Job scheduling
 Keyboard buffer
 Disk scheduling

Module 3:

Linked list:

Linked list can be defined as a collection of objects called nodes that are stored in the
memory.
They are represented by having each element pointing to the next element.
A node contains two fields, info field which stores the data and the pointer field which
stores the address of the next element.
The last node of the list contains pointer to the null.
Advantages:

1. It allocates the memory dynamically. All the nodes of linked list are not stored
nearby in the memory and linked together with the help of pointers.
2. Sizing is no longer a problem since we do not need to define its size at the time of
declaration. List grows as per the program's demand.

Operations on linked list:

1. Creation
2. Insertion
3. Selection
4. Traverse
5. Searching
6. Merging
7. Display
Creation:
It the operation that creates a linked list.
Insertion:
It is used to insert a new node into the linked list at a specified position.
A new node can be inserted:
 At the beginning of the linked list
 At the end of the linked list
 At the specified position of the linked list
 If the list is empty, the new node is added at the beginning of the linked list
Deletion:
It is used to remove a new from the linked list at a specified position.
A node can be removed:
 At the beginning of the linked list
 At the end of the linked list
 At the specified position of the linked list

Traverse:
It is the operation of going through all the nodes of a linked list from beginning to the end.
Searching:
It is the operation in which we search for the desired element in the linked list. If the desired
element is found, the search is successful.
Merging:
It is the process of appending or joining the second list to the end of the first list.
The first list containing m nodes and the second list containing n nodes, the merged linked
list is obtained by m+n.
Display:
It is used to print each and every node in linked list.

Types of linked lists:

1. Singly linked list

2. Doubly linked list
3. Circular linked list
4. Circular doubly linked list

Singly linked list:

It is one in which all node are linked together in some sequential manner. Hence it is calle
linear linked list.
It has a beginning and an end. The problem with this list is that we cannot access the
predecessor node from the current node.

START

INFO INFO X

Doubly linked list:

A doubly linked list is one in which all the nodes are linked together by multiple links, which
help in accessing both the successor and predecessor node within the list.
It has three fields, one for storing the data, one for the address of the predecessor node and
one for the address of the successor node

START

X 10 next prev 20 X
Circular linked list:
A circular linked list is one in which has no beginning or an end.
The last pointer field points to the first element on the linked list.

START

10 20

Doubly linked list:

A circular doubly linked list is one which has both successor and predecessor pointer in
circular manner.

START

10 20

Garbage collection:

Whenever a node is deleted, the memory space becomes reusable for future use. Collecting
these memory spaces from the storage is known as garbage collection.

Module 4:

Tree:
A tree is a recursive data structure containing a set of one or more data nodes where one
node is designated as the root of the tree while remaining nodes are called children of the
root.

Tree terminology contains:

 Root node
 Sub tree
 Leaf node
 Path: the sequence of consecutive edges
 Ancestor node
 Edge
 Degree: number of children of a node
 Level
 Height: maximum level of a tree.

Types of trees:

General tree:
General tree stores the elements in a hierarchical order in which the top level element is
always present at level 0 as the root element.
The nodes in the same level are known as siblings while nodes at different levels have
parent-children relationship.
Forests:
Forest can be defined as a set of subtrees which can be obtained by deleting the node of a
tree.
Binary tree:
Binary tree is a data structure in which each node can have at most 2 children.
Binary search tree:
Binary search tree is an ordered binary tree. All the elements in the left subtree are less than
the root while elements in the right sub tree are greater than or equal to root.

Binary tree:

A binary tree should have at most 2 children. They are generally divided into three disjoint
subsets:
 Root of the node
 Left binary subtree
 Right binary subtree

Types of binary trees:

Strictly binary tree:

In a strictly binary tree, every non-leaf node should contain degree 2.
Complete binary tree:
A binary tree is said to be a complete binary tree if all of the leaves are located at the same
level.
Extended binary tree:
Extended binary tree is a type of binary tree in which all the null sub tree of the original tree
are replaced with special nodes called external nodes and other nodes are called internal
nodes.
Skewed binary tree:
A skewed binary tree is a type of binary tree in which all the nodes have only either one
child or no child.

Binary tree representation:

1. Array representation: root -> left child of root -> right child of root -> left child of LF -> right
child of LF -> left child of RT -> right child of RT
2. Linked list representation: has three nodes, Lchild | data | Rchild

Binary tree operations:

1. Tree traversal
2. Insertion of nodes
3. Deletion of nodes
4. Searching for the node
5. Copying the binary tree
Tree traversal:
 In-order: left child -> root -> right child
 Pre-order: root -> left child -> right child
 Post-order: left child -> right child -> root
Module 5:

File organization, hashing and collision techniques.