Write a program that concatenates two linked list objects of characters. Class ListConcatenate should include a static method concatenate that takes references to both list objects as arguments and concatenates the second list to the first list. NOTE: Your solution should use the List class of Figure 21.3 to create the two Lists that will be concatenated. The main method should use the print method of the List class to print the content of each list after it is created. After concatenation, the concatenated list should also be printed. Remember that the method concatenate should be generic.

Figure 21.3:

// Fig. 21.3: List.java // ListNode and List class declarations. package com.deitel.datastructures;

// class to represent one node in a list class ListNode { // package access members; List can access these directly T data; // data for this node ListNode nextNode; // reference to the next node in the list

// constructor creates a ListNode that refers to object ListNode(T object) { this(object, null); }

// constructor creates ListNode that refers to the specified // object and to the next ListNode ListNode(T object, ListNode node) { data = object; nextNode = node; }

// return reference to data in node T getData() { return data; }

// return reference to next node in list ListNode getNext() { return nextNode; } } // end class ListNode

// class List definition public class List { private ListNode firstNode; private ListNode lastNode; private String name; // string like "list" used in printing

// constructor creates empty List with "list" as the name public List() { this("list"); }

// constructor creates an empty List with a name public List(String listName) { name = listName; firstNode = lastNode = null; }

// insert item at front of List public void insertAtFront(T insertItem) { if (isEmpty()) // firstNode and lastNode refer to same object firstNode = lastNode = new ListNode(insertItem); else // firstNode refers to new node firstNode = new ListNode(insertItem, firstNode); }

// insert item at end of List public void insertAtBack(T insertItem) { if (isEmpty()) // firstNode and lastNode refer to same object firstNode = lastNode = new ListNode(insertItem); else // lastNode's nextNode refers to new node lastNode = lastNode.nextNode = new ListNode(insertItem); }

// remove first node from List public T removeFromFront() throws EmptyListException { if (isEmpty()) // throw exception if List is empty throw new EmptyListException(name);

T removedItem = firstNode.data; // retrieve data being removed

// update references firstNode and lastNode if (firstNode == lastNode) firstNode = lastNode = null; else firstNode = firstNode.nextNode;

return removedItem; // return removed node data } // end method removeFromFront

// remove last node from List public T removeFromBack() throws EmptyListException { if (isEmpty()) // throw exception if List is empty throw new EmptyListException(name);

T removedItem = lastNode.data; // retrieve data being removed

// update references firstNode and lastNode if (firstNode == lastNode) firstNode = lastNode = null; else // locate new last node { ListNode current = firstNode;

// loop while current node does not refer to lastNode while (current.nextNode != lastNode) current = current.nextNode; lastNode = current; // current is new lastNode current.nextNode = null; }

return removedItem; // return removed node data }

// determine whether list is empty public boolean isEmpty() { return firstNode == null; // return true if list is empty }

// output list contents public void print() { if (isEmpty()) { System.out.printf("Empty %s%n", name); return; }

System.out.printf("The %s is: ", name); ListNode current = firstNode;

// while not at end of list, output current node's data while (current != null) { System.out.printf("%s ", current.data); current = current.nextNode; }

System.out.println(); } } // end class List