Linked Lists - Singly Linked List

We learned our first data structure "Arrays" in the last article. Now, its time to move on to "Linked Lists". Unlike arrays, linked list data structure allows us to store data without having any kind of index. Another difference is that an array is fixed in size by default. But linked list is always dynamic in size.

Linked list data structure consists of nodes. Each node contains two things, data and a reference to next node's address in memory.

The image above shows how a singly linked list is placed in the memory. But notice how each node is not in a sequential manner like an array. Each node is placed in the memory wherever it can fit in. This gives us a huge advantage over arrays. We can store as many nodes as we want in a linked list.

Another huge advantage of a linked list over an array is that's its faster to insert/delete items from a linked list as compared to an array. Because we don't need to shift the subsequent elements/nodes after inserting anywhere in the middle of linked list.

One drawback of linked list is that its slower than arrays in case of reading a value when its not pointed by head or tail. Because it has to walk up to the node in order to read its data.

Types Of Linked List

There are 3 main types of linked list:

• Singly Linked List

• Doubly Linked List

• Circular Linked List

We will talk about every single one of these, so let's start with Singly Linked List in this article:

Singly Linked List

A singly linked list is the simplest form of linked list. It consists of a number of nodes where each node has some data and a pointer to the next node.

One important thing to know about this form of linked list is that it allows to walk over it in only one direction, head to tail. I mean isn't it obvious? We only got one pointer on each node that references the next node but there is no pointer that references the previous one. So, we only know whats next resulting in one directional traversal.

Let's move on to how we can implement singly linked list in code.

Here are the steps

• Create a node which can store some data and a reference to next node

• Create a List class/struct which will serve the following purposes:

  • allow us to have a reference to head node

  • provide us with methods to push or pop to the linked list

Starting with the node we got:

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

Here we have a Node struct with two fields, val and next. It's a simple node to store any integer value and hold a reference to the another node of this type. Come to think of it, the next field is actually the base for this whole linked list.

Alright let's create our List struct:

struct List{
    ListNode* head;

    List() {
        head = nullptr;
    }
}

Notice we got a head field only pointing to the head of the linked list. While in the constructor we are making sure if it doesn't point to anything it should point to nullptr. If you came from other languages, the nullptr is basically acts as null but its a pointer.

For now we can create a linked list like this:

List* list = new List();

But we can't push or pop anything from it. Let's implement these functionalities!

Push Method

The push method will insert a new item as a new head of the linked list. Here is the implementation:

void push(int x) {
    ListNode* n = new ListNode(x);

    if(head == nullptr) {
        head = n;
    }else{
        n->next = head;
        head = n;
    }
}

Let's break it down so we get a better understanding of what is going on here. First we have the input value as x that should be inserted in the list. As everything in the list should be a ListNode pointer. We will make one using ListNode* n = new ListNode(x);.

Now all we have to do is make it head. We are checking if there is no head that means the list contains zero elements and we can set this new node as the head directly.

if(head == nullptr) {
    head = n;
}

Otherwise, we will make the current head as the 2nd element in the list. Ofcourse the first one (head) will be our new node now.

else{
    n->next = head;
    head = n;
}

Pop Method

Our push method is completed now lets move on to the pop method:

int pop() {
    int val = head->val;
    ListNode* next = head->next;

    delete head;

    head = next;

    return val;
}

This method is pretty straight forward. All we gotta do is make a backup of current node value and the 2nd element (because we will make it the new head, we need a reference to it for that).

int val = head->val;
ListNode* next = head->next;

Then we simply deleted the head node. The delete operator will remove the head node and deallocate any memory used by it. Next we will simply set 2nd element the head and return the value of the ex head.

Final Code

Here is the final code with some helper methods and tests:

#include <iostream>

// ignore/remove the 2 lines below if you don't want any tests
#define DOCTEST_CONFIG_IMPLEMENT_WITH_MAIN
#include "doctest.h"

using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

struct List{
    ListNode* head;

    List() {
        head = nullptr;
    }

    void push(int x) {
        ListNode* n = new ListNode(x);

        if(head == nullptr) {
            head = n;
        }else{
            n->next = head;
            head = n;
        }
    }

    int pop() {
        int val = head->val;
        ListNode* next = head->next;

        delete head;

        head = next;

        return val;
    }

    void print() {
        ListNode* curr = head;
        while(curr != nullptr){
            cout << curr->val << endl;
            curr = curr->next;
        }
    }
};

// TESTS (if you want)
TEST_CASE("push") {
    List* list = new List();

    list->push(5);
    list->push(10);

    CHECK(list->head->val == 10);
}

TEST_CASE("pop") {
    List* list = new List();

    list->push(5);
    list->push(10);

    CHECK(list->pop() == 10);
    CHECK(list->head->val == 5);
}

Time Complexity

Both push and pop methods in our linked list have a time complexity of O(1) because they directly manipulate the head and no loop is involved. No matter how big the linked list gets, these methods will take O(1) time.

Peek and Mutable Peek methods also have O(1) complexity, because we have a pointer to the head allowing us to peek directly.

Now that Singly Linked List is finished, let's move on to Doubly Linked List!