Singly Linked List in C++

Introduction

A Singly Linked List is one of the most fundamental data structures taught in Data Structures courses. Unlike arrays, linked lists store elements in non-contiguous memory locations and use pointers to maintain connections between nodes.

This lab session introduces students to singly linked lists using C++, helping them understand how dynamic memory allocation works and how nodes are connected logically. The lab also provides an overview of C++ programming concepts used in implementing linked lists.

Objective of the Lab

The main objective of this lab is to develop practical skills in working with singly linked lists using the C++ programming language.

By the end of this lab, students will:

Understand the concept of dynamic data structures
Learn how nodes are created and linked
Gain hands-on experience using C++ for data structure implementation
Apply linked list operations in real programming scenarios

Activity Outcomes

After completing this lab, students will be able to:

Create a singly linked list
Perform insertion operations in a linked list
Perform deletion operations from a linked list
Traverse and display all nodes of the linked list

Overview of Singly Linked List

A singly linked list consists of:

Data: stores the actual value
Next pointer: stores the address of the next node

Each node points only to the next node, and the last node points to NULL, indicating the end of the list.

struct Nodetype
{
       int data; /* an optional f i e l d */
       /* other useful data fi e l ds */
       Nodetype *next=NULL; /* link to next node, assigned NULL so that should not point garbage*/
};

Nodetype *first=NULL, *last=NULL; /* first and last pointers are global and point first and last node */

A singly-linked list may be depicted as in figure below:

Creation of a Singly Linked List

Creating a singly linked list involves:

Defining a node structure
Allocating memory dynamically
Assigning values to nodes
Linking nodes using pointers

The first node of the list is called the head, which acts as the starting point for all operations.

Insertion in a Singly Linked List

Insertion is the process of adding a new node to the list. Common insertion cases include:

Insertion at the beginning

#include <iostream>
using namespace std;

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

// Function to insert a node at the beginning
void insertAtBeginning(Node* &head, int value) {
    Node* newNode = new Node();
    newNode->data = value;

    // New node points to current head
    newNode->next = head;

    // Head points to new node
    head = newNode;
}

// Function to display the linked list
void display(Node* head) {
    Node* temp = head;
    while (temp != NULL) {
        cout << temp->data << " -> ";
        temp = temp->next;
    }
    cout << "NULL";
}

// Main function
int main() {
    Node* head = NULL;

    insertAtBeginning(head, 10);
    insertAtBeginning(head, 20);
    insertAtBeginning(head, 30);

    cout << "Linked List after insertion at beginning:\n";
    display(head);

    return 0;
}

Insertion at the end

#include <iostream>
using namespace std;

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

// Function to insert a node at the end
void insertAtEnd(Node* &head, int value) {
    Node* newNode = new Node();
    newNode->data = value;
    newNode->next = NULL;

    // If list is empty
    if (head == NULL) {
        head = newNode;
        return;
    }

    // Traverse to the last node
    Node* temp = head;
    while (temp->next != NULL) {
        temp = temp->next;
    }

    // Link last node to new node
    temp->next = newNode;
}

// Function to display the list
void display(Node* head) {
    Node* temp = head;
    while (temp != NULL) {
        cout << temp->data << " -> ";
        temp = temp->next;
    }
    cout << "NULL";
}

// Main function
int main() {
    Node* head = NULL;

    insertAtEnd(head, 10);
    insertAtEnd(head, 20);
    insertAtEnd(head, 30);

    cout << "Linked List after insertion at end:\n";
    display(head);

    return 0;
}

Insertion after a specific node

#include <iostream>
using namespace std;

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

// Function to insert a node after a specific value
void insertAfter(Node* head, int key, int value) {
    Node* temp = head;

    // Traverse the list to find the specific node
    while (temp != NULL && temp->data != key) {
        temp = temp->next;
    }

    // If key is found
    if (temp != NULL) {
        Node* newNode = new Node();
        newNode->data = value;

        // Link new node after the specific node
        newNode->next = temp->next;
        temp->next = newNode;
    } else {
        cout << "Value " << key << " not found in the list.\n";
    }
}

// Function to display the linked list
void display(Node* head) {
    Node* temp = head;
    while (temp != NULL) {
        cout << temp->data << " -> ";
        temp = temp->next;
    }
    cout << "NULL";
}

// Main function
int main() {
    Node* head = NULL;

    // Creating initial list
    head = new Node{10, NULL};
    head->next = new Node{20, NULL};
    head->next->next = new Node{30, NULL};

    cout << "Original List:\n";
    display(head);

    insertAfter(head, 20, 25);

    cout << "\nList after insertion:\n";
    display(head);

    return 0;
}

Insertion before a specific node

#include <iostream>
using namespace std;

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

// Function to insert a node before a specific value
void insertBefore(Node* &head, int key, int value) {
    // If list is empty
    if (head == NULL) {
        cout << "List is empty.\n";
        return;
    }

    // If the key is at the head node
    if (head->data == key) {
        Node* newNode = new Node();
        newNode->data = value;
        newNode->next = head;
        head = newNode;
        return;
    }

    Node* prev = NULL;
    Node* curr = head;

    // Traverse the list to find the specific node
    while (curr != NULL && curr->data != key) {
        prev = curr;
        curr = curr->next;
    }

    // If key is found
    if (curr != NULL) {
        Node* newNode = new Node();
        newNode->data = value;

        // Insert before the specific node
        newNode->next = curr;
        prev->next = newNode;
    } else {
        cout << "Value " << key << " not found in the list.\n";
    }
}

// Function to display the linked list
void display(Node* head) {
    Node* temp = head;
    while (temp != NULL) {
        cout << temp->data << " -> ";
        temp = temp->next;
    }
    cout << "NULL";
}

// Main function
int main() {
    Node* head = NULL;

    // Creating initial list
    head = new Node{10, NULL};
    head->next = new Node{20, NULL};
    head->next->next = new Node{30, NULL};

    cout << "Original List:\n";
    display(head);

    insertBefore(head, 20, 15);

    cout << "\nList after insertion:\n";
    display(head);

    return 0;
}

Insertion requires careful pointer manipulation to ensure the list remains connected without losing existing nodes.

Deletion from a Singly Linked List

Deletion involves removing a node from the list while maintaining the correct sequence of remaining nodes. Common deletion cases are:

Deletion from the beginning

#include <iostream>
using namespace std;

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

// Function to delete a node from the beginning
void deleteFromBeginning(Node* &head) {
    // Check if the list is empty
    if (head == NULL) {
        cout << "List is empty. Nothing to delete.\n";
        return;
    }

    Node* temp = head;      // Store current head
    head = head->next;      // Move head to next node
    delete temp;            // Free memory
}

// Function to display the linked list
void display(Node* head) {
    Node* temp = head;
    while (temp != NULL) {
        cout << temp->data << " -> ";
        temp = temp->next;
    }
    cout << "NULL";
}

// Main function
int main() {
    Node* head = NULL;

    // Creating initial list
    head = new Node{10, NULL};
    head->next = new Node{20, NULL};
    head->next->next = new Node{30, NULL};

    cout << "Original List:\n";
    display(head);

    deleteFromBeginning(head);

    cout << "\nList after deletion from beginning:\n";
    display(head);

    return 0;
}

Deletion from the end

#include <iostream>
using namespace std;

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

// Function to delete a node from the end
void deleteFromEnd(Node* &head) {
    // If list is empty
    if (head == NULL) {
        cout << "List is empty. Nothing to delete.\n";
        return;
    }

    // If list has only one node
    if (head->next == NULL) {
        delete head;
        head = NULL;
        return;
    }

    Node* temp = head;
    Node* prev = NULL;

    // Traverse to the last node
    while (temp->next != NULL) {
        prev = temp;
        temp = temp->next;
    }

    // Remove the last node
    prev->next = NULL;
    delete temp;
}

// Function to display the linked list
void display(Node* head) {
    Node* temp = head;
    while (temp != NULL) {
        cout << temp->data << " -> ";
        temp = temp->next;
    }
    cout << "NULL";
}

// Main function
int main() {
    Node* head = NULL;

    // Creating initial list
    head = new Node{10, NULL};
    head->next = new Node{20, NULL};
    head->next->next = new Node{30, NULL};

    cout << "Original List:\n";
    display(head);

    deleteFromEnd(head);

    cout << "\nList after deletion from end:\n";
    display(head);

    return 0;
}

Deletion of a specific node

#include <iostream>
using namespace std;

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

// Function to delete a specific value
void deleteSpecific(Node* &head, int key) {
    // If list is empty
    if (head == NULL) {
        cout << "List is empty. Nothing to delete.\n";
        return;
    }

    // If the node to be deleted is the head
    if (head->data == key) {
        Node* temp = head;
        head = head->next;
        delete temp;
        return;
    }

    Node* prev = NULL;
    Node* curr = head;

    // Traverse to find the specific node
    while (curr != NULL && curr->data != key) {
        prev = curr;
        curr = curr->next;
    }

    // If key is found
    if (curr != NULL) {
        prev->next = curr->next;
        delete curr;
    } else {
        cout << "Value " << key << " not found in the list.\n";
    }
}

// Function to display the linked list
void display(Node* head) {
    Node* temp = head;
    while (temp != NULL) {
        cout << temp->data << " -> ";
        temp = temp->next;
    }
    cout << "NULL";
}

// Main function
int main() {
    Node* head = NULL;

    // Creating initial list
    head = new Node{10, NULL};
    head->next = new Node{20, NULL};
    head->next->next = new Node{30, NULL};
    head->next->next->next = new Node{40, NULL};

    cout << "Original List:\n";
    display(head);

    deleteSpecific(head, 30);

    cout << "\nList after deleting specific node:\n";
    display(head);

    return 0;
}

During deletion, memory occupied by the removed node must be freed to avoid memory leaks.

Traversal of All Nodes

Traversal means visiting each node of the linked list one by one starting from the head node.

Traversal is used to:

Display list elements

#include <iostream>
using namespace std;

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

// Function to display the linked list elements
void display(Node* head) {
    // Check if the list is empty
    if (head == NULL) {
        cout << "List is empty.\n";
        return;
    }

    Node* temp = head;

    // Traverse the list
    while (temp != NULL) {
        cout << temp->data << " -> ";
        temp = temp->next;
    }
    cout << "NULL";
}

// Main function
int main() {
    Node* head = NULL;

    // Creating a sample linked list
    head = new Node{10, NULL};
    head->next = new Node{20, NULL};
    head->next->next = new Node{30, NULL};

    cout << "Linked List Elements:\n";
    display(head);

    return 0;
}

Search for a value

#include <iostream>
using namespace std;

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

// Function to search for a value in the linked list
bool search(Node* head, int key) {
    Node* temp = head;

    // Traverse the list
    while (temp != NULL) {
        if (temp->data == key) {
            return true;   // Value found
        }
        temp = temp->next;
    }
    return false;          // Value not found
}

// Main function
int main() {
    Node* head = NULL;

    // Creating a sample linked list
    head = new Node{10, NULL};
    head->next = new Node{20, NULL};
    head->next->next = new Node{30, NULL};
    head->next->next->next = new Node{40, NULL};

    int key;
    cout << "Enter value to search: ";
    cin >> key;

    if (search(head, key)) {
        cout << "Value found in the linked list.";
    } else {
        cout << "Value not found in the linked list.";
    }

    return 0;
}

Count the number of nodes

#include <iostream>
using namespace std;

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

// Function to count the number of nodes
int countNodes(Node* head) {
    int count = 0;
    Node* temp = head;

    // Traverse the list
    while (temp != NULL) {
        count++;
        temp = temp->next;
    }

    return count;
}

// Main function
int main() {
    Node* head = NULL;

    // Creating a sample linked list
    head = new Node{10, NULL};
    head->next = new Node{20, NULL};
    head->next->next = new Node{30, NULL};
    head->next->next->next = new Node{40, NULL};

    cout << "Number of nodes in the linked list: " << countNodes(head) << endl;

    return 0;
}

The traversal process continues until a node pointing to NULL is encountered.

Why Use Singly Linked Lists?

Efficient insertion and deletion
Dynamic size allocation
Better memory utilization compared to arrays
Useful in implementing stacks, queues, and other advanced data structures

3) Graded Lab Tasks

Note: The instructor can design graded lab activities according to the level of difficulty and complexity of the solved lab activities. The lab tasks assigned by the instructor should be evaluated in the same lab

Lab Task 1

Add functionality to display the Link List in reverse (both using loops and using recursive approach).

Lab Task 2

Add a function that merges two linked lists passed as parameter into a third new linked list.

Lab Task 3

Add a function to find multiple occurrences of data element in the list..

DS LAB 02: Singly Linked List in C++ | Data Structures Lab with Objectives and Operations

Write A Comment Cancel Reply

DS LAB 02: Singly Linked List in C++ | Data Structures Lab with Objectives and Operations

Singly Linked List in C++

Introduction

Objective of the Lab

Activity Outcomes

Overview of Singly Linked List

Creation of a Singly Linked List

Insertion in a Singly Linked List

Insertion at the beginning

Insertion at the end

Insertion after a specific node

Insertion before a specific node

Deletion from a Singly Linked List

Deletion from the beginning

Deletion from the end

Deletion of a specific node

Traversal of All Nodes

Display list elements

Search for a value

Count the number of nodes

Why Use Singly Linked Lists?

3) Graded Lab Tasks

Lab Task 1

Lab Task 2

Lab Task 3

Related Posts

DS LAB 01: C++ Revision and Array List: A Beginner-Friendly Lab Guide

Lesson 11: Introduction to Queue in C++

Lesson 10: Infix to Postfix Conversion Using Stack

Lesson 09: Introduction to Stack in C++

Write A Comment Cancel Reply