Linked List - Store your data in a chain of nodes

Linked List - Store your data in a chain of nodes

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.

What is a Linked List?

Linked List
Linked List

Ever imagined having a list that can grow and shrink as per your need? Well, we have the answer for you.

Let's say you have a list of 10 elements, and you put those elements in an array. That's fine for now, but what if you want to add more elements to the list (array)? You will have to create a new array with a new size and copy all the elements from the old array to the new one because the size of the array is fixed and their address in memory is in a continuous block. This is a very costly operation. So, what if you could just add the new elements to the list without having to create a new array? This is the case where Linked List comes into play.

Let me introduce Linked List to you. Linked List does not store the data in a continuous block of memory. Instead, it stores the data in nodes connected to each other like a chain. As the nodes are not in a continuous block of memory, the size of the Linked List can grow and shrink as per the need. Each node contains the data and a pointer (memory address) to the next node.

Structure of a Linked List

A Linked List is a collection of nodes. The entry point or the starting node of a Linked List is called the head. The last node of a Linked List points to NULL. The following image shows the structure of a Linked List.

Types of Linked List

To make things more interesting, there are different types of Linked List. Let's have a look at them.

Singly Linked List

Singly Linked List
Singly Linked List

Singly Linked List is like a 1-way street, where you can move in only one direction. Here in a Singly Linked List, each node contains the data and a pointer to the next node only. The last node points to NULL. That means the end is the true end. The following image shows the structure of a Singly Linked List.

Doubly Linked List

Doubly Linked List
Doubly Linked List

Let's say you want some flexibility in your Linked List. You want to move in both the directions. Well, Doubly Linked List is the answer to your question. In a Doubly Linked List, each node contains the data and two pointers - one to the next node and one to the previous node. The prev pointer of the head points to NULL and the next pointer of the last node points to NULL. The following image shows the structure of a Doubly Linked List.

Besides these two types of Linked List, there is another type of Linked List called Circular Linked List.

Circular Linked List

Circular Linked List
Circular Linked List

In a Circular Linked List, you can move in any direction and also you can move from the last node to the first node, and vice versa if it's a Doubly Circular Linked List. In a Circular Linked List, the last node points to the first node.

Doubly Circular Linked List is the same as Circular Linked List, but the last node points to the first node and the first node points to the last node. The following image shows the structure of a Circular Linked List.

Implementation of Linked List

Let's have a look at the implementation of Linked List in C++. We will be using the Singly Linked List for this. The node of the Linked List is defined as follows.

struct Node {
    int data;
    Node* next;

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

The data variable stores the data of the node and the next variable stores the pointer to the next node in the Linked List. The constructor of the Node structure initializes the data variable with the data passed to it and next variable with NULL.

The Linked List class is defined as follows.

class LinkedList {
public:
    Node* head;

    LinkedList() {
        head = NULL;
    }
};

Here, the head variable stores the pointer to the first node of the Linked List. The constructor of the LinkedList class initializes the head variable with NULL.

But, you want a working Linked List, right? So, let's create a basic Linked List with some nodes. The following code creates a Linked List with 3 nodes.

#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;
    }
};

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

    list->head = new Node(1);
    list->head->next = new Node(2);
    list->head->next->next = new Node(3);

    // print the Linked List
    Node* temp = list->head;
    while (temp != NULL) {
        cout << temp->data << " ";
        temp = temp->next;
    }

    return 0;
}

Wait, what's happening here? Let's break it down in steps.

  1. In the main function, we created a new Linked List list and initialized the head variable with NULL.
  2. Then, we created a new node with data 1 by calling the constructor of the Node structure and assigned it to the head variable of the Linked List.
  3. Then, we created a new node with data 2 by calling the constructor of the Node structure and assigned it to the next variable of the first node, list->head->next.
  4. Then, we created a new node with data 3 by calling the constructor of the Node structure and assigned it to the next variable of the second node, list->head->next->next.

Now, the Linked List looks like this.

Example Linked List
Example Linked List

Operations on Linked List

Now that you have a basic idea of Linked List, let's have a look at some operations that can be performed on a Linked List.

The operations on Linked List are described in the artcle Linked List - Operations.

References

Related Posts