In C++ Covert the following program (Singly linked list) into a doubly linked list and explain: #include using namespace std; // Create node which consists of data and pointer of next node class Node { public: int data; Node *next; }; // Create a class LinkedList class LinkedList { private: Node *head; Node *tail; // declare all the methods as public public: LinkedList() { head = nullptr; tail = nullptr; } // Method to append a new node at the end void append(int value) { // Allocate node Node *newNode = new Node; // push the data into node newNode->data = value; // make next of new node is NULL newNode->next = nullptr; // if linked list is empty then make new node as head and tail both if (head == nullptr) { head = newNode; tail = newNode; } // if linkedlist is not empty, add the newNode to tail else { tail->next = newNode; // Update the tail to new last node tail = newNode; } } // Method to print data inside the list void display(std::ostream &out) { Node *current = head; // Traverse the list till last node and print data of each node while (current != nullptr) { out << current->data << " "; current = current->next; } out << std::endl; } // method to display the linked list in reverse order using stack void tailDisplay(std::ostream &out) { // create a stack st stack st; // store head node in current pointer Node *current = head; // traverse on linked list and store the value in stack "st" while (current != nullptr) { // push value in stack st.push(current->data); current = current->next; } // print the top of the stack and delete the top using pop, till statck becomes empty while (st.empty() == false) { out << st.top() << " "; st.pop(); } out << std::endl; } // method to delete the tail node , if the given value is equal to the data in tail node void tailRemove(int value) { // current pointer stores address of the head node Node *current = head; // here we traverse on linked list, till the current pointer reaches the second last node while (current->next->next != NULL) { current = current->next; } // if the data in last node matches with the given value then delete last node if (current->next->data == value) { // store the last node in "toDelete" pointer Node *toDelete = current->next; // make the current node as last node current->next = NULL; // update the tail pointer tail = current; // delete the node stored in "toDelete" pointer delete toDelete; } } // method to delete the node void remove(int value) { Node *previous = nullptr; // store the head in current Node *current = head; // traverse the current on linked list while (current != nullptr) { // if the data to current node is equal to the given value then delete that node if (current->data == value) { // if the current node is head itself, the update the head pointer and delete the current node if (previous == nullptr) { head = current->next; delete current; current = head; } // if current node is not head node else { // update the next of previous node to the next of current node previous->next = current->next; // delete the current node delete current; current = previous->next; } // since we need to delete only first one occurence of the the given value // so we will break the while loop break; } // if the value is not matched with the current node then move the current node to the next node // and also update the previous pointer else { previous = current; current = current->next; } } } // method to append a new node at front void prepend(int value) { // allocate node Node *newNode = new Node; // push the data into node newNode->data = value; // push the data into node newNode->next = head; head = newNode; } }; int main() { LinkedList LL; LL.append(5); LL.append(33); LL.append(1); LL.append(7); LL.append(33); LL.append(12); LL.display(cout); LL.remove(33); LL.display(cout); LL.prepend(12); LL.display(cout); LL.remove(13); LL.display(cout); LL.tailDisplay(cout); LL.tailRemove(12); LL.display(cout); return 0; }
In C++ Covert the following program (Singly linked list) into a doubly linked list and explain:
#include <bits/stdc++.h>
using namespace std;
// Create node which consists of data and pointer of next node
class Node
{
public:
int data;
Node *next;
};
// Create a class LinkedList
class LinkedList
{
private:
Node *head;
Node *tail;
// declare all the methods as public
public:
LinkedList()
{
head = nullptr;
tail = nullptr;
}
// Method to append a new node at the end
void append(int value)
{
// Allocate node
Node *newNode = new Node;
// push the data into node
newNode->data = value;
// make next of new node is NULL
newNode->next = nullptr;
// if linked list is empty then make new node as head and tail both
if (head == nullptr)
{
head = newNode;
tail = newNode;
}
// if linkedlist is not empty, add the newNode to tail
else
{
tail->next = newNode;
// Update the tail to new last node
tail = newNode;
}
}
// Method to print data inside the list
void display(std::ostream &out)
{
Node *current = head;
// Traverse the list till last node and print data of each node
while (current != nullptr)
{
out << current->data << " ";
current = current->next;
}
out << std::endl;
}
// method to display the linked list in reverse order using stack
void tailDisplay(std::ostream &out)
{
// create a stack st
stack<int> st;
// store head node in current pointer
Node *current = head;
// traverse on linked list and store the value in stack "st"
while (current != nullptr)
{
// push value in stack
st.push(current->data);
current = current->next;
}
// print the top of the stack and delete the top using pop, till statck becomes empty
while (st.empty() == false)
{
out << st.top() << " ";
st.pop();
}
out << std::endl;
}
// method to delete the tail node , if the given value is equal to the data in tail node
void tailRemove(int value)
{
// current pointer stores address of the head node
Node *current = head;
// here we traverse on linked list, till the current pointer reaches the second last node
while (current->next->next != NULL)
{
current = current->next;
}
// if the data in last node matches with the given value then delete last node
if (current->next->data == value)
{
// store the last node in "toDelete" pointer
Node *toDelete = current->next;
// make the current node as last node
current->next = NULL;
// update the tail pointer
tail = current;
// delete the node stored in "toDelete" pointer
delete toDelete;
}
}
// method to delete the node
void remove(int value)
{
Node *previous = nullptr;
// store the head in current
Node *current = head;
// traverse the current on linked list
while (current != nullptr)
{
// if the data to current node is equal to the given value then delete that node
if (current->data == value)
{
// if the current node is head itself, the update the head pointer and delete the current node
if (previous == nullptr)
{
head = current->next;
delete current;
current = head;
}
// if current node is not head node
else
{
// update the next of previous node to the next of current node
previous->next = current->next;
// delete the current node
delete current;
current = previous->next;
}
// since we need to delete only first one occurence of the the given value
// so we will break the while loop
break;
}
// if the value is not matched with the current node then move the current node to the next node
// and also update the previous pointer
else
{
previous = current;
current = current->next;
}
}
}
// method to append a new node at front
void prepend(int value)
{
// allocate node
Node *newNode = new Node;
// push the data into node
newNode->data = value;
// push the data into node
newNode->next = head;
head = newNode;
}
};
int main()
{
LinkedList LL;
LL.append(5);
LL.append(33);
LL.append(1);
LL.append(7);
LL.append(33);
LL.append(12);
LL.display(cout);
LL.remove(33);
LL.display(cout);
LL.prepend(12);
LL.display(cout);
LL.remove(13);
LL.display(cout);
LL.tailDisplay(cout);
LL.tailRemove(12);
LL.display(cout);
return 0;
}
Trending now
This is a popular solution!
Step by step
Solved in 5 steps with 1 images
