Starting with the basics...
What is Linked List ?
A linked list is a sequence of elements which are connected via a link.
Or Simply, It is a chain of nodes.
It works on the principle of blockchain but instead of storing the address/hash of previous block , it stores the address of the next block. And the last block didn't contain any address , so we point it to a NULL/'0' address.
In linked list , these blocks are known as nodes , so don't confuse when I say blocks in place of nodes.
A node is basically a block of element which stores some data and the address of the next block. It is made up of 2 datatypes , one store the data and another is a pointer(it stores an memory address) which stores the address of the next node.
I also want to clear a myth that nodes do not take continuous memory location . May be it points to a different location.
Now, I am going to explain you through the codes using OOPS class datatype :
I had explained each line in comments, so, you can prefer to read from there.
#include <iostream>
using namespace std;
class node
{
public:
int data;
node *next = NULL
/*Create a 'node' of class type which contain 2 datatypes, one stores data and another is a pointer variable 'next' that stores the address of the next node.
It is a good practice to initialise a pointer with NULL value.*/
node(int val)
{
/*A parameterised constructor*/
/*It is initialised and will be executed whenever we create new objects of that class node datatype.*/
data = val;
next = NULL; // the point of using NULL is a “sentinel value” to mark as end of list. So initially, when the list is empty, head is set to NULL to follow this convention.
}
// functions
void insertAtTail(node *&head, int val);
void insertAtHead(node *&head, int val);
void deletionAtHead(node *&head);
void deletion(node *&head, int val);
void print(node *head);
};
( -> ) this is same as ( . ) for accessing any public functions of the class system datatype but used only with pointer variables.
e.g. normal.func( )
pointer->func( )
void node::insertAtTail(node *&head /*call by refrence*/, int val) // add a new node at the end
{
node *n = new node(val); // create a variable 'n' of the dataype 'node'
if (head == NULL) // check ,if the linked list is not empty
{
head = n; // add 'n' to the linked list
return;
}
node *temp = head; // here we create a pointer which traverse through the linked list 'head'
while (temp->next != NULL) // loop is executed till the next node of 'temp' , points to a NULL address
{
temp = temp->next; // traversing in linked list // move to the next node
}
temp->next = n; // add a new node at the end of the linked list by pointing the last node to 'n'
}
First node is known as Head and the last node known as Tail of the linked list.
void node::insertAtHead(node *&head, int val) // insert a new node at the head
{
node *n = new node(val);
n->next = head; // pointing to the 'head' address
head = n; // change the linked list 'head'
return;
}
Whenever we perform insertion and deletion from the original linked list , it is necessary to use call by reference instead of using call by value.
void node::deletionAtHead(node *&head) // deletion of node from the head position
{
node *todelete = head; // a temporary pointer that store the address of the first node
head = head->next; // move the linked list head to the next node
delete todelete; // delete the pointer that points to the first node
return;
}
delete( ) function is used to save from data loss because avoiding this step will cause the pointer points to a specific location to the system which were further used by hackers to access the system data.
void node::deletion(node *&head, int val)
{
if (head == NULL) // check whether linked list is empty or not
{
return;
}
if (head->next == NULL) // check whether linked list contain only 1 node
{
deletionAtHead(head);
return;
}
node *temp = head; // creating a temporary pointer is important because traversing in linked list through 'head' pointer will change the head of the linked list.
while (temp->next->data != val) // loop is executed till the next node 'data' becomes equals to 'val'
{
temp = temp->next;
}
node *todelete = temp->next; // a pointer is used to store the address of the next node of 'temp'
temp->next = temp->next->next; // breaking the link with the next node and connect with the node present next to the next node
delete todelete;
}
Note : Compiler understand this 'temp->next' as '(*temp).next'.
void node::print(node *head /*call by value*/ ) // print the linked list 'data'
{
while (head != NULL) // loop executes till the head points to a NULL address i.e. after the end node
{
cout << head->data << "->"; // accessing the 'data' variable of the 'node' datatype
head = head->next; // move 1-node ahead
}
cout << "NULL" << endl;
}
Note : Call by value would not change the linked list head, it's just, let the head traverse through the linked list.
int main()
{
node *head = NULL; // create a variable with datatype node ( we add a '*' because it stores an address with the int datatype 'data' )
// calling functions
head->insertAtTail(head, 1);
head->insertAtTail(head, 2);
head->insertAtTail(head, 3);
head->print(head);
head->insertAtHead(head, 4);
head->print(head);
head->deletionAtHead(head);
head->print(head);
head->deletion(head, 2);
head->print(head);
return 0;
}
Now, I would explain it through another datatype i.e. structures but inspite of diving deep into this , I would rather explain it through small code snippets.
Struct node
{
int data;
struct node *next = NULL;
};
Created a struct datatype node which contain 2 datatypes :
(1) int datatype 'data' to store data of the node
(2) struct node pointer 'next' that stores the address
struct node *p = NULL;
p = (struct node *)malloc(sizeof(struct node)); <br>
// (struct node*) used for typecasting
// malloc( ) is used for dynamically allocating memory of size struct node in heap memory
(*p).data = x;
// p->data
(*p).next = NULL;
// p->next
Note : If we are creating a memory without declaring any pointer variable then how can we use this memory in our program because we never know the address of that memory until we do not store it in any pointer variable.
We can create memory but it is wastage of resources because operating system know that we are using this but we are not. We do not know the address of that memory.
I had focused more on concepts rather than on questions because if you understand the concept, you can break any question with your knowledge.
The main motive behind this blog is to build the concept rather than focusing on the syntaxes and questions.
If you find any relevant information left to be included, you can comment down, I would add it.
And if you really like it, don't forget to put your thoughts in the comment section too.