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.

What will be an ideal response?


```
// 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

Computer Science & Information Technology

You might also like to view...

You can view basic network information in the Windows 10 Network and Sharing Center

Indicate whether the statement is true or false

Computer Science & Information Technology

WLAN stands for "wide local area network." __________

Answer the following statement true (T) or false (F)

Computer Science & Information Technology

Small slices of a data mart are called data warehouses.

Answer the following statement true (T) or false (F)

Computer Science & Information Technology

List three different sources that could provide the input bit referenced by the XIO instruction.

What will be an ideal response?

Computer Science & Information Technology