Problem Statement: Linked List in C++

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.

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.

• 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);

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.

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);

temp1->next = temp2;

return 0;

/*
< not recommended >

shorter version of the main function

*/
}
``````

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
• Space Complexity O(n)