Abstract Data Type(ADT)

ADT is a set of operations

ADT specifies what is to be done but how it is done not specified

Stack ADT have operations like push,pop but we don’t know how those operations are
implemented.

A linked list is a linear data structure in which all the elements, i.e., nodes, are stored in a
sequence but not in contiguous memory locations. Each node of a linked list contains two
parts:

Data: The actual value.

Pointer: A reference to the next node.

A singly linked list refers to a kind of linked list in which each node points to the following
node in the sequence, and the last node points to NULL, indicating the end of the list.

Singly Linked Lists are more commonly used in data structures due to their dynamic
allocation properties, which aid in better memory usage, node insertion, and deletion
compared to arrays.

What is a Singly Linked List in C?

A singly linked list in C is a list of nodes connected together sequentially, where each node
stores:

A piece of data (integer, character, etc.).

Each one gives a pointer to the next node.

The singly linked list starts from the first node, known as the head pointer. If the list is empty,
the head is assigned NULL.

Singly linked lists offer flexibility and dynamic memory utilisation. Unlike arrays, their size is
not fixed, and nodes can be added or removed without requiring memory reallocation or
data shifting.

Working of a Singly Linked List in C

The working mechanism of a singly linked list revolves around creating nodes, linking them,
and managing their connections dynamically. Here’s how it typically works:

Node Creation: Each node is created dynamically using memory allocation functions.
Sequential Linking: Nodes are linked together by assigning the next pointer of one node to
the address of the next node.

Head Management: The head pointer maintains a reference to the first node, ensuring
accessibility to the list.

Termination: The last node's pointer (next) is set to null, signaling that this is the end of the
list.

Traversing a singly linked list thus first starts from the head pointer and follows the chain of
the next pointers until the very end is reached.

Types of Operations in a Singly Linked List

The core strength of a singly linked list lies in its ability to handle dynamic data efficiently.
The primary operations it supports are insertion, deletion, and traversal. Let’s discuss each in
detail.

Insertion Operation in Singly Linked List

Insertion in the singly linked list is simply adding a new node in specific positions. There are
three major types of insertions:

At the beginning

At the end

At a specific position

1. Insertion at the Beginning

This operation involves putting a new node in front of the current head. Then the new node
thus becomes the first node, and the head pointer changes to point to it. This is a very
efficient operation, as it requires a constant amount of time no matter what the length of
the list might be.

Code Example:

#include <stdio.h>

#include <stdlib.h>

// Define the Node structure

struct Node {

int data;

struct Node* next;

};

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

void insertAtBeginning(struct Node** head, int newData) {

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); // Allocate memory

for the new node

newNode->data = newData; // Assign data to the new node

newNode->next = *head; // Make the new node point to the current head

*head = newNode; // Update the head to the new node

// Function to print the linked list

void printList(struct Node* head) {

while (head != NULL) { // Traverse the list until the end

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

head = head->next;

printf("NULL\n"); // Indicate the end of the list

int main() {

struct Node* head = NULL; // Initialize the head pointer to NULL

// Insert elements at the beginning of the list

insertAtBeginning(&head, 10);

insertAtBeginning(&head, 20);

insertAtBeginning(&head, 30);

// Print the linked list

 printList(head);

return 0;

Output:

30 -> 20 -> 10 -> NULL

Process returned 0(0X0) execution time : 2.749 s

press any key to continue

2. Insertion at the End

To add the node at the end, we can traverse the list until we reach the last node. The new
node is attached to the last node's pointer with the address of the new node.

Code Example:

#include <stdio.h>

#include <stdlib.h>

// Define the structure for a linked list node

struct node {

int data;

struct node* next;

};

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

void addLast(struct node** head, int val) {

// Create a new node

struct node* newNode = (struct node*)malloc(sizeof(struct node));

newNode->data = val;

newNode->next = NULL;

// If the linked list is empty, the new node becomes the head
 if (*head == NULL) {

*head = newNode;

} else {

// Otherwise, traverse to the last node

struct node* lastNode = *head;

while (lastNode->next != NULL) {

lastNode = lastNode->next;

// Add the new node at the end

lastNode->next = newNode;

// Function to print the linked list

void printList(struct node* head) {

struct node* temp = head;

while (temp != NULL) {

printf("%d -> ", temp->data); // Print the data in the current node

temp = temp->next; // Move to the next node

printf("NULL\n"); // Indicate the end of the list

int main() {

struct node* head = NULL; // Initialize the linked list as empty

// Add elements to the linked list

addLast(&head, 10);

addLast(&head, 20);
 addLast(&head, 30);

// Print the linked list

printList(head);

return 0;

Output

10 -> 20 -> 30 -> NULL

Process returned 0 (0X0) execution time : 0.848 s

press any key to continue

3. Insertion at a Specific Position

This operation involves navigating to the desired position in the list and adjusting the
pointers of the surrounding nodes to include the new node in the sequence.

Code Example:

#include <stdio.h>

#include <stdlib.h>

// Node structure

struct Node {

int data;

struct Node* next;

};

// Function to create a new node

struct Node* createNode(int x) {

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

if (!newNode) {

printf("Memory allocation failed.\n");

 exit(1);

newNode->data = x;

newNode->next = NULL;

return newNode;

// Function to print the linked list

void printList(struct Node* head) {

struct Node* curr = head;

while (curr != NULL) {

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

curr = curr->next;

printf("NULL\n");

// Function to insert a node at a specific position

struct Node* insertPos(struct Node* head, int pos, int data) {

if (pos < 1) {

printf("Invalid position.\n");

return head;

// If inserting at the head

if (pos == 1) {

struct Node* newNode = createNode(data);

newNode->next = head;
 return newNode;

struct Node* curr = head;

// Traverse to the node just before the desired position

for (int i = 1; i < pos - 1 && curr != NULL; i++) {

curr = curr->next;

// If position is greater than the number of nodes

if (curr == NULL) {

printf("Position is out of bounds.\n");

return head;

struct Node* newNode = createNode(data);

newNode->next = curr->next;

curr->next = newNode;

return head;

// Main function

int main() {

// Creating the list

struct Node* head = createNode(3);

head->next = createNode(5);

head->next->next = createNode(8);

head->next->next->next = createNode(10);
 // Print original list

printf("Original list:\n");

printList(head);

// Insert new node at position

int data = 12, pos = 3;

head = insertPos(head, pos, data);

// Print list after insertion

printf("\nList after insertion:\n");

printList(head);

// Cleanup remaining nodes

while (head != NULL) {

struct Node* temp = head;

head = head->next;

free(temp);

return 0;

Output

original list:

3 -> 5 -> 8 -> 10 -> NULL

List after insertion:

3 -> 5 -> 12 -> 8 -> 10 -> NULL

Deletion Operation in Singly Linked List

Deletion removes a node from the list while maintaining the structural integrity of the
remaining nodes. Similar to insertion, deletion can occur:

At the beginning

At the end

At a specific position

Code Example for Deleting at the Beginning Operation:

To delete the first node, the head pointer must be updated so that it points to the second
node. The memory allocated for the first node is then deallocated.

#include <stdio.h>

#include <stdlib.h>

// Node structure

struct Node {

int data;

struct Node* next;

};

// Function to create a new node

struct Node* createNode(int new_data) {

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

if (!newNode) {

printf("Memory allocation failed.\n");

exit(1);

newNode->data = new_data;

newNode->next = NULL;

return newNode;

}
// Function to delete the head node and return the new head

struct Node* deleteHead(struct Node* head) {

// Check if the list is empty

if (head == NULL) {

printf("The list is already empty.\n");

return NULL;

// Store the current head in a temporary variable

struct Node* temp = head;

// Move the head pointer to the next node

head = head->next;

// Free the memory of the old head node

free(temp);

return head;

// Function to print the linked list

void printList(struct Node* curr) {

while (curr != NULL) {

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

curr = curr->next;

printf("NULL\n");
}

// Main function

int main() {

// Create a hard-coded linked list

struct Node* head = createNode(3);

head->next = createNode(12);

head->next->next = createNode(15);

head->next->next->next = createNode(18);

// Print the original list

printf("Original list:\n");

printList(head);

// Delete the head node

head = deleteHead(head);

// Print the list after deleting the head

printf("\nList after deleting the head:\n");

printList(head);

// Cleanup remaining nodes

while (head != NULL) {

struct Node* temp = head;

head = head->next;

free(temp);

}
 return 0;

Output:

Original list:

3 -> 12 -> 15 -> 18 -> NULL

List after deleting the head:

12 -> 15 -> 18 -> NULL

Code Example for Deleting at End:

This entails traversing to the second-latest node and terminating at the last one connected
by accessing the next pointer via NULL.

#include <stdio.h>

#include <stdlib.h>

// Node structure for the linked list

struct Node {

int data;

struct Node* next;

};

// Function to create a new node

struct Node* createNode(int data) {

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

if (!newNode) {

printf("Memory allocation failed.\n");

exit(1);

newNode->data = data;
 newNode->next = NULL;

return newNode;

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

struct Node* removeLastNode(struct Node* head) {

// If the list is empty, return NULL

if (head == NULL) {

printf("The list is empty.\n");

return NULL;

// If the list has only one node, delete it and return NULL

if (head->next == NULL) {

free(head);

return NULL;

// Find the second last node

struct Node* secondLast = head;

while (secondLast->next->next != NULL) {

secondLast = secondLast->next;

// Delete the last node

free(secondLast->next);

// Change next of second last to NULL

 secondLast->next = NULL;

return head;

// Function to print the linked list

void printList(struct Node* head) {

while (head != NULL) {

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

head = head->next;

printf("NULL\n");

// Driver code

int main() {

// Creating a static linked list

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);

// Print the original list

printf("Original list:\n");

printList(head);

// Removing the last node

 head = removeLastNode(head);

// Print the list after removing the last node

printf("\nList after removing the last node:\n");

printList(head);

// Free remaining nodes to avoid memory leaks

while (head != NULL) {

struct Node* temp = head;

head = head->next;

free(temp);

return 0;

Output:

original list : 1 -> 2 -> 3 -> 4 -> 5 -> NULL

list after removing last node : 1 -> 2 -> 3 -> 4 -> NULL

process returned 0(0X0) exxecution time : 9.561 s

press any key to continue

Deleting a Node at a Specific Position

Here, the pointers of the surrounding nodes are adjusted to bypass the node to be deleted.
The memory allocated for the node is subsequently freed.

#include <stdio.h>

#include <stdlib.h>

// Node structure for the linked list

struct Node {

int data;

struct Node* next;

};

// Function to create a new node

struct Node* newNode(int data) {

struct Node* node = (struct Node*)malloc(sizeof(struct Node));

node->data = data;

node->next = NULL;

return node;

// Function to delete a node at a given position

struct Node* deleteNode(struct Node* head, int position) {

if (head == NULL) {

printf("The list is empty.\n");

return head;

struct Node* temp = head;

// Case 1: If the head is to be deleted

if (position == 1) {

head = head->next;

free(temp);

return head;

}
 // Traverse to the node just before the one to delete

struct Node* prev = NULL;

for (int i = 1; i < position && temp != NULL; i++) {

prev = temp;

temp = temp->next;

// If position is out of bounds

if (temp == NULL) {

printf("Position %d is out of bounds.\n", position);

return head;

// Unlink the node to delete and free it

prev->next = temp->next;

free(temp);

return head;

// Function to print the linked list

void printList(struct Node* head) {

while (head != NULL) {

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

head = head->next;

printf("NULL\n");

}
int main() {

// Create a linked list: 2 -> 3 -> 4 -> 5 -> NULL

struct Node* head = newNode(2);

head->next = newNode(3);

head->next->next = newNode(4);

head->next->next->next = newNode(5);

printf("Original list: ");

printList(head);

// Delete the node at position 2

int position = 2;

head = deleteNode(head, position);

printf("List after deletion: ");

printList(head);

// Cleanup remaining nodes

while (head != NULL) {

struct Node* temp = head;

head = head->next;

free(temp);

return 0;

Output:

original list : 2 -> 3 -> 4 -> 5 -> NULL

list after deletion : 2 -> 4 -> 5 -> NULL

Traversal Operation in Singly Linked List

Traversal refers to visiting each node in the list sequentially to perform operations like
displaying, processing, or searching for data. Starting from the head pointer, the traversal
follows the chain of the next pointers until it reaches the end (NULL).

Traversal is particularly useful for debugging and understanding the current structure of the
list.

Code Example:

#include <stdio.h>

#include <stdlib.h>

// Define the structure for a linked list node

struct Node {

int data;

struct Node* next;

};

// Function to create a new node

struct Node* createNode(int data) {

// Allocate memory for a new node

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

newNode->data = data; // Set the data

newNode->next = NULL; // Initialize the next pointer to NULL

return newNode;

// Function to traverse and print the linked list

void traverseList(struct Node* head) {

// Loop through the list until head becomes NULL

while (head != NULL) {

 printf("%d -> ", head->data); // Print the data of the current node

head = head->next; // Move to the next node

printf("NULL\n"); // Indicate the end of the list

int main() {

// Create a hard-coded linked list with values 10, 20, 30, 40

struct Node* head = createNode(10);

head->next = createNode(20);

head->next->next = createNode(30);

head->next->next->next = createNode(40);

// Traverse and print the linked list

traverseList(head);

// Free the allocated memory for nodes (optional but recommended)

struct Node* temp;

while (head != NULL) {

temp = head;

head = head->next;

free(temp);

return 0;

Output:

10 20 30 40

process returned 0(0X0) execution time : 0.390 s

Press any key to continue

Types of Operations in a Singly Linked List

The core strength of a singly linked list lies in its ability to handle dynamic data efficiently.
The primary operations it supports are insertion, deletion, and traversal. Let’s discuss each in
detail.

Insertion Operation in Singly Linked List

Insertion in the singly linked list is simply adding a new node in specific positions. There are
three major types of insertions:

At the beginning

At the end

At a specific position

1. Insertion at the Beginning

This operation involves putting a new node in front of the current head. Then the new node
thus becomes the first node, and the head pointer changes to point to it. This is a very
efficient operation, as it requires a constant amount of time no matter what the length of
the list might be.

Code Example:

#include <stdio.h>

#include <stdlib.h>

// Define the Node structure

struct Node {

int data;

struct Node* next;

};

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

void insertAtBeginning(struct Node** head, int newData) {

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); // Allocate memory

for the new node
 newNode->data = newData; // Assign data to the new node

newNode->next = *head; // Make the new node point to the current head

*head = newNode; // Update the head to the new node

// Function to print the linked list

void printList(struct Node* head) {

while (head != NULL) { // Traverse the list until the end

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

head = head->next;

printf("NULL\n"); // Indicate the end of the list

int main() {

struct Node* head = NULL; // Initialize the head pointer to NULL

// Insert elements at the beginning of the list

insertAtBeginning(&head, 10);

insertAtBeginning(&head, 20);

insertAtBeginning(&head, 30);

// Print the linked list

printList(head);

return 0;

Output:

30 -> 20 -> 10 -> NULL

Process returned 0(0X0) execution time : 2.749 s

press any key to continue

2. Insertion at the End

To add the node at the end, we can traverse the list until we reach the last node. The new
node is attached to the last node's pointer with the address of the new node.

Code Example:

#include <stdio.h>

#include <stdlib.h>

// Define the structure for a linked list node

struct node {

int data;

struct node* next;

};

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

void addLast(struct node** head, int val) {

// Create a new node

struct node* newNode = (struct node*)malloc(sizeof(struct node));

newNode->data = val;

newNode->next = NULL;

// If the linked list is empty, the new node becomes the head

if (*head == NULL) {

*head = newNode;

} else {

// Otherwise, traverse to the last node

struct node* lastNode = *head;

while (lastNode->next != NULL) {

 lastNode = lastNode->next;

// Add the new node at the end

lastNode->next = newNode;

// Function to print the linked list

void printList(struct node* head) {

struct node* temp = head;

while (temp != NULL) {

printf("%d -> ", temp->data); // Print the data in the current node

temp = temp->next; // Move to the next node

printf("NULL\n"); // Indicate the end of the list

int main() {

struct node* head = NULL; // Initialize the linked list as empty

// Add elements to the linked list

addLast(&head, 10);

addLast(&head, 20);

addLast(&head, 30);

// Print the linked list

printList(head);

return 0;
}

Output

10 -> 20 -> 30 -> NULL

Process returned 0 (0X0) execution time : 0.848 s

press any key to continue

3. Insertion at a Specific Position

This operation involves navigating to the desired position in the list and adjusting the
pointers of the surrounding nodes to include the new node in the sequence.

Code Example:

#include <stdio.h>

#include <stdlib.h>

// Node structure

struct Node {

int data;

struct Node* next;

};

// Function to create a new node

struct Node* createNode(int x) {

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

if (!newNode) {

printf("Memory allocation failed.\n");

exit(1);

newNode->data = x;

newNode->next = NULL;

return newNode;

}
// Function to print the linked list

void printList(struct Node* head) {

struct Node* curr = head;

while (curr != NULL) {

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

curr = curr->next;

printf("NULL\n");

// Function to insert a node at a specific position

struct Node* insertPos(struct Node* head, int pos, int data) {

if (pos < 1) {

printf("Invalid position.\n");

return head;

// If inserting at the head

if (pos == 1) {

struct Node* newNode = createNode(data);

newNode->next = head;

return newNode;

struct Node* curr = head;

// Traverse to the node just before the desired position

for (int i = 1; i < pos - 1 && curr != NULL; i++) {

 curr = curr->next;

// If position is greater than the number of nodes

if (curr == NULL) {

printf("Position is out of bounds.\n");

return head;

struct Node* newNode = createNode(data);

newNode->next = curr->next;

curr->next = newNode;

return head;

// Main function

int main() {

// Creating the list

struct Node* head = createNode(3);

head->next = createNode(5);

head->next->next = createNode(8);

head->next->next->next = createNode(10);

// Print original list

printf("Original list:\n");

printList(head);

// Insert new node at position

 int data = 12, pos = 3;

head = insertPos(head, pos, data);

// Print list after insertion

printf("\nList after insertion:\n");

printList(head);

// Cleanup remaining nodes

while (head != NULL) {

struct Node* temp = head;

head = head->next;

free(temp);

return 0;

Output

original list:

3 -> 5 -> 8 -> 10 -> NULL

List after insertion:

3 -> 5 -> 12 -> 8 -> 10 -> NULL

Deletion Operation in Singly Linked List

Deletion removes a node from the list while maintaining the structural integrity of the
remaining nodes. Similar to insertion, deletion can occur:

At the beginning

At the end

At a specific position
Code Example for Deleting at the Beginning Operation:

To delete the first node, the head pointer must be updated so that it points to the second
node. The memory allocated for the first node is then deallocated.

#include <stdio.h>

#include <stdlib.h>

// Node structure

struct Node {

int data;

struct Node* next;

};

// Function to create a new node

struct Node* createNode(int new_data) {

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

if (!newNode) {

printf("Memory allocation failed.\n");

exit(1);

newNode->data = new_data;

newNode->next = NULL;

return newNode;

// Function to delete the head node and return the new head

struct Node* deleteHead(struct Node* head) {

// Check if the list is empty

if (head == NULL) {
 printf("The list is already empty.\n");

return NULL;

// Store the current head in a temporary variable

struct Node* temp = head;

// Move the head pointer to the next node

head = head->next;

// Free the memory of the old head node

free(temp);

return head;

// Function to print the linked list

void printList(struct Node* curr) {

while (curr != NULL) {

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

curr = curr->next;

printf("NULL\n");

// Main function

int main() {

// Create a hard-coded linked list

 struct Node* head = createNode(3);

head->next = createNode(12);

head->next->next = createNode(15);

head->next->next->next = createNode(18);

// Print the original list

printf("Original list:\n");

printList(head);

// Delete the head node

head = deleteHead(head);

// Print the list after deleting the head

printf("\nList after deleting the head:\n");

printList(head);

// Cleanup remaining nodes

while (head != NULL) {

struct Node* temp = head;

head = head->next;

free(temp);

return 0;

Output:

Original list:

3 -> 12 -> 15 -> 18 -> NULL

List after deleting the head:

12 -> 15 -> 18 -> NULL

Code Example for Deleting at End:

This entails traversing to the second-latest node and terminating at the last one connected
by accessing the next pointer via NULL.

#include <stdio.h>

#include <stdlib.h>

// Node structure for the linked list

struct Node {

int data;

struct Node* next;

};

// Function to create a new node

struct Node* createNode(int data) {

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

if (!newNode) {

printf("Memory allocation failed.\n");

exit(1);

newNode->data = data;

newNode->next = NULL;

return newNode;

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

struct Node* removeLastNode(struct Node* head) {

// If the list is empty, return NULL

if (head == NULL) {

printf("The list is empty.\n");

return NULL;

// If the list has only one node, delete it and return NULL

if (head->next == NULL) {

free(head);

return NULL;

// Find the second last node

struct Node* secondLast = head;

while (secondLast->next->next != NULL) {

secondLast = secondLast->next;

// Delete the last node

free(secondLast->next);

// Change next of second last to NULL

secondLast->next = NULL;

return head;

}
// Function to print the linked list

void printList(struct Node* head) {

while (head != NULL) {

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

head = head->next;

printf("NULL\n");

// Driver code

int main() {

// Creating a static linked list

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);

// Print the original list

printf("Original list:\n");

printList(head);

// Removing the last node

head = removeLastNode(head);

// Print the list after removing the last node

printf("\nList after removing the last node:\n");

printList(head);
 // Free remaining nodes to avoid memory leaks

while (head != NULL) {

struct Node* temp = head;

head = head->next;

free(temp);

return 0;

Output:

original list : 1 -> 2 -> 3 -> 4 -> 5 -> NULL

list after removing last node : 1 -> 2 -> 3 -> 4 -> NULL

process returned 0(0X0) exxecution time : 9.561 s

press any key to continue

Deleting a Node at a Specific Position

Here, the pointers of the surrounding nodes are adjusted to bypass the node to be deleted.
The memory allocated for the node is subsequently freed.

#include <stdio.h>

#include <stdlib.h>

// Node structure for the linked list

struct Node {

int data;

struct Node* next;

};

// Function to create a new node

struct Node* newNode(int data) {

struct Node* node = (struct Node*)malloc(sizeof(struct Node));

node->data = data;

node->next = NULL;

return node;

// Function to delete a node at a given position

struct Node* deleteNode(struct Node* head, int position) {

if (head == NULL) {

printf("The list is empty.\n");

return head;

struct Node* temp = head;

// Case 1: If the head is to be deleted

if (position == 1) {

head = head->next;

free(temp);

return head;

// Traverse to the node just before the one to delete

struct Node* prev = NULL;

for (int i = 1; i < position && temp != NULL; i++) {

prev = temp;

temp = temp->next;
 }

// If position is out of bounds

if (temp == NULL) {

printf("Position %d is out of bounds.\n", position);

return head;

// Unlink the node to delete and free it

prev->next = temp->next;

free(temp);

return head;

// Function to print the linked list

void printList(struct Node* head) {

while (head != NULL) {

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

head = head->next;

printf("NULL\n");

int main() {

// Create a linked list: 2 -> 3 -> 4 -> 5 -> NULL

struct Node* head = newNode(2);

head->next = newNode(3);

head->next->next = newNode(4);
 head->next->next->next = newNode(5);

printf("Original list: ");

printList(head);

// Delete the node at position 2

int position = 2;

head = deleteNode(head, position);

printf("List after deletion: ");

printList(head);

// Cleanup remaining nodes

while (head != NULL) {

struct Node* temp = head;

head = head->next;

free(temp);

return 0;

Output:

original list : 2 -> 3 -> 4 -> 5 -> NULL

list after deletion : 2 -> 4 -> 5 -> NULL

Traversal Operation in Singly Linked List

Traversal refers to visiting each node in the list sequentially to perform operations like
displaying, processing, or searching for data. Starting from the head pointer, the traversal
follows the chain of the next pointers until it reaches the end (NULL).
Traversal is particularly useful for debugging and understanding the current structure of the
list.

Code Example:

#include <stdio.h>

#include <stdlib.h>

// Define the structure for a linked list node

struct Node {

int data;

struct Node* next;

};

// Function to create a new node

struct Node* createNode(int data) {

// Allocate memory for a new node

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

newNode->data = data; // Set the data

newNode->next = NULL; // Initialize the next pointer to NULL

return newNode;

// Function to traverse and print the linked list

void traverseList(struct Node* head) {

// Loop through the list until head becomes NULL

while (head != NULL) {

printf("%d -> ", head->data); // Print the data of the current node

head = head->next; // Move to the next node

printf("NULL\n"); // Indicate the end of the list

}

int main() {

// Create a hard-coded linked list with values 10, 20, 30, 40

struct Node* head = createNode(10);

head->next = createNode(20);

head->next->next = createNode(30);

head->next->next->next = createNode(40);

// Traverse and print the linked list

traverseList(head);

// Free the allocated memory for nodes (optional but recommended)

struct Node* temp;

while (head != NULL) {

temp = head;

head = head->next;

free(temp);

return 0;

Output:

10 20 30 40

process returned 0(0X0) execution time : 0.390 s

Press any key to continue

DOUBLY LINKED LIST:

Prev Data Next

Struct node

struct node*prev;

int data;

struct *next;

};

Create: Prev Next tail

new=(struct node*)malloc(size of struct node)); header NULL 10 2000

scanf(“%d”,&value) 1000 new node

new->prev=NULL;

new->data=value; Prev Next

new->next=NULL; 1000 20 3000

if(head==NULL) 2000 new node

head=new; 2000 30 NULL

tail=new; 3000

else

{
tail->next=new;

new->prev=tail;

tail=new;

DISPLAY:

temp=head 1000 NULL 10 2000

while(temp!=NULL)

1000 20 3000

{ 2000

printf(“%d”,temp->data)

temp=temp->next; 3000 2000 30 NULL

}

Insertion at beginning:

new=(struct node*)malloc(size of struct node));

scanf(“%d”,&value);

new->data=value;

new->prev=null;

new->next=head;

head->prev=new;

head=new;

Insertion at ending:

new=(struct node*)malloc(size of struct node));

scanf(“%d”,&value);

new->data=value;

new->next=null;

new->prev=tail;

tail->next=new;
tail=new;

DELETION

Beginning:

temp=head;

head=head->next;

temp->next=NULL;

head->prev=NULL;

Ending:

temp=tail;

tail=tail->prev;

temp->prev=NULL;

tail->next=NULL;

Deleting an element of specified location:

scanf(“%d”,&pos);

temp=head;

for(i=0;i<pos-1;i++)

temp=temp->next;

temp->next=temp->next->next;

temp->next->prev=temp;
 Circular linked list

Create and display

CREATE:

new=(struct node*)malloc(sizeof(struct node));

scanf(“%d”,&value);

new->data=value;

new->next=NULL;

if(head==NULL)

head=new;

tail=new;

else

tail->next=new;

tail=new;

tail->next=head;

DISPLAY:

while(temp->next!=head)

printf(“%d”,temp->data);

temp=temp->next;

printf(“%d”,temp->data)

Insertion

Beginning:

new=(struct node*)malloc(sizeof(struct node));

scanf(%d”,&value)

new->data=value;

new->next=head;

tail->next=new;

Ending:

new=(struct node*)malloc(sizeof(struct node));

scanf(%d”,&value)

new->data=value;

tail->next=new;

new->next=head;

tail=new;

DELETION:

Beginning:

temp=head;

head=head->next;

tail->next=head;

temp->next=NULL;

ENDING:

temp=head;

while(temp->next!=tail)

temp=temp->next;

tail->next=NULL;

temp->next=head;

tail=temp;
TREES:

A Tree Abstract Data Type (ADT) is a non-linear data structure that organizes data in a
hierarchical manner.

Tree Terminology:

Terminologies used in Trees

 Root – The top node in a tree.

 Child – A node directly connected to another node when moving away from the Root.

 Parent – Any nodes which has one or more children nodes.

 Siblings – Nodes with the same parent.

 Descendant – Any successor node on the path from root to that node.

 Ancestor – Any predecessor node on the path from root to that node

 Leaf – A node with no children.

 Degree – Number of sub trees of a node.

 Edge – Connection between one node to another.

 Path – A sequence of nodes and edges connecting a node with a descendant.

 Level – The level of a node is defined by 1 + (the number of connections between the node
and the root).
 Height of node – The height of a node is the number of edges on the longest downward
path between that node and a leaf.

 Height of tree – The height of a tree is the height of its root node.

 Depth – The depth of a node is the number of edges from the node to the tree's root node.

BINARY TREE ADT:

A Binary Tree is a type of tree data structure where each node can have a maximum of two
child nodes, a left child node and a right child node.

This restriction, that a node can have a maximum of two child nodes.

Types of Binary Trees

FULL BINARY TREE:

If each node of binary tree has either two children or no child at all.

PERFECT BINARY TREE:

A perfect binary tree in which all leaf nodes are at the same level.
COMPLETE BINARY TREE:

A complete binary tree is a binary tree in which every level except possibly the last node is
completely filled from left to right leaving no gaps.

SKEWED BINARY TREE:

If a tree which is dominated by left child node or right child node is said to be a skewed
binary tree.
Each node of a binary tree has the following 3 parts:

Data

Pointer to left child node

Pointer to right child node

Binary Tree Traversals

Binary tree traversal refers to the process of visiting each node in the tree exactly once in a
systematic way. There are four main types of binary tree traversals: in-order, pre-order, post-
order, and level-order. Each traversal method visits nodes in a different order.

1. In-order Traversal (Left, Root, Right)

In in-order traversal, the nodes are recursively visited in this order: left subtree, root node,
and then the right subtree.

Example:

In-order Traversal: 4, 2, 5, 1, 3

Steps:

Visit the left subtree: 4

Visit the root: 2

Visit the right subtree: 5

Visit the root: 1

Visit the right subtree: 3

2. Pre-order Traversal (Root, Left, Right)

In pre-order traversal, the nodes are recursively visited in this order: root node, left subtree,
and then the right subtree
Example:

Pre-order Traversal: 1, 2, 4, 5, 3

Steps:

Visit the root: 1

Visit the left subtree: 2

Visit the left subtree: 4

Visit the right subtree: 5

Visit the right subtree: 3

3. Post-order Traversal (Left, Right, Root)

In post-order traversal, the nodes are recursively visited in this order: left subtree, right
subtree, and then the root node.

Example:

Post-order Traversal: 4, 5, 2, 3, 1

Steps:

Visit the left subtree: 4

Visit the right subtree: 5

Visit the root: 2

Visit the right subtree: 3

Visit the root: 1

4. Level-order Traversal (Breadth-First)

In level-order traversal, the nodes are visited level by level from left to right. This traversal
uses a queue data structure to keep track of nodes.

Example:

Level-order Traversal: 1, 2, 3, 4, 5

Steps:

Visit the root: 1

Visit the nodes at the next level: 2, 3

Visit the nodes at the next level: 4, 5

Implementation of Binary Tree:

Using Arrays

Construct the root node at index 0

Left child is placed at 2i+1 where i is position of parent.

Right child is placed at 2i+2 where i is position of parent

 A
0

i=0,2i+2=2

i=0,2i+1=1
C
B

i=1,2i+1=3 i=1,2i+2=4

D E

i=3,2i+1=7 i=4,2i+1=9

F
G

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

A B C D E - - F - G

BINARY SEARCH TREE:

A binary search tree (BST) is a type of data structure used in computer science to store and
manage data. In a BST, each node is a part of the tree that holds a value. Each node can have
up to two children nodes. The node at the top is called the root.

The main rule of a BST is that for any node:

All the values in the left child and its descendants are smaller than the node's value.

All the values in the right child and its descendants are greater than the node's value.

This structure helps to quickly find, add, or remove values from the tree.
For example, if you want to find a value, you can start at the root and move left or right
depending on whether the value is smaller or larger than the current node, making the
search very efficient.

Example:

Consider the following binary search tree:

1. The root node is 10.

2. The left child of 10 is 5, and all values in the left subtree (3, 5, 7) are less than 10.

3. The right child of 10 is 15, and all values in the right subtree (15, 20) are greater than
10.

1. Insertion
Insertion in binary search tree includes adding a new node in a way that maintains the BST
property: for any node, all values in its left subtree are smaller, and all values in its right
subtree are greater.

Algorithm:

Start at the root node.

Compare the value to be inserted with the current node's value.

If the value is smaller, move to the left child.

If the value is greater, move to the right child.

Repeat steps 2-4 until you find an empty spot.

Insert the new node at the empty spot.

Example:

Insert the value 8 into the following BST:

Step-by-Step Insertion:

Start at the root (10).

8 is less than 10, move to the left child (5).

8 is greater than 5, move to the right child (7).

8 is greater than 7, move to the right child of 7 (which is empty).

Insert 8 as the right child of 7.

Result:
3. Searching

Searching in a binary search tree involves finding a node with a given value by leveraging the
BST property to reduce the number of comparisons.

Algorithm:

Start at the root node.

Compare the target value with the current node's value.

If the value is equal, the search is successful.

If the value is smaller, move to the left child.

If the value is greater, move to the right child.

Repeat steps 2-5 until you find the value or reach an empty spot (unsuccessful search).

Example:Search for the value 8 in the following BST:

Step-by-Step Searching:

Start at the root (10).

8 is less than 10, move to the left child

(5).

8 is greater than 5, move to the right

child (7).

8 is greater than 7, move to the right

child (8).

8 is equal to 8, search is successful.

EXPRESSION TREE:

A stack is used to build an expression tree. For each character, we cycle through the input
expressions and do the following.

If a character is an operand, add it to the stack.

If a character is an operator, pop both values from the stack and make both its children and
push the current node again.

Finally, the stack’s lone element will be the root of an expression tree.

Let us understand this above process using a postfix expression. The implementation of the
expression tree is described for the below expression.

ab+c*

Step1 : The first two symbols are operands, for which we generate a one-node tree
and push a reference to the stack.

Step2 : Next, read a’+’ symbol to pop two pointers to the tree, form a new tree, and push
a pointer to it onto the stack.

Step3 : In the next stage ‘c’ is read, we build a single node tree and store a pointer to it on
the stack.
Step4 : Finally, we read the last symbol’ ‘, pop two tree pointers, and build a new tree with
a,’‘as root, and a pointer to the final tree remains on the stack.
 B-tree

B-tree is a special type of self-balancing search tree in which each node can contain more
than one key and can have more than two children. It is a generalized form of the binary
search tree.

It is also known as a height-balanced m-way tree.

Searching Example

Let us search key k = 17 in the tree below of degree 3.

k is not found in the root so, compare it with the root key.

k is not found on the root

node
Since k > 11 , go to the right child of the root node.

Go to the right subtree

Compare k with 16. Since k > 16 , compare k with the next key 18.

Compare with the keys from

left to right
Since k < 18 , k lies between 16 and 18. Search in the right child of 16 or

the left child of 18. k lies in

between 16 and 18

k is found. k is found
Insertion Operation

If the tree is empty, allocate a root node and insert the key.

Update the allowed number of keys in the node.

Search the appropriate node for insertion.

If the node is full, follow the steps below.

Insert the elements in increasing order.

Now, there are elements greater than its limit. So, split at the median.

Push the median key upwards and make the left keys as a left child and the right keys as a
right child.

If the node is not full, follow the steps below.

Insert the node in increasing order.

The elements to be inserted are 8, 9, 10, 11, 15, 20, 17.
Deletion In B-Tree:

Example:

Let us consider the given tree. From the given tree we are to delete the following elements:

A = 20 , 53 , 89 , 90 , 85.

Assuming we have order = 5; minimum keys = ⌈ m/2⌉ – 1 = 2; maximum keys = ⌈ m/2⌉ + 1 =

4; minimum children = ⌈ m/2⌉ = 3
maximum children = m = 5

maximum children = m = 5
1. If the target key is at the leaf node:

If the target key is at the leaf node, we further study the given data to check if any of the
following cases exist:

Case 1: If the leaf node consists of the min number of keys according to the given
degree/order, then the key is simply deleted from the node.

Case 2: If the leaf contains the minimum number of keys, then:

Case 2a: The node can borrow a key from the immediate left sibling node,if it has more than
the minimum number of keys.The transfer of the keys take place through the parent node,
i.e, the maximum key of the left sibling moves upwards and replaces the parent; while the
parent key moves down to the target node from where the target key is simply deleted.

Case 2b: The node can borrow a key from the immediate right sibling node, if it has more
than the minimum number of keys.The transfer of the keys take place through the parent
node, i.e, the minimum key of the right sibling moves upwards and replaces the parent;
while the parent key moves down to the target node from where the target key is simply
deleted.

Case 2c: If neither of the siblings have keys more than the minimum number of keys
required then, merge the target node with either the left or the right sibling along with the
parent key of respective node.

Step 1:

The first element to be deleted from the tree structure is 20.

We can see the key lies in the leaf node.

Step 2:

The key 20 exists in a leaf node.

The node has more than the minimum number of keys required.

Thus the key is simply deleted from the node.

The tree after deletion is shown as follows.

Step 3:

The next element to be deleted from the tree is 53.

We can see from the image that the key exists in the leaf node.

Step 4:

4. Since the node in which the target key 53 exists has just the minimum number of
keys, we cannot delete it directly.

5. We check if the target node can borrow a key from it’s sibling nodes.

6. Since the target node doesn’t have any right sibling, it borrows from the left sibling
node.

7. As we have studied above how the process of borrow and replace takes place, we
apply it to the given structure.
Step 5:

The key 49 moves upwards to the parent node.

The key 50 moves down to the target node.

Step 6:

Now, since the target node has keys more than the minimum number of keys required, the
key can be deleted directly.

The tree structure after deletion is shown as follows.

Step 7:

 The next element to be deleted is 89.

  The target key lies within a leaf node as seen from the image.

Step 8:

 Again, the target node holds just the minimum number of keys required and hence
the node cannot be deleted directly.

 The target node now has to borrow a key from either of it’s siblings.

 We check the left sibling; it also holds just the minimum number of keys required.

 We check the right sibling node; it has one more than the minimum number of
nodes so the target node can borrow a key from it.
Step 9:

1. The key 93 moves up to the parent node.

2. The parent key 90 moves down to the target node.

Step 10:

Now, as the target node has sufficient number of keys the target key can directly be deleted
from the target node.

The tree structure after deletion is shown as follows.

Step 11:

The next key to be deleted is 90.

The key exists within a leaf node as shown in the image.

Step 12:

We can see that the target node has just the minimum number of keys.

The target node has to borrow a key from either of it’s siblings.

Since each of the siblings just have the number of the minimum keys, it cannot borrow the
keys directly

Step 13:

Since the target node cannot borrow from either of the siblings, we merge the target node,
either of the sibling node and the corresponding parent to them.

The process of merging is shown as follows.

Step 14:

 Since the target node now has sufficient number of keys, the target key 90 can be
deleted directly.

 The tree structure after the deletion of the element is shown as follows.

Step 15:

The next target node is 85.

Now here the node to be deleted is not a leaf node but an internal node.
Step 16:

In case, when an internal node is to be deleted, we replace the key with it’s inorder
predecessor or inorder successor.

We can select either of the child nodes if they have sufficient number of keys.

But as we can see in this case the target internal node can only borrow from it’s right child,
i.e, inorder predecessor.

The key 85 moves down to the child node; key 87 moves up to the parent node.

Step 17:

 Now, as the target key is moved to the leaf node, it can be simply deleted from the
leaf node.
 The final tree structure after deletion of various nodes and preserving the b-tree
properties is shown as follows.