Linked List

Singly linked list is a linear data structure in which the elements are
not stored in contiguous memory locations and each element is
connected only to its next element using a pointer.

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.

Node Structure: A node in a linked list typically consists of two

components:
1. Data: It holds the actual value or data associated with the node.
2. Next Pointer or Reference: It stores the memory address
(reference) of the next node in the sequence.

Head and Tail: The linked list is accessed through the head node,
which points to the first node in the list. The last node in the list points
to NULL or nullptr, indicating the end of the list. This node is known as
the tail node.

Why linked list data structure needed?

The main cases where we prefer linked list over arrays is due to ease
of insertion and deletion in linked list

Operations on Linked Lists

1. Insertion: Adding a new node to a linked list involves adjusting the
pointers of the existing nodes to maintain the proper sequence.
Insertion can be performed at the beginning, end, or any position
within the list
2. Deletion: Removing a node from a linked list requires adjusting the
pointers of the neighboring nodes to bridge the gap left by the
 deleted node. Deletion can be performed at the beginning, end, or
any position within the list.
3. Searching: Searching for a specific value in a linked list involves
traversing the list from the head node until the value is found or the
end of the list is reached.

A singly linked list is a fundamental data structure in computer

science and programming, it consists of nodes where each node
contains a data field and a reference to the next node in the node.
The last node points to null, indicating the end of the list. This linear
structure supports efficient insertion and deletion operations, making it
widely used in various applications. In this tutorial, we’ll explore the
node structure, understand the operations on singly linked lists
(traversal, searching, length determination, insertion, and deletion),
and provide detailed explanations and code examples to implement
these operations effectively.
Table of Content
 Understanding Node Structure
 Operations on Singly Linked List
 Traversal in Singly Linked List
 Searching in Singly Linked List
 Finding Length in Singly Linked List
 Insertion in Singly Linked List
 Deletion in Singly Linked List
Understanding Node Structure
In a singly linked list, each node consists of two parts: data and a
pointer to the next node. The data part stores the actual information,
while the pointer (or reference) part stores the address of the next
node in the sequence. This structure allows nodes to be dynamically
linked together, forming a chain-like sequence.

In this representation, each box represents a node, with an arrow

indicating the link to the next node. The last node points to NULL,
indicating the end of the list.
In most programming languages, a node in a singly linked list is
typically defined using a class or a struct.

// Definition of a Node in a singly linked list

struct Node {
int data;
struct Node* next;
};

// Function to create a new Node

struct Node* newNode(int data) {
struct Node* temp =
(struct Node*)malloc(sizeof(struct Node));
temp->data = data;
temp->next = NULL;
return temp;
}
In this example, the Node class contains an integer data field (data) to
store the information and a pointer to another Node (next) to establish
the link to the next node in the list.
Operations on Singly Linked List
 Traversal
 Searching
 Length
 Insertion:
o Insert at the beginning
o Insert at the end
o Insert at a specific position
 Deletion:
o Delete from the beginning
o Delete from the end
o Delete a specific node
Let’s go through each of the operations mentioned above, one by one.
Traversal in Singly Linked List
Traversal involves visiting each node in the linked list and performing
some operation on the data. A simple traversal function would print or
process the data of each node.
Step-by-step approach:
 Initialize a pointer current to the head of the list.
 Use a while loop to iterate through the list until the current pointer
reaches NULL.
 Inside the loop, print the data of the current node and move the
current pointer to the next node.
Below is the function for traversal in singly Linked List:

// Function to traverse and print the elements

// of the linked list
void traverseLinkedList(struct Node* head)
{
// Start from the head of the linked list
struct Node* current = head;

// Traverse the linked list until reaching the end (NULL)

while (current != NULL) {

// Print the data of the current node

printf("%d ", current->data);

// Move to the next node

current = current->next;
}

printf("\n");
}

Output

123
Searching in Singly Linked List
Searching in a Singly Linked List refers to the process of looking for a
specific element or value within the elements of the linked list.
Step-by-step approach:
1. Traverse the Linked List starting from the head.
2. Check if the current node’s data matches the target value.
 If a match is found, return true.
3. Otherwise, Move to the next node and repeat steps 2.
4. If the end of the list is reached without finding a match, return false.
Below is the function for searching in singly linked list:

// Function to search for a value in the Linked List

bool searchLinkedList(struct Node* head, int target)
{
// Traverse the Linked List
while (head != NULL) {
 // Check if the current node's
// data matches the target value
if (head->data == target) {
return true; // Value found
}

// Move to the next node

head = head->next;
}

return false; // Value not found

}
Finding Length in Singly Linked List
Finding Length in Singly Linked List refers to the process of
determining the total number of nodes in a singly linked list.
Step-by-step approach:
 Initialize a counter length to 0.
 Start from the head of the list, assign it to current.
 Traverse the list:
o Increment length for each node.
o Move to the next node (current = current->next).
 Return the final value of length.
Below is the function for finding length in Singly Linked List:

#include <stdio.h>
#include <stdlib.h>

// Definition of a Node in a singly linked list

struct Node {
int data; // Data part of the node
struct Node* next; // Pointer to the next node in the list
};

// Function to find the length of the linked list

int findLength(struct Node* head)
{
// Initialize a counter for the length
int length = 0;

// Start from the head of the list

struct Node* curr = head;

// Traverse the list and increment

 // the length for each node
while (curr != NULL) {
length++;
curr = curr->next;
}

// Return the final length of the linked list

return length;
}

Insertion in Singly Linked List

Insertion is a fundamental operation in linked lists that involves adding
a new node to the list. There are several scenarios for insertion:
a. Insertion at the Beginning of Singly Linked List :

Insertion at the Beginning of Singly Linked List

Step-by-step approach:
 Create a new node with the given value.
 Set the next pointer of the new node to the current head.
 Move the head to point to the new node.
 Return the new head of the linked list.
Below is the function for insertion at the beginning of singly linked list:

// Function to insert a new node at the beginning of the linked list

struct Node* insertAtBeginning(struct Node* head, int value)
{
// Create a new node with the given value
struct Node* new_node = newNode(value);

// Set the next pointer of the new node to the current head
new_node->next = head;
 // Move the head to point to the new node
head = new_node;

// Return the new head of the linked list

return head;
}
b. Insertion at the End of Singly Linked List:
To insert a node at the end of the list, traverse the list until the last
node is reached, and then link the new node to the current last node.-

Step-by-step approach:
 Create a new node with the given value.
 Check if the list is empty:
o If it is, make the new node the head and return.
 Traverse the list until the last node is reached.
 Link the new node to the current last node by setting the last node’s
next pointer to the new node.
Below is the function for insertion at the end of singly linked list:

// Function to insert a node at the end of the linked list

struct Node* insertAtEnd(struct Node* head, int value)
{
// Create a new node with the given value
struct Node* new_node = newNode(value);

// If the list is empty, make the new node the head

if (head == NULL)
return new_node;

// Traverse the list until the last node is reached

struct Node* curr = head;
 while (curr->next != NULL) {
curr = curr->next;
}

// Link the new node to the current last node

curr->next = new_node;

return head;
}
c. Insertion at a Specific Position of the Singly Linked List:
To insert a node at a specific position, traverse the list to the desired
position, link the new node to the next node, and update the links
accordingly.

We mainly find the node after which we need to insert the new node. If
we encounter a NULL before reaching that node, it means that the
given position is invalid.
Below is the function for insertion at a specific position of the singly
linked list:

// Function to insert a node at a specified position

struct Node* insertPos(struct Node* head, int pos, int data) {
if (pos < 1) {
printf("Invalid position!\n");
return head;
}

// Special case for inserting at the head

if (pos == 1) {
struct Node* temp = getNode(data);
temp->next = head;
 return temp;
}

// Traverse the list to find the node

// before the insertion point
struct Node* prev = head;
int count = 1;
while (count < pos - 1 && prev != NULL) {
prev = prev->next;
count++;
}

// If position is greater than the number of nodes

if (prev == NULL) {
printf("Invalid position!\n");
return head;
}

// Insert the new node at the specified position

struct Node* temp = getNode(data);
temp->next = prev->next;
prev->next = temp;

return head;
}

Deletion in Singly Linked List

Deletion involves removing a node from the linked list. Similar to
insertion, there are different scenarios for deletion:
a. Deletion at the Beginning of Singly Linked List:
To delete the first node, update the head to point to the second node in
the list.
Deletion at the Beginning of Singly Linked List

Steps-by-step approach:
 Check if the head is NULL.
o If it is, return NULL (the list is empty).
 Store the current head node in a temporary variable temp.
 Move the head pointer to the next node.
 Delete the temporary node.
 Return the new head of the linked list.
Below is the function for deletion at the beginning of singly linked list:

// Function to remove the first node of the linked list

struct Node* removeFirstNode(struct Node* head)
{
if (head == NULL)
return NULL;

// Move the head pointer to the next node

struct Node* temp = head;
head = head->next;

// Free the memory of the old head

free(temp);

return head;
}
b. Deletion at the End of Singly Linked List:
To delete the last node, traverse the list until the second-to-last node
and update its next field to None.

Deletion at the End of Singly Linked List

Step-by-step approach:
 Check if the head is NULL.
 o If it is, return NULL (the list is empty).
 Check if the head’s next is NULL (only one node in the list).
o If true, delete the head and return NULL.
 Traverse the list to find the second last node (second_last).
 Delete the last node (the node after second_last).
 Set the next pointer of the second last node to NULL.
 Return the head of the linked list.
Below is the function for deletion at the end of singly linked list:
C++CJavaPythonJavaScript

// Function to remove the last node of the linked list

struct Node* removeLastNode(struct Node* head)
{
if (head == NULL)
return NULL;

if (head->next == NULL) {
free(head);
return NULL;
}

// Find the second last node

struct Node* second_last = head;
while (second_last->next->next != NULL)
second_last = second_last->next;

// Delete last node

free(second_last->next);

// Change next of second last

second_last->next = NULL;

return head;
}
c. Deletion at a Specific Position of Singly Linked List:
To delete a node at a specific position, traverse the list to the desired
position, update the links to bypass the node to be deleted.
Deletion at a Specific Position of Singly Linked List

Step-by-step approach:
 Check if the list is empty or the position is invalid, return if so.
 If the head needs to be deleted, update the head and delete the
node.
 Traverse to the node before the position to be deleted.
 If the position is out of range, return.
 Store the node to be deleted.
 Update the links to bypass the node.
 Delete the stored node.
Below is the function for deletion at a specific position of singly linked
list:
C++CJavaPythonJavaScript

// Function to delete a node at a specific position

struct Node* deleteAtPosition(struct Node* head, int position)
{
// If the list is empty or the position is invalid
if (head == NULL || position < 1) {
return head;
}

// If the head needs to be deleted

if (position == 1) {
struct Node* temp = head;
head = head->next;
free(temp);
return head;
}

// Traverse to the node before the position to be deleted

 struct Node* curr = head;
for (int i = 1; i < position - 1 && curr != NULL; i++) {
curr = curr->next;
}

// If the position is out of range

if (curr == NULL || curr->next == NULL) {
return head;
}

// Store the node to be deleted

struct Node* temp = curr->next;

// Update the links to bypass the node to be deleted

curr->next = curr->next->next;

// Delete the node

free(temp);

return head;
}

Find Length of a Linked List (Iterative and Recursive)

Given a Singly Linked List, the task is to find the Length of the Linked
List.
Examples:
Input: LinkedList = 1->3->1->2->1
Output: 5
Input: LinkedList = 2->4->1->9->5->3->6
Output: 7
Count Linked List Nodes

Iterative Approach to Find the Length of a Linked List:

The idea is similar to traversal of Linked List with an additional variable
to count the number of nodes in the Linked List.
Following is the approach to find the length of the Linked List:
 Initialize count as 0.
 Initialize a node pointer, curr = head.
 Do following while curr is not NULL
o curr = curr -> next
o Increment count by 1.
 Return count.
Below is the implementation of the above approach:

// Iterative C program to find length or count of nodes in a

// linked list

#include <stdio.h>
#include <stdlib.h>

// Link list node

struct Node {
int data;
struct Node* next;
};

// Function to create a new node

struct Node* createNode(int new_data) {
struct Node* new_node =
(struct Node*)malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = NULL;
return new_node;
}

// Counts number of nodes in linked list

int countNodes(struct Node* head) {
// Initialize count with 0
int count = 0;

// Initialize curr with head of Linked List

struct Node* curr = head;

// Traverse till we reach NULL

while (curr != NULL) {

// Increment count by 1
count++;

// Move pointer to next node

curr = curr->next;
}

// Return the count of nodes

 return count;
}

// Driver code
int main() {

// Create a hard-coded linked list:

// 1 -> 3 -> 1 -> 2 -> 1
struct Node* head = createNode(1);
head->next = createNode(3);
head->next->next = createNode(1);
head->next->next->next = createNode(2);
head->next->next->next->next = createNode(1);

// Function call
printf("Count of nodes is %d", countNodes(head));
return 0;
}

Output

Count of nodes is 5
Time complexity: O(N), Where N is the size of the linked list
Auxiliary Space: O(1), As constant extra space is used.
Recursive Approach to Find the Length of a Linked List:
The idea is to use recursion by maintaining a function, say
countNodes(node) which takes a node as an argument and calls itself
with the next node until we reach the end of the Linked List. Each of the
recursive call returns 1 + count of remaining nodes.
Below is the implementation of the above approach:

// Recursive C program to find length

// or count of nodes in a linked list

#include <stdio.h>
#include <stdlib.h>

// Link list node

struct Node {
int data;
struct Node* next;
};
// Constructor to initialize a new node with data
struct Node* createNode(int new_data) {
struct Node* new_node = (struct Node*)malloc(sizeof(struct
Node));
new_node->data = new_data;
new_node->next = NULL;
return new_node;
}

// Recursively count number of nodes in linked list

int countNodes(struct Node* head) {

// Base Case
if (head == NULL) {
return 0;
}

// Count this node plus the rest of the list

return 1 + countNodes(head->next);
}

// Driver code
int main() {

// Create a hard-coded linked list:

// 1 -> 3 -> 1 -> 2 -> 1
struct Node* head = createNode(1);
head->next = createNode(3);
head->next->next = createNode(1);
head->next->next->next = createNode(2);
head->next->next->next->next = createNode(1);

// Function call to count the number of nodes

printf("Count of nodes is %d\n", countNodes(head));
return 0;
}

Output

Count of nodes is 5
Time Complexity: O(N), where N is the length of Linked List.
Auxiliary Space: O(N), Extra space is used in the recursion call stack.
 Reverse a Linked List




Given a linked list, the task is to reverse the linked list by changing the
links between nodes.
Examples:
Input: Linked List = 1 -> 2 -> 3 -> 4 -> NULL
Output: Reversed Linked List = 4 -> 3 -> 2 -> 1 -> NULL
Input: Linked List = 1 -> 2 -> 3 -> 4 -> 5 -> NULL
Output: Reversed Linked List = 5 -> 4 -> 3 -> 2 -> 1 -> NULL
Input: Linked List = NULL
Output: Reversed Linked List = NULL
Input: Linked List = 1->NULL
Output: Reversed Linked List = 1->NULL
Recommended Problem

Reverse a linked list

Table of Content
 [Expected Approach] Using Iterative Method – O(n) Time and O(1)
Space
 [Alternate Approach – 1] Using Recursion – O(n) Time and O(n)
Space
 [Alternate Approach – 2] Using Stack – O(n) Time and O(n) Space
[Expected Approach] Using Iterative Method – O(n) Time and O(1)
Space:
The idea is to reverse the links of all nodes using three pointers:
 prev: pointer to keep track of the previous node
 curr: pointer to keep track of the current node
 next: pointer to keep track of the next node
Starting from the first node, initialize curr with the head of linked list and
next with the next node of curr. Update the next pointer of curr with
prev. Finally, move the three pointer by updating prev with curr and
curr with next.
Follow the steps below to solve the problem:
 Initialize three pointers prev as NULL, curr as head, and next as
NULL.
 Iterate through the linked list. In a loop, do the following:
o Store the next node, next = curr -> next
o Update the next pointer of curr to prev, curr -> next = prev
o Update prev as curr and curr as next, prev = curr and curr =
next
Below is the implementation of the above approach:
// Iterative C program to reverse a linked list

#include <stdio.h>

struct Node {
int data;
struct Node* next;
};

// Given the head of a list, reverse the list and return the
// head of reversed list
struct Node* reverseList(struct Node* head) {

// Initialize three pointers: curr, prev and next

struct Node *curr = head, *prev = NULL, *next;
 // Traverse all the nodes of Linked List
while (curr != NULL) {

// Store next
next = curr->next;

// Reverse current node's next pointer

curr->next = prev;

// Move pointers one position ahead

prev = curr;
curr = next;
}

// Return the head of reversed linked list

return prev;
}

void printList(struct Node* node) {

while (node != NULL) {
printf(" %d", node->data);
node = node->next;
}
}

struct Node* createNode(int new_data) {

struct Node* new_node
= (struct Node*)malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = NULL;
return new_node;
}

int main() {

// Create a hard-coded linked list:

// 1 -> 2 -> 3 -> 4 -> 5
struct Node* head = createNode(1);
head->next = createNode(2);
head->next->next = createNode(3);
head->next->next->next = createNode(4);
 head->next->next->next->next = createNode(5);

printf("Given Linked list:");

printList(head);

head = reverseList(head);

printf("\nReversed Linked List:");

printList(head);

return 0;
}

Output

Given Linked list: 1 2 3 4 5

Reversed Linked List: 5 4 3 2 1
Time Complexity: O(n), Traversing over the linked list of size n.
Auxiliary Space: O(1)

[Alternate Approach – 1] Using Recursion – O(n) Time and O(n)

Space:
The idea is to reach the last node of the linked list using recursion then
start reversing the linked list from the last node.
Follow the steps below to solve the problem:
 Divide the list in two parts – first node and rest of the linked list.
 Call reverse for the rest of the linked list.
 Link the rest linked list to first.
 Fix head pointer to NULL.
// Recursive C program to reverse a linked list
#include <stdio.h>

struct Node {
int data;
struct Node* next;
};

// Given the head of a list, reverse the list and return the
// head of reversed list
struct Node* reverseList(struct Node* head) {
if (head == NULL || head->next == NULL)
return head;
 // reverse the rest of linked list and put the first element at the end
struct Node* rest = reverseList(head->next);

// Make the current head as last node of remaining linked list

head->next->next = head;

// Update next of current head to NULL

head->next = NULL;

// Return the reversed linked list

return rest;
}

// This function prints the contents

// of the linked list starting from the head
void printList(struct Node* node) {
while (node != NULL) {
printf(" %d", node->data);
node = node->next;
}
printf("\n");
}

struct Node* createNode(int new_data) {

struct Node* new_node =
(struct Node*)malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = NULL;
return new_node;
}

int main() {

// Create a hard-coded linked list:

// 1 -> 2 -> 3 -> 4 -> 5
struct Node* head = createNode(1);
head->next = createNode(2);
head->next->next = createNode(3);
head->next->next->next = createNode(4);
head->next->next->next->next = createNode(5);
 printf("Given Linked List:");
printList(head);

head = reverseList(head);

printf("Reversed Linked List:");

printList(head);

return 0;
}

Output

Given Linked List: 1 2 3 4 5

Reversed Linked List: 5 4 3 2 1
Time Complexity: O(n), visiting over every node one time.
Auxiliary Space: O(n) , Function call stack space.
[Alternate Approach – 2] Using Stack – O(n) Time and O(n) Space:
The idea is to traverse the linked list and push all nodes except the last
node into the stack. Make the last node as the new head of the
reversed linked list. Now, start popping the element and append each
node to the reversed Linked List. Finally, return the head of the reversed
linked list.

Follow the steps below to solve the problem:

 Push all the nodes(values and address) except the last node in the
stack.
 Once the nodes are pushed, update the Head pointer to the last
node.
 Start popping the nodes and push them at the end of the linked list in
the same order until the stack is empty.
 Update the next pointer of last node in the stack by NULL.
Below is the implementation of the above approach:
// C program to reverse linked list using Stack

#include <stdio.h>

struct Node {
int data;
struct Node* next;
};
// Function to create a new node
struct Node* createNode(int new_data) {
struct Node* new_node =
(struct Node*)malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = NULL;
return new_node;
}

// Function to reverse the linked list

struct Node* reverseList(struct Node* head) {

// Create a stack to store the nodes

struct Node* stack[100000];
int top = -1;

struct Node* temp = head;

// Push all nodes except the last node into stack

while (temp != NULL) {
stack[++top] = temp;
temp = temp->next;
}

// Make the last node as new head of the linked list

if (top >= 0) {
head = stack[top];
temp = head;

// Pop all the nodes and append to the linked list

while (top > 0) {

// append the top value of stack in list and

// pop the top value by decrementing top by 1
temp->next = stack[--top];

// move to the next node in the list

temp = temp->next;
}

// Update the next pointer of last node of stack to NULL

temp->next = NULL;
}
 return head;
}

void printList(struct Node* node) {

while (node != NULL) {
printf(" %d", node->data);
node = node->next;
}
printf("\n");
}

int main() {

// Create a hard-coded linked list:

// 1 -> 2 -> 3 -> 4 -> 5
struct Node* head = createNode(1);
head->next = createNode(2);
head->next->next = createNode(3);
head->next->next->next = createNode(4);
head->next->next->next->next = createNode(5);

printf("Given Linked List:");

printList(head);

head = reverseList(head);

printf("\nReversed Linked List:");

printList(head);

return 0;
}

Output

Given Linked List: 1 2 3 4 5

Reversed Linked List: 5 4 3 2 1
Time Complexity: O(N), Visiting every node of the linked list of size N.
Auxiliary Space: O(N), Space is used to store the nodes in the stack.
Sample Questions

 Identical Linked Lists

 Print the middle of a given linked list
 Write a function to get Nth node in a Linked List
 Nth node from the end of a Linked List
 Move last element to front of a given Linked List
 Make middle node head in a linked list
 Delete alternate nodes of a Linked List
 Add 1 to a number represented as linked list
 Add two numbers represented by linked lists
 Subtract Two Numbers represented as Linked Lists
 Find the sum of last n nodes of the given Linked List
 Pairwise swap elements of a given linked list
 Remove every k-th node of the linked list
 Remove duplicates from a sorted linked list
 Detect loop in a linked list
 Find length of loop in linked list
 Function to check if a singly linked list is palindrome
 Remove duplicates from an unsorted linked list
 Remove all occurrences of duplicates from a sorted Linked List
 Swap nodes in a linked list without swapping data
 Intersection point of two Linked Lists.
 Iteratively Reverse a linked list using only 2 pointers (An Interesting
Method)
 Segregate even and odd nodes in a Linked List
 Alternate Odd and Even Nodes in a Singly Linked List
 Rearrange a Linked List in Zig-Zag fashion
 Adding two polynomials using Linked List
 Union and Intersection of two Linked Lists
 Sort linked list which is already sorted on absolute values

Doubly Linked Lists in C

A Doubly Linked List (DLL) is a type of linked list where each node
contains three components: the data, a pointer to the next node, and a
pointer to the previous node. This allows traversal in both directions—
forward and backward.

Structure of a Doubly Linked List Node

Here’s how you can define a node for a doubly linked list in C:
struct Node {
int data;
struct Node* next;
struct Node* prev;
};
Key Characteristics

1. Bidirectional Traversal: Each node has a pointer to both the next

and the previous node, allowing traversal in both directions.
2. Dynamic Size: Like singly linked lists, doubly linked lists can grow
and shrink in size dynamically.
3. More Memory Usage: Each node requires extra memory for an
additional pointer.

Basic Operations

1. Insertion:
o At the beginning
o At the end
o After a given node

2. Deletion:
o From the beginning
o From the end
o A specific node

3. Traversal: Visiting each node in both directions.

4. Searching: Finding a node with a specific value.

C Programs for Doubly Linked Lists

Here are various C programs demonstrating common operations on a

doubly linked list:

1. Creating a Doubly Linked List

#include <stdio.h>
#include <stdlib.h>

struct Node {
int data;
struct Node* next;
struct Node* prev;
};
// Function to create a new node
struct Node* createNode(int data) {
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->data = data;
new_node->next = NULL;
new_node->prev = NULL;
return new_node;
}
2. Insertion at the Beginning
void insertAtBeginning(struct Node** head_ref, int new_data) {
struct Node* new_node = createNode(new_data);
new_node->next = (*head_ref);
if (*head_ref != NULL)
(*head_ref)->prev = new_node;
*head_ref = new_node;
}
3. Insertion at the End
void insertAtEnd(struct Node** head_ref, int new_data) {
struct Node* new_node = createNode(new_data);
struct Node* last = *head_ref;

if (*head_ref == NULL) {
*head_ref = new_node;
return;
}

while (last->next != NULL) {

last = last->next;
}

last->next = new_node;
new_node->prev = last;
}
4. Insertion After a Given Node
void insertAfter(struct Node* prev_node, int new_data) {
if (prev_node == NULL) {
printf("The given previous node cannot be NULL.\n");
return;
 }

struct Node* new_node = createNode(new_data);

new_node->next = prev_node->next;
prev_node->next = new_node;
new_node->prev = prev_node;

if (new_node->next != NULL) {
new_node->next->prev = new_node;
}
}
5. Deleting a Node
void deleteNode(struct Node** head_ref, struct Node* del) {
if (*head_ref == NULL || del == NULL) return;

if (*head_ref == del) {
*head_ref = del->next; // Change head if node to be deleted is head
}

if (del->next != NULL) {
del->next->prev = del->prev;
}

if (del->prev != NULL) {
del->prev->next = del->next;
}

free(del); // Free memory

}
6. Traversing the List (Forward and Backward)
void printListForward(struct Node* node) {
while (node != NULL) {
printf("%d <-> ", node->data);
node = node->next;
}
printf("NULL\n");
}

void printListBackward(struct Node* node) {

while (node != NULL) {
printf("%d <-> ", node->data);
 node = node->prev;
}
printf("NULL\n");
}
7. Searching for a Node
struct Node* search(struct Node* head, int key) {
struct Node* current = head;
while (current != NULL) {
if (current->data == key) {
return current; // Key found
}
current = current->next;
}
return NULL; // Key not found
}
8. Complete Example with All Operations

Here’s a complete program that incorporates the above functions:

#include <stdio.h>
#include <stdlib.h>

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

struct Node* createNode(int data) {

struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->data = data;
new_node->next = NULL;
new_node->prev = NULL;
return new_node;
}

void insertAtBeginning(struct Node** head_ref, int new_data) {

struct Node* new_node = createNode(new_data);
new_node->next = (*head_ref);
if (*head_ref != NULL)
(*head_ref)->prev = new_node;
*head_ref = new_node;
}

void insertAtEnd(struct Node** head_ref, int new_data) {

struct Node* new_node = createNode(new_data);
struct Node* last = *head_ref;
if (*head_ref == NULL) {
*head_ref = new_node;
return;
}
while (last->next != NULL) {
last = last->next;
}
last->next = new_node;
new_node->prev = last;
}

void insertAfter(struct Node* prev_node, int new_data) {

if (prev_node == NULL) {
printf("The given previous node cannot be NULL.\n");
return;
}
struct Node* new_node = createNode(new_data);
new_node->next = prev_node->next;
prev_node->next = new_node;
new_node->prev = prev_node;

if (new_node->next != NULL) {
new_node->next->prev = new_node;
}
}

void deleteNode(struct Node** head_ref, struct Node* del) {

if (*head_ref == NULL || del == NULL) return;

if (*head_ref == del) {
*head_ref = del->next; // Change head if node to be deleted is head
}

if (del->next != NULL) {
del->next->prev = del->prev;
}

if (del->prev != NULL) {
 del->prev->next = del->next;
}

free(del); // Free memory

}

void printListForward(struct Node* node) {

while (node != NULL) {
printf("%d <-> ", node->data);
node = node->next;
}
printf("NULL\n");
}

void printListBackward(struct Node* node) {

while (node != NULL) {
printf("%d <-> ", node->data);
node = node->prev;
}
printf("NULL\n");
}

struct Node* search(struct Node* head, int key) {

struct Node* current = head;
while (current != NULL) {
if (current->data == key) {
return current; // Key found
}
current = current->next;
}
return NULL; // Key not found
}

int main() {
struct Node* head = NULL;

insertAtEnd(&head, 1);
insertAtEnd(&head, 2);
insertAtEnd(&head, 3);
printf("Initial List: ");
printListForward(head);

insertAtBeginning(&head, 0);
 printf("After Inserting 0 at Beginning: ");
printListForward(head);

insertAfter(head->next, 1); // Insert after the second node

printf("After Inserting 1 After 1st Node: ");
printListForward(head);

deleteNode(&head, head->next); // Delete the second node

printf("After Deleting 2nd Node: ");
printListForward(head);

printf("Searching for 3: %s\n", search(head, 3) != NULL ? "Found" :

"Not Found");

printf("List in Reverse: ");

printListBackward(head);

return 0;
}
Circular Linked Lists in C

A Circular Linked List is a variation of the linked list in which the last
node points back to the first node, forming a circle. This structure allows
for a continuous traversal of the list without needing to check for NULL at
the end.

Types of Circular Linked Lists

1. Circular Singly Linked List: Each node contains a data field and
a pointer to the next node. The last node points to the first node.
2. Circular Doubly Linked List: Each node has pointers to both the
next and the previous nodes. The last node's next pointer points to
the first node, and the first node's previous pointer points to the
last node.

Structure of a Node

Here’s how you can define a node for a circular singly linked list in C:

struct Node {
int data;
struct Node* next;
};
Key Characteristics

1. No NULL Pointers: Unlike regular linked lists, there are no NULL

pointers in a circular linked list.
2. Circular Traversal: You can traverse the entire list starting from
any node and return to the starting point.
3. Dynamic Size: Like other linked lists, circular linked lists can grow
and shrink dynamically.

Basic Operations

1. Insertion:
o At the beginning
o At the end
o After a given node

2. Deletion:
o From the beginning
o From the end
o A specific node

3. Traversal: Visiting each node starting from any node.

4. Searching: Finding a node with a specific value.

C Programs for Circular Linked Lists

Here are various C programs demonstrating common operations on a

circular singly linked list:

1. Creating a Circular Linked List

#include <stdio.h>
#include <stdlib.h>

struct Node {
int data;
struct Node* next;
};

// Function to create a new node

struct Node* createNode(int data) {
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->data = data;
new_node->next = new_node; // Point to itself to make it circular
 return new_node;
}
2. Insertion at the Beginning
void insertAtBeginning(struct Node** head_ref, int new_data) {
struct Node* new_node = createNode(new_data);
struct Node* temp = *head_ref;

if (*head_ref == NULL) {
*head_ref = new_node;
} else {
while (temp->next != *head_ref) {
temp = temp->next; // Traverse to the last node
}
temp->next = new_node; // Link last node to new node
}
new_node->next = *head_ref; // New node points to head
*head_ref = new_node; // Update head
}
3. Insertion at the End
void insertAtEnd(struct Node** head_ref, int new_data) {
struct Node* new_node = createNode(new_data);
struct Node* temp = *head_ref;

if (*head_ref == NULL) {
*head_ref = new_node;
} else {
while (temp->next != *head_ref) {
temp = temp->next; // Traverse to the last node
}
temp->next = new_node; // Link last node to new node
}
new_node->next = *head_ref; // New node points to head
}
4. Insertion After a Given Node
void insertAfter(struct Node* prev_node, int new_data) {
if (prev_node == NULL) {
printf("The given previous node cannot be NULL.\n");
return;
}

struct Node* new_node = createNode(new_data);

 new_node->next = prev_node->next;
prev_node->next = new_node;
}
5. Deleting a Node
void deleteNode(struct Node** head_ref, int key) {
if (*head_ref == NULL) return;

struct Node *temp = *head_ref, *prev = NULL;

// If the head node itself holds the key

if (temp->data == key) {
if (temp->next == *head_ref) { // Only one node
free(temp);
*head_ref = NULL;
return;
} else {
while (temp->next != *head_ref) {
temp = temp->next;
}
temp->next = (*head_ref)->next; // Link last node to second node
free(*head_ref);
*head_ref = temp->next; // Update head
return;
}
}

// Search for the key to be deleted

while (temp->next != *head_ref && temp->next->data != key) {
temp = temp->next;
}

// If key was not found

if (temp->next == *head_ref) return;

struct Node* node_to_delete = temp->next;

temp->next = node_to_delete->next; // Unlink the node
free(node_to_delete); // Free memory
}
6. Traversing the List
void printList(struct Node* head) {
if (head == NULL) return;
 struct Node* temp = head;
do {
printf("%d -> ", temp->data);
temp = temp->next;
} while (temp != head);
printf("(back to %d)\n", head->data);
}
7. Searching for a Node
struct Node* search(struct Node* head, int key) {
if (head == NULL) return NULL;

struct Node* current = head;

do {
if (current->data == key) {
return current; // Key found
}
current = current->next;
} while (current != head);

return NULL; // Key not found

}
8. Complete Example with All Operations

Here’s a complete program that incorporates the above functions:

#include <stdio.h>
#include <stdlib.h>

struct Node {
int data;
struct Node* next;
};

struct Node* createNode(int data) {

struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->data = data;
new_node->next = new_node; // Point to itself
return new_node;
}

void insertAtBeginning(struct Node** head_ref, int new_data) {

 struct Node* new_node = createNode(new_data);
struct Node* temp = *head_ref;

if (*head_ref == NULL) {
*head_ref = new_node;
} else {
while (temp->next != *head_ref) {
temp = temp->next; // Traverse to the last node
}
temp->next = new_node; // Link last node to new node
}
new_node->next = *head_ref; // New node points to head
*head_ref = new_node; // Update head
}

void insertAtEnd(struct Node** head_ref, int new_data) {

struct Node* new_node = createNode(new_data);
struct Node* temp = *head_ref;

if (*head_ref == NULL) {
*head_ref = new_node;
} else {
while (temp->next != *head_ref) {
temp = temp->next; // Traverse to the last node
}
temp->next = new_node; // Link last node to new node
}
new_node->next = *head_ref; // New node points to head
}

void insertAfter(struct Node* prev_node, int new_data) {

if (prev_node == NULL) {
printf("The given previous node cannot be NULL.\n");
return;
}

struct Node* new_node = createNode(new_data);

new_node->next = prev_node->next;
prev_node->next = new_node;
}

void deleteNode(struct Node** head_ref, int key) {

if (*head_ref == NULL) return;
 struct Node *temp = *head_ref, *prev = NULL;

// If the head node itself holds the key

if (temp->data == key) {
if (temp->next == *head_ref) { // Only one node
free(temp);
*head_ref = NULL;
return;
} else {
while (temp->next != *head_ref) {
temp = temp->next;
}
temp->next = (*head_ref)->next; // Link last node to second node
free(*head_ref);
*head_ref = temp->next; // Update head
return;
}
}

// Search for the key to be deleted

while (temp->next != *head_ref && temp->next->data != key) {
temp = temp->next;
}

// If key was not found

if (temp->next == *head_ref) return;

struct Node* node_to_delete = temp->next;

temp->next = node_to_delete->next; // Unlink the node
free(node_to_delete); // Free memory
}

void printList(struct Node* head) {

if (head == NULL) return;

struct Node* temp = head;

do {
printf("%d -> ", temp->data);
temp = temp->next;
} while (temp != head);
printf("(back to %d)\n", head->data);
}
struct Node* search(struct Node* head, int key) {
if (head == NULL) return NULL;

struct Node* current = head;

do {
if (current->data == key) {
return current; // Key found
}
current = current->next;
} while (current != head);

return NULL; // Key not found

}

int main() {
struct Node* head = NULL;

insertAtEnd(&head, 1);
insertAtEnd(&head, 2);
insertAtEnd(&head, 3);
printf("Initial Circular List: ");
printList(head);

insertAtBeginning(&head, 0);
printf("After Inserting 0 at Beginning: ");
printList(head);

insertAfter(head->next, 1); // Insert after the second node

printf("After Inserting 1 After 1st Node: ");
printList(head);

deleteNode(&head, 2); // Delete node with value 2

printf("After Deleting Node with Value 2: ");
printList(head);

printf("Searching for 3: %s\n", search(head, 3) != NULL ? "Found" :

"Not Found");

return 0;
}
Stack Implementation Using a Linked List

A stack follows the Last In First Out (LIFO) principle, where the last
element added is the first to be removed.

Stack Implementation Code

#include <stdio.h>
#include <stdlib.h>

// Define the structure for a stack node

struct StackNode {
int data;
struct StackNode* next;
};

// Function to create a new stack node

struct StackNode* createNode(int data) {
struct StackNode* new_node = (struct
StackNode*)malloc(sizeof(struct StackNode));
new_node->data = data;
new_node->next = NULL;
return new_node;
}

// Function to check if the stack is empty

int isEmpty(struct StackNode* root) {
return !root;
}

// Function to push an item onto the stack

void push(struct StackNode** root, int data) {
struct StackNode* new_node = createNode(data);
new_node->next = *root;
*root = new_node;
printf("%d pushed to stack\n", data);
}

// Function to pop an item from the stack

int pop(struct StackNode** root) {
if (isEmpty(*root)) {
printf("Stack underflow\n");
return -1; // Return -1 if stack is empty
}
 struct StackNode* temp = *root;
int popped = temp->data;
*root = (*root)->next;
free(temp);
return popped;
}

// Function to peek at the top item of the stack

int peek(struct StackNode* root) {
if (isEmpty(root)) {
printf("Stack is empty\n");
return -1; // Return -1 if stack is empty
}
return root->data;
}

// Main function to demonstrate stack operations

int main() {
struct StackNode* stack = NULL;

push(&stack, 10);
push(&stack, 20);
push(&stack, 30);

printf("%d popped from stack\n", pop(&stack));

printf("Top element is %d\n", peek(stack));

return 0;
}
Queue Implementation Using a Linked List

A queue follows the First In First Out (FIFO) principle, where the first
element added is the first to be removed.

Queue Implementation Code

#include <stdio.h>
#include <stdlib.h>

// Define the structure for a queue node

struct QueueNode {
int data;
struct QueueNode* next;
};

// Define the structure for the queue

struct Queue {
struct QueueNode* front;
struct QueueNode* rear;
};

// Function to create a new queue node

struct QueueNode* createNode(int data) {
struct QueueNode* new_node = (struct
QueueNode*)malloc(sizeof(struct QueueNode));
new_node->data = data;
new_node->next = NULL;
return new_node;
}

// Function to create a queue

struct Queue* createQueue() {
struct Queue* queue = (struct Queue*)malloc(sizeof(struct Queue));
queue->front = queue->rear = NULL;
return queue;
}

// Function to check if the queue is empty

int isEmpty(struct Queue* queue) {
return queue->front == NULL;
}

// Function to enqueue an item

void enqueue(struct Queue* queue, int data) {
struct QueueNode* new_node = createNode(data);
if (queue->rear == NULL) {
queue->front = queue->rear = new_node;
printf("%d enqueued to queue\n", data);
return;
}
queue->rear->next = new_node;
queue->rear = new_node;
printf("%d enqueued to queue\n", data);
}

// Function to dequeue an item

int dequeue(struct Queue* queue) {
if (isEmpty(queue)) {
printf("Queue underflow\n");
return -1; // Return -1 if queue is empty
}
struct QueueNode* temp = queue->front;
int dequeued = temp->data;
queue->front = queue->front->next;

// If front becomes NULL, then change rear to NULL

if (queue->front == NULL) {
queue->rear = NULL;
}
free(temp);
return dequeued;
}

// Main function to demonstrate queue operations

int main() {
struct Queue* queue = createQueue();

enqueue(queue, 10);
enqueue(queue, 20);
enqueue(queue, 30);

printf("%d dequeued from queue\n", dequeue(queue));

printf("%d dequeued from queue\n", dequeue(queue));

return 0;
}