Data Structures & Algorithms Lab (MDM-222-ETC)
S.E (E & TC) Sem- I
BHARATI VIDYAPEETH’S
COLLEGE OF ENGINEERING FOR WOMEN, PUNE
Pune-Satara Road, Dhankawadi, Taluka – Haveli, Dist.- Pune
Accredited by NAAC with A Grade, Affiliated to Savitribai Phule Pune University (SPPU)
Approved by DTE. Govt. Of Maharashtra and AICTE, New Delhi
DTE Institute Code-EN6285, Pun Code-PU/PN/Engg. /150/2000
E-mail: -coewpune@bharatividyapeeth.edu Website: - http://coewpune.bharatividyapeeth.edu
Department of Electronics and Telecommunication Engineering
___________________________________________________________________________________
Experiment 3: Singly Linked List Operations.
Name: Class: SE Div - I/II
Roll No: Date of Submission:
Marks Obtained: / 10 Signature of the subject teacher:
___________________________________________________________________________________
TITLE: You are building a text editor where lines of text are stored dynamically. You need to allow
insertion and deletion of lines at any position, and display text both normally and in reverse.Use a singly
linked list to implement: display, insert (front/end/middle), delete (front/end/middle), display in reverse,
and reverse the list.
AIM:
To implement Singly Linked List operations (Insertion, Deletion, Display, Reverse) using dynamic
memory allocation in C.
OBJECTIVES:
To implement and understand dynamic memory allocation.
MAPPED OUTCOME: On performing this experiment, the student will be able to:
CO1.3: Implement and demonstrate the applicability of a Linked List.
.
THEORY:
A Linked List is a dynamic data structure used to store a collection of elements (called nodes). Each node
in a singly linked list has two fields:
Data Structures & Algorithms Lab (MDM-222-ETC)
S.E (E & TC) Sem- I
1. Data field – stores the actual information.
2. Link (pointer) field – stores the address of the next node.
The first node is called the head of the list, and the last node points to NULL, indicating the end of the
list.
Unlike arrays:
Linked lists do not require contiguous memory allocation.
Memory is allocated dynamically as nodes are created.
Size can grow or shrink at runtime.
Advantages of Linked List:
Efficient insertion and deletion at any position.
Dynamic size (no fixed limit like arrays).
Disadvantages:
Sequential access only (no direct indexing).
Extra memory required for storing the pointer field.
Types of Linked Lists:
Singly Linked List – Each node points to the next node.
Doubly Linked List – Nodes have links to both next and previous nodes.
Circular Linked List – Last node points back to the head node.
Applications of Linked List:
Dynamic memory management.
Implementation of stacks, queues, and graphs.
Text editors (managing lines of text).
Undo/Redo functionality.
Diagram of Singly Linked List:
Data Structures & Algorithms Lab (MDM-222-ETC)
S.E (E & TC) Sem- I
PSEUDOCODE/ALGORITHM/FLOWCHART:
// Define structure for Node
struct Node {
string line;
struct Node *next;
};
struct Node *head = NULL;
// Function to create a new node
function createNode(text) {
node = allocate memory for Node;
node->line = text;
node->next = NULL;
return node;
}
// Insert at front
function insertFront(text) {
node = createNode(text);
node->next = head;
head = node;
}
// Insert at end
function insertEnd(text) {
node = createNode(text);
if head == NULL
head = node;
else {
temp = head;
while temp->next != NULL
temp = temp->next;
temp->next = node;
}
}
// Insert at given position (1-based)
function insertAtPosition(text, pos) {
if pos == 1
insertFront(text);
else {
Data Structures & Algorithms Lab (MDM-222-ETC)
S.E (E & TC) Sem- I
temp = head;
for i = 1 to pos-2
temp = temp->next;
node = createNode(text);
node->next = temp->next;
temp->next = node;
}
}
// Delete from front
function deleteFront() {
if head == NULL print "Empty list";
else {
temp = head;
head = head->next;
free(temp);
}
}
// Delete from end
function deleteEnd() {
if head == NULL print "Empty list";
else if head->next == NULL {
free(head);
head = NULL;
}
else {
temp = head;
while temp->next->next != NULL
temp = temp->next;
free(temp->next);
temp->next = NULL;
}
}
// Delete from given position
function deleteAtPosition(pos) {
if pos == 1
deleteFront();
else {
temp = head;
for i = 1 to pos-2
temp = temp->next;
node = temp->next;
temp->next = node->next;
Data Structures & Algorithms Lab (MDM-222-ETC)
S.E (E & TC) Sem- I
free(node);
}
}
// Display normally
function display() {
temp = head;
while temp != NULL {
print temp->line;
temp = temp->next;
}
}
// Display in reverse (recursive)
function displayReverse(node) {
if node == NULL return;
displayReverse(node->next);
print node->line;
}
// Reverse the entire list
function reverseList() {
prev = NULL;
current = head;
while current != NULL {
next = current->next;
current->next = prev;
prev = current;
current = next;
}
head = prev;
}
// Main menu
main() {
do {
print "1.InsertFront 2.InsertEnd 3.InsertAtPos 4.DeleteFront";
print "5.DeleteEnd 6.DeleteAtPos 7.Display 8.DisplayReverse 9.ReverseList 10.Exit";
input choice;
switch(choice) {
case 1: insertFront(text); break;
case 2: insertEnd(text); break;
Data Structures & Algorithms Lab (MDM-222-ETC)
S.E (E & TC) Sem- I
case 3: insertAtPosition(text, pos); break;
case 4: deleteFront(); break;
case 5: deleteEnd(); break;
case 6: deleteAtPosition(pos); break;
case 7: display(); break;
case 8: displayReverse(head); break;
case 9: reverseList(); break;
case 10: exit();
}
} while(choice != 10);
}
ORAL QUESTIONS:
1. Define a node in a singly linked list.
2. Differentiate between singly, doubly, and circular linked lists.
3. Why is dynamic memory allocation important in linked lists?
4. How does deletion from the middle of a linked list work?
5. What is the time complexity of searching in a linked list?
CONCLUSION:
