Algorithms

Design and Analysis

Ch.5: Basic Data Structures
 Objectives
 Memory allocation.
 Understand the concept of Data Structures.
 Appreciate the importance of Abstract Data
structures.
 Understand and use Arrays.
 Understand the concept of Stacks.
 Implement stacks using arrays and linked list.
 Understand the concept of Queues.
 Implement queues using arrays and linked list.
 Understand the Linked List and various
operations on a singly linked list.
 MEMORY ALLOCATION
•While designing a program the programmer should concentrate on to allocate
memory when it is required and to deallocate once its use is over.
•There are two types of memory allocations :
•Static memory allocation or Compile time
•Dynamic memory allocation or Run time
•Static memory
•In static or compile time memory allocations, the required memory is
allocated to the variables at the beginning of the program.
short int i, j; //Two bytes per (total 2) integer variables
float a[5], f; //Four bytes per (total 6) floating point variables

•When the first statement is compiled, two bytes for both the variable 'i‟ and j
will be allocated.
•Second statement will allocate 20 bytes to the array a[5] elements of floating
point type, i.e., 5×4 and four bytes for the variable 'f‟.
 MEMORY ALLOCATION
•Static memory :has following drawbacks.

•Problems

• Again if you try to assign values to 15 elements of an array whose size is

declared as 10, then first 10 elements can be assigned and the other 5
elements cannot be assigned/accessed.

• If you store less number of elements than the number of elements for which
you have declared memory, and then the rest of the memory will be wasted.
That is the unused memory cells are not made available to other applications
(or process which is running parallel to the program) and its status is set as
allocated and not free.
 MEMORY ALLOCATION
•Dynamic memory
•The dynamic or run time memory allocation helps us to overcome this
problem.
•It makes efficient use of memory by allocating the required amount of
memory whenever is needed.
•In most of the real time problems, we cannot predict the memory
requirements.
•Dynamic memory allocation does the job at run time.

C language C++ language

i. malloc( ) i. new
ii. calloc( ) ii. delete
iii. realloc( )
iv. free( )
Dynamic Memory Allocation in C++

 Can allocate storage for a variable while program is running

 Computer returns address of newly allocated variable
 Uses new operator to allocate memory:
double *dptr;
dptr = new double;
Or
dptr = new double[number];//(array)

 new returns address of memory location

The run time input number

 Releasing Dynamic Memory

 Use delete to free dynamic memory:

delete fptr;
 Use [] to free dynamic array:
delete [] arrayptr;
 Only use delete with dynamic memory!
 Types of Data Structures
 The basic data types, provided by a language, like
int, float and char are considered as data structures,
they are called primal data structures.
 The more intricate ones like arrays, stack, queue
linked lists etc., described in the sections that follow
are called non-primal data structures.
 The latter can be linear as in the case of a stack or a
queue or can be non linear like a graph or a tree.
 Abstract Data Types
 Abstract Data Types (ADT) refers to the
abstraction of certain class of types that have
similar behavior.
 Such data structures are defined by the operations
that can be performed on the above said class.
 At times, the restrictions on such operation (s) are
also stated along with.
– Example: Stack.
 The stack ADT has been implemented using both
arrays and linked list in the slides that follow.
 Arrays
An array is a linear data structure, wherein
homogeneous elements are located at
consecutive locations.
An array can be of any standard data
type; for example an integer array, cannot
store a character; a string array would not
store a user defined structure.
A 2-D array contains rows and columns. The
base index of rows is 0 and so is that of a
column.
 2-D Array
 A 2-D array has many applications.

 One of the most important is matrix operations. A matrix is a 2

dimensional array.

– These operations are used in graphics and animations along with

many other things.

 The basic operations like that of addition and subtraction are O(n2)
algorithms.
(For example, a matrix A of order m × n, when added to another
matrix B of the same order, would require the execution of
O(n2) instructions, if m = n, otherwise O(mn))
 2-D Array

• The complexity of conventional matrix

multiplication is O(n3 ).

12
 Stack
 A stack is one of the most important and useful
non-primitive linear data structures in computer
science.
 It is an ordered collection of items into which new
data items may be added/inserted or deleted at only
one end, called the top of the stack.
 As all the addition and deletion in a stack is done
from the top of the stack, the last added element
will be first removed from the stack.
 That is why the stack is also called Last-in-First-
out (LIFO).
 Stack
 The insertion (or addition) operation is referred to
as push, and the deletion (or remove) operation as
pop.
 A stack is said to be empty or underflow, if it
contains no elements. At this point the top of the
stack is present at the bottom of the stack.
 It is overflow when the stack becomes full.
 It can be implemented in a static fashion with the
help of arrays or in a dynamic fashion with the
help of a linked list.
 Stack
The primitive operations performed on a stack are as follows:
 PUSH:
– The process of adding (or inserting) a new element to the top
of the stack.
– After every push operation the top is incremented by one. If
the array is full and no new element can be accommodated,
then the stack overflow condition occurs.

 POP:
– The process of deleting (or removing) an element from the
top of the stack.
– After every pop operation the stack is decremented by one. If
there is no element in the stack and the pop operation is
performed then the stack underflow condition occurs.
Stack
Stack
 Stack
 Stack can be implemented in two ways:
1. Static implementation (using Arrays)
2. Dynamic implementation (using Linked list)
 Static implementation using arrays is a very simple
technique but is not a flexible way.
 Moreover static implementation is not an efficient
method when resource optimization is concerned
(i.e., wasted or not sufficient memory).
Stack
Static Implementation of Stack-
Push() Function:
Algorithm:
push (int item)
{
if (TOP == MAX -1)
{
Print” OVERFLOW”;
}
else
{
TOP++;
a[TOP] = item;
}
}
Static Implementation of Stack-
Pop() Function
Algorithm:

Pop()
{
if (TOP != -1)
{
TOP--;
}
else
{
print “Underflow”;
}
}
APPLICATIONS OF STACKS
There are a number of applications of stacks:
1. Stack is internally used by compiler when we
implement (or execute) any recursive function.
2. Stack is also used to evaluate a mathematical
expression and to check the parentheses in an
expression.
3. Page-visited history in a Web browser. Internet Web
browsers store the addresses of recently visited sites on
a stack.
4. Undo sequence in a text editor. This undo operation in
text editors can be accomplished by keeping text
changes in a stack.
 Queue
 Queue is a linear collection where the elements are
added to one end and removed from the other end.
 It is similar to stack, except that the first item to be
inserted is the first one to be removed.
 The Queue follows the principle of First-In-First-
Out (FIFO).
 Placing an item in a queue is called “enqueue”,
which is done at the end of the queue called “rear”.
 Removing an item from a queue is called
“dequeue”, which is done at the other end of the
queue called “front”.
Queue
 Queue
 A queue can be implemented using an array or a
linked list.
 A queue implemented using an array is referred to
as a static queue while that implemented using a
linked list is called a dynamic queue.
Static Implementation of Queue-
ENQUEUE Function
ALGORITHM FOR ENQUEUE:
Insert_Queue (int VALUE )
{
if (REAR == MAX -1)
{
print “Overflow”;
}
else if (FRONT == REAR == -1)
{
FRONT = REAR = 0;
Queue[REAR] = VALUE;
}
else
{
REAR ++;
Queue[REAR ] = VALUE;
}
}
Static Implementation of Queue-
DEQUEUE Function
ALGORITHM FOR DEQUEUE:
Delete_Queue()
{
if (FRONT== REAR == -1)
{
print: “Underflow”;
}
else if (FRONT == REAR) // only one element
{
FRONT = REAR = -1;
}
else
{
FRONT ++;
}
}
 Example of Insertion and
Deletion in a queue
 In the figure, 12, 14, 16,
18, and 21 are added to a
queue having MAX = 5.
After which, 12 is
deleted. The queue has
empty place. However,
on insertion, the
Overflow condition is
raised as the value of
REAR is MAX - 1.
 OTHER QUEUES
 There are three major variations in a simple
queue:
 Circular Queue
 Double Ended Queue (Deque)
 Priority Queue
 Circular Queue
 Why circular queue:
•After a few insert and delete operations the rear might
reach the end of the queue and no more items can be
inserted although the items from the front of the queue have
been deleted and there is space in the queue.

•To solve this problem, queues implement wrapping

around. Such queues are called Circular Queues.

30
 Circular Queue
 Circular Queue is a linear
data structure in which the
operations are performed
based on FIFO (First In First
Out) principle and the last
position is connected back to
the first position to make a
circle.
 It is also called ‘Ring
Buffer’.
 Circular Queue
At any time the position of the element to be inserted will
be calculated by the relation

Rear = (Rear + 1) % MAX

After deleting an element from circular queue the position

of the front end is calculated by the relation

Front= (Front + 1) % MAX

 If ((REAR +1) % MAX = front), the queue is full and

cannot be inserted anymore.
32
 Circular Queue
ALGORITHM:
Insert_Circular_Queue ()
{
if (REAR = FRONT =-1)
{
REAR = FRONT = 0;
Circular_Queue [REAR] = VALUE;
}
else if (FRONT == (REAR + 1 )% MAX)
{
Print “Overflow”;
}
else
{
REAR = (REAR + 1 )% MAX;
Circular_Queue [REAR] = VALUE;
}
}
 Circular Queue (cont.)
ALGORITHM:
Delete_Circular_Queue()
{
if (REAR = FRONT =-1)
{
Print “Underflow”;
}
else if ( REAR = FRONT) // one element only
{
REAR =FRONT = -1;
}
else
{
FRONT = (FRONT + 1)% MAX;
}
}
 Double Ended Queue (Deque)
 Double Ended Queue or Deque is a generalized
version of Queue data structure that allows insert
and delete at both ends (i.e., new items can be
added at either the front or the rear. likewise,
existing items can be removed from either end).
 Double Ended Queue (Deque)
There are two types of deque depending upon the
restriction to perform insertion or deletion operations at the
two ends. They are
1. Input restricted deque
2. Output restricted deque

An input restricted deque is a deque, which allows

insertion at only 1 end, rear end, but allows deletion at both
ends, rear and front end of the lists.

An output-restricted deque is a deque, which allows

deletion at only one end, front end, but allows insertion at
36
both ends, rear and front ends, of the lists.
 Priority Queue
 Priority Queue is an extension of queue with
following properties.
 Every item has a priority associated with it.
 An element with high priority is dequeued
before an element with low priority.
 If two elements have the same priority, they are
served according to their order in the queue.
 APPLICATIONS OF QUEUE
There are a number of applications of queues:
1. Processor scheduling is implemented using
queue.
2. Printer server routines (in drivers) are
designed using queues.
3. All types of customer service software (like
Railway/Air ticket reservation) are
designed using queue to give proper service
to the customers.
 Linked List
 A linked list is a data structure whose basic unit is
a node.
 Each node has two parts namely: Data and Link.
 The Data part contains the value whereas the Link
part has the address of the next node.
 This helps to connect various nodes of a list.
 The last node of the list has NULL in the link part,
thus indicating that nothing is attached after the
last node.
 In the discussion that follows the first node would
be denoted by FIRST.
 Linked List (cont.)
 In C, a linked list can be created using
structures, the code of which is written as
follows.
struct node
{
int data;
struct node * LINK;
};
 Linked List (cont.)
 In the previous code, node is a structure having data
part, which is of any standard data type and the link,
which is a pointer to the node itself.
 The operators that might be used during the study
of pointers.
 Linked List (cont.)

Figure 1: A list with a single node

Figure 2: A list with two nodes.

Figure 3: A list having 3 nodes.

 Advantages of a Linked List
Linked list have many advantages and some of them are:
 Linked list are dynamic data structure. That is, they can grow or shrink
during the execution of a program.
 Efficient memory utilization: In linked list (or dynamic) representation,
memory is not pre-allocated. Memory is allocated whenever it is required.
And it is deallocated (or removed) when it is not needed
 Insertion and deletion are easier and efficient. Linked list provides flexibility
in inserting a data item at a specified position and deletion of a data item
from the given position.
 Many complex applications can be easily carried out with linked list.
Linked list has following disadvantages
 More memory: to store an integer number, a node with integer data and
address field is allocated. That is more memory space is needed.
 Access to an arbitrary data item is time consuming.
 Creation of a Linked List
 In order to create a linked list, allocate memory to
the node (in case of C, it can be done via malloc()).
 This is followed by setting value in the DATA part
of the node. If one wants to insert a new node, then
the address of the next node is set in the LINK
field.
 If there is just a single node
in the LIST then the LINK of
the first node becomes NULL.
 Insertion at the Beginning– An
Algorithm
ALGORITHM:
Input: VALUE and LIST
Insert_Beg()
{
//Create a node called temp.
struct node * temp;
Allocate memory to temp
//Now put the given value (VALUE) in the data part of temp.
temp-> DATA = VALUE;
//Set the LINK part of temp to FIRST.
temp-> LINK= FIRST;
Rename temp to FIRST
}
Insertion at the Beginning– An
Example
 Insertion at the End
 In order to insert an element at the end, first of all,
a pointer, PTR, is set at the beginning.
 The list is traversed till the LINK of the present
node becomes NULL.
 A new node called TEMP is created, the DATA of
which is set to the given value.
 The LINK of PTR is then set to TEMP. The LINK
of TEMP is then set to NULL, indicating that it has
become the last node.
Insertion at End– An Algorithm
ALGORITHM:
Insert_end ( VALUE)
{
PTR = FIRST;
while (PTR-> LINK != NULL)
{
PTR = PTR-> LINK;
}
Create a new node called TEMP;
SET TEMP-> DATA = VALUE;
SET PTR-> LINK = TEMP;
TEMP-> LINK = NULL;
}
Insertion at End– An Example
 Deleting a Node from the
Beginning– An Algorithm
 In order to delete a node from the beginning, the
DATA of FIRST is first stored in a backup.
 This is followed by renaming the FIRST-> LINK
(node to which the pointer of FIRST points) to
FIRST.
ALGORITHM:
delete_beg()
{
int backup = FIRST-> DATA;
Rename (FIRST->PTR ) as FIRST;
}
 Deleting a Node from the End
 In order to delete a node from the end, first of all we
traverse till the last but one node.
while ((PTR-> LINK)-> LINK != NULL)
 After the above code has been executed, PTR reaches
the last but one node.
 Now save the value of PTR-> LINK in the backup.
int backup = (PTR-> LINK)-> DATA;
 In the final step, the pointer of PTR is set to NULL.
PTR-> LINK = NULL;
Deleting a Node from the End–
An Algorithm
ALGOR ITHM:
delete_end()
{
PTR = FIRST;
while ((PTR-> LINK)-> LINK != NULL)
{
PTR = PTR-> LINK;
}
int backup = (PTR-> LINK)-> DATA;
PTR-> LINK = NULL;
}
 Other Types of Linked Lists

Doubly Linked List

Circular Linked List

 Doubly Linked List
 The node of a linked list may also have two links
namely: PREV and NEXT, such a linked list is
called a doubly linked list.
 There are two NULLs: at the first and last nodes in
the list.
 The insertion and deletion in such a linked list is a
bit involved.
 However, the extra effort pays as this can be used
to represent a number of useful data structures like
a binary tree.
Doubly Linked List (Cont.)

(c) An example of a doubly linked list having 3 nodes.

 Circular Linked List
A circular linked list is one in which the
LINK of the last node points to the FIRST
node.
Here, the circular list can be implemented
both by a singly linked list and a doubly
linked list.

An example of a circular linked list having 3 nodes.

 Advantages of a Linked List
Insertion and deletion in a linked list is
easier as compared to an array.
 Moreover, a linked list does not suffer from
the problem of limited placeholders as with
the case with arrays.
Linked lists are flexible, efficient and
provide more functionality as compared to
an array.
Moreover, the linked list algorithms are
more involved as compared to that of arrays.
 Limitations of Linked Lists
Memory Usage. More memory is required to
store elements in a linked list as compared to
an array. Because in a linked list each node
contains a pointer and it requires extra
memory for storage.
Traversal. A linked list does not allow direct
access to the individual elements. If you
want to access a particular item/node then
you have to start at the head and follow the
references until you get to that item.
 Limitations of Linked Lists
(Cont.)
Reverse Traversing. In linked list reverse
traversing is really difficult. In case of
doubly linked list its easier but extra memory
is required for back pointer hence wastage of
memory.
Time Complexity. Individual nodes are not
stored in the contiguous memory locations.
Access time for an individual element is
O(n) whereas in an array it is O(1).
 However, the advantages of using a linked
list are far more than its disadvantages.
Stack: Dynamic Implementation
ALGORITHM FOR PUSH:
push( int item)
//A node has two parts DATA and NEXT.
//PTR is a pointer to a node.
//FIRST is the first node of the list
//TEMP is a temporary node.
{
PTR=FIRST;
while( PTR-> NEXT !=NULL)
{
PTR = PTR -> NEXT;
}
Create a new node called TEMP.
TEMP-> DATA = item;
TEMP->NEXT = NULL;
PTR->NEXT = TEMP;
}
Stack: Dynamic Implementation
ALGORITHM FOR POP:
Input: None
Output: the element at the TOP of the stack.
// A node has two parts DATA and NEXT.
//PTR is a pointer to a node.
//FIRST is the first node of the list
//TEMP is a temporary node.
Pop()
{
PTR = FIRST;
while ( (PTR-> NEXT)-> NEXT != NULL)
{
PTR = PTR-> NEXT;
}
PTR-> NEXT = NULL;
}
 Key Terms
 Circular linked list a circular linked list is one in which
the NEXT of the last node points to the First node.
 Circular queue In a circular queue, the REAR is connected
to the 0th index of the array.
 Doubly linked list each node in a doubly linked list has
two links namely: PREV and NEXT.
 Linked list a linked list is a data structure whose basic unit
is a node. each node has two parts namely: Data and LINK.
the Data part contains the value whereas the LINK part has
the address of the next node.
 Queue is a linear data structure that follows the principle of
First in First Out.
 Stack is a linear data structure that follows the principle of
Last in First Out.
 Points to Remember
 Abstract data types (ADTs) refer to the abstraction of certain
class of types that have similar behaviour.
 An array is a linear data structure, wherein homogeneous
elements are located at consecutive locations.
 The complexity of linear search is O(n).
 The complexity of addition, subtraction of two matrices of order
n × n is O(n2).
 The complexity of conventional matrix multiplication is O(n3 ).
 Most of the elements in a sparse matrix are 0.
 The insertion and deletion in a linked list are easy as compared
to an array.
 A stack is used in conversion of expressions (like from infix to
postfix), in recursion, etc.
 Points to Remember
 Round Robin algorithm of CPU scheduling uses a queue.
 The static implementation of a stack is done using an array and
the dynamic implementation is done using a linked list.
 Problem of having empty spaces and still showing „overflow‟ in
a linear queue can be solved by using a circular queue.
 If a stack has n elements then the space complexity is O(n) and
the time complexity of each operation is O(1).
 The complexity of insertion or deletion at the beginning in the
linked list is O(1).
 The complexity of insertion at the end in a linked list is O(n).
 The complexity of deletion from the end in a linked list is O(n).
 The complexity of insertion or deletion in the middle of a linked
list is O(n).
 Review Questions
MCQ: ______is a version of a linked list in which
nodes can be navigated in the forward direction
only.
a. Doubly Linked List
b. Singly Linked List
c. Circular Linked List
d. All of the above

Matching:
1. Queue a. LIFO
2. Stack b. FIFI
True or False: The complexity of conventional
matrix multiplication is O(n2 )?
Any Questions?