Linked List like Arrays is a linear data structure, but unlike arrays, elements do not have to be at contiguous locations in Linked List, which makes it a lot different from the static or dynamic arrays.
Every node stores the reference (In Java or Python) or pointer (In C++) to the next node, that’s how, they form a linear sequence.
The idea is to drop the contiguous memory requirements so that insertions and deletions can efficiently at the middle also.
The other advantage of Linked List over arrays is that, we do not need to pre-allocate the space for the nodes.
[A |(Address to B)|]->[B | (Address to C)]->[C | (Address to D)]->[D | (Address to E)]->[E | (NULL)]
In the representation above, it may not be necessary that all nodes are allocated in a contiguous location. They might be allocated in any permutation or location.
The major advantage of Linked List is that, we can insert in the middle, delete from the middle, insert in the beginning, delete from the beginning, very efficiently.
Implementation of Linked List in C++:
#include <iostream>
using namespace std;
struct Node
{
int data;
//Self Referential Structure
Node *next;
Node(int x){
data = x;
x = NULL;
}
};
int main()
{
//Initially, we are creating the objects
//with NULL as the address to next Node
Node *head = new Node(10);
Node *temp1 = new Node(20);
Node *temp2 = new Node(30);
//Assigning the address of next node.
head->next = temp1;
temp1->next = temp2;
return 0;
}A Cleaner and Short Implementation can be:
#include <iostream>
using namespace std;
struct Node
{
int data;
//Self Referential Structure
Node *next;
Node(int x){
data = x;
x = NULL;
}
};
int main()
{
//Creating the head object and assigning the pointer to the next
//node during the initialization of the next node.
Node *head = new Node(10);
head->next = new Node(20);
head->next->next = new Node(30);
return 0;
}This is not the general representation of a Linked List as we can further implement functions such as insert at the beginning, insert at the middle, delete from the middle, delete from the beginning, etc.
