Write a program that concatenates two linked list objects of characters. The program should include function concatenate, which takes references to both list objects as arguments and concat- enates the second list to the first list.

Question

What will be an ideal response?

Answer 1

```
// ListNode class template definition
#ifndef LISTNODE_H
#define LISTNODE_H

template< typename T > class List; // forward declaration

template< typename NODETYPE >
class ListNode
{
friend class List< NODETYPE >; // make List a friend
public:
ListNode( const NODETYPE & ); // constructor
NODETYPE getData() const; // return the data in the node

// set nextPtr to nPtr
void setNextPtr( ListNode *nPtr )
{
nextPtr = nPtr;
} // end function setNextPtr

// return nextPtr
ListNode *getNextPtr() const
{
return nextPtr;
} // end function getNextPtr

private:
NODETYPE data; // data

ListNode *nextPtr; // next node in the list }; // end class ListNode

// constructor
template< typename NODETYPE >
ListNode< NODETYPE >::ListNode( const NODETYPE &info )
{
data = info;
nextPtr = 0;
} // end constructor

// return a copy of the data in the node
template< typename NODETYPE >
NODETYPE ListNode< NODETYPE >::getData() const
{
return data;
} // end function getData

#endif
```
```
// List class template definition
// Added copy constructor to member functions (not included in chapter).
#ifndef LIST_H
#define LIST_H

#include
#include
#include "ListNode.h"
using namespace std;

template< typename NODETYPE >
class List
{
public:
List(); // default constructor
List( const List< NODETYPE > & ); // copy constructor
~List(); // destructor

void insertAtFront( const NODETYPE & );
void insertAtBack( const NODETYPE & );
bool removeFromFront( NODETYPE & );
bool removeFromBack( NODETYPE & );
bool isEmpty() const;
void print() const;
protected:
ListNode< NODETYPE > *firstPtr; // pointer to first node
ListNode< NODETYPE > *lastPtr; // pointer to last node

// Utility function to allocate a new node
ListNode< NODETYPE > *getNewNode( const NODETYPE & );
}; // end class template List

// default constructor
template< typename NODETYPE >
List< NODETYPE >::List()
{
firstPtr = lastPtr = 0;
} // end constructor

// copy constructor
template< typename NODETYPE >
List< NODETYPE >::List( const List © )
{
firstPtr = lastPtr = 0; // initialize pointers

ListNode< NODETYPE > *currentPtr = copy.firstPtr;

// insert into the list
while ( currentPtr != 0 )
{
insertAtBack( currentPtr->data );
currentPtr = currentPtr->nextPtr;
} // end while
} // end List copy constructor

// destructor
template< typename NODETYPE >
List< NODETYPE >::~List()
{
if ( !isEmpty() ) // List is not empty
{
cout << "Destroying nodes ...\n";

ListNode< NODETYPE > *currentPtr = firstPtr;
ListNode< NODETYPE > *tempPtr;

while ( currentPtr != 0 ) // delete remaining nodes
{
tempPtr = currentPtr;
cout << tempPtr->data << ' ';
currentPtr = currentPtr->nextPtr;
delete tempPtr;
} // end while
} // end if

cout << "\nAll nodes destroyed\n\n";
} // end destructor

// Insert a node at the front of the list
template< typename NODETYPE >
void List< NODETYPE >::insertAtFront( const NODETYPE &value )
{
ListNode *newPtr = getNewNode( value );

if ( isEmpty() ) // List is empty
firstPtr = lastPtr = newPtr;
else // List is not empty
{
newPtr->nextPtr = firstPtr;
firstPtr = newPtr;
} // end else
} // end function insertAtFront

// Insert a node at the back of the list
template< typename NODETYPE >
void List< NODETYPE >::insertAtBack( const NODETYPE &value )
{
ListNode< NODETYPE > *newPtr = getNewNode( value );

if ( isEmpty() ) // List is empty
firstPtr = lastPtr = newPtr;
else // List is not empty
{
lastPtr->nextPtr = newPtr;
lastPtr = newPtr;
} // end else
} // end function insertAtBack

// Delete a node from the front of the list
template< typename NODETYPE >
bool List< NODETYPE >::removeFromFront( NODETYPE &value )
{
if ( isEmpty() ) // List is empty
return false; // delete unsuccessful
else
{
ListNode< NODETYPE > *tempPtr = firstPtr;

if ( firstPtr == lastPtr )
firstPtr = lastPtr = 0;
else
firstPtr = firstPtr->nextPtr;

value = tempPtr->data; // data being removed

delete tempPtr;
return true; // delete successful
} // end else
} // end function removeFromFront

// delete a node from the back of the list
template< typename NODETYPE >
bool List< NODETYPE >::removeFromBack( NODETYPE &value )
{
if ( isEmpty() )
return false; // delete unsuccessful
else
{
ListNode< NODETYPE > *tempPtr = lastPtr;

if ( firstPtr == lastPtr )
firstPtr = lastPtr = 0;
else
{
ListNode< NODETYPE > *currentPtr = firstPtr;

while ( currentPtr->nextPtr != lastPtr )
currentPtr = currentPtr->nextPtr;

lastPtr = currentPtr;
currentPtr->nextPtr = 0;
} // end else

value = tempPtr->data;
delete tempPtr;
return true; // delete successful
} // end else
} // end function removeFromBack

// Is the List empty?
template< typename NODETYPE >
bool List< NODETYPE >::isEmpty() const
{
return firstPtr == 0;
} // end function isEmpty

// Return a pointer to a newly allocated node
template< typename NODETYPE >
ListNode< NODETYPE > *List< NODETYPE >::getNewNode(
const NODETYPE &value )
{
ListNode< NODETYPE > *ptr = new ListNode< NODETYPE >( value );
return ptr;
} // end function getNewNode

// Display the contents of the List
template< typename NODETYPE >
void List< NODETYPE >::print() const
{
if ( isEmpty() ) // empty list
{
cout << "The list is empty\n\n";
return;
} // end if

ListNode< NODETYPE > *currentPtr = firstPtr;

cout << "The list is: ";

while ( currentPtr != 0 ) // display elements in list
{
cout << currentPtr->data << ' ';
currentPtr = currentPtr->nextPtr;
} // end while

cout << "\n\n";
} // end function print

#endif
```
```
#include
using namespace std;

#include "List.h"

template< typename T >
void concatenate( List< T > &first, List< T > &second )
{
List< T > temp( second ); // create a copy of second
T value; // variable to store removed item from temp

while ( !temp.isEmpty() )
{
temp.removeFromFront( value ); // remove value from temp list
first.insertAtBack( value ); // insert at end of first list
} // end loop
} // end function concatenate

int main()
{
List< char > list1; // storage for first list
List< char > list2; // storage for second list
char c;

// assign alphabets into first list, from a to e
for ( c = 'a'; c <= 'e'; c++ )
list1.insertAtBack( c );

// call function print to print the list
list1.print();

// assign from f to j into second list
for ( c = 'f'; c <= 'j'; c++ )
list2.insertAtBack( c );

list2.print();

// function concatenate will append list2 with list1
concatenate( list1, list2 );
cout << "The new list1 after concatenation is:\n";
list1.print();
return 0; // indicates successful termination
} // end main
```
The list is: a b c d e
The list is: f g h i j
All nodes destroyed
The new list1 after concatenation is:
The list is: a b c d e f g h i j
Destroying nodes ...
f g h i j
All nodes destroyed
Destroying nodes ...
a b c d e f g h i j
All nodes destroyed