Question

Project 1 - NodeList

write in c++ with 5 files:

main.cpp

List.h

List.cpp

ListNode.h

ListNode.cpp

Building upon the the ListNode/List code I would like you to extend the interface of a list to have these member functions as well.

struct ListNode {
  int element;
  ListNode *next;
}

1. Write a function to concatenate two linked lists. Given lists l1 = (2, 3, 1)and l2 = (4, 5), after return from l1.concatenate(l2)the list l1should be changed to be l1 = (2, 3, 1, 4, 5). Your function should not change l2and should not directly link nodes from l1to l2(i.e. the nodes inserted into l1should be copies of the nodes from l2.)

• Precondition: l1and 12are linked lists. The lists may be empty or non-empty.
• Postcondition: A copy of list l2is concatenated (added to the end) of list l1. List l2should be unchanged by the function. //
• NOTE:The nodes added to the list l1 must be copies of the nodes in list l2.

void concatenate(const List& l2);

2. Write a function to insert a number as the new ith node of a linked list. Nodes initially in positions i, i+1, ..., nshould be shifted to positions

• Precondition: The list may be empty or non-empty.
• Postcondition: The number value is inserted as the ith member of the list. If the list has fewer than i-1nodes in it, then value is inserted as the last node in the list.

void insertith(const int& value, const size_t& i);

3. Write a function to remove duplicate entries in a linked list. For example, given the list (5, 2, 2, 5, 3, 9, 2)as input, your function should change the list so that on return from the function it contains (5, 2, 3, 9).

• Precondition: The list may be empty or non-empty.
• Postcondition: Each node in the list must have a unique element value.

void removeDups();

The following appendfunction has been implemented and may be helpful for you!

void List::append( const int& data );

Sample testing driver code

int reserved_driver_main() {
    List l1;
    List l2;
    
    // test 1, insertith
    l1.insertith(1, 0);
    l1.insertith(5, 0);
    stringstream ss1;
    ss1 << l1;
    std::cout << ss1.str() << std::endl;
    if(ss1.str() == "5 -> 1 -> NULL (size: 2)"){
        std::cout << "1.1. insert ith successfully inserted; test passed" << std::endl; 
    } else {
        std::cout << "1.1. insert ith did not successfully insert; test failed" << std::endl; 
    }
    l1.makeEmpty();
    
    // test 2, remove dupes
    l1.insert(4);
    l1.insert(5);
    l1.insert(6);
    l1.insert(7);
    l1.remove(7);
    l1.insert(4);
    l1.insert(4);
    l1.insert(5);
    l1.removeDups();
    stringstream ss2;
    ss2 << l1;
    std::cout << ss2.str() << std::endl;
    if(ss2.str() == "5 -> 4 -> 6 -> NULL (size: 3)"){
        std::cout << "2.1. successfully removed duplicates; test passed" << std::endl; 
    } else {
        std::cout << "2.1. did not successfully remove duplicates; test failed" << std::endl; 
    }
    l1.makeEmpty();

    // test 3, concatenate
    l1.insert(7);
    l1.insert(6);
    l1.insert(5);
    l1.insert(4);
    l2.insert(11);
    l2.insert(10);
    l2.insert(9);
    l2.insert(8);
    l1.concatenate(l2);
    stringstream ss3;
    ss3 << l1;
    std::cout << ss3.str() << std::endl;
    if(ss3.str() == "4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> NULL (size: 8)"){
        std::cout << "3.1. successfully concatenated two lists; test passed" << std::endl; 
    } else {
        std::cout << "3.1. did not successfully concatenate two lists; test failed" << std::endl; 
    }
    l1.makeEmpty();
    l2.makeEmpty();
    
    // test 4, concatenate empty list
    l1.insert(4);
    l1.insert(5);
    l1.insert(6);
    l1.insert(7);
    l1.concatenate(l2);
    stringstream ss4;
    ss4 << l1;
    std::cout << ss4.str() << std::endl;
    if(ss4.str() == "7 -> 6 -> 5 -> 4 -> NULL (size: 4)"){
        std::cout << "4.1. successfully concatenated empty list; test passed" << std::endl; 
    } else {
        std::cout << "4.1. did not successfully concatenate empty list; test failed" << std::endl; 
    }
    l1.makeEmpty();
    
    return 0;
}

Answer 1

/*
* ListNode.h
*
* Created on: 26-Jul-2020
* Author:
*/

#ifndef LISTNODE_H_
#define LISTNODE_H_
#include <iostream>

struct ListNode {
   int element;
   ListNode *next;
public:
   /**
   * default constructor
   * set next to null
   * set element to value
   */
   ListNode(int value);

   /**
   * default destructor
   * free next node memory
   */
   virtual ~ListNode();
};

#endif /* LISTNODE_H_ */

/*
* ListNode.cpp
*
* Created on: 26-Jul-2020
* Author:
*/

#include "ListNode.h"

ListNode::ListNode(int value) {
   this->element = value;
   this->next = NULL;
}

ListNode::~ListNode() {
   delete this->next;
}

/*
* List.h
*
* Created on: 26-Jul-2020
* Author:
*/

#ifndef LIST_H_
#define LIST_H_

#include <iostream>
#include <sstream>
#include "ListNode.h"
using namespace std;

class List {
   ListNode *head;
   ListNode *tail;
   int size;
public:
   /**
   * default constructor
   * set head to null
   * set tail to null
   * set size to 0
   */
   List();

   /**
   * concatenate other list with this list
   * Precondition: l1and 12are linked lists. The lists may be empty or non-empty.
   * Postcondition: A copy of list l2is concatenated (added to the end) of list l1.
   *                List l2should be unchanged by the function.
   */
   void concatenate(const List &l2);

   /**
   * append a value at the end of the list
   * @param value to be append
   */
   void append(const int &value);

   /**
   * insert a value at the beginning of the list
   * @param value to be insert
   */
   void insert(const int &value);

   /**
   * insert a velue at ith position
   * Precondition: The list may be empty or non-empty.
   * Postcondition: The number value is inserted as the ith member of the list. If the list has fewer than i-1nodes in it,
   *                then value is inserted as the last node in the list.
   */
   void insertith(const int &value, const size_t &i);

   /**
   * remove a value from list
   * @param value to be remove
   */
   void remove(const int &value);

   /**
   * remove all duplicates of each elements from the list
   * Precondition: The list may be empty or non-empty.
   * Postcondition: Each node in the list must have a unique element value.
   */
   void removeDups();

   /**
   * search whether given value exist or not
   * @return true if exist otherwise return false
   */
   bool search(const int &value);

   /**
   * make this list empty
   */
   void makeEmpty();

   /**
   * friend function
   * overloaded insertion operator
   * for string stream
   */
   friend stringstream &operator<< (stringstream &ss, List &l);

   /**
   * default destructor
   * make this list empty
   */
   virtual ~List();
};

#endif /* LIST_H_ */

/*
* List.cpp
*
* Created on: 26-Jul-2020
* Author:
*/

#include "List.h"

List::List() {
   this->head = NULL;
   this->tail = NULL;
   this->size = 0;
}

void List::concatenate(const List &l2){
   ListNode *curr = l2.head;

   while (curr != NULL){
       this->append(curr->element);
       curr = curr->next;
   }
}

void List::append(const int &value){
   ListNode *newNode = new ListNode(value);
   this->size++;
   if (this->head == NULL){
       this->head = newNode;
       this->tail = newNode;
       return;
   }

   this->tail->next = newNode;
   this->tail = newNode;
}

void List::insert(const int &value){
   this->insertith(value, 0);
}

void List::insertith(const int &value, const size_t &i){
   ListNode *newNode = new ListNode(value);
   this->size++;
   if (this->head == NULL){
       this->head = newNode;
       this->tail = newNode;
       return;
   }

   if (i == 0){
       newNode->next = this->head;
       this->head = newNode;
       return;
   }

   ListNode *prev = this->head;
   ListNode *curr = prev->next;
   int j=1;
   while (curr != NULL){
       if (j == 1){
           prev->next = newNode;
           newNode->next = curr;
           return;
       }
       prev = curr;
       curr = curr->next;
   }

   this->tail->next = newNode;
   this->tail = newNode;
}

void List::remove(const int &value){

   while (this->head != NULL && this->head->element == value){
       this->head = this->head->next;
       this->size--;
   }

   if (this->head == NULL){
       return;
   }

   ListNode *prev = this->head;
   ListNode *curr = this->head->next;

   while (curr != NULL){
       if (curr->element == value){
           prev->next = curr->next;
           if (curr->next == NULL){
               this->tail = prev;
           }
           this->size--;
       } else {
           prev = curr;
       }
       curr = curr->next;
   }
}

void List::removeDups(){
   if (this->head == NULL){
       return;
   }
   List temp;
   temp.append(this->head->element);

   ListNode *prev = this->head;
   ListNode *curr = prev->next;

   while (curr != NULL){
       if (temp.search(curr->element)){
           prev->next = curr->next;
           if (curr->next == NULL){
               this->tail = prev;
           }
           this->size--;
       } else {
           temp.append(curr->element);
           prev = curr;
       }
       curr = curr->next;
   }
}

bool List::search(const int &value){
   ListNode *curr = this->head;

   while (curr != NULL){
       if (curr->element == value){
           return true;
       }
       curr = curr->next;
   }

   return false;
}

void List::makeEmpty(){
   delete this->head;
   this->head = NULL;
   this->tail = NULL;
   this->size = 0;
}

List::~List() {
   this->makeEmpty();
}

stringstream &operator<< (stringstream &ss, List &l){
   ListNode *curr = l.head;
   while (curr != NULL){
       ss<<curr->element;
       ss<<" -> ";
       curr = curr->next;
   }

   ss<<"NULL (size: "<<l.size<<")";
   return ss;
}

/*
* main.cpp
*
* Created on: 26-Jul-2020
* Author:
*/

#include <iostream>
#include "List.h"

int reserved_driver_main() {
List l1;
List l2;

// test 1, insertith
l1.insertith(1, 0);
l1.insertith(5, 0);
stringstream ss1;
ss1 << l1;
std::cout << ss1.str() << std::endl;
if(ss1.str() == "5 -> 1 -> NULL (size: 2)"){
std::cout << "1.1. insert ith successfully inserted; test passed" << std::endl;
} else {
std::cout << "1.1. insert ith did not successfully insert; test failed" << std::endl;
}
l1.makeEmpty();

// test 2, remove dupes
l1.insert(4);
l1.insert(5);
l1.insert(6);
l1.insert(7);
l1.remove(7);
l1.insert(4);
l1.insert(4);
l1.insert(5);
l1.removeDups();
stringstream ss2;
ss2 << l1;
std::cout << ss2.str() << std::endl;
if(ss2.str() == "5 -> 4 -> 6 -> NULL (size: 3)"){
std::cout << "2.1. successfully removed duplicates; test passed" << std::endl;
} else {
std::cout << "2.1. did not successfully remove duplicates; test failed" << std::endl;
}
l1.makeEmpty();

// test 3, concatenate
l1.insert(7);
l1.insert(6);
l1.insert(5);
l1.insert(4);
l2.insert(11);
l2.insert(10);
l2.insert(9);
l2.insert(8);
l1.concatenate(l2);
stringstream ss3;
ss3 << l1;
std::cout << ss3.str() << std::endl;
if(ss3.str() == "4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> NULL (size: 8)"){
std::cout << "3.1. successfully concatenated two lists; test passed" << std::endl;
} else {
std::cout << "3.1. did not successfully concatenate two lists; test failed" << std::endl;
}
l1.makeEmpty();
l2.makeEmpty();

// test 4, concatenate empty list
l1.insert(4);
l1.insert(5);
l1.insert(6);
l1.insert(7);
l1.concatenate(l2);
stringstream ss4;
ss4 << l1;
std::cout << ss4.str() << std::endl;
if(ss4.str() == "7 -> 6 -> 5 -> 4 -> NULL (size: 4)"){
std::cout << "4.1. successfully concatenated empty list; test passed" << std::endl;
} else {
std::cout << "4.1. did not successfully concatenate empty list; test failed" << std::endl;
}
l1.makeEmpty();

return 0;
}

int main(){
   reserved_driver_main();
}

Output: