Linked List - Operations

Linked List

Linked List is a linear data structure where each element is a separate object called node. Each node contains the data and a pointer to the next node.

To learn more about Linked List, read the article Linked List.

Operations on Linked List

Don't you want to do some crazy stuff with your Linked List? Well, you can do that. Let's have a look at some of the operations that can be performed on a Linked List.

Insertion at the beginning

You have a Linked List and you want to insert a new node at the beginning of the Linked List. How will you do that? Let's have a look at the code.

void insertAtBeginning(int data) {
    Node* newNode = new Node(data);

    if (head == NULL) {
        head = newNode;
        return;
    }

    newNode->next = head;
    head = newNode;
}

Here goes the explanation.

1. First, we created a new node newNode with the data passed to the function.
2. Then, we checked if the Linked List is empty or not. If the Linked List is empty, we assigned the newNode to the head variable of the Linked List and returned from the function.
3. If the Linked List is not empty, we assigned the head variable of the Linked List to the next variable of the newNode, that is newNode->next = head;. Then, we assigned the newNode to the head variable of the Linked List to make the newNode the first node of the Linked List.

Insertion at the end

You want to insert a new node at the end of the Linked List too. How will you do that? Let's have a look at the code.

void insertAtEnd(int data) {
    Node* newNode = new Node(data);

    if (head == NULL) {
        head = newNode;
        return;
    }

    Node* temp = head;
    while (temp->next != NULL) {
        temp = temp->next;
    }

    temp->next = newNode;
}

Here goes the explanation.

1. First, we created a new node newNode with the data passed to the function.
2. Again we checked if the Linked List is empty or not. If the Linked List is empty, we assigned the newNode to the head variable of the Linked List and returned from the function. The newNode will be the end node. Because, the only node present in the Linked List is the newNode.
3. If the Linked List is not empty, we created a new node temp and assigned the head variable of the Linked List to it. Then, we traversed the Linked List until we reached the last node.
4. Then, we assigned the newNode to the next variable of the last node, that is temp->next = newNode;.

Insertion at a given position

But, I guess you want to insert a new node at any position in the Linked List. How will you do that? Let's have a look at the code.

void insertAtPosition(int data, int position) {
    Node* newNode = new Node(data);

    if (head == NULL) {
        head = newNode;
        return;
    }

    if (position == 1) {
        newNode->next = head;
        head = newNode;
        return;
    }

    Node* temp = head;
    for (int i = 1; i < position - 1; i++) {
        temp = temp->next;
    }

    newNode->next = temp->next;
    temp->next = newNode;
}

Search

You have got a Linked List and you want to search for a node with a given data. How will you do that? Let's have a look at the code.

bool search(int data) {
    Node* temp = head;

    while (temp != NULL) {
        if (temp->data == data) {
            return true;
        }

        temp = temp->next;
    }

    return false;
}

Here goes the explanation.

1. First, we created a new node temp and assigned the head variable of the Linked List to it.
2. Then, we traversed the Linked List until we reached the last node.
3. Then, we checked if the data of the current node is equal to the data passed to the function. If it is, we returned true from the function. If not, we moved to the next node.
4. If we reached the last node of the Linked List and still the data is not found, we returned false from the function.

Traversal

Now you know how to search for a node with a given data. But, you want to print the data of all the nodes in the Linked List. How will you do that? Let's go through it.

void traverse() {
    Node* temp = head;

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

    cout << endl;
}

Here goes the explanation.

1. First, we created a new node temp and assigned the head variable of the Linked List to it.
2. Then, we traversed the Linked List until we reached the last node.
3. Then, we printed the data of the current node and moved to the next node.

Deletion at the beginning

You got all your data in a Linked List. But the first node does not seems to be useful. You want to delete the first node. How will you do that? Let's have a look at the code.

void deleteAtBeginning() {
    if (head == NULL) {
        return;
    }

    Node* temp = head;
    head = head->next;
    delete temp;
}

Here goes the explanation.

1. First, we checked if the Linked List is empty or not. If the Linked List is empty, we returned from the function.
2. Then, we created a new node temp and assigned the head variable of the Linked List to it. After that, we assigned the next variable of the head to the head variable by head = head->next;.
3. Then, we deleted the temp node from the memory.

Deletion at the end

Now it seems like the last node is not useful too. You want to delete the last node. Let's remove it.

void deleteAtEnd() {
    if (head == NULL) {
        return;
    }

    if (head->next == NULL) {
        delete head;
        head = NULL;
        return;
    }

    Node* temp = head;
    while (temp->next->next != NULL) {
        temp = temp->next;
    }

    delete temp->next;
    temp->next = NULL;
}

Here goes the explanation.

1. First, we checked if the Linked List is empty or not. If the Linked List is empty, we returned from the function.
2. Then, we checked if the Linked List has only one node. If the Linked List has only one node, we deleted the head node from the memory and assigned NULL to the head variable of the Linked List.
3. If the Linked List has more than one node, we created a new node temp and assigned the head variable of the Linked List to it. Then, we traversed the Linked List until we reached the second last node.
4. Then, we deleted the last node from the memory and assigned NULL to the next variable of the second last node.

Deletion at a given position

If all seems fine. But, for your curiosity, you want to delete a node at a given position. How will you do that? Let's have a look at the code.

void deleteAtPosition(int position) {
    if (head == NULL) {
        return;
    }

    if (position == 0) {
        Node* temp = head;
        head = head->next;
        delete temp;
        return;
    }


    Node* temp = head;
    for (int i = 1; i < position; i++) {
        temp = temp->next;
    }

    Node* toDelete = temp->next;
    temp->next = temp->next->next;
    delete toDelete;
}

Here goes the explanation.

1. First, we checked if the Linked List is empty or not. If the Linked List is empty, we returned from the function.
2. Then, we checked if the position is 0. If the position is 0, we deleted the head node from the memory and assigned NULL to the head variable of the Linked List.
3. If the position is not 0, we created a new node temp and assigned the head variable of the Linked List to it. Then, we traversed the Linked List until we reached the node at the given position.
4. Then, we created a new node toDelete and assigned the next variable of the temp node to it. After that, we assigned the next variable of the toDelete node to the next variable of the temp node by temp->next = temp->next->next;.
5. Then, we deleted the toDelete node from the memory.

At last, we have completed the implementation of the Linked List. Now, let's have a look at the complete code.

To make the code length not too long, I have included the major functions only.

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;

    Node(int data) {
        this->data = data;
        this->next = NULL;
    }
};

class LinkedList {
public:
    Node* head;

    LinkedList() {
        head = NULL;
    }

    void insertAtPosition(int data, int position) {
        Node* newNode = new Node(data);

        if (head == NULL) {
            head = newNode;
            return;
        }

        if (position == 0) {
            newNode->next = head;
            head = newNode;
            return;
        }

        Node* temp = head;
        for (int i = 1; i < position; i++) {
            temp = temp->next;
        }

        newNode->next = temp->next;
        temp->next = newNode;
    }

    void traverse() {
        Node* temp = head;

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

        cout << endl;
    }

    bool search(int data) {
        Node* temp = head;

        while (temp != NULL) {
            if (temp->data == data) {
                return true;
            }

            temp = temp->next;
        }

        return false;
    }

    void deleteAtPosition(int position) {
        if (head == NULL) {
            return;
        }

        if (position == 0) {
            Node* temp = head;
            head = head->next;
            delete temp;
            return;
        }

        Node* temp = head;
        for (int i = 1; i < position; i++) {
            temp = temp->next;
        }

        Node* toDelete = temp->next;
        temp->next = temp->next->next;
        delete toDelete;
    }
};

int main() {
    LinkedList* ll = new LinkedList();

    ll->insertAtPosition(10, 0);
    ll->insertAtPosition(20, 1);
    ll->insertAtPosition(30, 2);
    ll->insertAtPosition(40, 3);

    ll->traverse();

    cout << ll->search(30) << endl;
    cout << ll->search(50) << endl;

    ll->deleteAtPosition(2);

    ll->traverse();
}

Now I hope you have understood the Linked List. If you have any doubts, please contact me. I will be happy to help you.

References

• "Linked list - Wikipedia" En, https://en.wikipedia.org/wiki/Linked_list.
• "Linked List Data Structure - GeeksforGeeks" Geeksforgeeks, 18 Jun. 2002, https://www.geeksforgeeks.org/data-structures/linked-list/.
• "Linked List Operations: Traverse, Insert and Delete" Programiz, https://www.programiz.com/dsa/linked-list-operations.