May 8, 2022 5 min read Data Structure

Linked List Implementation in C++ - A Step by Step Guide

A linked list is a very simple data structure. It is essentially just a sequence of elements where each element links to the next element.

A linked list can consist of any type of data such as strings, characters, numbers etc. The data can be unique, duplicated, sorted or unsorted.

Difference between Array and Linked List

Elements are indexed in an array. i.e arr[3]. But, in the linked list, we have to iterate through each element.
Insertion and deletion can be very quick in the linked list.
If we're prepending an element the time complexity will be O(1) but in the case of append, it will be O(n) because we're iterating through each element to reach the last element.

Structure of Linked List

First of all, we need to create a structure that defines a single node because a linked list consists of nodes. This structure will have one data variable and a pointer which points to the next node.

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

Creation of Linked List

Once we have our structure, we will need a class which can handle the nodes. This class will consist of two pointer head and tail.

class LinkedList {
Private:
	node *head, *tail;
public:
	LinkedList() {
		// our constructor will set the pointers to nullptr
		// to avoid any garbage value.
		head = nullptr;
		tail = nullptr;
	}
};

At this point, we can write a node creation function. To create a node, we will need a pointer of a node type and the next position of a node which will be initially set to nullptr because it can be the last node of our linked list.

There are two things to keep in mind:

If a linked list is empty then the first node will be both head and tail.
If a linked list has nodes then we will insert a new node at the end and that node will become the tail of our linked list.

void createNode(int value) {
	node *n = new node();
	n->data = value;
	n->next = nullptr;
	if (! head) {
		head = n;
		tail = n;
	} else {
		tail->next = n;
		tail = n;
	}
}

Display Linked List

To display the content of our linked list, let's create a function which can iterate over the address of a node.

void print() {
	node *n = head;
	while (n) {
		cout << n->data << " ";
		n = n->next;
	}
}

Congrats, we have the blueprint of our linked list.
At this point, we will need two additional functions to insert and delete a node to complete the linked list.

Insert a Node

To insert a new node, we need to consider three use-cases:

1. Insert a node at the start:

Create a new node.
In the new node's next field, store the address of the head.
Make the new node the head of our linked list.

void insertNode(int value) {
	node *n = new node();
	n->data = value;
	n->next = head;
	head = n;
}

2. Insert a node at the end:

We have already achieved this functionality during the creation of a node. In that function, we inserted the created node at the end of the linked list.

3. Insert a node at a particular position:

To insert a node at a particular position, first of all, we need to know at which position a user wants to insert it.
After that, we will check which node comes before (previous node) and after our created node.
Once, we know about these two nodes, perform the following steps:

Update the next field of the previous node with the address of the new node.
Store the address of the next (current) node into the next field of the new node.

void insertNodeAtPOS(int pos, int value) {
	node *previous = new node();
	node *current = new node();
	node *n = new node;
	for (int i = 1; i < pos; ++i) {
		previous = current;
		current = current->next;
	}
	n->data = value;
	previous->next = n;
	n->next = current;
}

Delete a Node:

There are cases we need to consider:

1. Delete a node at the start

In this case, we will delete the first (head) node.

Store the address of the head in a pointer.
Make the second node the head of our linked list.
Delete the pointer.

void deleteFirstNode() {
	node *n = new node();
	n = head;
	head = head->next;
	delete n;
}

2. Delete a node at the end

Traverse the linked list and find the second last node.
Make two pointers to check the previous and current nodes.
Make the second last node the tail of our linked list and point the next field to nullptr.
Delete the last node.

void DeleteLastNode() {
	node *previous = new node();
	node *current = new node();
	current = head;
	while(current->next) {
		previous = current;
		current = current->next;
	}
	tail = previous;
	previous->next = nullptr;
	delete current;
}

3. Delete a node at a particular position:

Ask the user to provide the specific position of the node to be deleted.
Make two pointers to check the previous and current nodes.
Delete our current node.
Pass the address of the next node to the previous pointer.

void deleteNodeAtPOS(int pos) {
	node *previous = new node();
	node *current = new node();
	current = head;
	for (int i = 1; i < pos; ++i) {
		previous = current;
		current = current->next;
	}
	previous->next = current->next;
}

Congratulations, our linked list is ready.

Final code

#include <iostream>
using namespace std;

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

class LinkedList {
private:
    node *head, *tail;
public:
    LinkedList() {
        head = nullptr;
        tail = nullptr;
    }
    ~LinkedList() {
        node *previous = nullptr;
        node *current = head;
        while(current) {
            previous = current;
            current = current->next;
            delete previous;
        }
    }
    
    void createNode(int value) {
        node *n = new node();
        n->data = value;
        n->next = nullptr;
        if (! head) {
            head = n;
            tail = n;
        } else {
            tail->next = n;
            tail = n;
        }
    }
    
    void print() {
        node *n = head;
        while(n) {
            cout << n->data << " ";
            n = n->next;
        }
    }
    
    void insertNode(int value) {
        node *n = new node();
        n->data = value;
        n->next = head;
        head = n;
    }
    
    void insertNodeAtPOS(int pos, int value) {
        node *previous = new node();
        node *current = new node();
        current = head;
        for(int i = 1; i < pos; ++i) {
            previous = current;
            current = current->next;
        }
        node *n = new node();
        n->data = value;
        n->next = current;
        previous->next = n;
    }
    
    void deleteNode() {
        node *n = new node();
        n = head;
        head = head->next;
        delete n;
    }
    
    void deleteLastNode() {
        node *previous = new node();
        node *current = new node();
        current = head;
        while(current->next) {
            previous = current;
            current = current->next;
        }
        delete current;
        tail = previous;
        previous->next = nullptr;
    }
    
    void deleteNodeAtPOS(int pos) {
        node *previous = new node();
        node *current = new node();
        current = head;
        for (int i = 1; i < pos; ++i) {
            previous = current;
            current = current->next;
        }
        previous->next = current->next;
    }
};

int main() {
    LinkedList l;
    l.createNode(1);
    l.createNode(2);
    l.createNode(3);
    l.createNode(4);
    l.createNode(5);
    
    cout << "#### Display linkedlist ####" << endl;
    l.print();
    cout << endl;
    
    cout << "#### Insert at start ####" << endl;
    l.insertNode(6);
    l.print();
    cout << endl;
    
    cout << "#### Insert at POS ####" << endl;
    l.insertNodeAtPOS(3, 7);
    l.print();
    cout << endl;
    
    cout << "#### Delete at start ####" << endl;
    l.deleteNode();
    l.print();
    cout << endl;
    
    cout << "#### Delete at end ####" << endl;
    l.deleteLastNode();
    l.print();
    cout << endl;
    
    cout << "#### Delete at POS ####" << endl;
    l.deleteNodeAtPOS(2);
    l.print();
    cout << endl;
    
    return 0;
}