Linked list Flashcards
implementing a single linked list
#include (bits/stdc++.h> using namespace std;
struct Node{
int data;
Node* next;
Node(int x){
data=x;
next=NULL;
}
};
int main()
{
Node *head=new Node(10);
Node *temp1=new Node(20);
Node *temp2=new Node(30);
head->next=temp1;
temp1->next=temp2;
cout((head->data(("-->"((temp1->data(("-->"((temp2->data;
return 0;
}
traversal of a linked list from head to last node.
#include (bits/stdc++.h> using namespace std;
struct Node{
int data;
Node* next;
Node(int x){
data=x;
next=NULL;
}
};
void printlist(Node *head){
Node *curr=head;
while(curr!=NULL){
cout((curr->data((" ";
curr=curr->next;
}
}
int main()
{
Node *head=new Node(10);
head->next=new Node(20);
head->next->next=new Node(30);
head->next->next->next=new Node(40);
printlist(head);
return 0;
}
Recursive traversal of linked list
void traverse(Node* head)
{
if (head == NULL)
return;
// If head is not NULL, print current node // and recur for remaining list cout << head->data << " ";
traverse(head->next); }
Search in a linked list in both iterative and recursive approaches
#include (bits/stdc++.h> using namespace std;
struct Node{
int data;
Node* next;
Node(int x){
data=x;
next=NULL;
}
};
void printlist(Node *head){
Node *curr=head;
while(curr!=NULL){
cout((curr->data((" ";
curr=curr->next;
}cout((endl;
}
int search(Node * head, int x){
int pos=1;
Node *curr=head;
while(curr!=NULL){
if(curr->data==x)
return pos;
else{
pos++;
curr=curr->next;
}
}
return -1;
}
int main()
{
Node *head=new Node(10);
head->next=new Node(20);
head->next->next=new Node(30);
printlist(head);
cout(("Position of element in Linked List: "((search(head,20);
return 0;
}
Recursive approach
#include (bits/stdc++.h>
using namespace std;
struct Node{
int data;
Node* next;
Node(int x){
data=x;
next=NULL;
}
};
void printlist(Node *head){
Node *curr=head;
while(curr!=NULL){
cout((curr->data((" ";
curr=curr->next;
}cout((endl;
}
int search(Node * head, int x){
if(head==NULL)return -1;
if(head->data==x)return 1;
else{
int res=search(head->next,x);
if(res==-1)return -1;
else return res+1;
}
}
int main()
{
Node *head=new Node(10);
head->next=new Node(20);
head->next->next=new Node(30);
printlist(head);
cout(("Position of element in Linked List: "((search(head,20);
return 0;
}
insert at the beginning of Singly Linked List
#include (bits/stdc++.h> using namespace std;
struct Node{
int data;
Node* next;
Node(int x){
data=x;
next=NULL;
}
};
Node *insertBegin(Node *head,int x){
Node *temp=new Node(x);
temp->next=head;
return temp;
}
void printlist(Node *head){
Node *curr=head;
while(curr!=NULL){
cout((curr->data((" ";
curr=curr->next;
}
}
int main()
{
Node *head=NULL;
head=insertBegin(head,30);
head=insertBegin(head,20);
head=insertBegin(head,10);
printlist(head);
return 0;
}
insert a node at the end of linked list
#include (bits/stdc++.h> using namespace std;
struct Node{
int data;
Node* next;
Node(int x){
data=x;
next=NULL;
}
};
Node *insertEnd(Node *head,int x){
Node *temp=new Node(x);
if(head==NULL)return temp;
Node *curr=head;
while(curr->next!=NULL){
curr=curr->next;
}
curr->next=temp;
return head;
}
void printlist(Node *head){
Node *curr=head;
while(curr!=NULL){
cout((curr->data((" ";
curr=curr->next;
}
}
int main()
{
Node *head=NULL;
head=insertEnd(head,10);
head=insertEnd(head,20);
head=insertEnd(head,30);
printlist(head);
return 0;
}
delete first node of linked list
#include (bits/stdc++.h> using namespace std;
struct Node{
int data;
Node* next;
Node(int x){
data=x;
next=NULL;
}
};
void printlist(Node *head){
Node *curr=head;
while(curr!=NULL){
cout((curr->data((" ";
curr=curr->next;
}cout((endl;
}
Node *delHead(Node *head){
if(head==NULL)return NULL;
else{
Node *temp=head->next;
delete(head);
return temp;
}
}
int main()
{
Node *head=new Node(10);
head->next=new Node(20);
head->next->next=new Node(30);
printlist(head);
head=delHead(head);
printlist(head);
return 0; }
deletion of last node of a singly linked list
#include (bits/stdc++.h> using namespace std;
struct Node{
int data;
Node* next;
Node(int x){
data=x;
next=NULL;
}
};
void printlist(Node *head){
Node *curr=head;
while(curr!=NULL){
cout((curr->data((" ";
curr=curr->next;
}cout((endl;
}
Node *delTail(Node *head){
if(head==NULL)return NULL;
if(head->next==NULL){
delete head;
return NULL;
}
Node *curr=head;
while(curr->next->next!=NULL)
curr=curr->next;
delete (curr->next);
curr->next=NULL;
return head;
}
int main()
{
Node *head=new Node(10);
head->next=new Node(20);
head->next->next=new Node(30);
printlist(head);
head=delTail(head);
printlist(head);
return 0; }
Insertion at a given position in a linked list
Approach: To insert a given data at a specified position, the below algorithm is to be followed:
Traverse the Linked list upto position-1 nodes.
Once all the position-1 nodes are traversed, allocate memory and the given data to the new node.
Point the next pointer of the new node to the next of current node.
Point the next pointer of current node to the new node.
// C++ program for insertion in a single linked // list at a specified position #include (bits/stdc++.h> using namespace std;
// A linked list Node
struct Node {
int data;
struct Node* next;
};
// Size of linked list int size = 0;
// function to create and return a Node
Node* getNode(int data)
{
// allocating space
Node* newNode = new Node();
// inserting the required data newNode->data = data; newNode->next = NULL; return newNode; }
// function to insert a Node at required position
void insertPos(Node** current, int pos, int data)
{
// This condition to check whether the
// position given is valid or not.
if (pos ( 1 || pos > size + 1)
cout (( "Invalid position!" (( endl;
else {
// Keep looping until the pos is zero
while (pos--) {
if (pos == 0) {
// adding Node at required position Node* temp = getNode(data);
// Making the new Node to point to // the old Node at the same position temp->next = *current;
// Changing the pointer of the Node previous // to the old Node to point to the new Node *current = temp; } else // Assign double pointer variable to point to the // pointer pointing to the address of next Node current = &(*current)->next; } size++; } }
// This function prints contents
// of the linked list
void printList(struct Node* head)
{
while (head != NULL) {
cout (( " " (( head->data;
head = head->next;
}
cout (( endl;
}
// Driver Code
int main()
{
// Creating the list 3->5->8->10
Node* head = NULL;
head = getNode(3);
head->next = getNode(5);
head->next->next = getNode(8);
head->next->next->next = getNode(10);
size = 4; cout (( "Linked list before insertion: "; printList(head); int data = 12, pos = 3; insertPos(&head, pos, data); cout (( "Linked list after insertion of 12 at position 3: "; printList(head);
// front of the linked list data = 1, pos = 1; insertPos(&head, pos, data); cout (( "Linked list after insertion of 1 at position 1: "; printList(head);
// insertion at end of the linked list data = 15, pos = 7; insertPos(&head, pos, data); cout (( "Linked list after insertion of 15 at position 7: "; printList(head);
return 0; }
Sorted insert in a linked list
Algorithm:
Let input linked list is sorted in increasing order.
1) If Linked list is empty then make the node as
head and return it.
2) If the value of the node to be inserted is smaller
than the value of the head node, then insert the node
at the start and make it head.
3) In a loop, find the appropriate node after
which the input node (let 9) is to be inserted.
To find the appropriate node start from the head,
keep moving until you reach a node GN (10 in
the below diagram) who’s value is greater than
the input node. The node just before GN is the
appropriate node (7).
4) Insert the node (9) after the appropriate node
(7) found in step 3.
Implementation:
/* Program to insert in a sorted list */
#include (bits/stdc++.h>
using namespace std;
/* Link list node */
class Node {
public:
int data;
Node* next;
};
/* function to insert a new_node
in a list. Note that this
function expects a pointer to
head_ref as this can modify the
head of the input linked list
(similar to push())*/
void sortedInsert(Node** head_ref,
Node* new_node)
{
Node* current;
/* Special case for the head end */
if (*head_ref == NULL
|| (*head_ref)->data
>= new_node->data) {
new_node->next = *head_ref;
*head_ref = new_node;
}
else {
/* Locate the node before the
point of insertion */
current = *head_ref;
while (current->next != NULL
&& current->next->data
( new_node->data) {
current = current->next;
}
new_node->next = current->next;
current->next = new_node;
}
}
/* BELOW FUNCTIONS ARE JUST UTILITY TO TEST sortedInsert */
/* A utility function to
create a new node */
Node* newNode(int new_data)
{
/* allocate node */
Node* new_node = new Node();
/* put in the data */ new_node->data = new_data; new_node->next = NULL;
return new_node; }
/* Function to print linked list */
void printList(Node* head)
{
Node* temp = head;
while (temp != NULL) {
cout (( temp->data (( " ";
temp = temp->next;
}
}
/* Driver program to test count function*/
int main()
{
/* Start with the empty list */
Node* head = NULL;
Node* new_node = newNode(5);
sortedInsert(&head, new_node);
new_node = newNode(10);
sortedInsert(&head, new_node);
new_node = newNode(7);
sortedInsert(&head, new_node);
new_node = newNode(3);
sortedInsert(&head, new_node);
new_node = newNode(1);
sortedInsert(&head, new_node);
new_node = newNode(9);
sortedInsert(&head, new_node);
cout (( "Created Linked List\n";
printList(head);
return 0; } // This is code is contributed by rathbhupendra
Middle of a linked list
Naive approach=
#include (bits/stdc++.h>
using namespace std;
struct Node{
int data;
Node* next;
Node(int x){
data=x;
next=NULL;
}
};
void printlist(Node *head){
Node *curr=head;
while(curr!=NULL){
cout((curr->data((" ";
curr=curr->next;
}cout((endl;
}
void printMiddle(Node * head){
if(head==NULL)return;
int count=0;
Node *curr;
for(curr=head;curr!=NULL;curr=curr->next)
count++;
curr=head;
for(int i=0;i(count/2;i++)
curr=curr->next;
cout((curr->data;
}
int main()
{
Node *head=new Node(10);
head->next=new Node(20);
head->next->next=new Node(30);
head->next->next->next=new Node(40);
head->next->next->next->next=new Node(50);
printlist(head);
cout(("Middle of Linked List: ";
printMiddle(head);
return 0;
}
Efficient approach-
#include (bits/stdc++.h>
using namespace std;
struct Node{
int data;
Node* next;
Node(int x){
data=x;
next=NULL;
}
};
void printlist(Node *head){
Node *curr=head;
while(curr!=NULL){
cout((curr->data((" ";
curr=curr->next;
}cout((endl;
}
void printMiddle(Node * head){
if(head==NULL)return;
Node *slow=head,*fast=head;
while(fast!=NULL&&fast->next!=NULL){
slow=slow->next;
fast=fast->next->next;
}
cout((slow->data;
}
int main()
{
Node *head=new Node(10);
head->next=new Node(20);
head->next->next=new Node(30);
head->next->next->next=new Node(40);
head->next->next->next->next=new Node(50);
printlist(head);
cout(("Middle of Linked List: ";
printMiddle(head);
return 0;
}
finding the n-th node from the end of a given linked list
Method 1(Using length of Linked List) #include (bits/stdc++.h> using namespace std;
struct Node{
int data;
Node* next;
Node(int x){
data=x;
next=NULL;
}
};
void printlist(Node *head){
Node *curr=head;
while(curr!=NULL){
cout((curr->data((" ";
curr=curr->next;
}cout((endl;
}
void printNthFromEnd(Node * head,int n){
int len=0;
for(Node *curr=head;curr!=NULL;curr=curr->next)
len++;
if(len(n)
return;
Node *curr=head;
for(int i=1;i(len-n+1;i++)
curr=curr->next;
cout(((curr->data)((" ";
}
int main()
{
Node *head=new Node(10);
head->next=new Node(20);
head->next->next=new Node(30);
head->next->next->next=new Node(40);
head->next->next->next->next=new Node(50);
printlist(head);
cout(("Nth node from end of Linked List: ";
printNthFromEnd(head,2);
return 0;
}
Method 2(Using Two Pointers/References
#include (bits/stdc++.h>
using namespace std;
struct Node{
int data;
Node* next;
Node(int x){
data=x;
next=NULL;
}
};
void printlist(Node *head){
Node *curr=head;
while(curr!=NULL){
cout((curr->data((" ";
curr=curr->next;
}cout((endl;
}
void printNthFromEnd(Node * head,int n){
if(head==NULL)return;
Node *first=head;
for(int i=0;i(n;i++){
if(first==NULL)return;
first=first->next;
}
Node *second=head;
while(first!=NULL){
second=second->next;
first=first->next;
}
cout(((second->data);
}
int main()
{
Node *head=new Node(10);
head->next=new Node(20);
head->next->next=new Node(30);
head->next->next->next=new Node(40);
head->next->next->next->next=new Node(50);
printlist(head);
cout(("Nth node from end of Linked List: ";
printNthFromEnd(head,2);
return 0;
}
reversing a linked list in an iterative manner
Naive Code
#include (bits/stdc++.h>
using namespace std;
struct Node{
int data;
Node* next;
Node(int x){
data=x;
next=NULL;
}
};
void printlist(Node *head){
Node *curr=head;
while(curr!=NULL){
cout((curr->data((" ";
curr=curr->next;
}cout((endl;
}
Node *revList(Node *head){
vector(int> arr;
for(Node *curr=head;curr!=NULL;curr=curr->next){
arr.push_back(curr->data);
}
for(Node *curr=head;curr!=NULL;curr=curr->next){
curr->data=arr.back();
arr.pop_back();
}
return head;
}
int main()
{
Node *head=new Node(10);
head->next=new Node(20);
head->next->next=new Node(30);
printlist(head);
head=revList(head);
printlist(head);
return 0;
}
Efficient Code
#include (bits/stdc++.h>
using namespace std;
struct Node{
int data;
Node* next;
Node(int x){
data=x;
next=NULL;
}
};
void printlist(Node *head){
Node *curr=head;
while(curr!=NULL){
cout((curr->data((" ";
curr=curr->next;
}cout((endl;
}
Node *reverse(Node *head){
Node *curr=head;
Node *prev=NULL;
while(curr!=NULL){
Node *next=curr->next;
curr->next=prev;
prev=curr;
curr=next;
}
return prev;
}
int main()
{
Node *head=new Node(10);
head->next=new Node(20);
head->next->next=new Node(30);
printlist(head);
head=reverse(head);
printlist(head);
return 0;
}
Recursive reverse of a linked list
#include (bits/stdc++.h> using namespace std;
struct Node{
int data;
Node* next;
Node(int x){
data=x;
next=NULL;
}
};
void printlist(Node *head){
Node *curr=head;
while(curr!=NULL){
cout((curr->data((" ";
curr=curr->next;
}cout((endl;
}
Node *recRevL(Node *head){
if(head==NULL||head->next==NULL)return head;
Node *rest_head=recRevL(head->next);
Node *rest_tail=head->next;
rest_tail->next=head;
head->next=NULL;
return rest_head;
}
int main()
{
Node *head=new Node(10);
head->next=new Node(20);
head->next->next=new Node(30);
printlist(head);
head=recRevL(head);
printlist(head);
return 0;
}
Method 2- In this method a tail recursive solution is discussed to reverse the linked list. This method simply follows the iterative solution.
#include (bits/stdc++.h> using namespace std;
struct Node{
int data;
Node* next;
Node(int x){
data=x;
next=NULL;
}
};
void printlist(Node *head){
Node *curr=head;
while(curr!=NULL){
cout((curr->data((" ";
curr=curr->next;
}cout((endl;
}
Node *recRevL(Node *curr,Node *prev){
if(curr==NULL)return prev;
Node *next=curr->next;
curr->next=prev;
return recRevL(next,curr);
}
int main()
{
Node *head=new Node(10);
head->next=new Node(20);
head->next->next=new Node(30);
printlist(head);
head=recRevL(head,NULL);
printlist(head);
return 0;
}
Remove duplicates from a sorted single linked list
Algorithm:
Traverse the list from the head (or start) node. While traversing, compare each node with its next node. If the data of the next node is the same as the current node then delete the next node. Before we delete a node, we need to store the next pointer of the node
/* C++ Program to remove duplicates from a sorted linked list */ #include (bits/stdc++.h> using namespace std;
/* Link list node */
class Node
{
public:
int data;
Node* next;
};
/* The function removes duplicates from a sorted list */
void removeDuplicates(Node* head)
{
/* Pointer to traverse the linked list */
Node* current = head;
/* Pointer to store the next pointer of a node to be deleted*/ Node* next_next;
/* do nothing if the list is empty */ if (current == NULL) return;
/* Traverse the list till last node */
while (current->next != NULL)
{
/* Compare current node with next node */
if (current->data == current->next->data)
{
/* The sequence of steps is important*/
next_next = current->next->next;
free(current->next);
current->next = next_next;
}
else /* This is tricky: only advance if no deletion */
{
current = current->next;
}
}
}
/* UTILITY FUNCTIONS */
/* Function to insert a node at the beginning of the linked list */
void push(Node** head_ref, int new_data)
{
/* allocate node */
Node* new_node = new Node();
/* put in the data */ new_node->data = new_data;
/* link the old list off the new node */ new_node->next = (*head_ref);
/* move the head to point to the new node */ (*head_ref) = new_node; }
/* Function to print nodes in a given linked list */
void printList(Node *node)
{
while (node!=NULL)
{
cout((" "((node->data;
node = node->next;
}
}
/* Driver program to test above functions*/
int main()
{
/* Start with the empty list */
Node* head = NULL;
/* Let us create a sorted linked list to test the functions Created linked list will be 11->11->11->13->13->20 */ push(&head, 20); push(&head, 13); push(&head, 13); push(&head, 11); push(&head, 11); push(&head, 11);
cout(("Linked list before duplicate removal ";
printList(head);
/* Remove duplicates from linked list */ removeDuplicates(head);
cout(("\nLinked list after duplicate removal ";
printList(head);
return 0; }
// This code is contributed by rathbhupendra
Given a singly linked list of integers. The task is to display the linked list.
Example 1:
Input: LinkedList: 1->2->3->4->5 Output: 1 2 3 4 5 Constraints: 1 <= Number of nodes <= 100 0 <= value of nodes<= 103
vector displayList(Node *head)
{
vector v;
Node *temp = head;
while (temp != NULL) {
v.push_back(temp->data);
temp=temp->next;
}
return v;
}Given a singly linked list of size N. The task is to sum the elements of the linked list.
Example 1:
Input:
LinkedList: 1->2->3->4->5
Output: 15
Example 2:
Input:
LinkedList: 2->4->6->7->5->1->0
Output: 25
Your Task:
Your task is to complete the given function sumOfElements(), which takes head reference as argument and should return the sum of all the nodes in the Linked List.
Constraints:
1 <= n <= 100
1 <= value <= 103
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
int sumOfElements(Node *head)
{
int sum = 0;
Node* ptr;
ptr = head;
while (ptr != NULL) {
sum += ptr->data;
ptr = ptr->next;
}
return sum;
}
Count nodes of linked list
int getCount(struct Node* head){
int count = 0;
Node* current = head;
while (current != NULL) {
count++;
current = current->next;
}
return count;
}
Maximum And Minimum In Linked List
int maximum(Node *head)
{
int max = INT_MIN;
while (head != NULL) {
if (max < head->data) {
max = head->data;
}
head = head->next;
}
return max;
}
int minimum(Node *head)
{
int min = INT_MAX;
while (head != NULL) {
if (min > head->data) {
min = head->data;
}
head = head->next;
}
return min;
}
Search In Linked List
bool searchLinkedList(Node *head, int x)
{
Node* current = head;
while (current != NULL) {
if (current->data == x) {
return true;
}
current = current->next;
}
return false;
}Linked List Insertion at the end
Node *insertAtBegining(Node *head, int x) {
Node *temp = new Node(x);
temp->next=head;
return temp;
}
//Function to insert a node at the end of the linked list.
Node *insertAtEnd(Node *head, int x) {
Node*temp = new Node(x);
if(head == NULL){
return temp;
}
Node *curr=head;
while(curr->next!=NULL){
curr=curr->next;
}
curr->next=temp;
return head;
}
Given a linked list of size N and a key. The task is to insert the key in the middle of the linked list.
Example 1:
Input: LinkedList = 1->2->4 key = 3 Output: 1 2 3 4 Explanation: The new element is inserted after the current middle element in the linked list. Example 2:
Input: LinkedList = 10->20->40->50 key = 30 Output: 10 20 30 40 50 Explanation: The new element is inserted after the current middle element in the linked list and Hence, the output is 10 20 30 40 50.
Your Task:
The task is to complete the function insertInMiddle() which takes head reference and element to be inserted as the arguments. The printing is done automatically by the driver code.
Expected Time Complexity : O(N)
Expected Auxilliary Space : O(1)
Constraints:
1 <= N <= 104
Node* insertInMiddle(Node* head, int x)
{
if(head == NULL)
return NULL;
Node *a=head, *b=head;
while(1)
{
if(b->next==NULL)
break;
if( b->next->next==NULL)
break;
a=a->next;
b=b->next->next;
}
Node *c = new Node(x);
c->next=a->next;
a->next=c;
return head;
}
Linked List Insertion At Position
void insertAtPosition(Node *head, int pos, int data)
{
Node* temp=new Node(data);
int count=1;
while(head!=NULL) {
if(count==pos)
break;
head=head->next;
count++;
}
if(head==NULL)
return;
temp->next=head->next;
head->next=temp;
}
Insert In Sorted Linked List
Node * insertInSorted(Node * head, int data) {
Node *curr=head;
Node *temp=new Node(data);
if(head==NULL) {
return NULL;
}
if(head->data > temp->data) {
temp->next=head;
return temp;
}
while(curr->next!=NULL && curr->next->data < temp->data) {
curr=curr->next;
}
temp->next=curr->next;
curr->next=temp;
return head;
if(curr->next==NULL) {
curr=curr->next;
}
else {
curr->next=temp;
temp->next=NULL;
return head;
}
Delete Tail of Linked List
Node * deleteTail(Node *head)
{
if (head==NULL) return head;
else if (head->next == NULL) {
delete(head);
head = NULL;
}
else {
Node* ptr=head;
Node* ptr2=head;
while (ptr->next != NULL) {
ptr2=ptr;
ptr = ptr->next;
}
ptr2->next = NULL;
delete(ptr);
ptr=NULL;
return head; } }
Delete Head of Linked List
Node * deleteHead(Node *head)
{
if (head == NULL) return head;
Node * temp=head;
head=head->next;
temp->next=NULL;
delete temp; return head;
}
Linked List Delete at Position
Node * deleteAtPosition(Node *head,int pos)
{
if (pos==1) {
Node* temp = head;
head = head->next;
temp->next = NULL;
delete temp;
return head; } Node* curr = head; Node* prev = head;
int count = 1;
while (countnext;
}
Node* temp = curr->next;
prev->next = temp;
curr->next = NULL;
delete curr;
return head; }
Is Linked List Sorted
bool isSorted(Node * head)
{
if(head==NULL || head->next==NULL)
return true;
bool increasing=true;
bool decreasing=true;
Node * temp=head;
Node * temp2=head->next;
while(temp2)
{
if(temp2->datadata)
increasing=false;
temp2=temp2->next;
temp=temp->next;
}
temp=head;
temp2=head->next;
while(temp2)
{
if(temp2->data>temp->data)
decreasing=false;
temp2=temp2->next;
temp=temp->next;
}
return increasing||decreasing;
}
Join Two Linked Lists
Node * joinTheLists(Node * head1, Node * head2)
{
if (head1 == NULL or head2 == NULL ) return head1;
Node* curr = head1;
while (curr->next != NULL) {
curr = curr->next;
}
curr->next = head2;
return head1;
}Identical Linked Lists
while (head1 != NULL and head2 != NULL) {
if (head1->data != head2->data)
return false;
head1 = head1->next;
head2 = head2->next;
}
return true;
}Reverse a linked list
struct Node* reverseList(struct Node *head)
{
Node* preptr = NULL;
Node* currptr = head;
Node* nextptr;
while(currptr!=NULL){
nextptr=currptr->next;
currptr->next=preptr;
preptr=currptr;
currptr=nextptr;
}
return preptr;
}
Definition of a linked list
Linked Lists are linear or sequential data structures in which elements are stored at non-contiguous memory locations and are linked to each other using pointers.
Like arrays, linked lists are also linear data structures but in linked lists elements are not stored at contiguous memory locations. They can be stored anywhere in the memory but for sequential access, the nodes are linked to each other using pointers.
Advantages of Linked Lists over Arrays:
The size of the arrays is fixed, so we must know the upper limit on the number of elements in advance. Also, generally, the allocated memory is equal to the upper limit irrespective of the usage. On the other hand, linked lists are dynamic and the size of the linked list can be incremented or decremented during runtime.
Inserting a new element in an array of elements is expensive, because a room has to be created for the new elements, and to create room, existing elements have to shift.
On the other hand, nodes in linked lists can be inserted or deleted without any shift operation and is efficient than that of arrays.
Disadvantages of Linked Lists:
Random access is not allowed in Linked Lists. We have to access elements sequentially starting from the first node. So, we cannot do a binary search with linked lists efficiently with its default implementation. Therefore, lookup or search operation is costly in linked lists in comparison to arrays.
Extra memory space for a pointer is required with each element of the list.
Not cache-friendly. Since array elements are present at contiguous locations, there is a locality of reference which is not there in the case of linked lists.
Definition of double linked list
Similar to Singly Linked Lists, Doubly Linked Lists are also a sequential data structure with the only difference that the doubly linked lists contain two pointers instead of one to store the address of both next node and previous node respectively.
Each node contains two pointers, one pointing to the next node and the other pointing to the previous node.
The prev of Head node is NULL, as there is no previous node of Head.
The next of last node is NULL, as there is no node after the last node.
Advantages of doubly linked lists over singly linked list:
A DLL can be traversed in both forward and backward directions.
The delete operation in DLL is more efficient if the pointer to the node to be deleted is given.
We can quickly insert a new node before a given node.
In a singly linked list, to delete a node, a pointer to the previous node is needed. To get this previous node, sometimes the list is traversed. In DLL, we can get the previous node usin
Disadvantages of doubly linked lists over singly linked list:
Every node of DLL requires extra space for a previous pointer.
All operations require an extra pointer previous to be maintained. For example, an insertion, we need to modify previous pointers together with next pointers.
what is XOR Linked Lists
XOR Linked Lists are Memory Efficient implementation of Doubly Linked Lists. An ordinary Doubly Linked List requires space for two address fields to store the addresses of previous and next nodes. A memory-efficient version of Doubly Linked List can be created using only one space for the address field with every node. This memory efficient Doubly Linked List is called XOR Linked List or Memory Efficient Linked List as the list uses bitwise XOR operation to save space for one address. In the XOR linked list instead of storing actual memory addresses every node stores the XOR of addresses of previous and next nodes.
Ordinary Representation:
Node A: prev = NULL, next = add(B) // previous is NULL and next is address of B
Node B: prev = add(A), next = add(C) // previous is address of A and next is address of C
Node C: prev = add(B), next = add(D) // previous is address of B and next is address of D
Node D: prev = add(C), next = NULL // previous is address of C and next is NULL
XOR List Representation: Let us call the address variable in XOR representation as npx (XOR of next and previous)
Node A:
npx = 0 XOR add(B) // bitwise XOR of zero and address of B
Node B:
npx = add(A) XOR add(C) // bitwise XOR of address of A and address of C
Node C:
npx = add(B) XOR add(D) // bitwise XOR of address of B and address of D
Node D:
npx = add(C) XOR 0 // bitwise XOR of address of C and 0
Advantages of Circular Linked Lists:
Any node can be a starting point. We can traverse the whole list by starting from any point. We just need to stop when the first visited node is visited again.
Useful for implementation of a queue. Unlike this implementation, we don’t need to maintain two pointers for front and rear if we use a circular linked list. We can maintain a pointer to the last inserted node and the front can always be obtained as the next of last.
Circular lists are useful in applications to repeatedly go around the list. For example, when multiple applications are running on a PC, it is common for the operating system to put the running applications on a list and then to cycle through them, giving each of them a slice of time to execute, and then making them wait while the CPU is given to another application. It is convenient for the operating system to use a circular list so that when it reaches the end of the list it can cycle around to the front of the list.
Circular Doubly Linked Lists are used for implementation of advanced data structures like Fibonacci Heap.
Detect a loop in a linked list by hashing method
Hashing Solution :Traverse the list one by one and keep putting the node addresses in a Hash Table. At any point, if NULL is reached then return false and if next of current node points to any of the previously stored nodes in Hash then return true.
Pseudo Code
bool detectLoop(Node* h)
{
seen //HashMap
while (h != NULL)
{
// If this node is already present
// in hashmap it means there is a cycle
// (Because you we encountering the
// node for the second time).
if (seen.find(h) == True)
return true
// If we are seeing the node for
// the first time, insert it in hash
seen.insert(h)
h = h->next
}
return false
}Floyd’s Cycle-Finding Algorithm
This is the fastest method. Traverse linked list using two pointers. Move one pointer by one step and another pointer by two-step. If these pointers meet at the same node then there is a loop. If pointers do not meet then linked list doesn’t have a loop.
You may visualize the solution as two runners are running on a circular track, If they are having different speeds they will definitely meet up on circular track itself.
Pseudo Code
bool detectloop(Node* head)
{
Node *slow_p = head, *fast_p = head
while (slow_p && fast_p && fast_p->next)
{
slow_p = slow_p->next
fast_p = fast_p->next->next
if (slow_p == fast_p)
return true
}
return false
}
Find Intersection Point of Two Linked List
There are two singly linked lists in a system. By some programming error, the end node of one of the linked list got linked to the second list, forming an inverted Y shaped list. Write a program to get the point where two linked list merge.
Naive Solutions : This solution requires modifications to basic linked list data structure. Have a visited flag with each node. Traverse the first linked list and keep marking visited nodes. Now traverse the second linked list, If you see a visited node again then there is an intersection point, return the intersecting node. This solution works in O(m+n) but requires additional information with each node. A variation of this solution that doesn’t require modification to the basic data structure can be implemented using a hash. Traverse the first linked list and store the addresses of visited nodes in a hash. Now traverse the second linked list and if you see an address that already exists in the hash then return the intersecting node.
Node Count Difference Solution : Problem can be solved following these steps -
Get count of the nodes in the first list, let count be c1.
Get a count of the nodes in the second list, let count be c2.
Get the difference of counts d = abs(c1 – c2).
Now traverse the bigger list from the first node till d nodes so that from here onwards both the lists have equal no of nodes.
Then we can traverse both the lists in parallel till we come across a common node. (Note that getting a common node is done by comparing the address of the nodes)
Pseudo Code
/* function to get the intersection point of two linked
lists head1 and head2 /
int getIntesectionNode( Node head1, Node* head2)
{
c1 = getCount(head1)
c2 = getCount(head2)
d // difference
if(c1 > c2)
d = c1 - c2
return utility(d, head1, head2)
else :
d = c2 - c1
return utility(d, head2, head1)
}
/* function to get the intersection point of two linked
lists head1 and head2 where head1 has d more nodes than
head2 */
int utility(d, Node* head1, Node* head2)
{
Node* current1 = head1
Node* current2 = head2
for ( i = 0 to d-1 )
{
if(current1 == NULL)
return -1
current1 = current1->next
}
while(current1 != NULL && current2 != NULL)
{
if(current1 == current2)
return current1->data
current1= current1->next
current2= current2->next
}
return -1
}
Which of the following sorting algorithms can be used to sort a random linked list with minimum time complexity? A Insertion Sort B Quick Sort C Heap Sort D Merge Sort
Both Merge sort and Insertion sort can be used for linked lists.
The slow random-access performance of a linked list makes other algorithms (such as quicksort) perform poorly, and others (such as heapsort) completely impossible.
Since worst case time complexity of Merge Sort is O(nLogn) and Insertion sort is O(n^2), merge sort is preferred.
See following for implementation of merge sort using Linked List.
What is the output of following function for start pointing to first node of following linked list?
1->2->3->4->5->6 void fun(struct node* start)
{
if(start == NULL)
return;
printf(“%d “, start->data);
if(start->next != NULL )
fun(start->next->next);
printf(“%d “, start->data);
} A 1 4 6 6 4 1 B 1 3 5 1 3 5 C 1 2 3 5 D 1 3 5 5 3 1
Ans - D
fun() prints alternate nodes of the given Linked List, first from head to end, and then from end to head. If Linked List has even number of nodes, then skips the last node.
The following C function takes a single-linked list of integers as a parameter and rearranges the elements of the list. The function is called with the list containing the integers 1, 2, 3, 4, 5, 6, 7 in the given order. What will be the contents of the list after the function completes execution?
struct node
{
int value;
struct node *next;
};
void rearrange(struct node *list)
{
struct node *p, * q;
int temp;
if ((!list) || !list->next)
return;
p = list;
q = list->next;
while(q)
{
temp = p->value; p->value = q->value; q->value = temp; p = q->next; q = p?p->next:0;
}
} A 1,2,3,4,5,6,7 B 2,1,4,3,6,5,7 C 1,3,2,5,4,7,6 D 2,3,4,5,6,7,1
Ans- B
Explanation
The function rearrange() exchanges data of every node with its next node. It starts exchanging data from the first node itself.
In the worst case, the number of comparisons needed to search a singly linked list of length n for a given element is (GATE CS 2002)
(A) log 2 n
(B) n/2
(C) log 2 n – 1
(D) n
(D) n
Suppose each set is represented as a linked list with elements in arbitrary order. Which of the operations among union, intersection, membership, cardinality will be the slowest? (GATE CS 2004) (A) union only (B) intersection, membership (C) membership, cardinality (D) union, intersection
Answer: (D)
Explanation: For getting intersection of L1 and L2, search for each element of L1 in L2 and print the elements we find in L2.
There can be many ways for getting union of L1 and L2. One of them is as follows
a) Print all the nodes of L1 and print only those which are not present in L2.
b) Print nodes of L2.
All of these methods will require more operations than intersection as we have to process intersection node plus other nodes.
Consider the function f defined below.
struct item
{
int data;
struct item * next;
};
int f(struct item *p)
{
return (
(p == NULL) ||
(p->next == NULL) ||
(( P->data <= p->next->data) && f(p->next))
);
}
For a given linked list p, the function f returns 1 if and only if (GATE CS 2003)
(A) not all elements in the list have the same data value.
(B) the elements in the list are sorted in non-decreasing order of data value
(C) the elements in the list are sorted in non-increasing order of data value
(D) None of them
Answer: (B)
Explanation:
The function f() works as follows
1) If linked list is empty return 1
2) Else If linked list has only one element return 1
3) Else if node->data is smaller than equal to node->next->data and same thing holds for rest of the list then return 1
4) Else return 0
What are the time complexities of finding 8th element from beginning and 8th element from end in a singly linked list?
Let n be the number of nodes in linked list, you may assume that n > 8. (A) O(1) and O(n) (B) O(1) and O(1) (C) O(n) and O(1) (D) O(n) and O(n)
Answer: (A)
Explanation: Finding 8th element from beginning requires 8 nodes to be traversed which takes constant time.
Finding 8th from end requires the complete list to be traversed.
Is it possible to create a doubly linked list using only one pointer with every node.
(A) Not Possible
(B) Yes, possible by storing XOR of addresses of previous and next nodes.
(C) Yes, possible by storing XOR of current node and next node
(D) Yes, possible by storing XOR of current node and previous node
Ans - B
Given pointer to a node X in a singly linked list. Only one pointer is given, pointer to head node is not given, can we delete the node X from given linked list?
(A) Possible if X is not last node. Use following two steps (a) Copy the data of next of X to X. (b) Delete next of X.
(B) Possible if size of linked list is even.
(C) Possible if size of linked list is odd
(D) Possible if X is not first node. Use following two steps (a) Copy the data of next of X to X. (b) Delete next of
Answer: (A)
Explanation: Following are simple steps.
struct node *temp = X->next; X->data = temp->data; X->next = temp->next; free(temp);
You are given pointers to first and last nodes of a singly linked list, which of the following operations are dependent on the length of the linked list?
(A) Delete the first element
(B) Insert a new element as a first element
(C) Delete the last element of the list
(D) Add a new element at the end of the list
Answer: (C)
Explanation: a) Can be done in O(1) time by deleting memory and changing the first pointer.
b) Can be done in O(1) time, see push() here
c) Delete the last element requires pointer to previous of last, which can only be obtained by traversing the list.
d) Can be done in O(1) by changing next of last and then last.
Implement a simple circular linked list
#include (bits/stdc++.h> using namespace std;
struct Node{
int data;
Node* next;
Node(int d){
data=d;
next=NULL;
}
};
int main()
{
Node *head=new Node(10);
head->next=new Node(5);
head->next->next=new Node(20);
head->next->next->next=new Node(15);
head->next->next->next->next=head;
return 0;
}
Circular Linked List (Advantages & Disadvantages)
advantages traversal through any node is possible Implementation like round robin we can insert at the beginning and end just by maintaining a tail pointer disadvantages implementation of operations is complex
traversal of a circular linked list in C++.
Method 1(For Loop) #include (bits/stdc++.h> using namespace std;
struct Node{
int data;
Node* next;
Node(int d){
data=d;
next=NULL;
}
};
void printlist(Node *head){
if(head==NULL)return;
cout((head->data((" ";
for(Node *p=head->next;p!=head;p=p->next)
cout((p->data((" ";
}
int main()
{
Node *head=new Node(10);
head->next=new Node(5);
head->next->next=new Node(20);
head->next->next->next=new Node(15);
head->next->next->next->next=head;
printlist(head);
return 0;
}
output
10 5 20 15
TC- O(n)
Method 2(do while) #include (bits/stdc++.h> using namespace std;
struct Node{
int data;
Node* next;
Node(int d){
data=d;
next=NULL;
}
};
void printlist(Node *head){
if(head==NULL)return;
Node *p=head;
do{
cout((p->data((" ";
p=p->next;
}while(p!=head);
}
int main()
{
Node *head=new Node(10);
head->next=new Node(5);
head->next->next=new Node(20);
head->next->next->next=new Node(15);
head->next->next->next->next=head;
printlist(head);
return 0;
}
TC - O(n)
Insert at beginning of a circular linked list
Naive : O(n)
#include (bits/stdc++.h>
using namespace std;
struct Node{
int data;
Node* next;
Node(int d){
data=d;
next=NULL;
}
};
void printlist(Node *head){
if(head==NULL)return;
Node *p=head;
do{
cout((p->data((" ";
p=p->next;
}while(p!=head);
}
Node *insertBegin(Node * head,int x){
Node *temp=new Node(x);
if(head==NULL)
temp->next=temp;
else{
Node *curr=head;
while(curr->next!=head)
curr=curr->next;
curr->next=temp;
temp->next=head;
}
return temp;
}
int main()
{
Node *head=new Node(10);
head->next=new Node(20);
head->next->next=new Node(30);
head->next->next->next=head;
head=insertBegin(head,15);
printlist(head);
return 0;
}
15 10 20 30
Efficient Code
#include (bits/stdc++.h>
using namespace std;
struct Node{
int data;
Node* next;
Node(int d){
data=d;
next=NULL;
}
};
void printlist(Node *head){
if(head==NULL)return;
Node *p=head;
do{
cout((p->data((" ";
p=p->next;
}while(p!=head);
}
Node *insertBegin(Node * head,int x){
Node *temp=new Node(x);
if(head==NULL){
temp->next=temp;
return temp;
}
else{
temp->next=head->next;
head->next=temp;
int t=head->data;
head->data=temp->data;
temp->data=t;
return head;
}
}
int main()
{
Node *head=new Node(10);
head->next=new Node(20);
head->next->next=new Node(30);
head->next->next->next=head;
head=insertBegin(head,15);
printlist(head);
return 0;
}
insert at the end of a circular linked list
Naive : O(n)
#include (bits/stdc++.h>
using namespace std;
struct Node{
int data;
Node* next;
Node(int d){
data=d;
next=NULL;
}
};
void printlist(Node *head){
if(head==NULL)return;
Node *p=head;
do{
cout((p->data((" ";
p=p->next;
}while(p!=head);
}
Node *insertEnd(Node *head,int x){
Node *temp=new Node(x);
if(head==NULL){
temp->next=temp;
return temp;
}
else{
Node *curr=head;
while(curr->next!=head)
curr=curr->next;
curr->next=temp;
temp->next=head;
return head;
}
}
int main()
{
Node *head=new Node(10);
head->next=new Node(20);
head->next->next=new Node(30);
head->next->next->next=head;
head=insertEnd(head,15);
printlist(head);
return 0;
}
10 20 30 15
Efficient : O(1)
#include (bits/stdc++.h>
using namespace std;
struct Node{
int data;
Node* next;
Node(int d){
data=d;
next=NULL;
}
};
void printlist(Node *head){
if(head==NULL)return;
Node *p=head;
do{
cout((p->data((" ";
p=p->next;
}while(p!=head);
}
Node *insertEnd(Node *head,int x){
Node *temp=new Node(x);
if(head==NULL){
temp->next=temp;
return temp;
}
else{
temp->next=head->next;
head->next=temp;
int t=head->data;
head->data=temp->data;
temp->data=t;
return temp;
}
}
int main()
{
Node *head=new Node(10);
head->next=new Node(20);
head->next->next=new Node(30);
head->next->next->next=head;
head=insertEnd(head,15);
printlist(head);
return 0;
}
10 20 30 15
deleting first node of a circular linked list
Naive Code O(n)
#include (bits/stdc++.h>
using namespace std;
struct Node{
int data;
Node* next;
Node(int d){
data=d;
next=NULL;
}
};
void printlist(Node *head){
if(head==NULL)return;
Node *p=head;
do{
cout((p->data((" ";
p=p->next;
}while(p!=head);
}
Node *delHead(Node *head){
if(head==NULL)return NULL;
if(head->next==head){
delete head;
return NULL;
}
Node *curr=head;
while(curr->next!=head)
curr=curr->next;
curr->next=head->next;
delete head;
return (curr->next);
}
int main()
{
Node *head=new Node(10);
head->next=new Node(20);
head->next->next=new Node(30);
head->next->next->next=new Node(40);
head->next->next->next->next=head;
head=delHead(head);
printlist(head);
return 0;
}
20 30 40
Efficient Code O(1)
#include (bits/stdc++.h>
using namespace std;
struct Node{
int data;
Node* next;
Node(int d){
data=d;
next=NULL;
}
};
void printlist(Node *head){
if(head==NULL)return;
Node *p=head;
do{
cout((p->data((" ";
p=p->next;
}while(p!=head);
}
Node *delHead(Node *head){
if(head==NULL)return NULL;
if(head->next==head){
delete head;
return NULL;
}
head->data=head->next->data;
Node *temp=head->next;
head->next=head->next->next;
delete temp;
return head;
}
int main()
{
Node *head=new Node(10);
head->next=new Node(20);
head->next->next=new Node(30);
head->next->next->next=new Node(40);
head->next->next->next->next=head;
head=delHead(head);
printlist(head);
return 0;
}
20 30 40
code for deleting kth node of a circular linked list where k is less than or equal to the number of nodes in the list
#include (bits/stdc++.h> using namespace std;
struct Node{
int data;
Node* next;
Node(int d){
data=d;
next=NULL;
}
};
void printlist(Node *head){
if(head==NULL)return;
Node *p=head;
do{
cout((p->data((" ";
p=p->next;
}while(p!=head);
}
Node *deleteHead(Node *head){
if(head==NULL)return NULL;
if(head->next==head){
delete head;
return NULL;
}
head->data=head->next->data;
Node *temp=head->next;
head->next=head->next->next;
delete temp;
return head;
}
Node *deleteKth(Node *head,int k){
if(head==NULL)return head;
if(k==1)return deleteHead(head);
Node *curr=head;
for(int i=0;i(k-2;i++)
curr=curr->next;
Node *temp=curr->next;
curr->next=curr->next->next;
delete temp;
return head;
}
int main()
{
Node *head=new Node(10);
head->next=new Node(20);
head->next->next=new Node(30);
head->next->next->next=new Node(40);
head->next->next->next->next=head;
head=deleteKth(head,3);
printlist(head);
return 0;
}
10 20 40
Given a circular linked list of size n, you need to display the linked list. The tail of the linked list is connected to head.
Example 1:
Input: LinkedList: 1->2->3->4 (the last and the first node are connected, i.e. 4 -> 1) Output: 1 2 3 4 Example 2:
Input:
LinkedList: 1->2
(the last and the first node are connected,
i.e. 2 -> 1)
Output: 1 2
Your Task:
The task is to complete the function displayList() which takes head reference as argument and returns the circular linked list as a list.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).
vector displayList(Node *head)
{
if (head==NULL) return {};
vector vec;
Node* curr = head;
do {
vec.push_back(curr->data);
curr = curr->next;
}while (curr!=head);
return vec;
}Given a circular linked list of size n, you need to find the length of the list (total number of nodes). The tail of the linked list is connected to head.
Example 1:
Input: LinkedList: 1->2->3->4->5 (the first and the last node is connected, i.e 5 --> 1) Output: 5 Example 2:
Input:
LinkedList: 2->5->7->8->99->100
(the first and the last node is connected,
i.e 100 –> 2)
Output: 6
Your Task:
The task is to complete the function getLength() which takes head reference as argument and returns the total number of nodes in the list. The printing is done by the driver code.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
Constraints:
1 <= number of nodes <= 1000
int getLength(Node * head)
{
if (head==NULL) return 0;
if (head->next==NULL) return 1;
int count = 1;
Node* curr = head->next;
while (curr != head) {
count++;
curr = curr->next;
}
return count;
}Given head, the head of a singly linked list, find if the linked list is circular or not. A linked list is called circular if it not NULL terminated and all nodes are connected in the form of a cycle. An empty linked list is considered as circular.
Note: The linked list does not contains any inner loop.
Example 1:
Input: LinkedList: 1->2->3->4->5 (the first and last node is connected, i.e. 5 --> 1) Output: 1 Example 2:
Input: LinkedList: 2->4->6->7->5->1 Output: 0 Your Task: The task is to complete the function isCircular() which checks if the given linked list is circular or not. It should return true or false accordingly. (the driver code prints 1 if the returned values is true, otherwise 0)
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
Constraints:
1 <=Number of nodes<= 100
bool isCircular(Node *head)
{
if (head==NULL) return false;
if (head->next == head) return true;
Node* curr = head;
while (curr->next != NULL) {
if (curr->next == head) return true;
curr = curr->next;
}
return false;
}Given a circular linked list of size N, you need to insert an element data before the head and make it the new head. The tail of the linked list is connected to head.
Example 1:
Input: LinkedList: 1->2->3->4 (the first and last node is connected, i.e. 4 --> 1) data = 10 Output: 10 1 2 3 4 Example 2:
Input: LinkedList: 1 2 (the first and last node is connected, i.e. 2 --> 1) data = 5 Output: 5 1 2 Your Task: The task is to complete the function insertInHead() which takes head reference and data as arguments and returns the head of the updated list. The printing is done by the driver code.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
1 <= Number of nodes <= 1000
Node *insertInHead(Node * head, int data)
{
Node* temp = new Node(data);
if (head==NULL) {
temp->next = temp;
return temp;
}
temp->next = head->next;
head->next = temp;
swap(head->data, temp->data);
return head;
}
Given a circular linked list of size N, you need to insert an element data after the tail.
The tail of the linked list is connected to head.
Example 1:
Input: LinkedList: 1->2->3->4 (the first and last node is connected, i.e. 4 --> 1) data = 10 Output: 1 2 3 4 10 Example 2:
Input: LinkedList: 1 2 (the first and last node is connected, i.e. 2 --> 1) data = 5 Output: 1 2 5 Your Task: The task is to complete the function insertInTail() which takes head reference and data as arguments and returns the head of the updated list. The printing is done by the driver code.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
Node *insertInTail(Node * head, int data)
{
Node* temp = new Node(data);
if (head==NULL) {
temp->next = temp;
return temp;
}
temp->next = head->next; head->next = temp; swap(head->data, temp->data); head = temp; return head; }
You are given a circular linked list of size N. You need to insert an element data just after the given position pos.
The position of first element is 1. If the given position is greater than N, then don’t insert anything as it is not possible.
As the given linked list is circular, it means that the tail is connected to the head of the list.
Example 1:
Input: LinkedList: 1->2->3->4->5 (the first and last node is connected, i.e. 5 --> 1) position = 6, element = 10 Output: 1 2 3 4 5 Example 2:
Input: LinkedList: 2->4->6->7->5->1->0 (the first and last node is connected, i.e. 0 --> 2) position = 7,data = 99 Output: 2 4 6 7 5 1 0 99 Your Task: You only need to complete the function insertAtPosition that takes head, pos, and data as parameters. The printing is done automatically by the driver code.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
Constraints:
1 <= N, pos <= 103
void insertAtPosition(Node *head, int pos, int data)
{
Node* temp = new Node(data);
if (head == NULL) {
temp->next = temp;
head = temp;
return;
}
Node* curr = head;
for (int i = 1; inext == head) return;
curr = curr->next;
}
temp->next = curr->next;
curr->next = temp;
}
Given a circular linked list of size n, you have to delete the tail (last element) in the linked list.
In a circular linked list, the tail is connect to the head using the next pointer.
Example 1:
Input: LinkedList: 1->2 (the first and last node are connected, i.e. 2 --> 1) Output: 1 Example 2:
Input: LinkedList: 2->5->7->8->99->100 (the first and last node are connected, i.e. 100 --> 2) Output: 2 5 7 8 99 Your Task: The task is to complete the function deleteTail() which takes head reference and returns reference to the head node, which is then used to display the list. The printing is done automatically by the driver code.
Expected Time Complexity: O(n).
Expected Auxiliary Space: O(1).
Constraints:
2 <= number of nodes <= 103
Node * deleteTail(Node * head)
{
Node* curr = head;
while (curr->next->next != head)
curr = curr->next;
Node* temp = curr->next;
curr->next = curr->next->next;
delete temp;
return head;
}Given a circular linked list of size n, you have to delete the head of the linked list and return the new head.
In the circular linked list the tail of the list is connected to the head using the next pointer.
Note: Please also set the next of the original head to null.
Example 1:
Input: LinkedList: 1->2 (the first and last node are connected, i.e. 2 --> 1) Output: 2 Example 2:
Input: LinkedList: 2->5->7->8->99->100 (the first and last node are connected, i.e. 100 --> 2) Output: 5 7 8 99 100 Your Task: The task is to complete the function deleteHead() which takes head reference. The function deletes the head node and returns a reference to the new head node, which is then used to display the list. The printing is done automatically by the driver code.
Expected Time Complexity: O(n).
Expected Auxiliary Space: O(1).
Constraints:
2 <= number of nodes <= 103
Node * deleteHead(Node *head)
{
if(head==NULL)
return NULL;
Node *curr=head;
while(curr->next!=head)
{
curr=curr->next;
}
Node *temp=head;
head=head->next;
temp->next=NULL;
delete temp;
curr->next=head;
return head; }
Given a linked list of size n, you have to delete the node at position pos of the linked list and return the new head. The position of initial node is 1.
The tail of the circular linked list is connected to the head using next pointer.
Example 1:
Input: LinkedList: 1->2->3->4->5 (the first and last node are connected, i.e. 5 --> 1) position: 4 Output: 1 2 3 5 Example 2:
Input: LinkedList: 2->5->7->8->99->100 (the first and last node are connected, i.e. 5 --> 1) position: 6 Output: 2 5 7 8 99 Your Task: The task is to complete the function deleteAtPosition() which takes head reference and pos as argument and returns reference to the new head node, which is then used to display the list. The printing is done automatically by the driver code.
Expected Time Complexity: O(n).
Expected Auxiliary Space: O(1).
Constraints:
2 <= number of nodes <= 103
1 <= pos <= n
int getLength(Node * head)
{
Node *temp=head;
int count=0;
while(temp->next!=head)
{
count++;
temp=temp->next;
}
return count+1;
}
Node * deleteHead(Node *head)
{
Node * curr=head;
while(curr->next!=head)
{
curr=curr->next;
}
Node * temp=head; head=head->next; temp->next=NULL; curr->next=head; delete temp; return head;
}
Node * deleteTail(Node * head)
{
Node * temp=head;
Node * prev=head;
while(temp->next!=head)
{
prev=temp;
temp=temp->next;
}
prev->next=head; temp->next=NULL; delete temp; return head;
}
Node * deleteAtPosition(Node *head,int pos)
{
if(pos==1)
{
return deleteHead(head);
}
if(pos==getLength(head))
{
return deleteTail(head);
}
Node * curr=head; Node * prev=head; int count=1; while(countnext; } Node * next=curr->next; curr->next=NULL; prev->next=next; delete curr; return head;
}
Implement a simple Doubly Linked List in C++
#include (bits/stdc++.h> using namespace std;
struct Node{
int data;
Node* prev;
Node* next;
Node(int d){
data=d;
prev=NULL;
next=NULL;
}
};
void printlist(Node *head){
Node *curr=head;
while(curr!=NULL){
cout((curr->data((" ";
curr=curr->next;
}cout((endl;
}
int main()
{
Node *head=new Node(10);
Node *temp1=new Node(20);
Node *temp2=new Node(30);
head->next=temp1;
temp1->prev=head;
temp1->next=temp2;
temp2->prev=temp1;
printlist(head);
return 0;
}
10 20 30
Singly Vs Doubly Linked List (Advantages & Disadvantages
insertion at the beginning of Doubly Linked List
#include (bits/stdc++.h> using namespace std;
struct Node{
int data;
Node* prev;
Node* next;
Node(int d){
data=d;
prev=NULL;
next=NULL;
}
};
void printlist(Node *head){
Node *curr=head;
while(curr!=NULL){
cout((curr->data((" ";
curr=curr->next;
}cout((endl;
}
Node *insertBegin(Node *head,int data){
Node *temp=new Node(data);
temp->next=head;
if(head!=NULL)head->prev=temp;
return temp;
}
int main()
{
Node *head=new Node(10);
Node *temp1=new Node(20);
Node *temp2=new Node(30);
head->next=temp1;
temp1->prev=head;
temp1->next=temp2;
temp2->prev=temp1;
head=insertBegin(head,5);
printlist(head);
return 0;
}
5 10 20 30
Insert at end of a doubly linked list
#include (bits/stdc++.h> using namespace std;
struct Node{
int data;
Node* prev;
Node* next;
Node(int d){
data=d;
prev=NULL;
next=NULL;
}
};
void printlist(Node *head){
Node *curr=head;
while(curr!=NULL){
cout((curr->data((" ";
curr=curr->next;
}cout((endl;
}
Node *insertEnd(Node *head,int data){
Node *temp=new Node(data);
if(head==NULL)return temp;
Node *curr=head;
while(curr->next!=NULL){
curr=curr->next;
}
curr->next=temp;
temp->prev=curr;
return head;
}
int main()
{
Node *head=new Node(10);
Node *temp1=new Node(20);
Node *temp2=new Node(30);
head->next=temp1;
temp1->prev=head;
temp1->next=temp2;
temp2->prev=temp1;
head=insertEnd(head,40);
printlist(head);
return 0;
}
10 20 30 40
reversal of doubly linked list.
Node* reverseDLL(Node * head)
{
Node *temp=head;
Node *temp2=temp;
while(temp!=NULL)
{
Node *temp1=temp->next;
temp2=temp;
temp->next=temp->prev;
temp->prev=temp1;
temp=temp1;
}
return temp2;
}
deleting first node of a given doubly linked list.
#include (bits/stdc++.h> using namespace std;
struct Node{
int data;
Node* prev;
Node* next;
Node(int d){
data=d;
prev=NULL;
next=NULL;
}
};
void printlist(Node *head){
Node *curr=head;
while(curr!=NULL){
cout((curr->data((" ";
curr=curr->next;
}cout((endl;
}
Node *delHead(Node *head){
if(head==NULL)return NULL;
if(head->next==NULL){
delete head;
return NULL;
}
else{
Node *temp=head;
head=head->next;
head->prev=NULL;
delete temp;
return head;
}
}
int main()
{
Node *head=new Node(10);
Node *temp1=new Node(20);
Node *temp2=new Node(30);
head->next=temp1;
temp1->prev=head;
temp1->next=temp2;
temp2->prev=temp1;
head=delHead(head);
printlist(head);
return 0;
}
20 30
deleting last node of a doubly linked list
#include (bits/stdc++.h> using namespace std;
struct Node{
int data;
Node* prev;
Node* next;
Node(int d){
data=d;
prev=NULL;
next=NULL;
}
};
void printlist(Node *head){
Node *curr=head;
while(curr!=NULL){
cout((curr->data((" ";
curr=curr->next;
}cout((endl;
}
Node *delLast(Node *head){
if(head==NULL)return NULL;
if(head->next==NULL){
delete head;
return NULL;
}
Node *curr=head;
while(curr->next!=NULL)
curr=curr->next;
curr->prev->next=NULL;
delete curr;
return head;
}
int main()
{
Node *head=new Node(10);
Node *temp1=new Node(20);
Node *temp2=new Node(30);
head->next=temp1;
temp1->prev=head;
temp1->next=temp2;
temp2->prev=temp1;
head=delLast(head);
printlist(head);
return 0;
}
10 20
circular doubly linked list. It talks about its advantages and insertion
#include (bits/stdc++.h> using namespace std;
struct Node{
int data;
Node *prev;
Node* next;
Node(int d){
data=d;
prev=NULL;
next=NULL;
}
};
void printlist(Node *head){
if(head==NULL)return;
Node *p=head;
do{
cout((p->data((" ";
p=p->next;
}while(p!=head);
}
Node *insertAtHead(Node *head,int x){
Node *temp=new Node(x);
if(head==NULL){
temp->next=temp;
temp->prev=temp;
return temp;
}
temp->prev=head->prev;
temp->next=head;
head->prev->next=temp;
head->prev=temp;
return temp;
}
int main()
{
Node *head=new Node(10);
Node *temp1=new Node(20);
Node *temp2=new Node(30);
head->next=temp1;
temp1->next=temp2;
temp2->next=head;
temp2->prev=temp1;
temp1->prev=head;
head->prev=temp2;
head=insertAtHead(head,5);
printlist(head);
return 0;
}
Given a doubly linked list of n elements. The task is to display the linked list.
Example 1:
Input: LinkedList: 12345 Output: 1 2 3 4 5 5 4 3 2 1 Your Task: Your task is to complete the given function displayList(), which takes head reference as argument and returns the doubly linked list as an array ( vector in cpp, ArrayList in java, list in python) The driver's code print the list forward and backward.
Expected Time Complexity: O(n).
Expected Auxiliary Space: O(1).
vector displayList(Node *head)
{
vector res;
while(head != NULL) {
res.push_back(head->data);
head = head->next;
}
return res;
}
Given a doubly-linked list, a position p, and an integer x. The task is to add a new node with value x at the position just after pth node in the doubly linked list.
Example 1:
Input: LinkedList: 245 p = 2, x = 6 Output: 2 4 5 6 Explanation: p = 2, and x = 6. So, 6 is inserted after p, i.e, at position 3 (0-based indexing). Example 2:
Input: LinkedList: 1234 p = 0, x = 44 Output: 1 44 2 3 4 Explanation: p = 0, and x = 44 . So, 44 is inserted after p, i.e, at position 1 (0-based indexing). Your Task: The task is to complete the function addNode() which head reference, position and data to be inserted as the arguments, with no return type.
Expected Time Complexity : O(N)
Expected Auxilliary Space : O(1)
void addNode(Node *head, int pos, int data)
{
Node* new_node=new Node(data);
Node* temp=head;
if(pos==0){
new_node->next=head;
new_node->prev=NULL;
if(head->prev != NULL){
head->prev=new_node;
}
head=new_node;
}
for(int i=1;i(=pos;i++){
temp=temp->next;
}
new_node->next=temp->next;
temp->next=new_node;
new_node->prev=temp;
if(new_node->next != NULL){
new_node->next->prev=new_node;
}
}
Given a sorted doubly linked list and an element X, your need to insert the element X into correct position in the sorted DLL.
Example:
Input:
LinkedList:
X = 9
Output:
Your Task:
You only need to complete the function sortedInsert() that takes head reference and x as arguments and returns the head of the modified list. The printing and checking tasks are done by the driver code.
Expected Time Complexity: O(n).
Expected Auxiliary Space: O(1).
Constraints:
1 <= Number of nodes <= 103
Node* sortedInsert(Node * head, int x)
{
struct Node* current;
if (head == NULL)
head = getNode(x);
else if ((head)->data >= x) {
Node *newNode=getNode(x);
newNode->next = head;
newNode->next->prev = newNode;
head = newNode;
}
else {
current = head;
while (current->next != NULL && current->next->data ( x)
current = current->next;
Node *newNode=getNode(x); newNode->next = current->next; if (current->next != NULL) newNode->next->prev = newNode; current->next = newNode; newNode->prev = current; }
return head; }
Given a doubly linked list and a position. The task is to delete a node from given position in a doubly linked list.
Example 1:
Input: LinkedList = 1 3 4 x = 3 Output: 1 3 Explanation: After deleting the node at position 3 (position starts from 1), the linked list will be now as 1->3. Example 2:
Input: LinkedList = 1 5 2 9 x = 1 Output: 5 2 9 Your Task: The task is to complete the function deleteNode() which should delete the node at given position and return the head of the linkedlist.
Expected Time Complexity : O(N)
Expected Auxilliary Space : O(1)
class Solution
{
public:
Node* deleteNode(struct Node *head_ref,int x)
{
struct Node *del = head_ref;
x = x-1;
while(x--)
del = del->next;
/* base case */
if(head_ref == NULL || del == NULL)
return NULL;
/* If Node to be deleted is head Node */
if(head_ref == del)
head_ref = del->next;
/* Change next only if Node to be deleted is NOT the last Node */
if(del->next != NULL)
del->next->prev = del->prev;
/* Change prev only if Node to be deleted is NOT the first Node */
if(del->prev != NULL)
del->prev->next = del->next;
/* Finally, free the memory occupied by del*/
free(del);
return head_ref;
}
};
Given a circular doubly linked list consisting of N nodes, the task is to print the elements from head to tail, then from tail to head in two separate lines.
The tail of a circular doubly linked list is connected to head via its next pointer, and the previous pointer of head is connected to the tail.
Example 1:
Input: LinkedList: 12 (the last and first node are connected, i.e. 21) Output: 1 2 2 1 Example 2:
Input: LinkedList: 257899100 Output: 2 5 7 8 99 100 100 99 8 7 5 2 Your Task: The task is to complete the function displayList() which takes head reference as an argument and return the the circular doubly linked list as a list. Note: The returned list is printed twice, once forward and once backward.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).
vector displayList(Node *head)
{
vector vec;
Node* curr = head;
while(curr->next != head) {
vec.push_back(curr->data);
curr = curr->next;
}
vec.push_back(curr->data);
return vec;
}Given a doubly linked list, the task is to check if it is circular or not.
Example 1:
Input:
LinkedList: 23456
Output: 0
Example 2:
Input:
LinkedList: 46
(the last and the first node is connected,
i.e. 6 4
Output: 1
User Task:
The task is to complete the function isCircular() which takes head reference as an argument. The function should return true if the doubly LL is circular and false if it is not. (if the returned value if true, the driver code prints 1, otherwise 0)
Expected Time Complexity: O(n).
Expected Auxiliary Space: O(1).
class Solution{
public:
bool isCircular(Node * head)
{
if(head==NULL) return NULL;
if(head->prev!=NULL) {return true;}
return false;
}
};Given two circular doubly linked lists of sizes n1 and n2 respectively, the task is check if the corresponding elements of the lists are same or not.
The tail of a circular doubly linked list is connected to head via its next pointer, and the previous pointer of head is connected to the tail.
Example 1:
Input: LinkedList1: 1 LinkedList2: 1 Output: 1 Example 2:
Input: LinkedList1: 257899100 LinkedList2: 789732 Output: 0 Your Task: The task is to complete the function compareCLL() which takes head1 and head2 references as an arguments. The function should return true if all the corresponding elements of the lists are same, else it should return false. (The driver's code print 1 if the returned value is true, otherwise false.)
Expected Time Complexity: O(n1 + n2).
Expected Auxiliary Space: O(1).
class Solution{
public:
bool compareCLL(Node* head1, Node* head2) {
if (head1->data==head2->data) return true;
else return false;
Node* first = head1;
Node* sec = head2;
while (first != head1 and sec != head2) {
if (first->data != sec->data) return false;
first = first->next;
sec = sec->next;
}
if ((first==NULL and sec != NULL) or (first != NULL and sec == NULL)) return false;
return true;
} };
Given a circular doubly linked list of odd size n, the task is to print the middle element.
The tail of a circular doubly linked list is connected to head via its next pointer, and the previous pointer of head is connected to the tail.
Example 1:
Input:
LinkedList: 123
(The first and the last node is connected,
i.e 3 1)
Output: 2
Your Task:
The task is to complete the function findMiddle() which takes head reference as an argument. The function should return the middle element of CDLL.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
class Solution{
public:
int findMiddle(Node * head)
{
int count = 0;
Node* curr = head;
while (curr->next != head) {
curr = curr->next;
count++;
}
int mid = count/2;
curr = head;
for (int i=0; inext;
}
return curr->data;
}
};Definition of double linked list
Similar to Singly Linked Lists, Doubly Linked Lists are also a sequential data structure with the only difference that the doubly linked lists contain two pointers instead of one to store the address of both next node and previous node respectively.
Each node contains two pointers, one pointing to the next node and the other pointing to the previous node.
The prev of Head node is NULL, as there is no previous node of Head.
The next of last node is NULL, as there is no node after the last node.
