C++ PROGRAMMING ONLY: I need two functions written so they pass the tests in the

Question

C++ PROGRAMMING ONLY:

I need two functions written so they pass the tests in the makefile, also given. Guidelines also given for the two functions. I couldn't figure out the two.

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

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:

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
}

void LinkedList::RemoveDuplicates() {
//TODO
}

HERE IS THE MAKEFILE :

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

//LinkedList.h

#pragma once

class Node {

public:

Node * next;

int data;

};

class LinkedList {

public:

LinkedList();

~LinkedList();

void add(int data);

void InsertNth(int index, int data);

void RemoveDuplicates();

//added by cheggEA to print nodes , which is required to see the results

void print();

Node* head;

};

--------------------------------------------------

//LinkedList.cpp

#include "Sep_3_linkedList.h"

#include<iostream>

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

Node *cur = head, *prev = NULL,*newNode,*next;

//allocate newNode and populate node with data given

newNode = new Node;

newNode->data = data;

newNode->next = NULL;

int count = 0;

/*if (cur->next == NULL || cur == NULL)

{

if (index < count)

{

std::cout << "You can't insert at given index" << endl;

return;

}

}*/

//insert at head

if (count == index)

{

next = head;

head = newNode;

newNode->next = next;

return;

}

while (cur->next!= NULL && count !=index)

{

prev = cur;

++count;

cur = cur->next;

}

//insert after last node

if (cur == NULL && index == count+1)

{

cur->next = newNode;

return;

}

if (index > count + 1)

{

std::cout << " Can't insert at this position ";

return;

}

prev->next = newNode;

newNode->next = cur;

}

void LinkedList::RemoveDuplicates() {

Node *cur1 = head,*cur2=NULL;

int count =0 , tmpData,swapped = 0;

//first count the node

while (cur1 != NULL)

{

++count;

cur1 = cur1->next;

}

//TODO

do

{

swapped = 0;

cur1 = head;

while (cur1->next != cur2)

{

if(cur1!=NULL)

if (cur1->data > cur1->next->data)

{

tmpData= cur1->data;

cur1->data = cur1->next->data;

cur1->next->data = tmpData;

swapped = 1;

}

cur1 = cur1->next;

}

cur2 = cur1;

} while (swapped);

//now remove duplicates

Node *tmp;

print();

cur1 = head;

for (int i = 0; i < count; i++)

{

if (cur1->next != NULL)

{

if (cur1->data == cur1->next->data)

{

tmp = cur1->next;

cur1->next = cur1->next->next;

delete tmp;

}

cur1 = cur1->next;

}

else

break;

}

}

void LinkedList::print()

{

Node *cur = head;

std::cout << " Linked list is: ";

while (cur != NULL)

{

std::cout << cur->data << " ";

cur = cur->next;

}

}

--------------------------------------

#include<iostream>

#include "Sep_3_linkedList.h"

using namespace std;

int main()

{

LinkedList list;

list.add(8);

list.add(9);

list.add(11);

list.add(10);

//list.add(8);

list.add(9);

list.print();

list.InsertNth(0, 42);

//after insert 8 at index 0

list.print();

list.InsertNth(2, 12);

//after insert 12 at index 2

list.print();

list.InsertNth(8, 45);

//after insert 45 at index 8

list.print();

list.InsertNth(7, 45);

//after insert 8 at index 0

list.print();

list.InsertNth(8, 8);

list.print();

//remove duplicates

list.RemoveDuplicates();

cout << " Print after removing duplicates: ";

list.print();

}

/*output

Linked list is: 9 10 11 9 8

Linked list is: 42 9 10 11 9 8

Linked list is: 42 9 12 10 11 9 8

Can't insert at this position

Linked list is: 42 9 12 10 11 9 8

Linked list is: 42 9 12 10 11 9 45 8

Linked list is: 42 9 12 10 11 9 45 8 8

Linked list is: 8 8 9 9 10 11 12 42 45

Print after removing duplicates:

Linked list is: 8 9 10 11 12 42 45

*/

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.