252 Chapter 13: Collections
Chapter 13: Collections
Lab Exercises
Topics Lab Exercises
Linked Lists Linked List of Integers
Recursive Processing of Linked List
Linked List of Objects
Doubly Linked Lists
Queues An Array Queue Implementation
Chapter 13: Collections 253
A Linked List of Integers
File IntList.java contains definitions for a linked list of integers. The class contains an inner class IntNode that
holds information for a single node in the list (a node has a value and a reference to the next node) and the
following IntList methods:
public IntList()—constructor; creates an empty list of integers
public void addToFront(int val)—takes an integer and puts it on the front of the list
File IntListTest.java contains a driver that allows you to experiment with these methods. Save both of these files
to your directory, compile and run IntListTest, and play around with it to see how it works. Then add the
following methods to the IntList class. For each, add an option to the driver to test it.
2. public String toString()—returns a String containing the print value of the list.
4. public void replace(int oldVal, int newVal)—replaces all occurrences of oldVal in the list with newVal.
Note that you can still use the old nodes; just replace the values stored in those nodes.
// ***************************************************************
// FILE: IntList.java
//
// Purpose: Defines a class that represents a list of integers
//
// ***************************************************************
public class IntList
}
//—————————————–
// Adds given integer to front of list.
//—————————————–
public void addToFront(int val)
{
while (temp.next != null)
temp = temp.next;
//link new node into list
temp.next = newnode;
}
}
//—————————————–
{
System.out.println(“——————–“);
System.out.print(“List elements: “);
IntNode temp = front;
while (temp != null)
{
System.out.print(temp.val + ” “);
// Constructor; sets up the node given a value and IntNode reference
//——————————————————————
public IntNode(int val, IntNode next)
{
this.val = val;
this.next = next;
}
}
}
Chapter 13: Collections 255
// Creates a list, then repeatedly prints the menu and does what
// the user asks until they quit.
//—————————————————————-
public static void main(String[] args)
{
scan = new Scanner(System.in);
{
case 0:
case 1: //add to front
System.out.println(“Enter integer to add to front”);
case 2: //add to end
System.out.println(“Enter integer to add to end”);
case 3: //remove first element
case 4: //print
256 Chapter 13: Collections
list.print();
break;
default:
System.out.println(“3: Remove an integer from the front of the list”);
System.out.println(“4: Print the list”);
System.out.print(“\nEnter your choice: “);
}
}
Chapter 13: Collections 257
Recursive Processing of Linked Lists
File IntList.java contains definitions for a linked list of integers (see previous exercise). The class contains an
inner class IntNode, which holds information for a single node in the list (a node has a value and a reference to
the next node) and the following IntList methods:
public IntList()—constructor; creates an empty list of integers
public void addToFront(int val)—takes an integer and puts it on the front of the list
File IntListTest.java contains a driver that allows you to experiment with these methods. Save both of these files
to your directory. If you have not already worked with these files in a previous exercise, compile and run
IntListTest and play around with it to see how it works. Then add the following methods to the IntList class. For
each, add an option in the driver to test the method.
1. public void printRec()—prints the list from first to last using recursion. Hint: The basic idea is that you
print the first item in the list then do a recursive call to print the rest of the list. This means you need to
2. public void printRecBackwards()—prints the list from last to first using recursion. Hint: Printing backward
recursively is just like printing forward recursively except you print the rest of the list before printing this
element. Simple!
258 Chapter 13: Collections
A Linked List of Objects
Listing 12.2 in the text is an example of a linked list of objects of type Magazine; the file IntList.java contains
an example of a linked list of integers (see previous exercise). A list of objects is a lot like a list of integers or a
particular type of object such as a Magazine, except the value stored is an Object, not an int or Magazine. Write
a class ObjList that contains arbitrary objects and that has the following methods:
public void addToFront (Object obj)—puts the object on the front of the list
These methods are similar to those in IntList. Note that you won’t have to write all of these again; you can just
make very minor modifications to the IntList methods.
Also write an ObjListTest class that creates an ObjList and puts various different kinds of objects in it (String,
array, etc) and then prints it.
Doubly Linked Lists
Sometimes it is convenient to maintain references to both the next node and the previous node in a linked list.
This is called a doubly linked list and is illustrated in Figure 12.4 of the text. File DoubleLinked.java contains
definitions for a doubly linked list of integers. This class contains an inner class IntNode that holds information
for a single node in the list (its value and references to the next and previous nodes). The DoubleLinked class
also contains the following methods:
public DoubleLinked()—constructor; creates an empty list of integers
File DoubleLinkedTest.java contains a driver that allows you to experiment with these methods. Save both of
these files to your directory, compile and run DoubleLinkedTest, and play around with it to see how it works.
Then add the following methods to the DoubleLinked class. For each, add an option to the driver to test it.
1. public void addToEnd(int val)—takes an integer and puts it on the end of the list
3. public void removeLast()—removes the last element of the list. If the list is empty, does nothing.
4. public void remove(int oldVal)—removes the first occurrence of oldVal in the list.
// ***************************************************************
// DoubleLinked.java
//
// A class using a doubly linked list to represent a list of integers.
//
// ***************************************************************
public void print()
{
for (IntNode temp = list; temp != null; temp = temp.next)
System.out.println(temp.val);
}
// ———————————————-
// Adds new element to front of list
260 Chapter 13: Collections
//***************************************************************
// An inner class that represents a list element.
//***************************************************************
private class IntNode
{
public int val;
public IntNode next;
public IntNode prev;
{
private static Scanner scan;
private static DoubleLinked list = new DoubleLinked();
//—————————————————————-
// Creates a list, then repeatedly prints the menu and does what
// the user asks until they quit.
{
case 0:
Chapter 13: Collections 261
case 1: //print
case 2: //add to front
System.out.println(“Enter integer to add to front”);
newVal = scan.nextInt();
list.addToFront(newVal);
break;
default:
System.out.println(“Sorry, invalid choice”);
}
}
//—————————————–
// Prints the user’s choices
//—————————————–
public static void printMenu()
}
262 Chapter 13: Collections
An Array Queue Implementation
File QueueADT.java contains a Java interface representing a queue ADT. In addition to enqueue(), dequeue(),
and isEmpty(), this interface contains two methods that are not described in the book – isFull () and size(). File
ArrayQueue.java contains a skeleton for an array-based implementation of this interface; it also includes a
toString() method that returns a string containing the queue elements, one per line. File TestQueue.java contains
a simple test program.
Complete the method definitions in ArrayQueue.java. Some things to think about:
• A queue has activity at both ends — elements are enqueued at one end and dequeued from the other
end. In an array implementation this means that repeated enqueues and dequeues will shift the queue
dequeue methods to be implemented efficiently in both space and time.
• You’ll need to use integers to keep track of the indices of the front and back of the queue. Think
carefully about what initial values these variables (front and back) should get in the constructor and
how they should be incremented given the circular nature of the implementation.
• The easiest way to implement the size() method is to keep track of the number of elements as you go
with the numElements variable — just increment this variable when you enqueue an element and
decrement it when you dequeue an element.
• An easy way to tell if a queue is full in an array implementation is to check how many elements it
Study the code in TestQueue.java so you know what it is doing, then compile and run it. Correct any problems
in your Linked Queue class.
//**********************************************************
// QueueADT.java
// The classic FIFO queue interface.
//**********************************************************
public interface QueueADT
{
//———————————————
// Returns true if queue is empty.
//———————————————
public boolean isEmpty();
Chapter 13: Collections 263
//———————————————
// Returns the number of elements in the queue.
//———————————————
public int size();
}
public class ArrayQueue implements QueueADT
{
private final int DEFAULT_SIZE = 5;
private Object[] elements;
private int numElements;
private int front, back;
//———————————————
// Constructor; creates array of default size.
//———————————————
public ArrayQueue()
{
}
{
}
//———————————————
// Removes and returns object from front of queue.
//———————————————
public Object dequeue()
{
}
//———————————————
// Returns true if queue is empty.
//———————————————
public boolean isEmpty()
{
}
}
//———————————————
264 Chapter 13: Collections
// Returns the number of elements in the queue.
//———————————————
public int size()
{
}
}
}
//**********************************************************
// TestQueue
// A driver to test the methods of the QueueADT implementations.
//**********************************************************
public class TestQueue
{
public static void main(String[] args)
{
QueueADT q = new ArrayQueue();
System.out.println(“\nHere’s the queue: ” + q);
System.out.println(“It contains ” + q.size() + ” items.”);
System.out.println(“\nDequeuing two…”);
System.out.println(q.dequeue());
System.out.println(q.dequeue());
System.out.println(“\nHere’s the queue again: ” + q);
System.out.println(“Now it contains ” + q.size() + ” items.”);
System.out.println(“\nDequeuing everything in queue”);
while (!q.isEmpty())
System.out.println(q.dequeue());
}
266 Chapter 13: Collections
A Linked Queue Implementation
File QueueADT.java contains a Java interface representing a queue ADT. In addition to enqueue(), dequeue(),
and isEmpty(), this interface contains two methods that are not described in the book – isFull () and size(). File
LinkedQueue.java contains a skeleton for a linked implementation of this interface; it also includes a toString()
method that returns a string containing the queue elements, one per line. It depends on the Node class in
Node.java. (This could also be defined as an inner class.) File TestQueue.java contains a simple test program.
Complete the method definitions in LinkedQueue.java. Some things to think about:
• In enqueue() and dequeue() you have to maintain both the front and back pointers – this takes a little
thought. In particular, in enqueue be careful of the case where the queue is empty and you are putting
Study the code in TestQueue.java so you know what it is doing, then compile and run it. Correct any problems
in your Linked Queue class.
//*********************************************************
// QueueADT.java
// The classic FIFO queue interface.
//*********************************************************
public interface QueueADT
//———————————————
// Returns true if queue is empty.
//———————————————
public boolean isEmpty();
//———————————————
// Returns true if queue is full.
//***********************************************************
// LinkedQueue.java
public class LinkedQueue implements QueueADT