Array is a linear data structure.Which has fixed size(contgious memory allocation) and delition and inerstion in Array is difficult. Here the Linked List comes under role. It take the non-contigous memory allocation in (It is implemented on the heap memory rather than the stack memory.)
Many applications, such as text editors, rely on linked lists to implement undo/redo functionality. By using a doubly linked list, each operation can be recorded, allowing easy traversal to go back and forth in the history of operations.
Dynamic sizing: Efficient for applications where the number of elements changes frequently.
Efficient insertions and deletions: Particularly when modifications occur in the middle or at the beginning.
No need for contiguous memory: Unlike arrays, linked lists can be stored in non-contiguous memory locations.
Linked Lists Types
Singly
Doubly
Circular
Circular dubly
In this article we are gogin to deep down in the singley linked list also we will do the impletation of singly linked list.
Singly Linked List
A singly linked list is a linked list where each node only points to one node and the tail node points to null.There is not backword pointer(A pointer is just a variable that holds a memory address.)
Braking down
Node - [Data,Pointer]
- Data holds the actual value
Pointer point to another Node.
In the image above, you can easily understand what a pointer and a node are.
So that's the theory part—now let's jump into the coding part. I will walk you through each point and the intuition behind the code. Let's begin.
Take a look at the image. What do you think, and how would you go about coding this? What are the requirements to implement this concept in code?
The first thing we need is data and a pointer at every node, right? Every node will have the same structure: data and a pointer. So, we can easily create a class for the image with these two components.
#include <bits/stdc++.h>
using namespace std;
class Node
{
public:
Node *next;
int data;
// Constructor to initialize a node
Node(int d)
{
data = d;
next = NULL;
}
};
In this article, I will create three main functions for a singly linked list:
Create
Delete
Print
From your side, you can implement additional functions such as Update and Delete the Last Node (which is called the tail).
Let’s start by thinking about the create function. The idea behind the create function is to add a new node next to the previous one. But before that, when adding the first node, we need to add it at the head. Every subsequent node will be added after this first node.
class LinkedList{
public:
Node* head;
LinkedList(){
head = NULL;
}
void createNode(int d){
// create node
Node *newNode = new Node(d);
if (head == NULL)
{
head = newNode;
}
else
{
// rest of the node
Node *temp = head;
while (temp->next != NULL)
{
temp = temp->next;
}
temp->next = newNode;
}
};
Lets moves toward the delete function.
Suppose we need to delete the 3rd node. How can we delete it? We can't directly delete the node we want because if we do, the pointer associated with that node will also be deleted. This would cause us to lose track of the remaining nodes.
Instead, we can traverse the list using the "next" pointers to access each node. To delete the 3rd node, we can remove it by adjusting the pointer of the 2nd node, which is connected to the 3rd node. This way, we maintain the link between the remaining nodes.
void deleteNode(int d){
if(head->data == d){
Node* temp = head;
head = temp->next;
delete temp;
return;
}
// finding the data int the list
else{
Node* temp = head;
while(temp->next != NULL){
if(temp->next->data == d ){
Node* NodeToDelete;
NodeToDelete = temp->next;
temp->next = temp->next->next;
delete NodeToDelete;
}
temp = temp->next;
}
cout<<"Node not found"<<endl;
}
}
Last but not least Print function..
we just need to traverse entire linked list
void printList(){
Node* temp = head;
while (temp != NULL)
{
cout<<temp->data<<"->";
temp = temp->next;
}
cout<<"NULL";
}
Entire Code will look like..
#include <bits/stdc++.h>
using namespace std;
class Node
{
public:
Node *next;
int data;
Node(int d)
{
data = d;
next = NULL;
}
};
class LinkList
{
public:
Node *head;
LinkList()
{
head = NULL;
}
void addNode(int d)
{
// create Node
Node *newNode = new Node(d);
if (head == NULL)
{
head = newNode;
}
else
{
Node *temp = head;
while (temp->next != NULL)
{
temp = temp->next;
}
temp->next = newNode;
}
}
void deleteNode(int d){
if(head->data == d){
Node* temp = head;
head = temp->next;
delete temp;
return;
}
// finding the data int the list
else{
Node* temp = head;
while(temp->next != NULL){
if(temp->next->data == d ){
Node* NodeToDelete;
NodeToDelete = temp->next;
temp->next = temp->next->next;
delete NodeToDelete;
}
temp = temp->next;
}
cout<<"Node not found"<<endl;
}
}
void printList(){
Node* temp = head;
while (temp != NULL)
{
cout<<temp->data<<"->";
temp = temp->next;
}
cout<<"NULL";
}
};
int main()
{
LinkList list; // constructor..
list.addNode(10);
list.addNode(20);
list.addNode(30);
list.addNode(40);
list.addNode(50);
cout<<"Before Delition of Node"<<endl;
list.printList();
cout<<endl;
list.deleteNode(30);
cout<<"After Delition of Node"<<endl;
list.printList();
return 0;
}
Thank you for reading my content. Be sure to follow and comment on what you want me to write about next