LinkedList in C++

Problem Statement: Linked List in C++

What is Linked List?

A linked list is also a linear data structure like an array but the difference between an array and a linked list is “In an array, the elements are stored at contiguous memory locations but in a linked list the elements are not stored at the contiguous memory locations, they are stored dynamically”.

In the linked list the elements are linked with each other using pointers. It consists of items called “Nodes” which contain two parts. The first part stores the actual data and the second part has a pointer that points to the next node. 

The structure of a linked list is shown in the below image.

What is the head of a Linked list?

When you are allocating memory of elements dynamically it is obvious that you don’t have direct access to any element like arrays but you have to start somewhere right??

That’s why we gave the address of the first node a special name called Head we also have to stop somewhere that’s why we specified the pointer of the last node is NULL.

Types of Linked List:

  1. Singly Linked List
  2. Doubly Linked List
  3. Circular Linked List

In this article, we will focus only on the Singly Linked List.

  • Representation of inked List

Let’s see how a Linked List and each node are represented.

As we discussed earlier each node in a linked list consists of two parts:

  1. Data item and
  2. A pointer to the address of the next node

We initialize both the data item and the pointer in a struct as : 

struct Node
{
    int data;
 
    Node *next; // self referential structure
 
    Node(int x) // constructor
    {
        data = x;
        next = NULL;
    }
};

Understanding the structure of a linked list node is the key to having a grasp on it.

Each struct node has a data item and a pointer to the next struct node.

Let us create a Linked list with three items to understand how this actually works…

Node *head = new Node(10); // initializing
    Node *temp1 = new Node(20);
    Node *temp2 = new Node(30);
 
    head->next = temp1; // linking
    temp1->next = temp2;
 
    return 0;

  • The power of a linked list comes from the ability to break the chain and rejoin it.

E.g. if you want to add 15 between 10 and 20, the steps would be:

  1. Create a new node and allocate memory to it.
  2. Add its data as 4.
  3. Point its next pointer to the node containing 20 as data.
  4. And finally, change the next pointer of “10” to the node you just created.

Doing something similar in the array would have required shifting the positions of all the subsequent elements.

  • Linked List Utility

Lists are one of the most popular and efficient data structures, with implementation in every programming language.

Apart from that, linked lists are a great way to learn how pointers work. By practicing how to manipulate linked lists, you can prepare yourself to learn more advanced data structures like graphs and trees.

The full code of Linked List implementation in C++

Code:

C++ Code

// 10 -> 20 -> 30 -> NULL < linked list to be created >
 
#include <iostream>
using namespace std;
 
struct Node
{
    int data;
 
    Node *next; // self referential structure
 
    Node(int x) // constructor
    {
        data = x;
        next = NULL;
    }
};
 
int main()
{
    // recommended
 
    Node *head = new Node(10); // initializing
    Node *temp1 = new Node(20);
    Node *temp2 = new Node(30);
 
    head->next = temp1; // linking
    temp1->next = temp2;
 
    return 0;
 
    /*
    < not recommended >
 
    shorter version of the main function
 
    Node *head = new Node(10);
    head->next = new Node(20);
    head->next->next = new Node(30);
 
    initializing and linking together
    */
}

We can perform various operations in linked lists like insert, delete, searching, sorting, etc.

The complexities of the above-mentioned operations on a singly linked list  are: 

  • Time Complexity
OperationWorst caseBest Case
SearchO(n)O(n)
InsertO(n)O(1)
DeletionO(n)O(1)
  • Space Complexity O(n)

Linked List Applications

  • Dynamic memory allocation
  • Implemented in stack and queue
  • In undo functionality of softwares
  • Hash tables, graphs

Special thanks to Subrata Rajak for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article