IT T33- Data Structures

UNIT I
Basics: Abstract Data Type (ADT) - Introduction to Data Structures – Representation –
Implementation
Stack and List: Representation of Stack – Implementation – Application – Balancing Symbols –
Conversion of infix to postfix expression – Evaluating a postfix expression - Recursive function call
– Linked list ADT – Implementation using arrays – Limitations – Linked list using dynamic
Variables – Linked implementation of stacks – Circular list – Doubly Linked List

Objective
 To introduce the primary data structures and their associated operations
 Understand The concepts of linear data structure stack and its applications
 To introduce the concept of different types of linked lists

Outcome:
 Able to use the different types of data structures , stack and linked list concepts

1.1 Introduction to Data Structures

Data - A collection of facts, concepts, figures, observations, occurrences in a formalized manner.

Example: light, 10, 11.5.

1.1.1 Data Type

A data type is a term which refers to the kind of data that variables may hold in the
programming language.
Example: int, float, char,

Types of data types

 Built-in data types
 User defined data types

Built-in data type

The data type which is defined by the programming language itself is called built-in data
type.
Example: int, float, char, etc.

User defined data type

User defined data type can be defined using built in data types. In other words, using the
set of built-in data type user can define their own data type.

Example:
Array Structure
int regno[10]; typedef struct Stud
float marks[10]; {
char result[20]; int a;
-----
-----;
}s;

SMVEC- Department of Information Technology 1

IT T33- Data Structures
1.1.2 Data Structures:

Definition 1: A data structure is logical way of storing and organizing data either in
computer's memory or on the disk storage so that it can be used efficiently.

Definition 2: A data structure is defined as collection of elements and all possible operations
which are required for those set of elements.

1.1.3 Classification of data structure

Primary data structure

Primary data structure is the basic data structure that directly operates upon the machine
instruction. They have different representation on different computers.
Example:
8085 8086 Motorola Dual Core
int 2 byte 3 byte 1 byte 4 byte
float 3 byte 4 byte 5 byte 6 byte

Secondary data structure

Secondary data structure are more complicated data structures derived from primary data
structures.
Example: array, structure

Secondary data structure can be classified as:

1. Static Data Structure
2. Dynamic Data Structure

SMVEC- Department of Information Technology 2

IT T33- Data Structures
Static data structure (Finite Size Data Structure)
 Static data structure is created using static memory allocation (data structure form when
the number of data items are known in advance).
 The size will be known during the compilation time itself.

Example: array and structure

Dynamic data structure (Variable size Data Structure)

Dynamic data structure is created using dynamic memory allocation (data structure form
when the number of data elements are not known in advance).

Dynamic data structure can be classified as:

1. Linear Data Structure: Have a linear relationship between its adjacent elements.
Example: List
2. Non-Linear Data Structure: Do not have a linear relationship between its adjacent
elements, but have the hierarchical relationship.
Example: Tree

Tree Graph
A tree is a non-linear dynamic data structure A graph is similar to the tree except that it
that may point to one or more nodes at a has no hierarchical relationship between its
time. adjacent elements.

1.1.4 Difference between static and dynamic implementation of data structures

Static implementation of list Dynamic implementation of list
Memory must be allocated continuously. Memory can be allocated anywhere and are
linked together using linked list.
Memory will be wasted. Utilization of memory Utilization of memory is effective.
is poor.
Insertion and deletion operations are time Insertion and deletion operations are not time
consuming due to „SHIFT‟ operations. consuming.
Any element in the list can be accessed Elements can be accessed randomly.
sequentially.
There is a limitation on number of values in a There is no limitation on number of values in a
list because of fixed size of array. list.
Memory is allocated and reallocated for the Since the size of the list is known only at the
list at compile time because the size of the run time memory allocation and reallocation
list will be known in compile time only. are done at run time only.

SMVEC- Department of Information Technology 3

IT T33- Data Structures
1.1.5 Applications of data structure :
 Operating systems.
 Data Base Management System (DBMS).
 Compiler Design.
 Network Analysis

1.2 Abstract Data Type (ADT)

 The Abstract Data Type (ADT) is a set of operations .They are the mathematical abstractions
and define how the set of operations are implemented.
 In Abstract Data Type all the implementation details are hidden.

ADT = Type + Function + Behavior of each function

The ADT is a combination of
„D‟ - Set of domains
„F‟ - Set of functions
„A‟ – Set of axioms in which only what to be done is mentioned but how it has to be
done is not mentioned

Instances-Instances represent the element on which various operations can be performed.

Operations- Operations represent basic operation that can be performed on those elements.

1.2.1 Array ADT

Array is collection of similar data elements in contiguous memory location.
Instance: An array of some size, index i and total number of elements in the array is n.
Operations:

Store() This operation stores the desired element at each successive

location.
Search() This operation searches the specific element from the list of elements
in the array.
Display() This operation displays all the elements in the array.

Sort() This operation arranges the elements in ascending or descending

order of an array.

1.2.2 LIST ADT

In a linked list, each element is called a node. Every node in the list points to the next node
in the list.

Instance: List is an ordered set of elements.

The general form of the list is A1 A2, A3 . . . . . An

A1, - First element of the list

An,- Last element of the list
N - Size of the list If the element at position i is A. then its successor (next) is Ai+1 and its
predecessor (previous) is Ai-1.

SMVEC- Department of Information Technology 4

IT T33- Data Structures
Operations:

Operations Axioms
createlist() Create an initialized list object.
destroylist() Free the memory allocated for the list.
getdata() Returns the data stored in the current node or index.
getcount() Returns the number of elements in the list.
inserrtfirst() Insert a new element in the first position of the list.
insertintermediate() Insert a new element in any intermediate position of the list.
insertlast() Insert a new element in the last position of the list.

Note: The list ADT can be used as the building block for many other types of abstract data type
such as STACK ADT and QUEUE ADT.

1.3 Stack ADT

 Stack is a linear data structure in which data is added and removed at only one end.
 The end from which the elements are added and deleted is referred as the „top’ of the
stack.
 Thus, the last element that is pushed into the stack, is the first element to be popped out of
the stack, so it is called as Last In First Out (LIFO).
 Stack is also referred as PILES or PUSH down list.

The primary operations that can be carried out on the stack are:

1. PUSH (Insertion)
2. POP (Deletion)
3. PEEK(Display the top of the stack)
4. DISPLAY

Two ways of implementation of Stack:

 Static implementation of stack using array

 Dynamic implementation of stack using linked list

1.3.1 Static Implementation of Stack Using ARRAY

 The simplest way of representing a stack is by single dimensional array.

 In array, the number of elements in the array is fixed, not possible to change the number of
elements through the operation insertion and deletion.
 In stack, the size of the stack varies continuously when elements are pushed and popped.
 One end of the array (bottom of the sack) is fixed and the other end of the array (top of
the stack) is continuously changed depending upon the elements pushed or popped in
the stack.

SMVEC- Department of Information Technology 5

IT T33- Data Structures

1.3.2 Basic Operations

PUSH
 The procedure of inserting a new element tothe top of the stack is known as Push
Operation.
 While implementing push the overflow condition is checked to prevent pushing an element
,when the stack is full

Algorithm push(stack, top, stacksize)

{
if top=stacksize-1
{
write "Stack overflow. Push operation not possible.";
return;
}
read rollno;
top=top+1;
stack[top]=rollno;
}

POP
 The procedure of removing element from the top of the stack is called Pop Operation
 While implementing the pop operation, the underflow condition is checked to prevent pop
out an element ,when the stack is empty.

Algorithm pop(stack, top, stacksize)

{
if top=-1
{
write "Stack underflow. Pop operation not possible.";
return;
}
write "The element to be deleted.",stack[top];
rollno=stack[top];
top=top-1;
write rollno;
return;
}

PEEK
 Peek operation is used to display the element from the stack pointed by the point by
top.
 While implementing the peek operation, the underflow condition is checked to prevent
peek,when the stack is empty.

SMVEC- Department of Information Technology 6

IT T33- Data Structures
Algorithm peek(stack,top)
{
if top=-1
{
write "Stack underflow. Peek operation not possible.";
return;
}
write stack[top];
return;
}

DISPLAY
 To read or display the element from the stack, traverse in the stack from top to 0th position.
 Thee underflow condition of the stack is to be checked to avoid retrieving an element from
empty stack.
Algorithm display(stack,top)
{
if top=-1
{
write "Stack is in underflow condition. Peek operation is not possible.";
return;
}
for i=top to step-1
{
write stack[top];
}
return;
}

Example for Stack Operations

1.4 Dynamic Implementation of Stack Using Linked List

1.4.1 Problems with Array Implementation of Stack:

 The size of the stack must be determined when a stack is declared i.e during compile time
 Space is wasted if we use less elements
 We cannot "push" more elements than the array can hold
1.4.2 Creating Linked Stack Data Structure:
 Allocate memory for each new element dynamically at run time, the stack can grow and
shrink in size without wasting the memory space.
 Each node in the stack should contain two parts:
o data: the user's data
o next(or) link: the address of the next element in the stack

SMVEC- Department of Information Technology 7

IT T33- Data Structures

Structure for Linked Stack Basic operation

struct node 1. PUSH
{ 2. POP
int data; 3. PEEK
struct node *link; 4. DISPLAY
}

Push Operation

Algorithm Push(struct node *top)

{ struct node *newnode;
newnode=new node;
read rollno;
newnode->data=rollno;
newnode->link=NULL;
if top=NULL
{ top=newnode;
}
else
{ newnode->link=top;
top=newnode;
}
return *top;
}

Pop Operation
Algorithm pop(struct node *top)
{
struct node *temp;
if top=NULL
{
write "Stack is in underflow condition. Pop operation is not possible.";
return;
}
temp=top;
top=top->link;
write "Delete rollno.";
delete temp;
}

Peek Operation
Algorithm pop(struct node *top)
{
struct node *temp;
if top=NULL
{ write "Stack is in underflow condition. Pop operation is not possible.";
return;
}
write top->data;
return;
}

SMVEC- Department of Information Technology 8

IT T33- Data Structures

Display Operation
Algorithm pop(struct node *top)
{
struct node *temp;
if top=NULL
{
write "Stack is in underflow condition. Pop operation is not possible.";
return;
}
temp=top;
while temp!=NULL
{ write temp->data;
temp=temp->link;
}
return;
}

1.5 Applications of Stack

 Balanced Parenthesis
 Conversion from infix to postfix
 Evaluation of arithmetic expression
 Recursion

1.5.1 Balanced Parenthesis

The balanced parenthesis problem is to determine the set of parenthesis in the expression
or not.
Algorithm for balanced Parenthesis
1. Consider the expression with character and parenthesis (),{},[] to determine if an
expression is balanced or not.
2. For each character that is used to read from the expression, follow the next steps.
3. If the character is an opening parenthesis (,{,[ then push it into the stack.
4. If the character is closing symbol or parenthesis ),},] then check the last entry in the stack
using pop operation and compare the symbol in opening brace list in corresponding
position.
5. If it is matched, repeat the step from 2 until you reach the end of statement.
6. If it is not matched, or if the stack is empty which not reaching the end of expression, the
given expression is unbalanced.
7. If the stack is empty while the end of the expression the given expression is balanced.

(a+b)#- balanced ((a+b)# - unbalanced

SMVEC- Department of Information Technology 9

IT T33- Data Structures
1.5.2 Conversion from infix to postfix expression
An expression is string of operators and operands. Operands- Numeric values Operators-
Unary & binary operator
 Unary operator- It includes only single operand (+,-) Eg: +a, -b, b--,++a
 Binary Operator: It includes two or more operands(+,-,*,/) Eg: a+b, a-b*c;

Types of Expression
1. Infix expression: operand1 operator operand2 : a+b
2. Postfix expression: opeand1 operand2 operator: ab+
3. Prefix expression: operator operand1 operand2+ab

Rules which has to be followed while converting infix expression to postfix form :
 The expression is to be read from left to right.
 Read one character at a time from infix expression.
 Make use of stack to store the operators.
 There should not be any parenthesis in the postfix form

1.5.2.1 Algorithm for Infix to postfix conversion:

Algorithm infix_to_Postfix(instring,poststring)
{
Initially stack is empty;
Initialize the stack;
while(instring!=NULL)
{
ch=get the character from instring;
if(ch=operand)
{
append ch into poststring;
}
else if(ch='(')
{
pop the data from the stack and append the data into post string
until we get '(' from the stack;
}
else if(ch=operator)
{
while(precedence(top of stack)>=precedence of ch)
{
pop the data from the stack and append into poststring;
}
push ch into stack;
}
}
pop all data from the stack and append into poststring until stack is empty;
}

1.5.2.2 Postfix Expression (or) Reverse Polish notation (RPN):

A way of writing mathematical expressions in a format where the operators are written after the
operands; puts expressions in a format that can be used by the interpreter or compiler.The advantage
of postfix (or) reverse polish notation is that the order of operation evaluation is unique without the need
for precedence rules or parenthesis.
The notation is used because the format that the equation is easier for machines to interpret rather than
the infix notation.
SMVEC- Department of Information Technology 10
IT T33- Data Structures
Advantages
 No need for parentheses - avoid ambiguity
 Calculations occur as soon as an operator is specified
 RPN uses a stack. Intermediate results are available for later use
 RPN calculators have no limit on the complexity of the expressions that can be evaluated
 No equals key required for it to be evaluated

1.5.3 Evaluation of postfix expression

 Scan each term of the expression from left to right
 Use a single stack to hold the operands
 If a term is an operand, push it onto the stack
 If a term is a binary operator, evaluate its result because its two operands are already on
stack on the top positions
 Pop the stack to retrieve the operands
 Evaluate the expression
 Push the result back onto the stack

When it comes to the evaluation of the expression, following rules are used.

 Brackets should be evaluated first.

 The * and / have equal priority, which is higher than + and -.
 All operators are left associative, or when it comes to equal operators, the evaluation
is from left to right.
Example : The total evaluation is as follows.
2 + 3 * (4 – 6 / 2 + 7) / (2 + 3)-(( 4 – 1) * (2 – 10 /2 ))
=2 + 3 * 8 / (2 + 3) - ((4 - 1) * (2 – 10 / 2))
=2 + 3 * 8 / 5 -((4 - 1) * (2 – 10 / 2))
=2 + 3 * 8 /5 -(3 * (2 – 10 / 2))
=2 + 3 * 8 /5 -(3 * (2 - 5))
=2 + 3 * 8 / 5 - (3 * (-3))
=2 + 3 * 8 / 5 + 9
=2 + 24 / 5 + 9
=2 + 4.8 + 9
=6.8 + 9
=15.8
SMVEC- Department of Information Technology 11
IT T33- Data Structures
Algorithm for postfix evaluation
Algorithm Evaluate_postfix(poststring)
{ initialize stack;
while(poststring!=NULL)
{
ch=get the character from the poststring;
if ch=operand
{
Read value for ch and push the value into stack;
}
else if(ch=operator)
{
pop the two operands from the stack
perform the arithmetic operation with the operator and
push the result into the stack;
}
}

pop the data from the stack and return popped data;
}

Example :5 3 2 + 8 * +

SMVEC- Department of Information Technology 12

IT T33- Data Structures

1.6 Recursive function call

Recursion: Recursion is a technique that breaks a problem into one or more sub-problems that
are similar the original problem.

Recursive function: A recursive function is defined as a function that calls itself to solve a smaller
version of its task until a final call is made which doesn‟t require a call to itself.

Application using Recursion: Tower of Hanoi is one of the main applications of a recursion. It
says that, "if you can solve n-1 cases, then you can easily solve the nth case.

 Every program to be executed the main is loaded into a program stack at the beginning of
execution. It remains there until it completes, at which time it is popped off of the stack.
 If main calls a function, that function is loaded onto the top of the stack and remains there until it
is complete at which point it is popped off of the stack.
 A recursive function calls itself. That means another instance of the function will be placed on
the stack and will remain there until the function completes.

1.6.1Example for Recursion function:

int Fact(n) int Fact1(int n, int res)
{ {
return Fact1(n, 1); if (n==1)
} return res;
return Fact1(n-1, n*res);
}
Stack representation of recursion: (Calculating the factorial of 4)

SMVEC- Department of Information Technology 13

IT T33- Data Structures

1.7 Linked list ADT

1.7.1 Implementation (representation) of LIST ADT

The list can be implemented using two methods:

 Static implementation using array (Array Implementation of List)
 Dynamic implementation using linked list (Linked list representation of List)

Array representation of list (static)

One of the simple ways of representing the list is by means of array. Both lists and array
are ordered collection of elements, but array and list are two different things.

Array
The number of elements in the array is fixed and it is not possible to change the number of
elements in the array because insertion and deletion are not allowed in array.

1.7.2 List using array

 The size of the list varies continuously when the elements are deleted or inserted.
 The list is stored in a part of array. So, an array can be declared large enough to hold
maximum number of elements of a list.
 During the execution of the program, the size of the list can be varied within the space
reserved for it.
 One end of the array is fixed and other end of the array is constantly changed depending
upon the element inserted and deleted in the list.

1.7.3 Basic operations in a LIST using array

1. Creation of the list

2. Insertion
 Insertion of an element in the first position of the list
 Insertion of an element in the intermediate position of the list
 Insertion of an element in the last position of the list
3. Deletion
 Deletion of an element from any position of the list
 Deletion of an element from the last position of the list
4. Searching an element from the list
5. Traversal of a list (Display the elements from the list)

SMVEC- Department of Information Technology 14

IT T33- Data Structures
1.7.4 Creation of the List
Algorithm createlist()
{
do
{
top=top+1;
read rollno;
roll[top]=rollno;
read ch;
} while ch='y';
return;
}

1.7.5 Insertion of an element at last position

Algorithm insertlast()
{
if top=listsize-1 then
{
write "List is full. Insertion is not possible";
return;
}
read rollno;
top=top+1;
roll[top]=rollno;
return;
}

1.7.6 Insertion of an element in the intermediate position

Algorithm intermediate()
{
if top=listsize-1 then
{
write "List is full. Insertion is not possible.";
return; }
read key;
for i=0 to top
{
if roll[i]=key
{ for j=top to i
{
roll[j+1]=roll[j];
}
}
read rollno;
roll[i]=rollno;
}
top=top+1;
return;
}

SMVEC- Department of Information Technology 15

IT T33- Data Structures

1.7.7 Deletion of first element from the list

Algorithm deletefirst(roll,top)
{
if top=-1 then
{
write "List is empty. Deletion is not possible.";
return;
}
del data=roll[0];
for j=1 to top
{
roll[j-1]=roll[j];
}
top=top-1;
write "The data",deldata, "was deleted";
}

1.7.8 Deletion of an intermediate element from the list

Algorithm deleteintermediate(roll,top)
{
if top=-1 then
{
write "List is empty. Deletion is not possible.";
return;
}
read key;
for i=0 to top
{
if roll[i]=key then
{
deldata=roll[i];
for j=i+1 to top
{
roll[j-1]=roll[j];
}
}
}
top=top-1;
write deldata;
}
1.7.9 Traversal of the list
Algorithm search(roll,top)
{
if top=-1 then
{
write "List is empty. Deletion is not possible.";
return;
}
read key;
for i=0 to top
{
write roll[i];
}
return;
}
SMVEC- Department of Information Technology 16
IT T33- Data Structures

1.7.10 Searching of an element from the given list

Algorithm search(roll,top)
{
if top=-1 then
{
write "List is empty. Deletion is not possible.";
return;
}
read key;
for i=0 to top
{
if roll[i]=key then
{
write "Key exits";
return;
}
}
write "Key does not exists";
return;
}

1.7.11 Modification of an element in the list

Algorithm modify (roll,top)
{
if top=-1 then
{
write "List is empty. Deletion is not possible.";
return;
}
read key;
for i=0 to top
{
if roll[i]=key then
{
read rollno;
roll[i]=rollno;
return;
}
}
write "Key does not exists";
return;
}

Limitations of static or array implementation of list:

 There is a limitation on number of elements in a list because of fixed size of array.
 Insertion and deletion of elements in the list (array) is complicated because it requires
shifting of elements.
 Shifting is a time logic consuming process.

SMVEC- Department of Information Technology 17

IT T33- Data Structures
1.8 Linked list representation of List

 A linked list is a linear collection of data elements. These data elements are called nodes.
 Every node in the list points to the next node in the list.
 Therefore, in a linked list every node contains two types of information:
o Data field - Data field contains actual data of an element to be stored in a list.
o Link/Address field- It is also referred to as next address field which contains the
address of next node in the list. It is a pointer or link to the next node in the list.

1.8.1 Three types of Linked List address

 External Address
 Internal Address
 NULL Address

External Address- The address of the first node in the list is the external address. This address
is stored in the header pointer which points to the first node in the list. The entire link can be
accessed only with the help of the header pointer.

Internal Address- Internal address is the address stored in each and every node of the linked
list except the last node.

NULL Address- NULL address is the address stored by the NULL pointer from the last node
of the list which indicates the end point of the list.

1.8.2 Types of linked list

1. Singly Linked List
2. Doubly Linked List
3. Circular Linked List

Singly Linked List(SLL)

 In singly linked list, each node has a single link to its next node. This node is also
referred as a linear linked list.
 In singly linked list, we can traverse the list to only one direction (from head to NULL
pointer in the list). It cannot traverse through the list in the reverse direction from NULL
pointer to the head pointer of the list.
Basic operations in singly linked list

 Creation of a list
 Insertion of a node in a list
o Inserting a first node in the list
o Inserting a last node in the list
o Inserting an intermediate node in the list
 Deletion of a node in a list
 Modification of a node in a list
 Searching a node in a list
 Traverse of a list

SMVEC- Department of Information Technology 18

IT T33- Data Structures

1.8.3 Node Representation of Linked List

In the linear linked list the node is divided into two parts, first part contains information field and the
second part holds the address of the next node.

struct node
{ int data;
struct node *next;
} *start =NULL;
Start node

Data Next Data Next Data Next Data NULL

Address of the next node

Example of Singly Linked List

1.8.4 Inserting an item:

Inserting a new node has three situations:

This operation is used to insert a new node in the linked list at the specified position
1. Insertion at beginning of the list
2. Insertion at middle of the list
3. Insertion at end of the list

1.8.4.1 Insertion at beginning:

- Obtain space for new node
- Assign data to the data field of the new node
- Set the next field of the new node to the beginning of the linked list
- Change the reference pointer of the linked list to point to the new node

Start

Data Next Data Next Data NULL

X Next
p

SMVEC- Department of Information Technology 19

IT T33- Data Structures

Algorithm:

Node insertbeg(node *start, int x)

{ p=(node*)malloc(sizeof(node));
p->data=x;
p->next=start;
start=p;
}

1.8.4.2 Insertion at middle:

- Obtain space for new node

- Assign data to the data field of the new node
- Set the next field of the new node to q->next
- Change the reference pointer of the linked list to point to the new node q->next=p.
q

Data Next Data Next Data NULL

X Next
P
Algorithm:

p=(node*)malloc(sizeof(node));
q = start;
while(key != q->data && q != null)
q=q->next;
p->next = q->next;
q->next=p

1.8.4.3 Insertion at end:

Start q

Data Next Data Next Data NULL

X NULL
P

SMVEC- Department of Information Technology 20

IT T33- Data Structures
Algorithm:

P=(node*)malloc(sizeof(node));
p->data=X;
p->next=NULL;
if(start == NULL)
start=p;
q=start;
while(q->next!=NULL)
q=q->next;
q->next=p

1.8.5 Deletion:
This operation is used to delete an item from the linked list. Here we have three situations.

1. Deleting the first item

2. Deleting the last item
3. Deleting the meddle of the list
1.8.5.1 Algorithm for deleting the first item:
1. Store the address of the first node in a pointer variable, say P
p=start
2. Move the head to the next node.
head = head -> next
3. Free the node whose address is stored in the pointer variable P,
free(P).

Start

5 Next 4 Next 7 NULL

P Before Deletion

Start

4 Next 7 NULL

After Deletion

1.8.5.2 Algorithm for Deleting the middle item:

1. Store the address of the preceding node in a pointer variable q. Node to be deleted is
marked as key node.
2. Store the address of the key node in a pointer variable p, so that it can be freed
subsequently.
3. Make the successor of the key node as the successor of the node pointed by q.
q->next = p->next
4. Free the node whose address is stored in the pointer variable p.
free(p)

SMVEC- Department of Information Technology 21

IT T33- Data Structures

Start node

Data Next Data Next Data Next Data NULL

q p

1.8.5.3 Algorithm for Deleting the last item:

If(start->next == NULL)
free(start)
else
q=start;
while(q-> next != NULL)
q=q->next
p=q->next
free(p)

Start node

Data Next Data Next Data Next

q
Data NULL

1.8.6 Algorithm to display (or) traverse the elements in a linked list: p

q=start;
while(q!=NULL)
write q->data
q=q->next

1.9 Circular Linked List(CLL)

Circular linked list is another form of linked list in which the last node of the list is connected
to the first node in the list. There are 2 types:

 Circular singly linked list

 Circular doubly linked list
Circular linked list looks like a cyclic linked list where there is no null pointer to indicate the end
of the list.

Basic Operations:
1. Insertion
2. Deletion
3. Traversal / Display
A queue data structure can be implemented using a circular linked list with a single pointer “rear”
as the front node can be accessed through the rear node

SMVEC- Department of Information Technology 22

IT T33- Data Structures
struct node
{
int data;
struct node *next;
} *start=NULL;
1.9.1 Insertion at end:
Insertion of a node at the start or end of a circular linked list identified by a pointer to the last node
of the linked list takes a constant amount of time.

Start node

Data Next Data Next Data Next Data Next

Address of the
first node

rear P

Data Next Data Next Data Next Data Next

Algorithm:
If(rear==NULL)
rear=p;
p->next =p;
return p;
else
rear->next = p;
p->next= rear->next;
rear=p;

1.9.2 Insertion at middle:

q start

Data Next Data Next Data Next Data Next

Data Next

SMVEC- Department of Information Technology 23

IT T33- Data Structures
Algorithm:

Node *insert(int *start, int x, int loc)

{
P=node(node*)malloc(sizeof(node));
If(start==NULL)
p->next=p
return(p)
q=head->next;
for(i=0; i < loc; i++) //loc is position of qth element
q=q->next;
p->next=q->next;
q->next=p
return(p);
}

1.9.3 Deletion:
q start

Data Next Data Next Data Next Data Next

p
Algorithm:

Node *delete (int *head, int x, int loc)

{
If(head==NULL)
write “Underflow”
else If(start->next==start)
free(p);
else
q=head->next;
for(i=0; i < loc; i++) //loc is position of qth element
q=q->next;
p=q->next;
q->next=p->next;
free(p);
}

SMVEC- Department of Information Technology 24

IT T33- Data Structures
1.9.4 Display:

Algorithm:

display( node *rear)

{
node *p;
if(rear!=NULL)
{
P=rear->next;
do
{
write p->next;
P=p->next;
}while(p!=rear->next);
}
}

1.10 Doubly Linked List(DLL)

For some applications, especially for those where it is necessary to traverse the list in both
direction, doubly linked list works much better than singly linked list. Doubly linked list is an
advanced form of singly linked list in which each node contains three fields:
 Previous Address Field
 Data Field
 Next Address Field

The previous link field contains the address of its previous node. This field is also referred
as backward link field. The data field stores the information part of the node. The next field
contains address of its next node in the list. This field is also referred to as forward link field.

Basic operations
1. Insert
2. Delete
3. Traverse

One of the most striking disadvantages of these lists is that the inability to traverse the list in the
backward.

In most of the real world applications it is necessary to reverse the list both in forward
direction and backward direction. The most appropriate data structure for such an application is a
doubly linked list.

A double linked list is one in which all nodes are linked together by multiple number of links
which help in accessing both the successor node and predecessor node form the given node
position. It provides bi-directional traversing.

SMVEC- Department of Information Technology 25

IT T33- Data Structures
Each node in a double linked list has two linked fields. These are used to point to the
successor node and predecessor nodes. Prev field holds the address of the previous node and
next field holds the address of the nest node.

prev data next

struct node
{
Int data;
struct node *prev, *next;
} *start=NULL;

Start node

NULL data next Prev data next Prev data NULL

1.10.1 Creating a node:

Step 1: create memory space for the new data

q=(node*)malloc(sizeof(node));

step 2: store x in the newly acquired node

q->data=x;

step 3: make previous and next field as NULL ;

q->prev=NULL; q->next=NULL

Initially start is NULL

Start NULL 5 NULL After insertion of 5

Start
P

NULL 5 next Prev 2 NULL After insertion of 2

1.10.2 Insertion at middle:

Insertion and deletion are two basic operations on such lists. Consider that a new node pointed to
by p is to be inserted after the node pointed to by q in a doubly linked list. Links of two nodes are
altered during insertion.

SMVEC- Department of Information Technology 26

IT T33- Data Structures

Start q

NULL 5 next Prev 11 next Prev 6 NULL

Prev 3 next

Start q

NULL 5 next Prev 11 next Prev 3 next Prev 6 NULL

P
Previous link
1.10.3 Algorithm for Insertion at beginning:

insertbeg()
{
p=(node*)malloc(sizeof(node));
p->data=x
p->prev=NULL
p->next=start;
if( start!=NULL)
start ->prev=p;
}

1.10.4 Algorithm for Insertion at end:

insertend()
{
p=(node*)malloc(sizeof(node));
p->data=x
p->next=NULL;
q=start;
while(q->next!=NULL)
q=q->next;
p->prev=q;
q->next=p
}

SMVEC- Department of Information Technology 27

IT T33- Data Structures
1.10.5 Deletion of node:

When a node, pointed to by P is to be deleted then its predecessor node x and its successor node
y will be affected.

- Right link at x should be set to y.

- Left link at y should be set to x.
- Release the memory allocated to the node pointed to by p.

Start X Y

NULL 5 next Prev 11 next Prev 3 next Prev 6 NULL

P
Start X Y

NULL 5 next Prev 11 next Prev 3 next Prev 6 NULL

p->prev->next=p->next;
p->next->prev=p->prev;
free(p);

1.10.6 Algorithm for display the elements in a linked list:

display()
{ q=start;
while(q!=NULL)
printf(“%d”,q->data)
q=q->next
}

1.11 Polynomial expression representation using linked list:

Polynomials:
One classic example of an ordered list is a polynomial.

Definition:
A polynomial is the sum of terms where each term consists of variable, coefficient and
exponent.
Various operations which can be performed on the polynomial are,
 Addition of two polynomials
 Multiplication of two polynomials
 Evaluation of polynomials

SMVEC- Department of Information Technology 28

IT T33- Data Structures
The Polynomial Expression can be represented using Linked list by the following illustration,

1.11.1 Structure of the polynomial expression linked list

struct list
{
int coef;
int pow;
struct list *next;
};
struct list *p1=NULL,*p2=NULL,*p=NULL;

1.11.2 Creating node for polynomial expression

generate(struct list *node)

{
read node->coef
read node->pow
node->next=(struct list*)malloc(sizeof(struct list));
node=node->next;
node->next=NULL;
}

1.11.3 Addition of two polynomials

add(struct list *p1,struct list *p2,struct list *p)

{
while(p1->next && p2->next)
{
if(p1->pow > p2-> pow)
{
p-> pow = p1-> pow;
p->coef= p1-> coef;
p1= p1->next;
}

SMVEC- Department of Information Technology 29

IT T33- Data Structures
else if(p1->pow < p2->pow)
{
p->pow=p2->pow;
p->coef=p2->coef;
p2=p2->next;
}
else
{
p->pow=p1->pow;
p->coef=p1->coef+p2->coef;
p1=p1->next;
p2=p2->next;
}
p->next=(struct list *)malloc(sizeof(struct list));
p=p->next;
p->next=NULL;
}

while(p1->next || p2->next)
{
if(p1->next)
{
p->pow=p1->pow;
p->coef=p1->coef;
p1=p1->next;
}
if(p2->next)
{
p->pow=p2->pow;
p->coef=p2->coef;
p2=p2->next;
}
p->next=(struct list *)malloc(sizeof(struct list));
p=p->next;
p->next=NULL;
}
}

SMVEC- Department of Information Technology 30

IT T33- Data Structures
Two Marks

1. Define Data Structures (December 2014)(November 2013)

Definition 1: A data structure is logical way of storing and organizing data either in
computer's memory or on the disk storage so that it can be used efficiently.

Definition 2: A data structure is defined as collection of elements and all possible operations
which are required for those set of elements.

2. Define Linear data structure?

Linear data structures are data structures having a linear relationship between its adjacent
elements. Eg. Linked List.

3. Define Non Linear data structure?(December 2014)

Non Linear data structures are data structures don‟t have a linear relationship between its
adjacent elements, but had the hierarchical relationship. Ex. Graph, Tree.

4. Define Linked Lists

Linked list consists of a series of structures, which are not necessarily adjacent in memory.
Each structure contains the element and a pointer to a structure containing its successor. We call
this theNext Pointer. The last cell‟sNext pointer points to NULL.

5. What are different types of Linked List?

Single linked list
Double linked list
Circular linked list

6 What are different types of Circular Linked List?(April 2015)

Circular Single linked list
Circular double linked list
7. List the basic operations carried out in a linked list

The basic operations carried out in a linked list include:

• Creation of a list
• Insertion of a node
• Deletion of a node
• Modification of a node
• Traversal of the list

8. List out the advantages of using a linked list

 It is not necessary to specify the number of elements in a linked list during its declaration
 Linked list can grow and shrink in size depending upon the insertion and deletion that
occurs in the list
 Insertions and deletions at any place in a list can be handled easily and efficiently
 A linked list does not waste any memory space
SMVEC- Department of Information Technology 31
IT T33- Data Structures

9. List out the disadvantages of using a linked list

 Searching a particular element in a list is difficult and time consuming

 A linked list will use more storage space than an array to store the same number of
elements

10. List out the applications of a linked list (December 2014)

Some of the important applications of linked lists are manipulation of polynomials, sparse
matrices, stacks and queues.

11. State the difference between arrays and linked lists (November 2013)

Arrays Linked Lists

Size of an array is fixed Size of a list is variable

It is necessary to specify the number of It is not necessary to specify the number of

elements during declaration. elements during declaration
Insertions and deletions are Insertions and deletions are carried
somewhat difficult out easily
It occupies less memory than a linked list for It occupies more memory
the same number of elements

12. Define a stack

Stack is an ordered collection of elements in which insertions and deletions are

restricted to one end. The end from which elements are added and/or removed is referred
to as top of the stack. Stacks are also referred as piles, push-down lists and last-in-first-
out (LIFO) lists.

13. List out the basic operations that can be performed on a stack (December 2014)

The basic operations that can be performed on a stack are

• Push operation
• Pop operation
• Peek operation
• Empty check
• Fully occupied check

14. State the different ways of representing expressions

The different ways of representing expressions are

• Infix Notation
• Prefix Notation
• Postfix Notation

SMVEC- Department of Information Technology 32

IT T33- Data Structures

16. State the rules to be followed during infix to postfix conversions (December 2014)
Rules which has to be followed while converting infix expression to postfix form :
• The expression is to be read from left to right.
• Read one character at a time from infix expression.
• Make use of stack to store the operators.
• There should not be any parenthesis in the postfix form

17. State the difference between stacks and linked lists

The difference between stacks and linked lists is that insertions and deletions may occur
anywhere in a linked list, but only at the top of the stack

18. Mention the advantages of representing stacks using linked lists than arrays

• It is not necessary to specify the number of elements to be stored in a stack during its
declaration, since memory is allocated dynamically at run time when an element is added
to the stack

• Insertions and deletions can be handled easily and efficiently

• Linked list representation of stacks can grow and shrink in size without wasting memory
space, depending upon the insertion and deletion that occurs in the list

• Multiple stacks can be represented efficiently using a chain for each stack

19. What is the data structures used to perform recursion?

Stack. Because of its LIFO (Last In First Out) property it remembers its „caller‟ so knows
whom to return when the function has to return. Recursion makes use of system stack for storing
the return addresses of the function calls. Every recursive function has its equivalent iterative (non-
recursive) function. Even when such equivalent iterative procedures are written, explicit stack is to
be used.

20. Define an Abstract Data Type (ADT) May 2014)(December 2014)(May2018)

An abstract data type is a set of operations. ADTs are mathematical abstractions; In ADT‟s
definition ,implementation of operations is not mentioned. Objects such as lists, sets and graphs,
along with their operations can be viewed as abstract data types.

21. What are the advantages of modularity?

• It is much easier to debug small routines than large routines

• It is easier for several people to work on a modular program simultaneously
• A well-written modular program places certain dependencies in only one
 routine, making changes easier

22. What are the objectives of studying data structures?

 To identify and create useful mathematical entities and operations to determine what
classes of problems can be solved using these entities and operations

SMVEC- Department of Information Technology 33

IT T33- Data Structures
 To determine the representation of these abstract entities and to implement the abstract
operations on these concrete representation

23. List the applications of stacks (November 2015)

• Towers of Hanoi
• Reversing a string
• Balanced parenthesis
• Recursion using stack
• Evaluation of arithmetic expressions

24. Why we need cursor implementation of linked lists?

Many languages such as BASIC and FORTRAN do not support pointers. If linked lists are
required and pointers are not available, then an alternative implementation must be used known as
cursor implementation.

25. List the applications of set ADT.

• Maintaining a set of connected components of a graph

• Maintain list of duplicate copies of web pages
• Constructing a minimum spanning tree for a graph

Assignment Questions

1. Write a program to convert an infix expression that includes (, ), +, -, *, and / to postfix.

2. Write a routine to solve the towers of Hanoi problem. The conditions are
 You can move only one disk at a time.
 For temporary storage, a third pole may be used.
 You cannot place a disk of larger diameter on a disk of smaller diameter.

3. Write an array implementation of self-adjusting lists. In a self-adjusting list, all insertions are
performed at the front. A self-adjusting list adds a find operation, and when an element is
accessed by a find, it is moved to the front of the list without changing the relative order of
the other items.
4. Write a routine to perform polynomial addition using singly linked list.
5. Write a routine to maintain the singly linked list in sorted order.

SMVEC- Department of Information Technology 34