Program to create and display a singly linked list
Code:
#include <bits/stdc++.h>
using namespace std;
struct Node
{
int val;
struct Node *next;
};
void printList(Node *head)
{
while (head != NULL)
{
cout << head->val << " ";
head = head->next;
}
cout << endl;
}
void addNode(Node **head, int value)
{
Node *new_node = new Node();
Node *last = (*head);
new_node->val = value;
new_node->next = nullptr;
if ((*head) == nullptr)
{
(*head) = new_node;
return;
}
while (last->next != nullptr)
{
last = last->next;
}
last->next = new_node;
}
int main()
{
int n = 10;
Node* head =nullptr;
addNode(&head,7 );
addNode(&head,8 );
addNode(&head,6 );
printList(head);
}
Output:
7 8 6
Program to create a singly linked list of n nodes and count the number of nodes
Code:
#include <bits/stdc++.h>
using namespace std;
struct Node
{
int val;
struct Node *next;
};
void countNodes(Node *head)
{
int count = 0;
while (head != NULL)count++,head = head->next;
cout <<"Number of nodes are: "<<count<<endl;
}
void insertEnd(Node **head, int value){
Node * new_node = new Node();
Node * last = (*head);
new_node->val = value;
new_node->next= nullptr;
if((*head)==nullptr){
(*head)=new_node;
return;
}
while (last->next!=nullptr){
last = last->next;
}
last->next = new_node;
}
void deleteDuplicates(Node * head){
for(Node* i = head; i != nullptr and i->next!=nullptr;i=i->next){
Node*j = i;
while(j->next != nullptr){
if(i->val == j->next->val){
Node * temp = j->next;
j->next = j->next->next;
delete temp;
}
else {
j=j->next;
}
}
}
}
void swap(struct Node *a, struct Node *b)
{
int temp = a->val;
a->val = b->val;
b->val = temp;
}
void sortLinkedList(Node *start) {
if (start == NULL)
return;
bool swapped;
Node *i,*j = NULL;
do{
swapped = 0;
i = start;
while (i->next != j){
if (i->val > i->next->val){
swap(i, i->next);
swapped = true;
}
i = i->next;
}
j = i;
}
while (swapped);
}
int main()
{
int n = 10;
Node* head =nullptr;
insertEnd(&head,7 );
insertEnd(&head,8 );
insertEnd(&head,1 );
insertEnd(&head,2 );
insertEnd(&head,-1 );
sortLinkedList(head);
countNodes(head);
}
Output:
Number of nodes are: 5
Program to create a singly linked list of n nodes and display it in reverse order
Code:
#include <bits/stdc++.h>
using namespace std;
struct Node
{
int val;
struct Node *next;
};
void printList(Node *head)
{
while (head != NULL)
{
cout << head->val << " ";
head = head->next;
}
cout << endl;
}
void addNode(Node **head, int value)
{
Node *new_node = new Node();
Node *last = (*head);
new_node->val = value;
new_node->next = nullptr;
if ((*head) == nullptr)
{
(*head) = new_node;
return;
}
while (last->next != nullptr)
{
last = last->next;
}
last->next = new_node;
}
void printReverse(Node* head){
if(head==nullptr)return;
printReverse(head->next);
if(head!=nullptr){
cout<<head->val<<" ";
}
cout<<endl;
}
int main()
{
int n = 10;
Node* head =nullptr;
addNode(&head,7 );
addNode(&head,8 );
addNode(&head,6 );
cout<<"Elements in Linked List: ";
printList(head);
cout<<"Element Reversed:\n";
printReverse(head);
}
Output:
Elements in Linked List: 7 8 6 Element Reversed: 6 8 7
Program to delete a new node from the beginning of the singly linked list
Code:
#include <bits/stdc++.h>
using namespace std;
struct Node
{
int val;
struct Node *next;
};
void printList(Node *head)
{
while (head != NULL)
{
cout << head->val << " ";
head = head->next;
}
cout << endl;
}
void addNode(Node **head, int value)
{
Node *new_node = new Node();
Node *last = (*head);
new_node->val = value;
new_node->next = nullptr;
if ((*head) == nullptr)
{
(*head) = new_node;
return;
}
while (last->next != nullptr)
{
last = last->next;
}
last->next = new_node;
}
void deleteNode(Node **head, int value){
Node* temp = *head;
Node* prev = nullptr;
if(temp!=nullptr and temp->val == value){
(*head) = temp->next;
delete temp;
return;
}
while(temp!=nullptr and temp->val != value){
prev = temp;
temp = temp->next;
}
if(temp == nullptr)return;
prev->next = temp->next;
delete temp;
}
int main()
{
int n = 10;
Node* head =nullptr;
addNode(&head,7 );
addNode(&head,8 );
addNode(&head,6 );
deleteNode(&head,7 );
cout<<"Elements left:\n";
printList(head);
}
Output:
Elements left: 8 6
Program to delete a new node from the middle of the singly linked list
Code:
#include <bits/stdc++.h>
using namespace std;
struct Node
{
int val;
struct Node *next;
};
void printList(Node *head)
{
while (head != NULL)
{
cout << head->val << " ";
head = head->next;
}
cout << endl;
}
void addNode(Node **head, int value)
{
Node *new_node = new Node();
Node *last = (*head);
new_node->val = value;
new_node->next = nullptr;
if ((*head) == nullptr)
{
(*head) = new_node;
return;
}
while (last->next != nullptr)
{
last = last->next;
}
last->next = new_node;
}
void deleteNode(Node **head, int value){
Node* temp = *head;
Node* prev = nullptr;
if(temp!=nullptr and temp->val == value){
(*head) = temp->next;
delete temp;
return;
}
while(temp!=nullptr and temp->val != value){
prev = temp;
temp = temp->next;
}
if(temp == nullptr)return;
prev->next = temp->next;
delete temp;
}
int main()
{
int n = 10;
Node* head =nullptr;
addNode(&head,7 );
addNode(&head,8 );
addNode(&head,6 );
deleteNode(&head,8 );
cout<<"Elements left:\n";
printList(head);
}
Output:
Elements left: 7 6
Program to delete a node from the end of the singly linked list
Code:
#include <bits/stdc++.h>
using namespace std;
struct Node
{
int val;
struct Node *next;
};
void printList(Node *head)
{
while (head != NULL)
{
cout << head->val << " ";
head = head->next;
}
cout << endl;
}
void addNode(Node **head, int value)
{
Node *new_node = new Node();
Node *last = (*head);
new_node->val = value;
new_node->next = nullptr;
if ((*head) == nullptr)
{
(*head) = new_node;
return;
}
while (last->next != nullptr)
{
last = last->next;
}
last->next = new_node;
}
void deleteNode(Node **head, int value){
Node* temp = *head;
Node* prev = nullptr;
if(temp!=nullptr and temp->val == value){
(*head) = temp->next;
delete temp;
return;
}
while(temp!=nullptr and temp->val != value){
prev = temp;
temp = temp->next;
}
if(temp == nullptr)return;
prev->next = temp->next;
delete temp;
}
int main()
{
int n = 10;
Node* head =nullptr;
addNode(&head,7 );
addNode(&head,8 );
addNode(&head,6 );
deleteNode(&head,6 );
cout<<"Elements left:\n";
printList(head);
}
Output:
Elements left: 7 8
Program to determine whether a singly linked list is the palindrome
Code:
#include <bits/stdc++.h>
using namespace std;
struct Node
{
int val;
struct Node *next;
};
void printList(Node *head)
{
while (head != NULL)
{
cout << head->val << " ";
head = head->next;
}
cout << endl;
}
void addNode(Node **head, int value)
{
Node *new_node = new Node();
Node *last = (*head);
new_node->val = value;
new_node->next = nullptr;
if ((*head) == nullptr)
{
(*head) = new_node;
return;
}
while (last->next != nullptr)
{
last = last->next;
}
last->next = new_node;
}
bool palindrome(Node *head){
Node* temp = head;
stack<int>st;
while(temp!=nullptr){
st.push(temp->val);
temp = temp->next;
}
while(head!=nullptr){
int top_element = st.top();
st.pop();
if(head->val != top_element)return false;
head=head->next;
}
return true;
}
int main()
{
int n = 10;
Node* head =nullptr;
addNode(&head,7);
addNode(&head,8);
addNode(&head,7);
printList(head);
if(palindrome(head)){
cout<<"It is palindrome."<<endl;
}
else cout<<"It is not a palindrome."<<endl;
}
Output:
7 8 7 It is palindrome.
Program to find the maximum and minimum value node from a singly linked list
Code:
#include <bits/stdc++.h>
using namespace std;
struct Node
{
int val;
struct Node *next;
};
void printList(Node *head)
{
while (head != NULL)
{
cout << head->val << " ";
head = head->next;
}
cout << endl;
}
void addNode(Node **head, int value)
{
Node *new_node = new Node();
Node *last = (*head);
new_node->val = value;
new_node->next = nullptr;
if ((*head) == nullptr)
{
(*head) = new_node;
return;
}
while (last->next != nullptr)
{
last = last->next;
}
last->next = new_node;
}
void findMinMax(Node* head){
int mn = numeric_limits<int>::max();
int mx = numeric_limits<int>::min();
while(head != NULL){
mn = min(head->val,mn);
mx = max(head->val,mx);
head = head->next;
}
cout<<"Minimum element is "<<mn<<endl;
cout<<"Maximum element is "<<mx<<endl;
}
bool palindrome(Node *head){
Node* temp = head;
stack<int>st;
while(temp!=nullptr){
st.push(temp->val);
temp = temp->next;
}
while(head!=nullptr){
int top_element = st.top();
st.pop();
if(head->val != top_element)return false;
head=head->next;
}
return true;
}
int main()
{
int n = 10;
Node* head =nullptr;
addNode(&head,7 );
addNode(&head,8 );
addNode(&head,9 );
printList(head);
findMinMax(head);
}
Output:
7 8 9 Minimum element is 7 Maximum element is 9
Program to insert a new node at the middle of the singly linked list
Code:
#include <bits/stdc++.h>
using namespace std;
struct Node
{
int val;
struct Node *next;
};
void printList(Node *head)
{
while (head != NULL)
{
cout << head->val << " ";
head = head->next;
}
cout << endl;
}
void insertFront(Node** head,int value) {
struct Node* new_node = new Node();
new_node->val = value;
new_node->next =(*head);
(*head) = new_node;
}
void insertEnd(Node **head, int value){
Node * new_node = new Node();
Node * last = (*head);
new_node->val = value;
new_node->next= nullptr;
if((*head)==nullptr){
(*head)=new_node;
return;
}
while (last->next!=nullptr){
last = last->next;
}
last->next = new_node;
}
void insertMiddle(Node ** head, int value){
if((*head)==nullptr){
insertFront(head,value);
return;
}
Node * new_node = new Node();
new_node->val = value;
new_node->next = nullptr;
Node * temp = (*head);
int len = 0;
while(temp!=nullptr)len++,temp=temp->next;
int count =(len-1)/2;
temp = (*head);
while(count--)temp=temp->next;
new_node->next = temp->next;
temp->next=new_node;
}
int main()
{
int n = 10;
Node* head =nullptr;
insertMiddle(&head,7 );
insertMiddle(&head,8 );
insertMiddle(&head,9 );
cout<<"Node inserted in the middle: ";
printList(head);
}
Output:
Node inserted in the middle: 7 9 8
Program to remove duplicate elements from a singly linked list
Code:
#include <bits/stdc++.h>
using namespace std;
struct Node
{
int val;
struct Node *next;
};
void printList(Node *head)
{
while (head != NULL)
{
cout << head->val << " ";
head = head->next;
}
cout << endl;
}
void insertEnd(Node **head, int value){
Node * new_node = new Node();
Node * last = (*head);
new_node->val = value;
new_node->next= nullptr;
if((*head)==nullptr){
(*head)=new_node;
return;
}
while (last->next!=nullptr){
last = last->next;
}
last->next = new_node;
}
void deleteDuplicates(Node * head){
for(Node* i = head; i != nullptr and i->next!=nullptr;i=i->next){
Node*j = i;
while(j->next != nullptr){
if(i->val == j->next->val){
Node * temp = j->next;
j->next = j->next->next;
delete temp;
}
else {
j=j->next;
}
}
}
}
int main()
{
int n = 10;
Node* head =nullptr;
insertEnd(&head,7 );
insertEnd(&head,8 );
insertEnd(&head,9 );
insertEnd(&head,9 );
insertEnd(&head,9 );
insertEnd(&head,9 );
cout<<"Original List: ";
printList(head);
cout<<"After deleting duplicate elements in the list:";
deleteDuplicates(head);
printList(head);
}
Output:
Original List: 7 8 9 9 9 9 After deleting duplicate elements in the list:7 8 9
Program to search an element in a singly linked list
Code:
#include <bits/stdc++.h>
using namespace std;
struct Node
{
int val;
struct Node *next;
};
void printList(Node *head)
{
while (head != NULL)
{
cout << head->val << " ";
head = head->next;
}
cout << endl;
}
void insertEnd(Node **head, int value){
Node * new_node = new Node();
Node * last = (*head);
new_node->val = value;
new_node->next= nullptr;
if((*head)==nullptr){
(*head)=new_node;
return;
}
while (last->next!=nullptr){
last = last->next;
}
last->next = new_node;
}
void deleteDuplicates(Node * head){
for(Node* i = head; i != nullptr and i->next!=nullptr;i=i->next){
Node*j = i;
while(j->next != nullptr){
if(i->val == j->next->val){
Node * temp = j->next;
j->next = j->next->next;
delete temp;
}
else {
j=j->next;
}
}
}
}
bool searchElement(Node* head,int target) {
while (head != NULL){
if(head->val == target){
return true;
}
head = head->next;
}
return false;
}
int main()
{
int n = 10;
Node* head =nullptr;
insertEnd(&head,7 );
insertEnd(&head,8 );
insertEnd(&head,9 );
insertEnd(&head,22 );
insertEnd(&head,53 );
insertEnd(&head,13 );
if(searchElement(head,53)){
cout<<"Element Found"<<endl;
}
else{
cout<<"Element Not Found"<<endl;
}
}
Output:
Element Found
Program to Convert a Given Binary Tree to Doubly Linked List
Code:
#include <bits/stdc++.h>
struct Node {
int data;
Node *left, *right;
};
Node* add_node(int data)
{
Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return node;
}
void BTreeToDLL(Node* root, Node*& head)
{
if (root == NULL)
return;
BTreeToDLL(root->right, head);
root->right = head;
if (head != NULL)
head->left = root;
head = root;
BTreeToDLL(root->left, head);
}
void display_list(Node* head)
{
printf("After converting Binary Tree to Doubly Linked List:\n");
while (head)
{
printf("%d ", head->data);
head = head->right;
}
}
int main()
{
Node* root = add_node(5);
root->left = add_node(3);
root->right = add_node(6);
root->left->left = add_node(1);
root->left->right = add_node(4);
root->right->right = add_node(8);
root->left->left->left = add_node(0);
root->left->left->right = add_node(2);
root->right->right->left = add_node(7);
root->right->right->right = add_node(9);
Node* head = NULL;
BTreeToDLL(root, head);
display_list(head);
return 0;
}
Output:
After converting Binary Tree to Doubly Linked List: 0 1 2 3 4 5 6 7 8 9
Program to Create a Circular Linked List of N Nodes and Count the Number of Nodes
Code:
#include <bits/stdc++.h>
using namespace std;
struct node {
int data;
struct node * next;
};
void createList(struct node **head, int n);
void displayList(struct node *head);
int count(struct node *head);
int main()
{
int n, choice;
struct node *head = NULL;
cout<<"Enter total node to create: ";
cin>>n;
createList(&head, n);
displayList(head);
cout<<"Total nodes are "<<count(head)<<"\n";
return 0;
}
int count(struct node *head)
{
int total = 0;
struct node *current = head;
do
{
current = current->next;
total++;
} while (current != head);
return total;
}
void createList(struct node **head, int n)
{
int i, data;
struct node *prevNode, *newNode;
prevNode = NULL;
newNode = NULL;
for(i=1; i<=n; i++)
{
newNode = (struct node *) malloc(sizeof(struct node));
cout<<"Enter value of "<<i<<" node: ";
cin>>data;
newNode->data = data;
newNode->next = NULL;
if (prevNode != NULL)
prevNode->next = newNode;
prevNode = newNode;
if (*head == NULL)
*head = newNode;
}
prevNode->next = *head;
cout<<"Circular Linked List Created.\n";
}
void displayList(struct node *head)
{
struct node *current;
int n = 1;
if(head == NULL)
{
cout<<"Empty list.\n";
return;
}
current = head;
cout<<"Elements in the list are:\n";
do
{
cout<<"Element "<<n++<<" = "<<current->data<<"\n";
current = current->next;
} while (current != head);
}
Output:
Enter total node to create: 4 Enter value of 1 node: 22 Enter value of 2 node: 54 Enter value of 3 node: 89 Enter value of 4 node: 64 Circular Linked List Created. Elements in the list are: Element 1 = 22 Element 2 = 54 Element 3 = 89 Element 4 = 64 Total nodes are 4
