CSL 102-

Data Structures
Module 4

Computer Science and Engineering

Indian Institute of Information Technology, Nagpur.

1
24-02-2026
 Introduction to Linked Lists

• Linked List is a linear data structure, in which elements are not stored at
a contiguous location, rather they are linked using pointers.
• Linked List forms a series of connected nodes, where each node stores
the data and the address of the next node.
• Typically, a linked list, in its simplest form looks like the following

Head
Data Link/Next
50

15 100 20 200 25 300 30 NULL

50 100 200 300

2
24-02-2026
Arrays versus Linked Lists

Head 50 1000
.
30
300
b
.
25
200
x
.
Y
.
20
100

.
15
50
Data Address 3
 Few salient features

• There is a pointer (called header) points the first element (also called
node)

• Successive nodes are connected by pointers.

• Last element points to NULL.

• It can grow or shrink in size during execution of a program.

• It can be made just as long as required.

• It does not waste memory space, consume exactly what it needs.

4
 Why linked list data structure needed?

• Dynamic Data structure: The size of memory can be allocated or de-

allocated at run time based on the operation insertion or deletion.

• Ease of Insertion/Deletion: The insertion and deletion of elements are

simpler than arrays since no elements need to be shifted after insertion
and deletion, Just the address needed to be updated.

• Efficient Memory Utilization: As we know Linked List is a dynamic

data structure the size increases or decreases as per the requirement so this
avoids the wastage of memory.

• Implementation: Various advanced data structures can be implemented

using a linked list like a stack, queue, graph, hash maps, etc.

5
 Disadvantages of Linked Lists

• Random Access: Unlike arrays, linked lists do not allow direct access to
elements by index. Traversal is required to reach a specific node.

• Extra Memory: Linked lists require additional memory for storing the
pointers, compared to arrays.

6
 Defining a Node of a Linked List

• Each structure of the list is called a node, and consists of two fields:
1. Item (or) data
2. Address of the next item in the list (or) pointer to the next node in the
list

How to define a node of a linked list?

struct node
struct node {
{ char name[100];
int data; int code;
struct node *next; float salary;
}; struct node *next;
struct node *head, *ptr; };
ptr=(struct node *)malloc(sizeof(struct node )); struct node *head, *ptr;
ptr=(struct node *)malloc(sizeof(struct node));

Note:
Such structures which contain a member field pointing to the same structure type are called
self-referential structures.
7
 Types of Lists: Single Linked List

Depending on the way in which the links are used to maintain adjacency,
several different types of linked lists are possible.

Single linked list (or simply linked list)

• A head pointer addresses the first element of the list.
• Each element points at a successor element.
• The last element has a link value NULL.

8
 Types of Lists: Double Linked List

• Doubly linked list is almost similar to singly linked list except it contains two
address fields, where one of the address field contains reference of the next
node and other contains reference of the previous node.

• First and last node of a linked list contains a terminator generally a NULL
value, that determines the start and end of the list.

• Doubly linked list is sometimes also referred as bi-directional linked list since
it allows traversal of nodes in both direction.

• Since doubly linked list allows the traversal of nodes in both direction, we can
keep track of both first and last nodes.

9
 Defining a Node of a Double Linked List

Each node of doubly linked list (DLL) consists of three fields:

1. Item (or) Data
2. Pointer of the next node in DLL
3. Pointer of the previous node in DLL

How to define a node of a doubly linked list (DLL)?

struct node node

{
int data; Data
struct node *next; // Pointer to next node in DLL
struct node *prev; // Pointer to previous node in DLL prev next
};

10
 Double versus Single Linked List

Advantages over singly linked list

1) A DLL can be traversed in both forward and backward direction.
2) The delete operation in DLL is more efficient if pointer to the node to be deleted
is given.

Disadvantages over singly linked list

1) Every node of DLL Require extra space for an previous pointer.
2) Implementing and maintaining doubly linked lists can be more complex than
singly linked lists.

11
 Types of Lists: Circular Linked List
• The pointer from the last element in the list points back to the first element.

• A circular linked list is basically a linear linked list that may be single- or
double-linked. The only difference is that there is no any NULL value
terminating the list.

• In fact in the list every node points to the next node and last node points to
the first node, thus forming a circle. Since it forms a circle with no end to
stop it is called as circular linked list.

12
Operations on Linked Lists

13
 Creation of Linked List

struct node *createNode() void traverse(struct node *head)

{ {
struct node *newNode; struct node *ptr=head;
newNode=(struct node *)malloc(sizeof(struct printf("\n The Single Linked List elements are: ");
node)); while(ptr!=NULL)
printf("Enter data\n"); {
scanf("%d", &newNode->data); printf("%d \n",ptr->data);
newNode->next=NULL; ptr=ptr->next;
return newNode; }
} }

#include<stdio.h>
struct node *CreateLL(int n)
#include<stdlib.h>
{
struct node
int i;
{
struct node *head=createNode();
int data;
struct node *curr=head;
struct node *next;
};
for(i=1;i<n;i++)
{ int main()
curr->next=createNode(); {
curr=curr->next; struct node* head=CreateLL(4);
} traverse(head);
return head; return 0;
} } 14
 Insertion in Linked List

SN Operation Description

1 Insertion at beginning It involves inserting any element at the front of the list.
We just need to a few link adjustments to make the
new node as the head of the list.

2 Insertion at end of the It involves insertion at the last of the linked list. The
list new node can be inserted as the only node in the list or
it can be inserted as the last one. Different logics are
implemented in each scenario.

3 Insertion after It involves insertion after the specified node of the

specified node linked list. We need to skip the desired number of
nodes in order to reach the node after which the new
node will be inserted.
15
 Insertion at beginning

Head

100
Old link
30
20 200 25 300 NULL

15 NULL 100 200 300

Tmp /new node 50

16
24-02-2026
 Insertion at beginning

Head

100
Old link
30
20 200 25 300 NULL
head=newnode
15 NULL 100 200 300

Tmp /new node 50 newnode->next=head;

17
24-02-2026
 Insertion at beginning

Head

50

30
20 200 25 300 NULL
head=newnode
15 100 100 200 300

Tmp /new node 50 newnode->next=head; struct node* addBeg(struct node* head)

{
printf("Node to be added in beg\n");
struct node* newnode=createNode();
newnode->next=head;
head=newnode;
return head;
}
18
24-02-2026
 Insertion at end of the list

Head

tmp

20 200 25 NULL

100 200 30 NULL

300

19
24-02-2026
 Insertion at end of the list

Head

tmp

newnode
20 200 25 300

100 200 30 NULL

struct node *addatend(struct node *head)

{ 300 tmp>next= newnode;
struct node *tmp=head;
Struct node* newnode = createnode();
while(tmp-> next!=NULL)
{
tmp=tmp->next;
}
tmp->next= newnode;
return head;
} 20
24-02-2026
 New List after insertion at start an at end

Head
Data Link/Next
50 tmp

15 100 20 200 25 300 30 NULL

50 100 200 300

21
24-02-2026
 Insertion at Pos

Head
Data Link/Next
50 tmp

15 100 20 200 25 300 30 NULL

50 100 200 300

60 NULL newnode->next=tmp->next;

newnode

250

22
24-02-2026
 Insertion at Pos

Head
Data Link/Next
50 tmp

15 100 20 200 25 300 30 NULL

50 100 200 300

60 NULL newnode->next=tmp->next;

newnode

250

23
24-02-2026
 Insertion at Pos

Head
Data Link/Next
50 tmp

15 100 20 200 25 250 30 NULL

50 100 200 300

struct node* addatPos(struct node *head,int pos)
{ 60 NULL newnode->next=tmp->next;
struct node* newnode=createNode();
struct node *tmp=head;
for(int i=1;i<pos-1;i++) tmp->next=newnode; newnode
{

}
tmp=tmp->next; 250
newnode->next=tmp->next;
tmp->next=newnode;
return head;
} 24
24-02-2026
 Single Linked List: Deletion

Deletion steps
•Start from the header node
•Manage links to
•Delete at front
•Delete at end
•Delete at any position
•freeingup the node as free space.

25
24-02-2026
 Deletion and Traversing

SN Operation Description
1 Deletion at beginning It involves deletion of a node from the beginning of the list. This is the simplest
operation among all. It just need a few adjustments in the node pointers.

2 Deletion at the end of the It involves deleting the last node of the list. The list can either be empty or full.
list Different logic is implemented for the different scenarios.

3 Deletion after specified It involves deleting the node after the specified node in the list. we need to skip the
node desired number of nodes to reach the node after which the node will be deleted. This
requires traversing through the list.

4 Traversing In traversing, we simply visit each node of the list at least once in order to perform
some specific operation on it, for example, printing data part of each node present in
the list.

5 Searching In searching, we match each element of the list with the given element. If the
element is found on any of the location then location of that element is returned
otherwise null is returned.

26
24-02-2026
 Free Memory after Deletion

• Do not forget to free() memory location dynamically allocated for a node after
deletion of that node.

• It is the programmer’s responsibility to free that memory block.

• Failure to do so may create a dangling pointer – a memory, that is not used

either by the programmer or by the system.

• The content of a free memory is not erased until it is overwritten.

27
24-02-2026
 Deletion in singly linked list at beginning

struct node *deletefrombeg(struct node *head)

{
struct node *ptr = head;
head = head->next;
free(ptr);
printf("Sucessfully deleted node");
return head;
}
28
24-02-2026
 Deletion in singly linked list at the end

struct node *deletefromend(struct node *head)

{
struct node *ptr = head;
struct node *ptr1;
while(ptr->next != NULL)
{
ptr1 = ptr;
ptr = ptr->next;
}
ptr1->next = NULL;
free(ptr);
29
return head; }
24-02-2026
 Deletion in singly linked list after the specified node

struct node *delafter(struct node *head, int pos)

{
int i;
struct node *ptr, *ptr1;
ptr = head;
for(i = 1; i < pos; i++) {
ptr1 = ptr;
ptr = ptr->next;
}
ptr1->next = ptr->next;
free(ptr);
30
return head; }
24-02-2026
 Traversing

void display(struct node *start)

{
struct node *ptr = start;
printf("the list elements are: \n");
while(ptr != NULL)
{
printf("%d \n", ptr->data);
ptr = ptr->next;
}
}

31
24-02-2026
Delete the Entire Single linked List
Cont…
Cont…
Cont…
Cont…
Cont…
Cont…

Repeat this process till

we reach last node
Cont…
Cont…
Cont…
Cont…
Reverse the Entire Single linked List
Cont…

prev next

Our first target is to put NULL in link part of the 1st node without loosing the
reference of the 2nd node
Cont…

prev next

next
prev
Cont…

prev next

If we want to update link part of 2nd node, we need to move head pointer to the 2nd
node.
Cont…

prev next

next
prev
prev

But we also need to keep the track of previous node so we copy head to prev.
Cont…
After this we move head to next node. i.e. head = next

prev next

We should stop iteration when head becomes NULL

Cont…

while(head != NULL)
{
next = head->link;
head->link = prev;
prev = head;
head = next;
}
head = prev;
 Reverse the Entire Single linked List Program
#include <stdio.h>
#include <stdlib.h> struct node* reverse(struct node *head)
{
struct node { struct node *prev = NULL;
int data; struct node *next = NULL;
struct node* link; while(head != NULL)
}; {
next = head->link;
int main() { head->link = prev;
head = reverse(head); prev = head;
ptr = head; head = next;
while(ptr != NULL) }
{ head = prev;
printf("%d ", ptr->data); return head;
ptr = ptr->link; }
}
return 0;
}
 Doubly linked list
• A Doubly Linked List (DLL) contains an extra pointer, typically called the
previous pointer, together with the next pointer and data which are there in
the singly linked list.

struct node
{
struct node *prev;
int data;
struct node *next;
}

51
24-02-2026
 Doubly linked list

52
24-02-2026
 Doubly linked list
• Advantages of DLL over the singly linked list:
1. A DLL can be traversed in both forward and backward directions.
2. The delete operation in DLL is more efficient if a pointer to the node to be
deleted is given.
3. We can quickly insert a new node before a given node.
4. In a singly linked list, to delete a node, a pointer to the previous node is
needed. To get this previous node, sometimes the list is traversed. In DLL, we
can get the previous node using the previous pointer.

53
24-02-2026
 Doubly linked list
• Disadvantages of DLL over the singly linked list:
• Every node of DLL Requires extra space for a previous pointer.
• All operations require an extra pointer previous to be maintained. For example,
in insertion, we need to modify previous pointers together with the next
pointers.

54
24-02-2026
 Doubly linked list

SN Operation Description
1 Insertion at beginning Adding the node into the linked list at beginning.

2 Insertion at end Adding the node into the linked list to the end.

3 Insertion after specified Adding the node into the linked list after the specified node.
node
4 Deletion at beginning Removing the node from beginning of the list

5 Deletion at the end Removing the node from end of the list.
6 Deletion of the node having Removing the node which is present just after the node containing the
given data given data.

7 Searching Comparing each node data with the item to be searched and return the
location of the item in the list if the item found else return null.

8 Traversing Visiting each node of the list at least once in order to perform some
specific operation like searching, sorting, display, etc.

55
24-02-2026
 Creation of Doubly Linked List
struct node *createNode() void traverseForward(struct node *head)
{ {
struct node *newNode; struct node *ptr = head;
newNode = (struct node *)malloc(sizeof(struct printf("\nForward Traversal:\n");
node)); while(ptr != NULL)
printf("Enter data\n"); {
scanf("%d", &newNode->data); printf("%d\n", ptr->data);
newNode->prev = NULL; ptr = ptr->next;
newNode->next = NULL; }
return newNode; }
}
#include<stdio.h>
struct node *CreateDLL(int n) #include<stdlib.h>
{ struct node
int i; {
struct node *head = createNode(); int data;
struct node *curr = head; struct node *prev;
struct node *newNode; struct node *next;
for(i = 1; i < n; i++) };
{
newNode = createNode(); int main()
curr->next = newNode; {
newNode->prev = curr; struct node *head = CreateDLL(4);
curr = curr->next; traverseForward(head);
} // traverseBackward(head);
return head; return 0;
} }
56
 Insertion in DLL at beginning
struct node *insertatbeg(struct node *head)
{
struct node *newNode = createNode();

if (head == NULL)
{
head = newNode;
}
else
{
newNode->next = head;
head->prev = newNode;
head = newNode;
}

return head;
}

57
24-02-2026
 Insertion in DLL at last
struct node *insertatLast(struct node *head)
{
struct node *newnode = createNode();
struct node *tmp = head;
if (head == NULL) // if LL is empty
{
return newnode;
}
// Traverse to last node
while (tmp->next != NULL)
{
tmp = tmp->next;
}
// Link new node at the end
tmp->next = newnode;
newnode->prev = tmp;

return head;
}
58
24-02-2026
 Insertion in DLL after specified node
struct node* addatPos(struct node *head, int pos)
{
struct node* newnode = createNode();
struct node *tmp = head;
// Move to (pos-1)th node
for(int i = 1; i < pos - 1 && tmp != NULL; i++)
{
tmp = tmp->next;
}
if(tmp == NULL)
{
printf("Invalid position\n"); if(tmp->next != NULL)
return head; tmp->next->prev = newnode;
}
// Linking for DLL tmp->next = newnode;
newnode->next = tmp->next; return head;
newnode->prev = tmp; }

59
24-02-2026
 Deletion in DLL at beginning

struct node* delstart(struct node *head)

{
struct node * ptr = head;
head=head->next;
head->prev=NULL;
free(ptr);
return head;
} 60
24-02-2026
 Deletion in DLL at last

struct node* delstart(struct node *head)

{
struct node * temp = head;
while(temp->next != NULL)
{
temp=temp->next;
}
temp->prev->next=NULL;
free(temp);
return head;
}

61
24-02-2026
 Deletion in DLL at specified location

struct node *deleteafter(struct node *head, int pos)

{
struct node *tmp = head;
int i;
for(i = 1; i < pos; i++)
{
tmp = tmp->next;
}
tmp->prev->next = tmp->next;
tmp->next->prev = tmp->prev;
return head;
} 62
24-02-2026
Cont…
Why Doubly Linked List?
Cont…
Why Doubly Linked List?
 Reverse Doubly Linked List

1. Traverse the linked list using a pointer

2. Swap the prev and next pointers for all nodes

3. At last, change the head pointer of the doubly linked list

 Reverse Doubly Linked List

struct node *reverse(struct node *head)

{ if (temp != NULL)
struct node *temp = NULL; head = temp->prev;
struct node *current = head;
return head;
while (current != NULL) }
{
temp = current->prev;
current->prev = current->next;
current->next = temp;
current = current->prev;
}
Circular Linked List
Cont…
Cont…
Create a Node in Circular Linked List
Cont…
Create a Node in Circular Singly Linked List
Cont…
Reason To have Tail pointer
Cont…
Reason To have Tail pointer
Cont…
Reason To have Tail pointer
Cont…
Reason To have Tail pointer
Cont…
Reason To have Tail pointer
Cont…
Reason To have Tail pointer
Cont…
Reason To have Tail pointer
Cont…
Insertion at Beginning Circular Singly Linked List
Cont…
Insertion at Beginning Circular Singly Linked List
Cont…
Insertion at Beginning Circular Singly Linked List
Cont…
Insertion at Beginning Circular Singly Linked List
Cont…
Insertion at Beginning Circular Singly Linked List
Cont…
Program

struct node struct node *addAtBeg(struct node * tail, int data)

{ {
int data; struct node *newP = malloc(sizeof(struct node));
struct node *next; newP->data = data;
}; newP->next = tail->next;
tail->next = newP;
return tail;
int main() }
{
struct node * tail;
tail = addToEmpty(45);
tail = addAtBeg(tail, 34);
return 0;
}
Cont…
Traverse Circular Singly Linked List
Cont…
Traverse Circular Singly Linked List
Cont…
Traverse Circular Singly Linked List
Cont…
Traverse Circular Singly Linked List
Cont…
Traverse Circular Singly Linked List
Cont…
Traverse Circular Singly Linked List
Cont…
Traverse Circular Singly Linked List
Cont…
Traverse Circular Singly Linked List
Cont…
Traverse Circular Singly Linked List
Cont…
Traverse Circular Singly Linked List
Cont…
Traverse Circular Singly Linked List
Cont…
Traverse Circular Singly Linked List
Cont…
Traverse Circular Singly Linked List
Cont…
Traverse Circular Singly Linked List
Cont…
Traverse Circular Singly Linked List
Cont…
Program

struct node void print(struct node *tail)

{ {
int data; struct node *p = tail->next;
struct node *next; do
}; {
printf("%d ", p->data);
p = p->next;
int main() }while (p!=tail->next);
{ printf("\n");
struct node * tail; }
tail = addToEmpty(45);
tail = addAtBeg(tail, 34);
print(tail);
return 0;
}
Cont…
Insertion at END in Circular Singly Linked List
Cont…
Insertion at END in Circular Singly Linked List
Cont…
Insertion at END in Circular Singly Linked List
Cont…
Insertion at END in Circular Singly Linked List
Cont…
Insertion at END in Circular Singly Linked List
Cont…
Program
struct node struct node *addAtEnd(struct node * tail, int data)
{ {
int data; struct node *newP = malloc(sizeof(struct node));
struct node *next; newP->data = data;
}; newP->next = NULL;

newP->next = tail->next;
int main() tail->next = newP;
{ tail = tail->next;
struct node * tail; return tail;
tail = addToEmpty(45); }
tail = addAtBeg(tail, 34);
tail = addAtEndtail, 4);
return 0;
}
Cont…
Insertion After Given Position in CSLL
Cont…
Insertion After Given Position in CSLL
Cont…
Insertion After Given Position in CSLL
Cont…
Insertion After Given Position in CSLL
Cont…
Insertion After Given Position in CSLL
Cont…
Insertion After Given Position in CSLL
Cont…
Insertion After Given Position in CSLL
Cont…
Insertion After Given Position in CSLL
Cont…
Insertion After Given Position in CSLL
Cont…
Insertion After Given Position in CSLL
Cont…
Insertion After Given Position in CSLL
Cont…
struct node struct node *addAfterPos(struct node * tail, int data, int pos)
{ {
int data; struct node *p = tail->next;
struct node *next; struct node *newP = malloc(sizeof(struct node));
}; newP->data = data;
newP->next = NULL;
while(pos > 1){
int main() p = p->next;
{ pos--;
struct node * tail; }
tail = addToEmpty(45); newP->next = p->next;
tail = addAtBeg(tail, 34); p->next = newP;
print(tail); if(p == tail)
{
tail = addAtEnd(tail, 6); tail = tail->next;
print(tail); }
return 0; return tail;
} }
Cont…
Deletion of First Node in CSLL
Cont…
Deletion of First Node in CSLL
Cont…
Deletion of First Node in CSLL
Cont…
Deletion of First Node in CSLL
Cont…
Deletion of Last Node in CSLL
Cont…
Deletion of Last Node in CSLL
Cont…
Deletion of Last Node in CSLL
Cont…
Deletion of Last Node in CSLL
Cont…
Deletion of Last Node in CSLL
Cont…
Deletion of Last Node in CSLL
Cont…
Deletion of Intermediate Node in CSLL
Cont…
Deletion of Intermediate Node in CSLL
Cont…
Deletion of Intermediate Node in CSLL
Cont…
Deletion of Intermediate Node in CSLL
Cont…
Deletion of Intermediate Node in CSLL
Cont…
Deletion of Intermediate Node in CSLL
Cont…
Deletion of Intermediate Node in CSLL
Cont…
Count Number of Nodes in CSLL
Cont…
Count Number of Nodes in CSLL
Cont…
Count Number of Nodes in CSLL
Cont…
Count Number of Nodes in CSLL
Cont…
Count Number of Nodes in CSLL
Cont…
Count Number of Nodes in CSLL
Cont…
Search an Element in CSLL
Cont…
Search an Element in CSLL
Cont…
Search an Element in CSLL
Cont…
Search an Element in CSLL
Cont…
Search an Element in CSLL
Cont…
Search an Element in CSLL
Circular Doubly Linked List
Cont…
Create a Node in Circular Doubly Linked List
Cont…
Insertion at Beginning
Cont…
Insertion at Beginning
Cont…
Insertion at Beginning
Cont…
Insertion at Beginning
Cont…
Insertion at Beginning
Cont…
Insertion at Beginning
Cont…
Insertion at Beginning
Cont…
Insertion at Beginning
Cont…
Insertion at Beginning
Cont…
Insertion at Beginning
Cont…
Insertion at Beginning
Cont…
Insertion at the End
Cont…
Insertion at the End
Cont…
Insertion at the End
Cont…
Insertion at the End
Cont…
Insertion at the End
Insertion at the End
Cont…
Insertion at the End
Cont…
Insertion after given Position
Cont…
Insertion after given Position
Cont…
Insertion after given Position
Cont…
Insertion after given Position
Cont…
Insertion after given Position
Cont…
Insertion after given Position
Cont…
Insertion after given Position
Cont…
Insertion after given Position
Cont…
Insertion after given Position
Cont…
Insertion after given Position
Cont…
Insertion after given Position
Cont…
Delete the First Node
Cont…
Delete the First Node
Cont…
Delete the First Node
Cont…
Delete the First Node
Cont…
Delete the First Node
Cont…
Delete the First Node
Cont…
Delete the Last Node
Cont…
Delete the Last Node
Cont…
Delete the Last Node
Cont…
Delete the Last Node
Cont…
Delete the Last Node
Cont…
Delete the Last Node
Cont…
Delete the Intermediate Node
Cont…
Delete the Intermediate Node
Cont…
Delete the Intermediate Node
Cont…
Delete the Intermediate Node
Cont…
Delete the Intermediate Node
Cont…
Delete the Intermediate Node
Cont…
Delete the Intermediate Node
Cont…
Delete the Intermediate Node
Cont…
Delete the Intermediate Node
Cont…
Delete the Intermediate Node
Cont…
Delete the Intermediate Node