Linked list is a very useful linear data structure. In this article we will get to know about some basic operations of linked list, its types and how it is better than array and also some of its disadvantages.

What is Linked List?

A linked list is a type of linear data structure made up of serially connected nodes. Each node stores data and the address of the subsequent node in this location.

A linked list is composed of nodes, where each node holds a value or data and a reference (or link) to the next node in the sequence.

The first node is called the head, while the last node points to null, indicating the end of the list.

One of the key properties of a linked list is its dynamic nature. Unlike arrays the data are not stored in contiguous addresses. Data can be inserted or deleted from any node without shifting like in arrays.

Topics covered in this article:

• Creating a Node in Linked List
• Insertion in Linked List
• Traversing in Linked List
• Searching a Value in Linked List
• Deleting a Node in Linked List
• Types of Linked List
• Comparison between Array and Linked List
• Advantage and Disadvantage in Linked List

Creating a Node in Linked List:

To create a node in C++ we have used a class here. Inside the class node we have declared a variable called data and a pointer called link.  This is how we create a node.

The structure is as follows-

class Node {
public:
    int data;
    Node* link;
};

Insertion in Linked List:

To insert in a Linked List we have created a function called create. The create function is responsible for inserting new nodes at the end of the linked list. It takes an integer n as input, allocates memory for a new node, assigns n to the data attribute of the new node, and links it to the existing list by updating the link attribute. If the list is empty (i.e., head is NULL), the new node becomes the head and the temp pointer is set to newnode.

The structure is as follows-

void create(int n) {
    Node* newNode = new Node();
    newNode->data = n;
    newNode->link = nullptr;

    if (head == nullptr) {
        head = newNode;
    } else {
        Node* temp = head;
        while (temp->link != nullptr) {
            temp = temp->link;
        }
        temp->link = newNode;
    }
}

Traversing in Linked List:

To insert in a Linked List we have created a function called display. The display function is used to traverse the linked list and print the data values of each node. It starts by setting temp to head and continues until temp becomes NULL. It prints the data value of the current node, moves temp to the next node using the link attribute, and repeats the process until the end of the list is reached.

The structure is as follows-

 void display() {
    Node* temp = head;
    while (temp != nullptr) {
        cout << temp->data << " ";
        temp = temp->link;
    }
    cout << endl;
}

The implementation of the code to create, insert and display the nodes of a linked list is as follows-

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* link;
};

Node* head = nullptr;

void create(int n) {
    Node* newNode = new Node();
    newNode->data = n;
    newNode->link = nullptr;

    if (head == nullptr) {
        head = newNode;
    } else {
        Node* temp = head;
        while (temp->link != nullptr) {
            temp = temp->link;
        }
        temp->link = newNode;
    }
}

void display() {
    Node* temp = head;
    while (temp != nullptr) {
        cout << temp->data << " ";
        temp = temp->link;
    }
    cout << endl;
}

int main() {
    create(5);
    create(6);
    create(7);
    create(8);

    cout << "The linked list is: ";
    display();

    return 0;
}

Output:

the linked list is:5 6 7 8 

Searching an Element in Linked List

To search an element in a Linked List we can do the searching we can either search by the element itself to find location or search by location to find what data is available in that particular location. C++ code for both methods have been provided.

Search an Element Location in Linked List:

Here we insert a element or data, and we obtain the location of the inserted data in the linked list. 

//create the node and insert as mentioned before

void searchLocationOf(int value)
{
    Node* temp = head;
    int pos = 1;
    bool found = false;
    while (temp != nullptr)
    {
        if (temp->data == value)
        {
            found = true;
            break;
        }
        temp = temp->link;
        pos++;
    }
    
    if (found)
    {
        cout << "Location of data " << value << ": " << pos << endl;
    }
    else
    {
        cout << "Data not found in the list." << endl;
    }
}

int count()
{
    Node* temp = head;
    int count = 0;
    while (temp != nullptr)
    {
        temp = temp->link;
        count++;
    }
    return count;
}

void display()
{
    Node* temp = head;
    while (temp != nullptr)
    {
        cout << temp->data << " ";
        temp = temp->link;
    }
    cout << endl;
}

int main()
{
    create(5);
    create(6);
    create(7);
    create(8);

    int value;
    cout << "Enter the data value you want to search: ";
    cin >> value;

    searchLocationOf(value);

    return 0;
}

Output 1:

Enter the data value you want to search: 5
Location of data 5: 1

Output 2:

Enter the data value you want to search: 2
Data not found in the list.

Find the Element at an Given Location in Linked List:

Finding a data at a given location can be tedious if the list is long enough. To find what data is present at a particular location we insert a location value, and we obtain the data or value present at the location we searched for in the linked list. 

//create the node and insert node as mentioned before

void searchNoAt(int p)
{
    Node* temp = head;
    int pos = 1;
    while (temp != nullptr && pos != p)
    {
        temp = temp->link;
        pos++;
    }
    
    if (temp != nullptr)
    {
        cout << "Data at position " << p << ": " << temp->data << endl;
    }
    else
    {
        cout << "Invalid position!" << endl;
    }
}

int count()
{
    Node* temp = head;
    int count = 0;
    while (temp != nullptr)
    {
        temp = temp->link;
        count++;
    }
    return count;
}

void display()
{
    Node* temp = head;
    while (temp != nullptr)
    {
        cout << temp->data << " ";
        temp = temp->link;
    }
    cout << endl;
}

int main()
{
    create(5);
    create(6);
    create(7);
    create(8);


    int p;
    int listSize = count();
    cout << "Enter the position you want to search: ";
    cin >> p;

    if (p <= listSize && p > 0)
    {
        searchNoAt(p);
    }
    else
    {
        cout << "Invalid position! Enter a position within the range 1 to " << listSize << endl;
    }

    return 0;
}

Output 1:

Enter the position you want to search: 3
Data at position 3: 7

Output 2:

Enter the position you want to search: 7
Invalid position! Enter a position within the range 1 to 4

Deleting a Node in Linked List:

In a Linked List you may be asked to delete the Head, Tail or any node at a given position. Here's an implementation to perform the task.

Deleting Head and Tail in Linked List:

//Create the node and insert node as mentioned before

//----functions to delete head and tail

void deleteHead() {
    if (head == nullptr) {
        cout << "List is empty. Unable to delete." << endl;
        return;
    }

    Node* temp = head;
    head = head->link;
    delete temp;
}
void deleteTail() {
    if (head == nullptr) {
        cout << "List is empty. Unable to delete." << endl;
        return;
    }

    if (head->link == nullptr) {
        // Deleting the only node in the list
        delete head;
        head = nullptr;
        return;
    }
    Node* temp = head;
    while (temp->link->link != nullptr) {
        temp = temp->link;
    }

    Node* delNode = temp->link;
    temp->link = nullptr;
    delete delNode;
}
void display() {
    Node* temp = head;
    while (temp != nullptr) {
        cout << temp->data << " ";
        temp = temp->link;
    }
    cout << endl;
}
int main() {
    create(5);
    create(6);
    create(7);
    create(8);

	// Delete head
    cout<<"after deleting head: ";
    deleteHead();
    display();

    // Delete tail
    cout<<"after deleting tail: ";

    deleteTail();
    display();

    return 0;
}

Output:

after deleting head: 6 7 8
after deleting tail: 6 7 

Deleting at any Position Linked List:

//Create the node and insert node as mentioned before

void deleteAtLocation(int pos) {
    if (head == nullptr) {
        cout << "List is empty. Unable to delete." << endl;
        return;
    }

    if (pos == 1) {
        // Deleting the head node
        Node* temp = head;
        head = head->link;
        delete temp;
    } else {
        // Deleting a node at a specific position
        Node* prev = nullptr;
        Node* curr = head;
        int count = 1;

        while (count < pos && curr != nullptr) {
            prev = curr;
            curr = curr->link;
            count++;
        }

        if (curr == nullptr) {
            cout << "Invalid position. Unable to delete." << endl;
            return;
        }

        prev->link = curr->link;
        delete curr;
    }
}

void display() {
    Node* temp = head;
    while (temp != nullptr) {
        cout << temp->data << " ";
        temp = temp->link;
    }
    cout << endl;
}

int main() {
    create(5);
    create(6);
    create(7);
    create(8);

    int pos;

    cout << "Enter the position to delete: ";
    cin >> pos;

    deleteAtLocation(pos);

    display();

    return 0;
}

Output:

Enter the position to delete: 1
6 7 8 

Types of Linked List:

Linked lists are a popular data structure used in programming and can be classified into several types based on their properties and functionalities. Here are the commonly known types of linked lists:

Singly Linked List:

• In a singly linked list, each node contains a data element and a pointer (often called link or next) to the next node in the list.
• It allows traversal only in one direction, starting from the head node to the tail node.
• It is the simplest and most commonly used type of linked list.

We have discussed about various operations of singly linked list above.

Doubly Linked List:

• In a doubly linked list, each node contains a data element and two pointers: one pointing to the previous node (often called prev or previous) and the other to the next node (often called next).
• It allows traversal in both directions, forwards and backwards, which provides more flexibility compared to a singly linked list.
• It requires more memory to store the additional pointer for each node.

Circular Linked List:

• In a circular linked list, the last node of the list points back to the first node, creating a loop or circle.
• It can be implemented as a singly linked list or a doubly linked list.
• It is useful in scenarios where continuous looping or circular operations are required, such as round-robin scheduling.

Comparison between Array and Linked List:

Advantage and Disadvantage of Linked List: