1

2
Please read this disclaimer before proceeding:

This document is confidential and intended solely for the educational purpose of RMK
Group of Educational Institutions. If you have received this document through email in
error, please notify the system manager. This document contains proprietary information
and is intended only to the respective group / learning community as intended. If you
are not the addressee you should not disseminate, distribute or copy through e-mail.
Please notify the sender immediately by e-mail if you have received this document by
mistake and delete this document from your system. If you are not the intended
recipient you are notified that disclosing, copying, distributing or taking any action in
reliance on the contents of this information is strictly prohibited.
24CS201 Data Structures
(Lab Integrated)
Department : CSE,IT,ADS,CSBS,CSD

Batch / Year : 2024 – 2028 / I

Date : 20.1.2025

Created by : Subject handling faculty

members
 1. CONTENTS
Page
S. No. Contents
No
1 Contents 5

2 Course Objectives 6

3 Pre Requisites 7

4 Syllabus 8

5 Course outcomes 11

6 CO- PO/PSO Mapping 12

7 Lecture Plan 13

8 Activity based learning 14

9 Lecture Notes 16
10 Assignments 51

11 Part A Questions & Answers 52

12 Part B Questions 56

13 Supportive online Certification 57

courses
14 Real time Applications 58

15 Contents beyond the Syllabus 61

16 Assessment Schedule 62

17 Prescribed Text Books & Reference 63

Books
18 Mini Project Suggestions 64

5
 2. COURSE OBJECTIVES

To understand the concepts of List ADTs.

To learn linear data structures – stacks and queues ADTs.

To understand and apply Tree data structures

To understand and apply Graph structures

To analyze sorting, searching and hashing algorithms

6
 3. PRE REQUISITES

• Pre-requisite Chart

24CS201 – DATA STRUCTURES

24CS101 – PROGRAMMING IN C++

7
 4. SYLLABUS
DATA STRUCTURES L T P C
24CS201
(Common CSE,IT,ADS,CSBS,CSD) 3 0 3 4.5
OBJECTIVES:

The Course will enable learners to:

v To understand the concepts of List ADTs
v To learn linear data structures – stacks and queues
v To understand and apply Tree data structures
v To understand and apply Graph structures
v To analyze sorting, searching and hashing algorithms

UNIT I LINEAR DATA STRUCTURES – LIST 9+9

Algorithm analysis - running time calculations - Abstract Data Types (ADTs) – List ADT –
array- based implementation – linked list implementation – singly linked lists - circularly
linked lists - doubly-linked lists – applications of lists – Polynomial Manipulation – All
operations (Insertion, Deletion, Merge, Traversal).
List of Exercise/Experiments:
1. Array implementation of List ADTs.
2. Linked list implementation of List ADTs.

UNIT II LINEAR DATA STRUCTURES – STACKS, QUEUES 9+9

Stack ADT – Stack Model - Implementations: Array and Linked list - Applications - Balancing
symbols - Evaluating arithmetic expressions - Conversion of Infix to postfix expression -
Queue ADT – Queue Model - Implementations: Array and Linked list - applications of queues
- Priority Queues – Binary Heap – Applications of Priority Queues.
List of Exercise/Experiments:
1. Array implementation of Stack and Queue ADTs.
2. Linked list implementation of Stack and Queue ADTs.
3. Applications of List – Polynomial manipulations
4. Applications of Stack – Infix to postfix conversion and expression evaluation.
UNIT III NON LINEAR DATA STRUCTURES-TREES 9+9
Tree ADT – tree traversals - Binary Tree ADT – expression trees
– applications of trees – binary search tree ADT– AVL Tree.
 SYLLABUS Contd...
List of Exercise/Experiments:
1. Implementation of Binary Trees and operations of Binary Trees.
2. Implementation of Binary Search Trees.
3. Implementation of Heaps using Priority Queues.

UNIT IV NON LINEAR DATA STRUCTURES - GRAPHS 9+9

Definition – Representation of Graph – Types of graph - Breadth-first traversal - Depthfirst

traversal – Topological Sort – Applications of graphs – BiConnectivity – Euler circuits.
List of Exercise/Experiments:
1. Graph representation and Traversal algorithms.

9+9
UNIT V SEARCHING, SORTING AND HASHING TECHNIQUES

Searching- Linear Search - Binary Search - Sorting - Bubble sort - Selection sort - Insertion
sort – Hashing - Hash Functions – Separate Chaining – Open Addressing – Rehashing –
Extendible Hashing.
List of Exercise/Experiments:
1. Implement searching and sorting algorithms.
TOTAL: 45 (L) + 45 (P) = 90 PERIODS
 OUTCOMES:
Upon completion of the course, the students will be able to:
CO1: Analyze algorithms and abstract data types (ADTs).

CO2: Evaluate fundamental data structures.

CO3: Implement linked data structures and its application.

CO4: Apply advanced tree data structures.
CO5: Understand basic graph theory concepts.
CO6: Evaluate various searching and sorting algorithms.

TEXT BOOKS:
1. Mark Allen Weiss, “Data Structures and Algorithm Analysis in C++”, 4th Edition, Pearson
Education, 2014.
2. SartajSahni, “Data Structures, Algorithms and Applications in C++”, Silicon paper
publications, 2004.

REFERENCES:
1. Rajesh K. Shukla, “Data Structures using C and C++”, Wiley India Publications, 2009.
2. NarasimhaKarumanchi, “Data Structure and Algorithmic Thinking with Python: Data
Structure and Algorithmic Puzzles”, CareerMonk Publications, 2020.
3. Jean-Paul Tremblay and Paul Sorenson, “An Introduction to Data Structures with
Application”, McGraw-Hill, 2017.
4. Mark Allen Weiss, “Data Structures and Algorithm Analysis in Java”, Third Edition, Pearson
Education, 2012.
5. Ellis Horowitz, SartajSahni, Susan Anderson-Freed, “Fundamentals of Data Structures in
C”, Second Edition, University Press, 2008.
6. Ellis Horowitz, SartajSahni, Dinesh P Mehta, “Fundamentals of Data Structures in C++”,
Second Edition, Silicon Press, 2007.
7. https://infyspringboard.onwingspan.com/web/en/app/toc/lex_auth_013501578165051392
10584/overview

LIST OF EQUIPMENTS:
1. Standalone desktops with C/C++ compiler (or) Server with C/C++ compiler.
 5. COURSE OUTCOMES
Upon completion of the course, the students will be able to:

COURSE OUTCOMES HKL

CO1 Analyze algorithms and abstract data types (ADTs). K3

CO2 Evaluate fundamental data structures.

K3

CO3 Implement linked data structures and its

K3
application.

CO4 Apply advanced tree data structures.

K3

CO5 Understand basic graph theory concepts. K3

CO6 Evaluate various searching and sorting algorithms. K2

HKL = Highest Knowledge Level

1
1
 6. CO-PO/PSO Mapping

PROGRAM OUTCOMES PSO

CO PO PO PO PO PO PO PO PO PO PO PO PO P P P
S S S
1 2 3 4 5 6 7 8 9 10 11 12 O O O
1 2 3
CO1 3 3 3 1 1 - - - 2 1 - 1 - - -

CO2 3 2 3 1 2 - - - 2 1 - 1 - - -

CO3 3 3 3 1 2 - - 1 2 1 - 1 - - -

CO4 3 3 3 1 2 - - - 2 1 - 1 - - -

CO5 3 3 3 1 2 - - 1 2 1 - 1 - - -

CO6 2 3 3 - 3 - - 1 2 2 - 3 - - -

Correlation Level
1. Slight (Low)
2. Moderate (Medium)
3. Substantial (High) ,
If there is no correlation, put “-“.

12
 7. LECTURE PLAN
Sl. Taxon
No. of. Proposed Actual Pertaining Mode of
No Topics o my
. Periods Date Date CO Delivery
Level

Algorithm analysis- As per

MD 1,
1 running time 1 calender K3 MD 4
CO1, CO6
calculations
Abstract Data
As per CO1
Types (ADTs) – List MD 1,
2 1 calender K3 MD 4
ADT

Array-based MD 1,
3 1 As per CO1 K2 MD 4
implementation
calender
–Linked List
implementation

Singly linked list As per CO1

MD 1,
4 implementation – 1 calender K3 MD 4
All operations

Circularly linked list As per CO1

MD 1,
5 implementation 2 calender K2 MD 4
– All operations

As per CO1 MD 1,
Doubly-
6 1 calender K3 MD 4
linked list
implementation –
All operations
As per CO1 MD 1,
Applications of
7 1 calender K3 MD 4
lists

As per CO1 MD 1,
Polynomial
8 1 calender K2 MD 4
Manipulation –
Addition,
Subtraction
Polynomial As per CO1 MD 1,
9 Manipulation - 1 calender K3 MD 4
Multiplication
CO1
As per
10 calender
- Lab Exercises 2 K2 Code
11 tantra

* MD1 – Oral Presentation

* MD 4 – Hands on using any IDE
 8. Activity Based Learning
Common Activities

Learning Methods Activities

Class Exercises, Challenge Yourself, Practice

Learn by Solving Problems at Home exercises posted in Code Tantra
Portal

Learn by Questioning Knowledge Check / MCQ Using Code Tantra

portal and RMK Nextgen App

Learn by Hands on Practice programs and Home work programs

available in Code Tantra Portal
 8. Activity Based Learning
Quiz and Flashcards

Goal: Test and reinforce knowledge about lists.

Activity:
◦Conduct a quiz with questions like:
•What is a list?
•Name the operations possible on a list.
•Write a program to reverse a list.
◦Use flashcards for quick Q&A sessions on list-related terms and
operations.
Learning Outcome: Students consolidate their understanding of lists
and their features.

Understanding Lists: Group Brainstorming

Goal: Familiarize students with the concept of lists and their characteristics.
Activity:
◦Divide students into small groups.
◦Provide each group with index cards and markers.
◦Ask them to write down examples of real-world objects that can be
represented as a list (e.g., a shopping list, a queue at a store).
◦Each group presents their examples to the class.
Learning Outcome: Students understand that a list is an ordered collection of
elements that can be traversed sequentially.

15
 9. LECTURE NOTES

Unit I

LINEAR DATA STRUCTURES – LIST

18
 UNIT – I
ALGORITHM
An algorithm is a clearly defined set of step-by-step instructions designed to solve a specific
problem or perform a task. Once an algorithm is formulated and verified to be correct, a
critical next step is to assess its efficiency in terms of resource utilization, such as time and
space. Efficient algorithms are crucial because they ensure practical usability. For instance:
Time Efficiency: An algorithm that sorts 1 million numbers but takes a year to execute is
impractical for real-world applications.
Space Efficiency: Similarly, an algorithm that requires a gigabyte of memory might not be
feasible for systems with limited storage resources.
Example:
Consider two algorithms for sorting a list of numbers:
Algorithm A (Bubble Sort):
Steps: Compare each pair of adjacent numbers in the list and swap them if they are
out of order. Repeat this process until the list is sorted.
Time Complexity: O(n²) for a list of size nnn. Sorting 1 million numbers would take a
significant amount of time.
Algorithm B (Merge Sort):
Steps: Divide the list into halves, sort each half recursively, and merge the sorted
halves.
Time Complexity: O(n log n). This algorithm is much faster for larger lists.
Although both algorithms solve the same problem (sorting), Algorithm B is more efficient
and practical for large datasets because it optimizes time without excessively consuming
space. This demonstrates the importance of evaluating an algorithm's resource requirements
to ensure real-world applicability.
Algorithm Analysis: Running Time Calculations
Algorithm analysis focuses on evaluating the efficiency of an algorithm in terms of its
resource consumption, primarily running time and space. This is typically represented using
Big-O notation, which describes the upper bound of an algorithm's running time as a
function of input size N. It provides insights into worst-case, average-case, and best-case
scenarios.

17
Big-O Notation:
 Big-O ignores constant factors and lower-order terms to describe the dominant term
that defines the growth rate. For example:
o O(1): Constant time, irrespective of input size.
o O(N): Linear growth proportional to NNN.
o O(logN): Logarithmic growth; problems are reduced significantly at each step.
Running time analysis allows developers to:
 Compare multiple algorithms for efficiency.
 Eliminate inefficient algorithms early in the design process.
 Optimize bottlenecks in existing implementations
Example of Big-O Analysis:
int sum(int n) {
int partialSum = 0; // Line 1: Constant time
for (int i = 1; i <= n; ++i) // Line 2: Loop executes N times
partialSum += i * i * i; // Line 3: Multiplications + addition, O(1)
return partialSum; // Line 4: Constant time
}
Analysis:
Line 1 & 4 contribute O(1).
Line 3 executes NNN times, contributing O(N).
Total time complexity: O(N)

General Rules for Calculations:

Rule 1: FOR loops
The running time is the product of the loop iterations and the time taken by statements
inside the loop.
Rule 2: Nested Loops
Multiply the iterations of all loops. For example:
for (int i = 0; i < n; i++) // Outer loop, O(N)
for (int j = 0; j < n; j++) // Inner loop, O(N)
k++; // Total: O(N2)
Rule 3: Consecutive Statements
The total running time is the sum of individual statements; dominated by the largest term.
Rule 4: If/Else Conditions
Consider the larger branch cost plus the evaluation time for the condition.
Maximum Subsequence Sum Problem
Problem Statement
Given N integers A1,A2,…,AN (possibly negative), find the maximum sum of a contiguous
subsequence. If all integers are negative, the maximum subsequence sum is considered 0.

Example Input: −2,11,−4,13,−5,−2 ;

Expected Output: 20 (Subsequence: 11,−4,13)

Algorithm 1: Cubic Time Complexity (O(N3))

This brute-force approach exhaustively tries all possible subsequences.

/*Cubic maximum contiguous subsequence sum algorithm. */

int maxSubSum1(const vector<int> &a) {
int maxSum = 0;
for (int i = 0; i < a.size(); ++i) {
for (int j = i; j < a.size(); ++j) {
int thisSum = 0;

for (int k = i; k <= j; ++k)

thisSum += a[k];

if (thisSum > maxSum)

maxSum = thisSum;
}
}
return maxSum;
}
Time Complexity: O(N3), as there are three nested loops.
Inefficiency: Most calculations are redundant (e.g., recomputing sums for overlapping
subsequences).

Algorithm 2: Quadratic Time Complexity (O(N2))

This improves the first algorithm by avoiding redundant calculations.
/* Quadratic maximum contiguous subsequence sum algorithm. */
int maxSubSum2(const vector<int> &a) {
int maxSum = 0;
for (int i = 0; i < a.size(); ++i) {
int thisSum = 0;
for (int j = i; j < a.size(); ++j) {
thisSum += a[j];
if (thisSum > maxSum)
maxSum = thisSum;
}
}
return maxSum;
}
Optimization Insight:
• Avoid recomputing partial sums:

• Time Complexity:

Algorithm 3: Divide and Conquer

Using the divide-and-conquer strategy:
Split the array into two halves.
Solve for the left half and right half recursively.
Compute the maximum sum that spans the middle and combine results.

Example:
For [4,−3,5,−2,−1,2,6,−2] the maximum subsequence can:
Be entirely in the left half [4,−3,5].
Be entirely in the right half [2,6].
Span both halves [4,−3,5,−2,−1,2,6].
Implementation:
int maxSumRec(const vector<int> &a, int left, int right) {
if (left == right) // Base case: single element
return max(0, a[left]);
int center = (left + right) / 2;
int maxLeftSum = maxSumRec(a, left, center);
int maxRightSum = maxSumRec(a, center + 1, right);
int maxLeftBorderSum = 0, leftBorderSum = 0;
for (int i = center; i >= left; --i) {
leftBorderSum += a[i];
maxLeftBorderSum = max(maxLeftBorderSum, leftBorderSum);
}
int maxRightBorderSum = 0, rightBorderSum = 0;
for (int j = center + 1; j <= right; ++j) {
rightBorderSum += a[j];
maxRightBorderSum = max(maxRightBorderSum, rightBorderSum);
}
return max({maxLeftSum, maxRightSum, maxLeftBorderSum + maxRightBorderSum});
}
int maxSubSum3(const vector<int> &a) {
return maxSumRec(a, 0, a.size() - 1);
}

Algorithm 4: Linear Time Complexity (O(N))

This optimal approach processes the array in a single pass.
Key Insight:
A subsequence ending at position j is either:
Extended from the subsequence ending at j−1 or
A new subsequence starting at j.
Implementation:
/ * Linear-time maximum contiguous subsequence sum algorithm. */
int maxSubSum4(const vector<int> &a) {
int maxSum = 0, thisSum = 0;
for (int j = 0; j < a.size(); ++j) {
thisSum += a[j];

if (thisSum > maxSum)

maxSum = thisSum;
else if (thisSum < 0)
thisSum = 0; // Reset for new subsequence
}
return maxSum;
}
Time Complexity: O(N).
This algorithm is space-efficient (constant additional space) and well-suited for real-time
applications

LINEAR DATA STRUCTURES - LIST

What is a Data Structure?
A Data Structure is a collection of data elements which defines the way of storing and
organizing data in a computer so that it can be used efficiently.
It comprises of
va collection of data elements
vthe relationships among them and
vthe functions or operations that can be applied to the data.

Why is Data Structure needed?

It influences the ability of a computer to store/retrieve data to/from any location in the
memory.
It enables a computer system to perform its task more efficiently.
Classification of Data Structures
Data structures can be classified into two classes namely:
Primitive data structures and Non-Primitive data structures.
A primitive data structure refers to the fundamental data types which are supported
by a programming language. Examples are integer, real, character, and Boolean. Non-
primitive data structures are created using primitive data structures.
Non-primitive data structures can further be classified into two categories:
Linear data structures and Non-linear data structures.
If the elements of a data structure are stored in a linear or sequential order, then it is a
linear data structure. Examples are arrays, linked lists, stacks, and queues. Linear data
structures can be implemented in memory in two different ways. One way is to use an
array based implementation and the other is to use a linked list implementation. If the
elements of a data structure are not stored in a sequential order, then it is a non-linear
data structure. Examples are trees and graphs.

Data
Structures

Primitive Non Primitive

Data Data
Structures Structures

integer character real boolean

Non Linear
Linear Data Data
Structures Structures

Linked
Array Stack Queue Tree Graph
List

Fig 1.1. Classification of Data Structures

ABSTRACT DATA TYPES (ADTs)
An abstract data type (ADT) is a set of operations. Abstract data types are mathematical
abstractions. They do not mention how the set of operations is implemented.
An ADT is as an extension of modular design.
Modularity has two advantages :
1. Debugging is easier
2. Many people can work on the modular program simultaneously. Examples:
Data structures such as lists, stacks, queues, trees and graphs along with their operations, can
be viewed as abstract data types.

Fig: 1.2 An array of 6 elements represented in memory

Limitations of Arrays:
1.Arrays are of fixed size.
2.Contiguous memory locations may not be always available.
3.Insertion and deletion are quite difficult in an array as the elements are stored in
consecutive memory locations and the shifting operation is costly.
To overcome the limitations of arrays, we use linked lists.

LIST ADT
A list is of the form a1,a2,a3,a4,……….,an. The size of the list is n. The first element of
the list is a1 and an is the last element. The position of element ai in a list is i. A list of size 0
is called as a null list. Some of the operations that can be performed on a list are insert,
delete, find, print etc. Let us look at the operations with the help of an example.
If the list contains the following elements 34,82,14,62,18,12 then
•find(13) returns 3
•insert(72,4) makes the list into 34,82,14,62,72,18,12 (i.e) 72 is inserted after position 4.
•delete(18) makes the list into 34,82,14,62,72,12.

Array Implementation of Lists

Insertion into a list
/* Insert the element ele at given position pos into the list*/
for( i=size;i>pos;i--)
arr[i]=arr[i-1];
arr[pos]=ele;
Deletion from a list
/* Delete element ele from the list; Assume ele is present in the list*/ for(i=1;i<=size;i++)
if(arr[i]==ele)
pos=i;
for(i=pos;i<size-1;i++) arr[i]=arr[i+1];
size--;
Note : Arrays are generally not used to implement lists as the insertions and deletions is time
consuming and expensive due to the shifting operation involved and the list size must also be
known in advance.

Linked List-Based Implementation:

A linked list consists of nodes where each node contains:
Data: The element stored.
Pointer: A reference to the next node (and optionally the previous node in doubly linked lists).
Code Example:
#include <iostream>
using namespace std;

// Node structure
struct Node {
int data;
Node* next;

Node(int value) : data(value), next(nullptr) {}

};
class LinkedList {
private:
Node* head;
public:
// Constructor to initialize the linked list
LinkedList() : head(nullptr)
{}

25
 // Insert an element at the beginning
void insertAtHead(int value) {
Node* newNode = new Node(value);
newNode->next = head;
head = newNode;
}
// Delete the first occurrence of a value
void deleteValue(int value) {
if (!head) {
cout << "List is empty." << endl;
return;
}
if (head->data == value) {
Node* temp = head;
head = head->next;
delete temp;
return;
}
Node* current = head;
while (current->next && current->next->data != value) {
current = current->next;
}
}
if (current->next) {
Node* temp = current->next;
current->next = current->next->next;
delete temp;
} else {
cout << "Value not found." << endl;
}
// Display all elements in the list
void display() const {
Node* current = head;
while (current) {
cout << current->data << " ";
current = current->next;
}
cout << endl;
}
};
int main() {
LinkedList list;
list.insertAtHead(10);
list.insertAtHead(20);
list.insertAtHead(30);
cout << "List elements: ";
list.display(); // Output: 30 20 10
list.deleteValue(20); // Delete node with value 20
cout << "After deletion: ";
list.display(); // Output: 30 10
return 0;
}

SINGLY LINKED LIST

vThe linked list consists of a series of nodes, which are not necessarily adjacent in
memory.
vEach node contains two fields namely the data element and a pointer(called as the next
pointer) to the next node as shown in Fig 1.3.
The next pointer of the last node in the list points to NULL.

Data element Next pointer

Fig 1.3. Structure of a node in a linked list
 Fig 1.4. A Linked List
In Fig 1.4, the linked list consists of 5 elements a1,a2,a3,a4,a5 respectively. Let us
assume that these 5 nodes reside in memory locations 1000, 1786, 1234, 1321 and
3451 respectively. Then we can represent our linked list as shown in Fig 1.5.

Fig 1.5 Linked List with actual pointer values

Linked List with a Header
A header is a special node that is used to keep track of a linked list. It is also called as a
dummy node or sentinel node.

Fig 1.6 Linked List with a header

Programming Details of a Linked List
Type Declarations for Linked Lists
typedefstruct node *node_ptr;
struct node {
element_type element;
node_ptr next;
};
typedef node_ptr LIST;
typedef node_ptr position;
Function to test whether a linked list is empty
int is_empty( LIST L )
{ return( L->next == NULL );
}

Fig 1.7. Empty List with header

Create Node in Singly Linked List
struct node {
int data;
struct node *next;
};
typedef struct node *NODE;
class Sll {
NODE first;
public: Sll() {
first = NULL;
}
NODE createNode();
};
NODE Sll :: createNode() {
NODE temp;
temp = new node;
temp -> next = NULL;
return temp;
}
int main() {
Sll s;
int x;
NODE first = NULL;
first = s.createNode();
cout << "Enter element of first node : ";
cin >> x;
first -> data = x;
first -> next = s.createNode();
cout << "Enter element of second node : ";
cin >> x;
first -> next -> data = x;
cout << " The list is :" first -> data << " --> " first -> next -> data << " -
-> NULL\n";
}
Function to test whether current position is the last in a linked list
int is_last( position p, LIST L )
return( p->next == NULL );
Find Routine
Find routine returns the position of a given element x in the list.
/* Return position of x in L; NULL if not found */ position find
( element_type x, LIST L )
{
position p;
p = L->next;
while( (p != NULL) && (p->element != x) )
p = p->next;
return p;
}
Find_previous Routine
Find previous routine is used to return the previous node of given element x.
/* Uses a header. If element is not found, then next field */
/* of returned value is NULL */
position find_previous( element_type x, LIST L )
{
position p; p = L;
while( (p->next != NULL) && (p->next->element != x) )
p = p->next;
return p;
}
Insertion routine for linked lists
The following routine is used to insert an element x after a given position p.
/* Insert (after legal position p).*/
/* Header implementation assumed. */
void insert( element_type x, LIST L, position p )
{
position tmp_cell;
tmp_cell = (position) malloc( sizeof (struct node) );
if( tmp_cell == NULL )
fatal_error("Out of space!!!");
else
{
tmp_cell->element = x;
tmp_cell->next = p->next;
p->next = tmp_cell;
}
}

Fig 1.8. Insertion in a Linked List

insertAtBegin() in SLL
NODE first = NULL;
void Sll::insertAtBegin(int x) {
NODE temp;
temp = createNode();
temp -> data = x;
temp -> next = first;
first = temp;
}
NODE Sll::createNode() {
NODE temp;
temp = new node;
temp -> next = NULL;
return temp;
}
struct node {
int data;
struct node *next;
};
31
typedef struct node *NODE;
 Fig 1.8-A. Insertion in a Linked List
Deletion routine for linked lists
Deletion Routine is used to delete a given element x from the list. It uses
find_previous routine to locate the previous node of element x.
/* Assume that the position is legal. */
/* Assume use of a header node. */
void
delete( element_type x, LIST L )
{
position p, tmp_cell;
p = find_previous( x, L ); if( p->next != NULL )
{ /* x is found: delete it */
tmp_cell = p->next;
p->next = tmp_cell->next; /* bypass the cell to be deleted */ free( tmp_cell );
}
}

Fig 1.9 Deletion from a Linked List

32
deleteAtBegin() in SLL
void Sll::deleteAtBegin() {
NODE temp = first;
if (first == NULL) {
cout << "SLL is empty. So, deletion is not possible.\n";
} else {
first = first -> next;
cout << "The deleted element from SLL : " << temp -> data
<< "\n";
delete temp;
}
}

Fig 1.9-A. Before Deletion from a Linked List

Fig 1.9-B. After Deletion from a Linked List

CIRCULARLY LINKED LIST

In circularly linked list the last node points to the first node/ header node of the linked
list. The last node of the list contains a pointer to the first node of the list. The circular
singly liked list has no beginning and no ending. There is no null value present in the
next part of any of the nodes as shown in the Fig 1.10.

33
 L 10 20 30 40

Fig 1.10 Circularly Linked List

Advantages of Circular linked List
It allows to traverse the list starting at any point.
It allows quick access to the first and last records.
Circularly doubly linked list allows to traverse the list in either direction. Disadvantages
of Circular linked List
Reversing a list is complex compared to linear linked list
If proper care is not taken in managing the pointers, it leads to infinite loop
Moving to previous node is difficult, as it is needed to complete an entire circle
Declaration of node:
typedef struct node *position; struct node
{
int data;
position next;
}; data next

Fig 1.11 Structure of a node in a Circularly linked list

Declaring a node with 2 fields.
1.data field
2.pointer to the next node as shown in the Fig 1.11
Routine to create the list:
•This routine creates a single node and get assigned to the tmpcell pointer.
•The next pointer of the last node in the list points to the first node or header node as
shown in the Fig 1.12.
List Createlist()
{
position tmpcell;
tmpcell=(struct node*)malloc(sizeof(struct node));
if(tmpcell==NULL)
cout<<Error out of space; tmpcell->next=tempclell;
return(tmpcell); }
 tmpcell

data next

Fig 1.12 Node Creation in a Circularly linked list

Routine to insert an element to the CLL
In Fig 1.13, inserts a given data in the already existing circular linked list.
P points to the Previous node to which the new node has to be inserted.
The new node is assigned to tmpcell.
For example, if 50 should be inserted at the end position just by rearranging the pointers
as numbered from 1 to 2 insertion can be done.

void insert(Elementtype x, List L, Position P)

{
position tmpcell;
tmpcell =(struct node*)malloc(sizeof(struct node));
if(tmpcell==NULL)
cout<<Error out of space;
tmpcell->element=X;
tmpcell->next=p->next;
p->next=tmpcell;
} tmpcell
P
2
L 10 20 30 40 50

Fig 1.13 Insertion in a Circularly linked list

 struct node {
int data;
struct node *next;
};
typedef struct node *NODE;
class Cll {
NODE first;
public: Cll() {
first = NULL;
}
NODE createNode();
};
NODE Cll :: createNode() {
NODE temp;
temp = new node;
temp -> next = NULL;
return temp;
}

int main() {
cll s;
int x;
NODE first = NULL;
first = s.createNode();
cout << "Enter element of first node : ";
cin >> x;
first -> data = x;
first -> next = s.createNode();
cout << "Enter element of second node : ";
cin >> x;
first -> next -> data = x;
first -> next->next=first;
cout << " The list is :" first -> data << " --> " first -> next -> data << " -->
NULL\n";
}
Sample Output:
Routine to delete an element from CLL
• In Fig 1.14, deletes a data from the given circular linked list.
• The Pointer P points to the node to be deleted.
• The Pointer T points to the previous node of the node to be deleted.
• For example, if 50 needs to be deleted just by rearranging the pointers as
numbered 1 and 2 deletion can be done.
void delete(Elementtype x, List L)
{
position P, T;
p= find(X, L); T=P-> next;
While(T->next!=P)
T=T->next;
T->next=P->next; free(P);
} T P

L 1 2 3 4 5
0 0 0 0 0
free
‘ P’
1 2

Fig 1.14 Deletion from a Circularly linked list

Routine to find an element

In Fig 1.15, finds a given element in the circular linked list.
P is a pointer which initially points to the first node in CLL and then moves down the list to
find the element.
Position find(Elementtype x, List L)
{
Position P;
P=L->next;
while(P!=L && P-<element!=X)
P=P->next;
return(P);
}
 Routine to find an element
 In Fig 1.15, finds a given element in the circular linked list.
 P is a pointer which initially points to the first node in CLL and then moves down the list
to find the element.

Position find(Elementtype x, List L)

{
Position P;
P=L->next;
while(P!=L && P-<element!=X)
P=P->next;
return(P);
} P
L 10 20 30 40

Fig 1.15. Find the element from a Circularly linked list

Routine to print the elements from CLL
 In Fig 1.16, prints the element in the circular linked list.
 The list can be displayed in forward direction.
 P is a pointer which initially points to the first node in CLL and then moves down the list to
print the elements in the CLL using next field.
void printlist(List L)
{
Position P;
P=L -> next;
while(P!= L)
{
cout<< P->element;
P=P->next;
}

Fig 1.16. Print the element from a Circularly linked list

 DOUBLY LINKED LIST
In Fig 1.17, a Linked list in which each node is linked to both its successor and its
predecessor is said to be doubly linked list.
 Each node in the list has two pointers, one to the next node and one to the
previous one.
 The ends of the list are defined by NULL pointers.

Fig 1.17. Doubly linked list

Advantages
In doubly linked list, it is convenient to traverse lists backwards.
It simplifies deletion, because no need to refer to a key by using a pointer to
the previous cell. It is available in the node itself.
Disadvantages
An extra field to the data structure, containing a pointer to the previous cell which adds
to the space requirement and also doubles the cost of insertions and deletions because
there are more pointers to fix.

Creating and performing various operations in a doubly linked list

Declarations
typedef int element_type;
typedef struct node *node_ptr; typedef node_ptr LIST;
typedef node_ptr Position;
Declaring a node with 3 fields.
• data field
• pointer to next node
• pointer to previous node
Routine to create the DLL
This routine creates a single node and get assigned to the tmpcell pointer. The next field
and prev field are assigned NULL as shown in the Fig 1.18.

Fig 1.18 Node Creation in Doubly linked list

 LIST createlist()
{
Position tmpcell;
tmpcell =(struct node*)malloc(sizeof(struct node));
if(tmpcell==NULL)
cout<<out of space;
tmpcell->next=NULL;
tmpcell->prev=NULL;
return tmpcell;
}

Fig 1.19. Insertion in a Doubly linked list

Routine to insert an element to the DLL
In Fig 1.19,inserts a given data in the already existing doubly linked list. P points to the Previous
node to which the new node has to be inserted. The new node is assigned to tmpcell. For
example if 25 should be inserted between 20 and 30 just by rearranging the pointers as
numbered from 1 to 4 insertion can be done.
void insert( element_type X, LIST L, Position P )
{
position tmpcell;
tmpcell = createlist(); tmpcell->element=X;
tmpcell->next = P->next; /* 1 -steps as numbered in figure*/
P->next = tmpcell; /* 2 */
tmpcell->prev=P; /* 3 */ if(tmpcell->next!=NULL)
tmpcell->next->prev=tmpcell; /* 4 */
}

Routine to delete an element from DLL

In Fig 1.20, deletes a data from the given doubly linked list.
The Pointer P points to the node to be deleted.
The Pointer T points to the previous node of the node to be deleted.
For example if 20 needs to be deleted just by rearranging the pointers as
numbered deletion can be done.
 L 10 20 30 40

T P

Fig 1.20. Deletion from a Doubly linked list

void delete( element_type X, LIST L )
{
Position P, T;
P = find( X, L );
T=P->prev;
T->next=P->next; /* 1 -steps as numbered in figure*/
if( P->next != NULL )
P->next->prev = T; /* 2 */
free( P );
}
Routine to find an element
This routine finds a given element in the doubly linked list.
P is a pointer which initially points to the first node in DLL and then moves down the list to
find the element.
Position find ( element_type X, LIST L )
{
Position P;
P = L->next;
while( (P != NULL) && (P->element != X ))
P = P->next;
return P;
}
Routine to print the elements from DLL
This routine prints the element in the doubly linked list.
The list can be displayed both in forward and reverse direction.
P is a pointer which initially points to the first node in DLL and then moves down the list to
print the elements in the DLL using next field.
The list can be printed in backward direction by using the prev field.
void printlist(LIST L)
{
Position P;
P=L->next;
printf(“List forward”);
while(P->next!=NULL)
{
cout<<P->element;
P=P->next;
}
cout<<P->element;
cout<<List backward;
while(P!=NULL)
{
cout<<P->element;
P=P->prev;
}
}

LINKED LIST APPLICATIONS

Few applications of List are:

1.Polynomial ADT (Simple way to represent single-variable polynomial)
2.Radix sort
3.Multilist

1. The Polynomial ADT:

An ADT can be defined for a single-variable polynomial with nonnegative exponents by using a
list.
•F(X)=∑Ni=0Ai​Xi
where:
•Ai​ is the coefficient of Xi .
•i is the exponent of the term, starting from 0.
•N is the degree of the polynomial.
 Using a list (such as an array or linked list), this polynomial can be represented and
manipulated efficiently. Each term of the polynomial is stored as an element or node in
the list.
Attributes:
Coefficients: Store the coefficients of terms in a list.
Exponents: The exponent of each term corresponds to the index in the list (for arrays)
or is explicitly stored in each node (for linked lists).
Operations:
Create Polynomial: Initialize an empty polynomial.
Add Term: Add a new term to the polynomial (insert or update a coefficient for a given
exponent).
Delete Term: Remove a term with a specific exponent.
Evaluate Polynomial: Calculate the value of the polynomial for a given value of
�.
Add Polynomials: Merge two polynomials by summing coefficients of terms with the
same exponents.
Display Polynomial: Print the polynomial in mathematical notation.
Declaring a node with 3 fields as shown in the Fig 1.21
1.Coeff_array field
2. High_power field
3. pointer to next node

Coeff_ High_ next

array power

Fig 1.21. Structure of a node in Polynomial ADT

Procedure to initialize a polynomial to Zero:

This routine initialize a polynomial with zero to coeff_array part and high_power part void
zero_polynomial( POLYNOMIAL poly )
{
unsigned int i;
for( i=0; i<=MAX_DEGREE; i++ )
poly->coeff_array[i] = 0;
poly->high_power = 0;
}
Procedure to add two polynomials:
In Fig 1.21, adds the two polynomials.
•Consider the first polynomial as poly1, second polynomial as poly2 and the resultant
polynomial as poly.
•Set the pointer p1 pointing to first node in the poly1, p2 pointing to first node in the poly2
and p pointing to poly.
•Compare the exponent of p1 with the exponent of p2.
v If the exponent of the p1 is same as the exponent of the p2, then add the coefficient of
both the node and add this node in the resultant list which is called as poly. After that
move both p1 and p2 to the next node. At the same time increment p by one to store the
next resultant term in the poly.
v If they are not equal, then consider whichever polynomial has the bigger coefficient that
must be added to the resultant list and move the corresponding pointer to the next node.
v Do the above procedure until null node is reached in either of the poly1 or poly2.
v If the null node is identified in any of the list(poly1 or poly 2), stop the procedure and then
add the remaining nodes from the the other list one by one in the resultant list.

•void add_polynomial( POLYNOMIAL poly1, POLYNOMIAL poly2, POLYNOMIAL

poly_sum )
{
int i; zero_polynomial( poly_sum );
poly_sum->high_power = max( poly1->high_power, poly2->high_power); for( i=poly_sum-
>high_power; i>=0; i-- )
poly_sum->coeff_array[i] = poly1->coeff_array[i] + poly2->coeff_array[i];
}

Examples of polynomial equations:

Input:
1st number = 5x^2 + 4x^1 + 2x^0
2nd number = 5x^1 + 5x^0
Output:
5x^2 + 9x^1 + 7x^0
Input:
1st = 5x^7 + 4x^6 + 2x^5 +7x^3
2nd = 5x^6 + 2x^5 + 4x^2 + 3x^1 + 5x^0
Output:
5x^7 + 9x^6 + 4x^5 + 7x^3 + 4x^2 + 3x^1 + 5x^0
 P1
POLY 1
5 2 4 1 2 0 NULL

P2
POLY 2
5 1 5 0 NULL

RESULTANT POLY P
5 2 9 1 7 0 NULL

Fig 1.21:
NODE STRUCTURE
Coeff_ High_ next
array power

Fig 1.22. Structure of a node in a Circularly linked list

Procedure to multiply two polynomials

To this routine multiply the two polynomials.

Consider the first polynomial as poly1 and the second polynomial as poly2.
Set the pointer p1 pointing to first node in the poly1, p2 pointing to first node in the poly2
and p pointing to poly.
Step 1: Multiply p1 coefficient with p2 and add the corresponding exponent of p1 and p2.
Add this node in the resultant poly list. After that move p2 to point to the next node in the
list. At the same time increment p by one to store the next resultant term in the poly.
Step 2: Do the above procedure until the null node is reached in poly2.
Step 3: Now move p1 to point to the next node in the poly1. Then repeat the step 1 and 2
until null node is reached in poly1.

void mult_polynomial( POLYNOMIAL poly1, POLYNOMIAL poly2, POLYNOMIAL poly_prod )

{
unsigned int i, j; zero_polynomial( poly_prod );
poly_prod->high_power = poly1->high_power + poly2->high_power;
if( poly_prod->high_power > MAX_DEGREE )
error("Exceeded array size");
else
for( i=0; i<=poly->high_power; i++ )
for( j=0; j<=poly2->high_power; j++ )
poly_prod->coeff_array[i+j] += poly1->coeff_array[i] * poly2->coeff_array[j];
}
Examples of polynomial equations:
Input:
1st number = 5x^2 + 4x^1 + 2x^0
2nd number = 5x^1 + 5x^0
Output:
25x^3 + 25x^2 + 20x^2 + 20x^1 + 10x^1 + 10x^0

Linked List implementation of the polynomial ADT:

v An alternate way to implement polynomial ADT is singly Linked List.

v Each term in the polynomial is contained in one cell and the cells are sorted in
decreasing order of exponents.
Type declaration for linked list implementation of the Polynomial ADT:
typedef struct node *node_ptr;
struct node
{
int coefficient;
int exponent;
node_ptr next;
};
typedef node_ptr POLYNOMIAL; /* keep nodes sorted by exponent */
Linked list implementation is mainly preferred when there are a greater number of
coefficients with value zero in a given polynomial.
 2. Radix Sort:
Radix sort is sometimes known as card sort, because it was used, until the advent of
modern computers, to sort old-style punch cards.
This is a fast sort known as bucket sort. Ex: 64, 8, 216,
512, 27, 729, 0, 1, 343, 125
1)Bucket sort by least significant digit as shown in Table 1.1 Sorted List : 0,1,
512,343, 64, 125, 216, 27, 8, 729
2)Now sort by the next least significant digit (the tens place) as shown in Table 1.2
Sorted list: 0, 1, 8, 512, 216, 125, 27, 729, 343, 64
3)Now sort by the hundreds digit place as shown in Table 1.3 Sorted List: 0, 1, 8, 27,
64, 125, 216, 343, 512, 729
Buckets after first step of radix sort

0 1 512 343 64 125 216 27 8 729

0 1 2 3 4 5 6 7 8 9

Table: 1.1. Buckets after first step of radix sort

 Buckets after the second pass of radix sort

Table: 1.2: Buckets after the second step of radix sort

64
27
8
1
0 125 216 343 512 729
0 1 2 3 4 5 6 7 8 9

Table: 1.3: Buckets after the last pass of radix sort

3.Multilists:
A university with 40,000 students and 2,500 courses needs to be able to generate two types of
reports.
lists the class registration for each class,
lists by student, the classes that each student is registered for.
For the above requirement, it can be implemented by a two-dimensional array, but roughly 0.1%
only will have meaningful data. So a circular linked list can be
used. Two lists are combined into one. All the lists use a header.

Fig 1.23. Multilist implementation for registration problem

vAs the Figure 1.22 shows, we have combined two lists into one. All lists use a
header and are circular.
vTo list all of the students in class C3, we start at C3 and traverse its list (by going
right). The first cell belongs to student S1.
vAlthough there is no explicit information to this effect, this can be determined by
following the student's linked list until the header is reached.
vOnce this is done, we return to C3's list (we stored the position we were at in the
course list before we traversed the student's list) and find another cell, which can
be determined to belong to S3. We can continue and find that S4 and S5 are also in
this class.
vUsing a circular list saves space but does so at the expense of time. In the worst
case, if the first student was registered for every course, then every entry would
need to be examined in order to determine all the course names for that student.
vIn this application there are relatively few courses per student and few students
per course, this is not likely to happen.
vIf it were suspected that this could cause a problem, then each of the (non
header) cells could have pointers directly back to the student and class header. This
would double the space requirement, but simplify and speed up the implementation
 QUIZ

Ready to take a Quiz? Click on below Link

https://revisely.com/quiz/pXnen2

ONLINE LEARNING

Sl.No Topic Link

http://littlesvr.ca/dsa-html5-
1 Linked list animations/linkedlist.php

https://visualgo.net/en/list
2 Doubly linked list

50
 10. ASSIGNMENT : UNIT – I
(CO1, K4)

1. Write a C++ program to split a circular linked list into two halves.
2. Implement merge sort for a singly linked list.
3. Write a function that counts the number of times a given int occurs in
a Linked List.
4. Write a C++ program for Convert singly linked list into circular linked
list.
5. Represent a sparse matrix using a linked list. Implement functions to:
a. Store the matrix in a linked list.
b. Add two sparse matrices.
c. Display the matrix.

51
 11. PART A : Q & A : UNIT – I
SNo Questions and Answers CO K

What is Data Structure?

1 A Data Structure is a collection of data elements which K1

defines the way of storing and organizing data in a
computer so that it can be used efficiently.

List the types of Data Structures with example?

Linear data structures: If the elements of a data

structure are stored in a linear or sequential order, then
it is a linear data structure. Examples are arrays, linked
2 K2
lists, stacks, and queues.
Non-Linear data structure: If the elements of a data
structure are not stored in a sequential order, then it is a
non-linear data structure. Examples are trees and
graphs.

What is ADT?
An abstract data type (ADT) is a set of operations.
3 CO1 K1
Abstract data types are mathematical abstractions. They
do not mention how the set of operations is
implemented.
State the advantages of ADT?

4 1. Debugging is easier K2
2. Many people can work on the modular program
simultaneously.
What are Linked Lists?
The linked list onsists of a series of nodes, which are not
5 K1
necessarily adjacent in memory. Each node contains two
fields namely the data element and a pointer(called as
the next pointer) to the next node
What is the use of Header node in Linked lists?

6 A header is a special node that is used to keep track of a linked K2

list. It is also called as a dummy node or sentinel52
node.
 11. PART A : Q & A : UNIT – I
SNo Questions and Answers CO K
Write a routine to check the list is empty?.
7 K2
int is_empty( LIST L )
{ return( L->next == NULL ); }
Write a routine to check the whether the current position
8 is the last node of linked lists. K2
int is_last( position p, LIST L )
{
return( p->next == NULL );
}
When singly linked list can be represented as circular
linked list?
In a singly linked list, all the nodes are connected with forward
links to the next nodes in the list. The last node CO1
9 K2
has a next field, NULL. In order to implement the
circularly linked lists from singly linked lists, the last node’s
next field is connected to the first node

What are the advantages of CLL?

• It allows to traverse the list starting at any point.
10 K2
• It allows quick access to the first and last records.
 Circularly doubly linked list allows to traverse the list in
either direction.
What are the disadvantages of CLL?
• Reversing a list is complex compared to linear linked
11 list K2
• If proper care is not taken in managing the pointers,
it leads to infinite loop
• Moving to previous node is difficult, as it is needed to
complete an entire Circle
What are the advantages of DLL?
In doubly linked list, it is convenient to traverse lists backwards.
12 K2
It simplifies deletion, because no need to refer to a key by using
a pointer to the previous cell. It is available in 53
the node itself.
 11. PART A : Q & A : UNIT – I
SNo Questions and Answers CO K

What is doubly linked list?

A Linked list in which each node is linked to both its successor and
13 its predecessor is said to be doubly linked list. Each node in the list K1
has two pointers, one to the next node and one to the previous
one. The ends of the list are defined by NULL pointers.

What are the disadvantages of DLL?

CO1
An extra field to the data structure, containing a pointer to the K2
14 previous cell which adds to the space requirement and also
doubles the cost of insertions and deletions because there are
more pointers to fix.

List down the applications of List.

• Representation of polynomial ADT
15 K2
• Used in radix and bubble sorting
• In a FAT file system, the metadata of a large file is
organized as a linked list of FAT entries.
• Simple memory allocators use a free list of unused
memory regions, basically a linked list with the list pointer
inside the free memory itself.

How the polynomial is represented using linked lists?

The polynomial equation can be represented with linked list as
16 K2
follows:
struct polynomial
{int coefficient; int
exponent;
struct polynomial *next;};
 11. PART A : Q & A : UNIT – I
SNo Questions and Answers CO K

What are the advantages & disadvantages of linked list?

Advantages:
•Memory location for a linked list is dynamic, that is memory
allocation is done during runtime.
•Insertion and deletion of elements can be done
efficiently.
17 K1
• Memory allocation for each node of a linked list need
not be continuous.
Disadvantages:
•Nodes of a linked list cannot be accessed directly. To access a
particular node accessing should start only from the beginning.
CO1
• To store a single data, along with data, memory must

be allocated for a pointer also, which wastes memory.

• Searching takes more time compared to arrays.

What do you mean by traversing a list?

18 K1
Traversing a linked list means accessing the nodes of the list in
order to perform some processing on them.
Give the built in functions available in C language for
19 dynamic memory allocation. K1

malloc(), calloc(), free()

What are header linked lists?

A header linked list is a special type of linked list which contains
20 K1
a header node at the beginning of the list.
START will not point to the first node of the list but START
will contain the address of the header node.

55
 12. PART B QUESTIONS : UNIT – I
(CO1, K2)
1. Write algorithms to perform insertion, deletion operations in array
implementation of list.

2. Explain Singly Linked list and its operations with necessary code.

3. Write functions to insert, delete and display a node from a Circular linked list.

4. Write functions to insert and delete a node from a doubly linked list.

5. How polynomial manipulations are performed with lists? Explain the operations.

PART C QUESTIONS (CO1, K3)

1. Given a singly linked list, rotate the linked list counter-clockwise by k nodes. Where k
is a given positive integer. For example, if the given linked list is 10->20->30->40-
>50->60 and k is 4, the list should be modified to
50->60->10->20->30->40. Assume that k is smaller than the count of nodes in linked list

2. Delete all odd nodes of a Circular Linked List

a. Given a circular singly linked list containing N nodes, the task is to delete all the odd
nodes from the list.

3. Find the largest node in Doubly linked list

a. Given a doubly-linked list, find the largest node in the doubly linked list.

4. Remove all nodes from a Doubly Linked List containing Fibonacci numbers
5. Swap Kth node from beginning with Kth node from end in a Doubly Linked List. Given a
doubly-linked list, the task is to swap Kth node from the beginning with Kth node from
the ending.

a. Input: DLL = 1 <-> 2 <-> 3 <-> 4 <-> 5 <-> 6, K = 3

Output: 1 2 4 3 5 6

Explanation:
Third node from the beginning(3) is swapped with third node from the ending(4).

b. Input: DLL = 1 <-> 2 <-> 3 <-> 4 <-> 5, K = 1

Output: 5 2 3 4 1
56
 13. SUPPORTIVE ONLINE
CERTIFICATION COURSES

UNITS : I TO V

COURSERA
DATA STRUCTURES
DATA STRUCTURES AND
ALGORITHMS DATA STRUCTURES
AND PERFORMANCE PYTHON
DATA STRUCTURES

UDEMY
LEARNING DATA STRUCTURES IN C PROGRAMMING
LANGUAGE DATA STRUCTURES IN C LANGUAGE

NPTEL
PROGRAMMING, DATA STRUCTURES AND ALGORITHM USING
PYTHON

57
 14. REAL TIME APPLICATIONS :
UNIT – I
Linked List

1. Image viewer – Previous and next images are linked, hence can be accessed by next and
previous button.
2. Previous and next page in web browser – We can access previous and next URL searched in
web browser by pressing back and next button since, they are linked as linked list.
3. Music Player – Songs in music player are linked to previous and next song. You can play songs
from either starting or ending of the list.
4. File System: It is highly useful in file system handling where for example the file allocation
table contains a sequential list of locations where the files is split up and stored on a disk.
Remember that overtime it is hard for an OS to find disk space to cover the entire file so it
usually splits these up into chunks across the physical hard drive and stores a sequential list
of links together as a linked

list.

Industry Projects

 Phone directory / Mobile Contacts Management

 Problem Statement: Typically, phone book management encompasses searching, sorting, and
deleting operations. A distinctive feature of the search queries here is that the user sees
suggestions from the contact list after entering each character.

 Solution: Doubly Linked list is used to implement the Phone directory.

 A System to Represent Task Dependencies In Trello

 A Trello board is a list of lists, filled with cards, used by you and your team. Trello has
everything you need to organize projects of any size. Open a card and you can add comments,
upload file attachments, create checklists, add labels and due dates, and more.

58
 14. REAL TIME APPLICATIONS :
UNIT – I
DAY TO DAY LIFE AND INDUSTRY

 Problem Statement: We recommend the following system:

1. Store each task in a Trello card.

2. Store a task's dependencies as items in a checklist on the card.

3. If your task has both pre-requisites and sub-tasks, separate them into two
checklists.
4. Each item in a dependencies checklist is a link to a card on which the task
depends.

5. If a card depends on this one, add a link back to the former in the attachments.
6. That is, if we have two cards, a dependent and a dependency, we add in a
checklist on the dependent card a link to the dependency card, and we add a link
in the attachments of the dependency card back to the dependent card.

7. Solution: Using a linked list for each checklist card

A. Telephone Chain

A telephone chain is implemented directly as a linked list. Here's how it works:

v A group organizer collects the phone numbers of all members.

v The organizer assigns each member the number of one other member to call.
(Sometimes they will assign their own number so that they know the
message got through, but this is optional.)
v When a message needs to be sent, the organizer calls the head of the list and
delivers the message.

v The head calls the number they were assigned and delivers the message.

v Step 4 is repeated until everyone has heard the message.

Obviously care must be taken to set up the list in step 2 so that everyone is linked.
Also, the list is usually public so that if someone gets an answering machine or
busy tone, they can call the next number down and keep the
59
chain moving.
14. REAL TIME APPLICATIONS :
UNIT – I

B. Human Brain

Human brain of a child(In order to remember something eg . poem he has to

link it , if you will ask him the last line he will have to read from the first line)

C. Message delivery on Network

Message delivery on network (message is broken into packets and each packet has a
key of the next one so that at the receiver's end , it will be easy to club them)

60
 15. CONTENTS BEYOND
SYLLABUS : UNIT – I

Linked List – Advanced Data Structures

This topic describes how to pass data structures using linked lists of arbitrary lengths.
Unlike the simpler examples covered in earlier sections, the following examples are
written using both the XDR C library routines and the XDR data description language.
The section "XDR standard" describes the XDR data definition language used below.

The head of the linked list can be thought of as the data object; that is, the head is not
merely a convenient shorthand for a structure. Similarly, the nxt field is used to indicate
whether or not the object has terminated. Unfortunately, if the object continues, the nxt
field is also the address where it continues. The link addresses carry no useful
information when the object is serialized.
The Boolean field indicates whether there is more data following it. If the Boolean is
FALSE, then it is the last data field of the structure. If it is TRUE, then it is followed by a
gnumbers structure and (recursively) by a gnumbers_list.
For a detailed description, refer to the link.

61
 16. ASSESSMENT SCHEDULE

Tentative schedule for the Assessment During 2024-2025 Even

semester

Name of
S.NO Start Date End Date Portion
the
Assessment
1 Unit Test 1 08.02.2025 15.02.2025 UNIT 1

2 IAT 1 24.02.2025 28.02.2025 UNIT 1 & 2

3 Unit Test 2 18.03.2025 22.03.2025 UNIT 3

4 IAT 2 01.04.2025 05.04.2025 UNIT 3 & 4

5 Model 28.04.2025 07.05.2025 ALL 5 UNITS

62
17. PRESCRIBED TEXT BOOKS &
REFERENCE BOOKS
TEXTBOOKS:
1. Mark Allen Weiss, “Data Structures and Algorithm Analysis in C++”,
4th Edition, Pearson Education, 2014.
2. SartajSahni, “Data Structures, Algorithms and Applications in C++”,
Silicon paper publications, 2004.

REFERENCES:
1. Rajesh K. Shukla, “Data Structures using C and C++”, Wiley India
Publications, 2009.
2. NarasimhaKarumanchi, “Data Structure and Algorithmic Thinking
with Python: Data Structure and Algorithmic Puzzles”, CareerMonk
Publications, 2020.
3. Jean-Paul Tremblay and Paul Sorenson, “An Introduction to Data
Structures with Application”, McGraw-Hill, 2017.
4. Mark Allen Weiss, “Data Structures and Algorithm Analysis in Java”,
Third Edition, Pearson Education, 2012.
5. Ellis Horowitz, SartajSahni, Susan Anderson-Freed, “Fundamentals
of Data Structures in C”, Second Edition, University Press, 2008.
6. Ellis Horowitz, SartajSahni, Dinesh P Mehta, “Fundamentals of
Data Structures in C++”, Second Edition, Silicon Press, 2007.
7.https://infyspringboard.onwingspan.com/web/en/app/toc/lex_auth
_01350157816505139210584/overview

LIST OF EQUIPMENTS:
1. Systems with Linux/Ubuntu Operating System with gnu C++
compiler
63
18. MINI PROJECT SUGGESTION

Objective:
This module facilitate hands-on skills of the students (from the
practical courses more effectively) and they can try the following
mini projects for deep understanding in Data Structures.

Planning:
This method is mostly used to improve the ability of students in
application domain and also to reinforce knowledge imparted during
the lecture.
Being a technical institute, this method is extensively used to provide
empirical evidence of theory learnt.
Students are asked to prepare mini projects involving application of
the concepts, principles or laws learnt.
The faulty guides the students at various stages of developing the
project and gives timely inputs for the development of the model.

64
 MINIPROJECT TOPICS

1. Hospital Patient Management System

Description:
Simulate a hospital's patient management system using a circular linked list to
handle patient queues.

Features:

 Add patients to the queue (based on arrival order).

 Serve patients (remove the next patient in the queue once attended).

 Search for a patient by name or ID.

 Display the current patient queue.

 Support for emergency patients (insert at the front of the queue).

2. Movie Playlist Manager

Description:
Build a movie playlist system using a doubly linked list.

Features:

 Add movies to the playlist (beginning, end, or a specific position).

 Delete movies from the playlist by name or position.

 Traverse through the playlist (next/previous).

 Display the entire playlist.

 Play movies in shuffle mode.

3. To-Do List Manager

Description:
Create a to-do list manager using a singly linked list.

Features:

 Add tasks to the list (beginning, end, or a specific position).

 Mark tasks as completed (remove from the list).

 Display the current list of tasks.

 Sort tasks by priority or due date

4. Circular Parking Lot Management

Description:
Manage a circular parking lot using a circular linked list, where each slot is a node.

Features:

 Park a car in the next available slot.

 Remove a car from a slot.

 Display the status of all parking slots.

 Search for a car by its license plate.

5. City Traffic Light Simulation

Description:
Simulate a city's traffic light system using a circular linked list, where each node represents a
traffic light.

Features:

 Simulate the change of traffic lights in a circular fashion (red -> green -> yellow).

 Display the current status of all traffic lights.

 Manually control a specific light.