Write a program that concatenates two linked list objects of characters. Class L

Question

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<T>
{
// package access members; List can access these directly
T data; // data for this node
ListNode<T> 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<T> node)
{
data = object;
nextNode = node;
}

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

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

// class List definition
public class List<T>
{
private ListNode<T> firstNode;
private ListNode<T> 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<T>(insertItem);
else // firstNode refers to new node
firstNode = new ListNode<T>(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<T>(insertItem);
else // lastNode's nextNode refers to new node
lastNode = lastNode.nextNode = new ListNode<T>(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<T> 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<T> 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<T>

Explanation / Answer

HI, Please find my implementation.

Please let me know in case of any issue.

public class ListConcatenate {

   public static <E> void concatenate(List<E> list1, List<E> list2) throws EmptyListException{

       // making copy of list2

       List<E> copyList2 = new List<>();

       // appending all elements of list2 to list1

       while(!list2.isEmpty()){

           E item = list2.removeFromFront();

           list1.insertAtBack(item);

           copyList2.insertAtBack(item);

       }

       // now again adding all elements of copyList2 to list2

       while(!copyList2.isEmpty()){

           E item = copyList2.removeFromFront();

           list2.insertAtBack(item);

       }

   }

   public static void main(String[] args) throws EmptyListException {

       List<Character> list1 = new List<>();

       List<Character> list2 = new List<>();

       list1.insertAtBack('A');

       list1.insertAtBack('B');

       list1.insertAtBack('C');

       list1.insertAtBack('D');

       list2.insertAtBack('E');

       list2.insertAtBack('F');

       list2.insertAtBack('G');

       list2.insertAtBack('H');

       list1.print();

       list2.print();

       concatenate(list1, list2);

       list1.print();

       list2.print();

   }

}

/*

Sample run:

The list is: A B C D

The list is: E F G H

The list is: A B C D E F G H

The list is: E F G H

*/

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.