C++ Programming ONLY; I need two functions written below, please fill in only th
ID: 3742862 • Letter: C
Question
C++ Programming ONLY;
I need two functions written below, please fill in only the TODO area.
Guidelines for the two functions are:
1.
Write a function InsertNth() which can insert a new node at any index within the list. The index should in the range [0...length] (but its not garanteed), and the new node should be inserted so as to be at that index.
For example: The linked list looks like this: 1 -> 3 InsertNth(1, 2) will insert 2 into the 1st index The result looks like this: 1 -> 2 -> 3
Keep note:
If the requested index is out of bounds, do nothing
Do not mess with function declaration
Only code within the InsertNth function
and
2.
Write a RemoveDuplicates() function which deletes any duplicate nodes from the list. Ideally, the list should only be traversed once. Code only assesed on ascending order.
Keep Note:
Assume list is sorted like the examples above
Make sure you consider this case 1 -> 1 -> 1 -> 1
Do not mess with the function declaration
Only code within the RemoveDuplicates function
For example:
This one:
8 -> 9 -> 10 -> 11
8 -> 8 -> 9 -> 9
8 -> 8 -> 10 -> 42
empty
to
8 -> 9 -> 10 -> 11
8 -> 9
8 -> 10 -> 42
empty
HERE IS THE CODE GIVEN:
class Node {
public:
Node* next;
int data;
};
class LinkedList {
public:
LinkedList();
~LinkedList();
void add(int data);
void InsertNth(int index, int data);
void RemoveDuplicates();
Node* head;
};
LinkedList::LinkedList() {
this->head = nullptr;
}
LinkedList::~LinkedList() {
while(head != nullptr) {
Node* temp = head->next;
delete head;
head = temp;
}
}
void LinkedList::add(int data) {
Node* node = new Node();
node->data = data;
node->next = this->head;
this->head = node;
}
void LinkedList::InsertNth(int index, int data) {
//TODO ONLY FILL IN HERE
}
void LinkedList::RemoveDuplicates() {
//TODO ONLY FILL HERE
}
AND HERE IS THE MAKEFILE WITH TESTS:
CC = g++
CPPFLAGS = -g -Wall -std=c++11
BIN_DIR = bin
GTEST_LL = -I /usr/include/gtest/ -l gtest -l gtest_main -pthread
all: $(BIN_DIR) $(BIN_DIR)/DestructorTest $(BIN_DIR)/InsertNthTest $(BIN_DIR)/RemoveDuplicatesTest
valgrind --leak-check=yes ./$(BIN_DIR)/DestructorTest
valgrind --leak-check=yes ./$(BIN_DIR)/InsertNthTest
valgrind --leak-check=yes ./$(BIN_DIR)/RemoveDuplicatesTest
$(BIN_DIR)/DestructorTest: $(BIN_DIR)/LinkedList.o
$(CC) $(CPPFLAGS) $(BIN_DIR)/DestructorTest.o $^ $(GTEST_LL) -o $@
$(BIN_DIR)/InsertNthTest: $(BIN_DIR)/LinkedList.o
$(CC) $(CPPFLAGS) $(BIN_DIR)/InsertNthTest.o $^ $(GTEST_LL) -o $@
$(BIN_DIR)/RemoveDuplicatesTest: $(BIN_DIR)/LinkedList.o
$(CC) $(CPPFLAGS) $(BIN_DIR)/RemoveDuplicatesTest.o $^ $(GTEST_LL) -o $@
$(BIN_DIR)/LinkedList.o: LinkedList.cpp
$(CC) $(CPPFLAGS) -c $< -o $@
$(BIN_DIR):
mkdir $(BIN_DIR)
.phony: clean test
clean:
-@rm -rf $(BIN_DIR)
DestructorTest: $(BIN_DIR) $(BIN_DIR)/DestructorTest
valgrind --leak-check=yes ./$(BIN_DIR)/DestructorTest
InsertNthTest: $(BIN_DIR) $(BIN_DIR)/InsertNthTest
valgrind --leak-check=yes ./$(BIN_DIR)/InsertNthTest
RemoveDuplicatesTest: $(BIN_DIR) $(BIN_DIR)/RemoveDuplicatesTest
valgrind --leak-check=yes ./$(BIN_DIR)/RemoveDuplicatesTest
Explanation / Answer
Written BOTH THE FUNCTION
#include <iostream>
class Node {
public:
Node* next;
int data;
};
class LinkedList {
public:
LinkedList();
~LinkedList();
void add(int data);
void InsertNth(int index, int data);
void RemoveDuplicates();
Node* head;
};
LinkedList::LinkedList() {
this->head = nullptr;
}
LinkedList::~LinkedList() {
while(head != nullptr) {
Node* temp = head->next;
delete head;
head = temp;
}
}
void LinkedList::add(int data) {
Node* node = new Node();
node->data = data;
node->next = this->head;
this->head = node;
}
void LinkedList::InsertNth(int index, int data) {
//TODO ONLY FILL IN HERE
int size = 0;
Node* curr = head;
while(curr != nullptr) {
curr = curr->next;
++size;
}
if(index < 0 || index >size)
return;
if(index == 0){
Node* node = new Node();
node->data = data;
node->next = this->head;
this->head = node;
}else{
int i;
Node* a = head;
for(i = 1; i < index; i++)
a = a->next;
Node* tmp = new Node();
tmp->data = data;
tmp->next = a->next;
a->next = tmp;
}
}
void LinkedList::RemoveDuplicates() {
Node* current = head;
Node* next_next;
if (current == NULL)
return;
while (current->next != nullptr)
{
if (current->data == current->next->data)
{
next_next = current->next->next;
free(current->next);
current->next = next_next;
}
else
{
current = current->next;
}
}
}
===============
PLEASE UPVOTE if helpful
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.