Write a LinkedList member function called duplicateValue that will duplicate a v
ID: 3910070 • Letter: W
Question
Write a LinkedList member function called duplicateValue that will duplicate a value in a singly linked list of integers by inserting a new node next to the node with that value. You may insert the node before or after the node with the given value; make your decision based on which is easier to implement. The function will return true if it is successful at duplicating the value. If the value does not exist, the function will return false. For simplicity, the function will only duplicate the value the first time it encounters the value.
Here is a minimal prototype for the LinkedList:
This example output:
Explanation / Answer
main.cpp
#include <iostream>
using namespace std;
typedef struct Node{
int data;
Node *next;
}Node;
class LinkedList {
private:
Node* head;
Node* tail;
public:
LinkedList();
void addTail(int data);
bool duplicateValue(int value);
void display();
};
LinkedList::LinkedList()
{
head = NULL;
tail = NULL;
}
void LinkedList::addTail(int data)
{
Node *current;
Node *node = new Node;
node->data = data;
node->next = NULL;
//if head is in null make the newly created node as head
if (head == NULL)
{
head = node;
tail = node;
}
else
{ //set the current to tail, make the newly created node as current's next node
current = tail;
//Add item to the tail of the linked list
current->next = node;
tail = node;
}
}
//duplicateValue function searches for the given value in LinkedList and if found inserts a new node
//after the node with the given value in the LinkedList. If the given value is not found the function returns a FALSE
bool LinkedList::duplicateValue(int value)
{
Node *current = head, *temp; // Initialize current
//iterative through the LinkedList until the given value is found or the search reaches the end of the list
while (current != NULL)
{
if (current->data == value) //if the given value is found
{
Node *node = new Node; // create a new node with the given value
node->data = value;
node->next = NULL; //make the next pointer of newly created node to NULL
//if the current node is tail(last) node, then make the newly created node as tail
//so that when the new node is added after the current node which is tail, the new node will be tail node
if(current == tail)
tail = node;
temp = current->next; //temp will point to next node of current node with given value
current->next = node; //next node of current node with given value will be the newly created node
node->next = temp; //next node of newly created node will the old next node of current node with given value
return true;
}
current = current->next;
}
return false;
}
//display function to display the linked list
void LinkedList::display()
{
Node *current;
current = head; // make the current to point to head node
cout<<"Head node is: "<<head->data<<endl;
//Display each node's data iteratively until it reaches the null
while(current != NULL)
{
cout<<current->data<<" ";
current = current->next; //after displaying the current node's data move to next node
}
cout<<" Tail node is: "<<tail->data<<endl;
}
int main()
{
LinkedList ll;
ll.addTail(-5);
ll.addTail(30);
ll.addTail(20);
ll.addTail(10);
ll.display();
cout<<" duplicating 10 (should change the list) ";
bool isDuplicated = ll.duplicateValue(10);
ll.display();
cout<<" duplicating 0 (should not change the list) ";
isDuplicated = ll.duplicateValue(0);
ll.display();
cout<<" duplicating -5 (should change the list) ";
isDuplicated = ll.duplicateValue(-5);
ll.display();
cout<<" duplicating 20 (should change the list) ";
isDuplicated = ll.duplicateValue(20);
ll.display();
return 0;
}
Output:
Head node is: -5
-5 30 20 10
Tail node is: 10
duplicating 10 (should change the list)
Head node is: -5
-5 30 20 10 10
Tail node is: 10
duplicating 0 (should not change the list)
Head node is: -5
-5 30 20 10 10
Tail node is: 10
duplicating -5 (should change the list)
Head node is: -5
-5 -5 30 20 10 10
Tail node is: 10
duplicating 20 (should change the list)
Head node is: -5
-5 -5 30 20 20 10 10
Tail node is: 10
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.