Singly linked list
Published by
sanya sanya
Definition:
A singly linked list is a linear data structure that consists of a sequence of nodes, each containing a value and a pointer pointing to the next node in the sequence.
Creation:
Approach:
- Create a class node with int data which will contain value and a pointer node*next which will contain the address of next node.
- Make a constructor which points the next pointer in node to null.
- In the main function, create variables of node* type, assign data to them and link nodes.
Code:
#include <bits/stdc++.h>
using namespace std;
// Structure of Node
class node {
public:
int data;
node* next;
//Constructor
node(int d){
next=NULL;
data=d;
}
};
int main()
{
node* head;
node* second;
// Allocate 2 nodes in the heap
head = new node(4);
second = new node(2);
// Link first node with second
head->next = second;
printList(head);
return 0;
}
Traversal:
Approach:
- Start from n=head node and print its data.
- Make n=n->next
- Iterate through the list till n!=NULL
Code:
#include <bits/stdc++.h>
using namespace std;
// Structure of Node
class node {
public:
int data;
node* next;
//Constructor
node(){
next=NULL;
}
};
void printList(node* n)
{
while (n != NULL) {
cout << n->data << " ";
n = n->next;
}
}
int main()
{
node* head;
node* second;
node* third;
// Allocate 3 nodes in the heap
head = new node();
second = new node();
third = new node();
// Assign data in first node
head->data = 1;
// Link first node with second
head->next = second;
// Assign data to second node
second->data = 2;
second->next = third;
// Assign data to third node
third->data = 3;
third->next = NULL;
printList(head);
return 0;
}
Insertion: Insertion in a singly linked list can be done in 3 ways:
- At head (In the beginning)
- At any position
- At tail (In the end)
Insertion at head
Approach:
- Create a new node ‘n’ and assign the value to node
- If the linked list is empty, make n as the head and tail of list
- Else, n->next= head (Make next of new node as head) and move the head to point at n.
Code:
void insertatHead(node*&head, node*&tail, data){
//Create a new node
node*n= new node (data);
//Check if the linked list is empty
if(head==NULL){
head=n;
tail=n;
}
else{
//Add new node before head
n->next=head;
//Point head to new node
head=n;
}
}
Insertion at tail
Approach:
- Create a new node ‘n’ and assign the value to node
- If the linked list is empty, make n as the head and tail of list
- Else, tail->next= n (Make next of tail as new node) and move the tail to point at n.
Code:
void insertatTail(node*&head, node*&tail, data){
//Create a new node
node*n= new node (data);
//Check if the linked list is empty
if(head==NULL){
head=n;
tail=n;
}
else{
//Add new node after tail
tail->next=n;
//Point tail to new node
tail=n;
}
}
Insertion at any position
Approach:
- Create a new node ‘n’ and assign the value to node
- Traverse the linked list till position-1 and point node*temp to it
- Point the next pointer of n node to next pointer of temp node
(n->next=temp->next)
- Point next pointer of temp to n
(temp->next=n)
Code:
void insertatPosition(node*&head, node*&tail, int pos){
//Create a new node
node*n= new node (data);
//Create a temp pointer
node*temp=head;
//Traverse the list till position-1
for(int i=1; i<pos-1; i++){
temp=temp->next;
}
n->next=temp->next;
temp->next=n;
}
Deletion: Deletion in a singly linked list can be done in 3 ways:
- At head (In the beginning)
- At any position
- At tail (In the end)
Deletion at head
Approach:
- If the linked list is empty, return
- Else if the linked list has a single node, delete head and point head and tail to NULL
- Else, create node*temp and point it to next node of head
- Delete head
- Make temp as head
Code:
void deleteatHead(node*&head, node*&tail){
//Check if the linked list is empty
if(head==NULL){
return;
}
//Check single node condition
else if(head->next==NULL){
delete head;
head=NULL;
tail=NULL;
}
//Multiple node condition
else{
node*temp=head->next;
delete head;
head=temp;
}
}
Deletion at tail
Approach:
- If the linked list is empty, return
- Else if the linked list has a single node, delete head and point head and tail to NULL
- Else, create node*temp and point it to head
- Traverse using temp till second last node of list
- Point next of temp to NULL
- Delete tail
- Make temp as tail
Code:
void deleteatTail(node*&head, node*&tail){
//Check if the linked list is empty
if(head==NULL){
return;
}
//Check single node condition
else if(head->next==NULL){
delete head;
head=NULL;
tail=NULL;
}
//Multiple node condition
else{
node*temp=head;
while(temp->next!=tail){
temp=temp->next;
}
Temp->next=NULL;
delete tail;
tail=temp;
}
}
Deletion at any position
Approach:
- If the linked list is empty, return
- Create a pointer temp which points to head
- Traverse through the list with temp until pos-1 or until NULL
- Create another pointer, n, which points to temp->next->next
- Delete temp->next
- Link temp to n
Code:
void deleteatPosition(node*&head, node*&tail, int pos){
//Check if the linked list is empty
if(head==NULL){
return;
}
else{
node*temp=head;
for(int i=1; i<=pos-1;i++){
temp=temp->next;
}
node*n=temp->next->next;
delete temp->next;
temp->next=n;
}
}
Length: Length of a linked list represents the total number of nodes in it.
Length can be found iteratively or recursively. Both the approaches are discussed below.
Iteratively:
Approach:
- Initialize count to 0
- Create a node* temp which points to head
- Iterate till temp!=NULL and increment count by 1
- Return count
Code:
int length (node*head){
int count=0;
node*temp=head;
while(temp!=NULL){
count++;
temp=temp->next;
}
return count;
}
Recursively:
Approach:
- Base case will be if head is NULL, return 0
- Recursive case will be 1+ length(head->next);
Code:
int length (node*head){
//Base case
if(head==NULL){
return 0;
}
//Recursive case
else{
return 1+ length(head->next);
}
}
Searching: An element can be searched in a linked list either iteratively or recursively. Both the approaches are discussed below.
Iteratively:
Algorithm:
- Create a pointer that points to head
- Iterate through the list, if key is found return true
- Return false
Code:
bool searchIteratively (node* head, int key){
node*temp=head;
while(temp!=NULL){
if(temp->data==key){
return true;
}
temp=temp->next;
}
return false;
}
Recursively:
Algorithm:
- Return false if head is NULL
- Return true if head->data==key
- Return searchrecursively(head->next,key)
Code:
bool searchRecursively (node* head, int key){
//Base Case
if(head==NULL){
return false;
}
//Recursive case
if(head->data==key){
return true;
}
return searchRecursively(head->next,key);
}
Reversing: A singly linked list can be reversed either iteratively and recursively. Both the approaches are discussed below.
Iteratively:
Algorithm:
- Initialize three pointers prev as NULL, curr as head, next as NULL
- Iterate through the list and do the following in a loop
- Before changing the next of curr, store the next node (next=curr->next)
- Link next of curr to prev (curr->next=prev)
- Update prev as curr and curr as next
Code:
node* reverse(node*&head){
node*prev=NULL;
node*curr=head;
node*next=NULL;
while(curr!=NULL){
next=curr->next;
curr->next=prev;
prev=curr;
curr=next;
}
return prev; //This will be the new head of linked list
}
Recursively:
Algorithm:
- return head if linked list is empty or in single node condition
- recursively reverse the linked list from head->next and store its new head in k pointer
- point head->next to NULL
- Traverse through the list and make the last node as head
Code:
node* reverse(node*head){
if(head==NULL||head->next==NULL){
return head;
}
node* temp=head->next;
head->next=NULL;
node*n=reverse(temp);
node*k=n;
while(k->next!=NULL){
k=k->next;
}
k->next=head;
return n;
}
Find mid:
Algorithm:
- Traverse the linked list using 2 pointers
- Move slow pointer by 1 and fast pointer by 2
- When fast pointer reaches NULL, slow pointer will be at middle
Code:
int middle(node* head){
node* slow=head;
node* fast=head;
if(head!=NULL){
while(fast!=NULL && fast->next!=NULL){
fast= fast->next->next;
slow=slow->next;
}
return slow->data;
}
Library
WEB DEVELOPMENT
FAANG QUESTIONS