What is a Linked List

A Linked List is a data structure in which each Node points to the next to create a dynamic list. Linked Lists are also called dynamic lists. It works similar to an array but has some advantages compared to a static list.

struct Node {
  Node* next;
  int value;
};

Node

Why do we use Linked Lists

The main problems with arrays are insertion and deletion of an element. Each time you delete an element you are forced to shift all the elements above it one cell down. This operation costs Θ(n). Nevertheless, when we use a linked list instead these operations have a cost of Θ(1), we just need to change the pointer of the element before the deleted node to point to the element after the deleted node.

 

When we need to insert an element we are facing the same problem. An array has a predefined static size: it means we need to create another greater array in order to insert a new element into it (that is how C++ vector works). This is not an issue if we use a linked list because its size is dynamic.

When you need to delete or insert elements dynamically into a list a linked list is more efficient compared to an array

The problem with linked list is that each time we need to select a specific node we need to cycle to the entire list to find it because we only store a reference to the head node. This operation is Θ(n). Therefore, linked list is not efficient with searching operations.

Linked List C++ Implementation

I have developed a C++ class that implements linked list. All the source code is free and open source, you can download it on my Github page LassSandro/LinkedList. I am going to explain how some functions of the class work.

Linked List C++

insertNode(int)

// Push node at the end of the list
void LinkedList::insertNode(int value) {
    Node* temp = createEmptyNode(value);

    // If list is empty
    // Set tail and head to the new temp node
    if (isEmpty()) {
        setHead(temp);
        setTail(temp);

        increaseLength();
        return;
    }

    // Append new node at the end and set tail
    getTail()->next = temp;
    setTail(temp);

    increaseLength();
}

With insertNode(int) we can insert a new node at the end of the list. We simply create a new node with the given value and attach it at the end of the list by making the previous last node point to the new node created. If the list is empty the new node is the only one in the list (it is both the head and the tail).

searchValue(int)

// Return node index if find value
// Return -1 if not find
int LinkedList::searchValue(int value) {
    Node* curr = getHead();
    int currIndex = 0;

    while(curr != nullptr) {
        if (curr->value == value) {
            return currIndex;
        }

        curr = curr->next;
        ++currIndex;
    }

    return -1;
}

As we said the main problem with linked list is searching. In order to find a value, we need to start from the head and cycle through the whole list until we find the requested value. If the value is in the list we return the index of the node we found, otherwise we return -1.

insertNode(unsigned, int)

// Insert node in a specific position
void LinkedList::insertNode(unsigned index, int value) {
    // Check position index
    if (index > length) {
        positionError(index);
        return;
    }

    // Insert head (index == 0)
    if (index == 0) {
        insertHead(value);
        return;
    }


    Node* temp = createEmptyNode(value);

    Node* curr = getHead();
    // Set current index to position '1'
    unsigned currIndex = 1;

    // Reach node at requested position
    while (currIndex != index) {
        curr = curr->next;
        ++currIndex;
    }

    // If last position requested
    if (currIndex == length) {
        insertNode(value);
        return;
    }

    // Change pointers to insert node in
    temp->next = curr->next;
    curr->next = temp;

    increaseLength();
}

If we want to insert a new node in a specific position the process is nearly the same. This time we need to find the node in the specified position. To do that we cycle from the head each node until we reach the index inserted. Then we check if the node selected is the tail, in this case we call the insertNode(int) function. If not, we just need to make the current node point to the new node and the new node point to the next of the current one.

deleteNode(unsigned)

// Delete node in specific position
void LinkedList::deleteNode(unsigned index) {
    // Check position index
    if (index >= length) {
        positionError(index);
        return;
    }

    // Delete head (index == 0)
    if (index == 0) {
        deleteHead();
        return;
    }

    // Set curr node (head)
    Node* curr = getHead();
    unsigned currIndex = 1;

    // Stop when reach position OR the last element
    while (currIndex != index || currIndex != (length - 1)) {
        curr = curr->next;
        ++currIndex;
    }

    // Change tail if reached last element
    if (currIndex == (length - 1)) {
        setTail(curr);
        curr->next = nullptr;

        decreaseLength();
        return;
    }

    // Change next to remove element from list
    curr->next = curr->next->next;

    decreaseLength();
}

The process to find the requested node to delete is the same as the insertNode(unsigned, int) function above but this time we are looking for the node before the index's one. Once we find that node we just need to make it point to the node next to the node that we want to delete.

Deletion

 

These are the main functions of our C++ Linked List class implementation. We will update the repository with some more functionalities in the near future. Feel free to contribute yourself to the project. Stay tuned for future updates, sign up to our newsletter to not miss any new article.