Question

C++ Assignment

Project 1 - NodeList

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;
}

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);

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);

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;
}

List.cpp

#include "List.h"
#include "ListNode.h"

List::List() {
   head = NULL;
   listSize = 0;
}

List::~List() {
#ifdef SHOW_DESTRUCTOR_CALLS
   std::cout << "about to--> makeEmpty();" << std::endl;
#endif
   makeEmpty();
#ifdef SHOW_DESTRUCTOR_CALLS
   std::cout << "about to--> delete( head );" << std::endl;
#endif
   delete( head );
}

bool List::isEmpty() const {
   return( head == NULL );
}

void List::makeEmpty() {
   while (head != NULL) {
       remove( head->getElement() );
   }
}

int List::size() const {
   return( listSize );
}

void List::insert( const int& data ) {
   // place data into a ListNode at the front of the list
   // it will move the head node to behind the node
   // we create dynamically
   ListNode* temp = head;
   ListNode* newnode = new ListNode( data );
   head = newnode;
   newnode->setNext( temp );
   listSize++;
}

void List::append( const int& data ) {
// adds an element to the end of the list
if ( isEmpty() ) {
head = new ListNode( data );
} else {
// find the end of the list
ListNode* temp = head;
while (temp->getNext() != NULL)
temp = temp->getNext();
  
// add node
temp->setNext( new ListNode( data ) );
}
listSize++;
}
  

void List::remove( const int& data ) {
   ListNode* current = head;
   ListNode* previous = NULL;
   ListNode* nodeToRemove = NULL;
   while (current != NULL) {
       // have we found it at the current node???
       if (current->getElement() == data) {
           // found it at head node
           if (previous == NULL) {
               nodeToRemove = head;
               head = head->getNext();
           }
           // found it inside the list somewhere
           else {
               nodeToRemove = current;
               // skip the current node
               previous->setNext( current->getNext() );
           }
           delete( nodeToRemove );
           listSize--;
           break;
       }
       // keep looking
       else {
           previous = current;
           current = current->getNext();
       }
   }
}

std::ostream& operator << ( std::ostream& outs, const List& l) {
   return( l.printList( outs ) );
}

std::ostream& operator << ( std::ostream& outs, const List* l) {
   return( l->printList( outs ) );
}

std::ostream& List::printList( std::ostream& outs ) const {
   if (isEmpty())
       outs << "Empty List" << std::endl;
   else {
       ListNode* current = head;
       while (current != NULL) {
           outs << current->getElement() << " -> ";
           current = current->getNext();
       }
       outs << "NULL (size: " << size() << ")";
   }
   return( outs );
}

// ---------- implemented methods ------------

void List::concatenate( const List& B ) {
// Insert code here...
}

void List::insertith( const int& data, const size_t& i) {
// Insert code here...
}

void List::removeDups() {
// Insert code here...
}
'

List.h

#ifndef LIST_H
#define LIST_H
#include <iostream>
#include "ListNode.h"

// comment this line to suppress output in the destructor
// this may be useful for identifying where your program is having memory issues!
#define SHOW_DESTRUCTOR_CALLS

class List {
public:
  
   List();
   ~List();
  
// Implement these!
void concatenate( const List& B);
void insertith( const int& data, const size_t& i);
void removeDups();
//-----------------
  
   bool isEmpty() const;
   int size() const;
   void makeEmpty();
   void insert( const int& data );
   void append( const int& data );
   void remove( const int& data );
  
   friend std::ostream& operator << ( std::ostream& outs, const List& l );
   friend std::ostream& operator << ( std::ostream& outs, const List* l );
  
private:
   ListNode* head;
   int listSize;
  
   std::ostream& printList( std::ostream& outs ) const;
  
};

#endif
ListNode.cpp

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

ListNode::ListNode( const int& theElement,
               ListNode* nextNode ) : element( theElement ), next( nextNode ) {
}

const int ListNode::getElement() const {
   return( element );
}

void ListNode::setNext( ListNode * nextNode ) {
   next = nextNode;
}

ListNode * ListNode::getNext() const {
   return( next );
}

Answer 1

1)

CODE

void concatenate(ListNode *b) {

ListNode *temp = b;

while(temp.next != NULL) {

append(temp->data);

temp = temp->next;

}

}

NOTE: As per HOMEWORKLIB POLICY, I am allowed to answer only 1 coding question (including sub-parts) on a single post. Kindly post the remaining questions separately and I will try to answer them. Sorry for the inconvenience caused.