Singly Linked List in C++

A singly Linked List is the simplest linked list in which you can traverse the list only in one direction from head to the last node.

A Linked List is a linear data structure in which each element is stored in the form of a node and each node contains two parts, one part is to store the data and another part contains a pointer pointing to the next node (the pointer holds the address of the next node).

Unlike an array, in linked list nodes are not stored at a contiguous memory location. All nodes are linked using pointers and form a linear structure. We use a head pointer that always points to the first node of the list and it is used to traverse the linked list. The last node of the list points to null that indicates the end of the list.

List of Operations on Singly Linked List.

1. Creating a new List.

Create a class Node with two attributes one is data and the other one is a node. The data is used to store elements and the node is a pointer pointing to the next node.

class Node{
    public:
    int data;
    Node *next;
    //constructor
    Node(int data){
        this->data = data;
        this->next = NULL;
    }
};

As we are creating a completely new list it means there should be no address to store inside the head pointer so in that case, the head pointer points to null. Create a new node and the head node will store the address of the newly created node.

2. Adding a new node to the List.

We have three cases for adding a new node in a singly linked list. We can add a node at the front of the list, at the end of the list, or anywhere in the list.

Adding a node at the front takes O(1) time complexity.
Adding a node at the end takes O(n) time complexity.
Adding a node anywhere in between takes O(n) time complexity.

Read our post, Insertion in a Singly Linked List to understand the process of adding a new node in detail.

3. Search for a node in the list.

To search for a value in a linked list, we need to traverse the list to compare the value and in the worst case, it will take O(n) time. The below function will return true if the value is present in the list.

bool search(Node *head, int value){
    Node *current = head;
    //traverse list
    while(current != NULL){
        if(current->data == value)
           return true;
        current = current->next;   
    }
    return false;
}

4. Remove a node from the list.

We can remove a node from the front, end, or middle of the linked list and worst case it can take O(n) time complexity. Always remember to free the memory of the deleted node.

C++ Code Implementation of Singly Linked List.

//C++ Example of Singly Linked List
#include<iostream>
using namespace std;

class Node{
    public:
    int data;
    Node *next;
    //constructor
    Node(int data){
        this->data = data;
        this->next = NULL;
    }
};

//Add a node to the list
Node *addNode(Node *head, int data){

    Node *new_node = new Node(data);
    //add a new node when list is empty
    if(head == NULL)
      head = new_node;
    //adding new node at the front of the list  
    else{
        new_node->next = head;
        head = new_node;
    }
    return head;  
}

//Search a node in the list
bool search(Node *head, int value){
    Node *current = head;
    //traverse list
    while(current != NULL){
        if(current->data == value)
           return true;
        current = current->next;   
    }
    return false;
}
//Remove a node from the list
void deleteNode(Node* head, int position)
{
    Node* temp;
    Node* prev;
    temp = head;
    prev = head;
    for (int i = 0; i < position; i++) {
        if (i == 0 && position == 1) {
            head = head->next;
            free(temp);
        }
        else {
            if (i == position - 1 && temp) {
                prev->next = temp->next;
                free(temp);
            }
            else {
                prev = temp;
 
                // Position was greater than
                // number of nodes in the list
                if (prev == NULL)
                    break;
                temp = temp->next;
            }
        }
    }
}
//Traversing Linked List
void display(Node *head){
    Node *temp = head;

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

int main(){
    Node *head = new Node(32);
    head = addNode(head, 20);
    head = addNode(head, 40);
    head = addNode(head, 12);

    cout<<"Singly Linked List: ";
    display(head);
    
    if(search(head, 20))
      cout<<"\nValue is present in the List";
    else
      cout<<"\nValue is not present in the List";

    deleteNode(head, 2);

    cout<<"\nSingly Linked List after deletion: ";
    display(head);

    return 0;    
}

Output:

Singly Linked List: 12 40 20 32
Value is present in the List
Singly Linked List after deletion: 12 20 32