Directed Lab Work Problem I: Common objects in two lists Suppose that aList and
ID: 3820004 • Letter: D
Question
Directed Lab Work
Problem I: Common objects in two lists
Suppose that aList and bList are instances of java.util.ArrayList. Use two iterators to find and display all the items that are common in both lists.
One way to do this is to scan the items in the first list aList and for each item currentItem, scan the entire bList, checking its elements consecutively for equality to currentItem. The basic idea is to use an iterator for scanning the items in each list, e.g. aIterator and bIterator.
Follow the steps below.
Step 1. Create a new Eclipse project Lab20, a class CommonItems and a method findCommon in it:
findCommon(ArrayList<String> aList, ArrayList<String> bList)
Step 2. In the findCommon method create an iterator ial for aList.
Step 3. Use the iterator in a while loop to consecutively access each element of the aList.
Step 4. Within the loop, create an iterator ibl for bList.
Step 5. Create a Boolean variable found to indicate whether the current item from the first list is equal to the currently considered item from the second list. Initialize it to false.
Step 6. Write a nested while loop using the iterator ibl to access each item from the second list in turn. At each step of the loop, check whether the current element from the first list is equal to the current element from the second list, and if so, assign true to the variable found.
Step 7. Upon exiting the nested loop, if the current item from aList is equal to at least one item from bList, print it.
Step 8. Create a main method in the CommonItems class for testing the findCommon method.
Step 9. Declare two arrays of strings, a and b and initialize them with some values.
Step 10. Declare two lists of type ArrayList - alist and blist, and add the values from the arrays a and b to them correspondingly (in a loop).
Step 11. Call the findCommon() method to find the common items in the lists and print the result.
Checkpoint: Test your program by executing the CommonItems class.
ListInterface.java
/**
An interface for the ADT list.
Entries in the list have positions that begin with 1.
@author Frank M. Carrano
@version 3.0
*/
public interface ListInterface<T>
{
/** Adds a new entry to the end of this list.
Entries currently in the list are unaffected.
The listÕs size is increased by 1.
@param newEntry the object to be added as a new entry */
public void add(T newEntry);
/** Adds a new entry at a specified position within this list.
Entries originally at and above the specified position
are at the next higher position within the list.
The listÕs size is increased by 1.
@param newPosition an integer that specifies the desired
position of the new entry
@param newEntry the object to be added as a new entry
@return true if the addition is successful, or
false if newPosition < 1, or newPosition > getLength() + 1 */
public boolean add(int newPosition, T newEntry);
/** Removes the entry at a given position from this list.
Entries originally at positions higher than the given
position are at the next lower position within the list,
and the listÕs size is decreased by 1.
@param givenPosition an integer that indicates the position of
the entry to be removed
@return a reference to the removed entry or null, if either
the list was empty, givenPosition < 1, or
givenPosition > getLength() */
public T remove(int givenPosition);
/** Removes all entries from this list. */
public void clear();
/** Replaces the entry at a given position in this list.
@param givenPosition an integer that indicates the position of
the entry to be replaced
@param newEntry the object that will replace the entry at the
position givenPosition
@return true if the replacement occurs, or false if either the
list is empty, givenPosition < 1, or
givenPosition > getLength() */
public boolean replace(int givenPosition, T newEntry);
/** Retrieves the entry at a given position in this list.
@param givenPosition an integer that indicates the position of
the desired entry
@return a reference to the indicated entry or null, if either
the list is empty, givenPosition < 1, or
givenPosition > getLength() */
public T getEntry(int givenPosition);
/** Sees whether this list contains a given entry.
@param anEntry the object that is the desired entry
@return true if the list contains anEntry, or false if not */
public boolean contains(T anEntry);
/** Gets the length of this list.
@return the integer number of entries currently in the list */
public int getLength();
/** Sees whether this list is empty.
@return true if the list is empty, or false if not */
public boolean isEmpty();
/** Retrieves all entries that are in this list in the order in which
they occur in the list. */
public T[] toArray();
} // end ListInterface
ListWithIteratorInterface.java
import java.util.Iterator;
/**
An interface for the ADT list that has an iterator.
@author Frank M. Carrano
@author Timothy M. Henry
@version 4.0
*/
public interface ListWithIteratorInterface<T> extends ListInterface<T>, Iterable<T>
{
public Iterator<T> getIterator();
} // end ListWithIteratorInterface
LinkedListWithIterator.java
import java.util.Iterator;
import java.util.NoSuchElementException;
/**
A class that implements the ADT list by using a chain of nodes.
The list has an iterator. The class is similar to LList.
@author Frank M. Carrano
@author Timothy M. Henry
@version 4.0
*/
public class LinkedListWithIterator<T>
implements ListWithIteratorInterface<T>
{
private Node firstNode;
private int numberOfEntries;;
public LinkedListWithIterator()
{
initializeDataFields();
} // end default constructor
public void clear()
{
initializeDataFields();
} // end clear
public void add(T newEntry) // OutOfMemoryError possible
{
Node newNode = new Node(newEntry);
if (isEmpty())
firstNode = newNode;
else // Add to end of non-empty list
{
Node lastNode = getNodeAt(numberOfEntries);
lastNode.setNextNode(newNode); // Make last node reference new node
} // end if
numberOfEntries++;
} // end add
public void add(int newPosition, T newEntry) // OutOfMemoryError possible
{
if ((newPosition >= 1) && (newPosition <= numberOfEntries + 1))
{
Node newNode = new Node(newEntry);
if (newPosition == 1) // Case 1
{
newNode.setNextNode(firstNode);
firstNode = newNode;
}
else // Case 2: list is not empty
{ // and newPosition > 1
Node nodeBefore = getNodeAt(newPosition - 1);
Node nodeAfter = nodeBefore.getNextNode();
newNode.setNextNode(nodeAfter);
nodeBefore.setNextNode(newNode);
} // end if
numberOfEntries++;
}
else
throw new IndexOutOfBoundsException("Illegal position given to add operation.");
} // end add
public T remove(int givenPosition)
{
T result = null; // Return value
if ((givenPosition >= 1) && (givenPosition <= numberOfEntries))
{
assert !isEmpty();
if (givenPosition == 1) // Case 1: remove first entry
{
result = firstNode.getData(); // Save entry to be removed
firstNode = firstNode.getNextNode();
}
else // Case 2: not first entry
{
Node nodeBefore = getNodeAt(givenPosition - 1);
Node nodeToRemove = nodeBefore.getNextNode();
Node nodeAfter = nodeToRemove.getNextNode();
nodeBefore.setNextNode(nodeAfter);
result = nodeToRemove.getData(); // Save entry to be removed
} // end if
numberOfEntries--;
return result; // Return removed entry
}
else
throw new IndexOutOfBoundsException("Illegal position given to remove operation.");
} // end remove
public T replace(int givenPosition, T newEntry)
{
if ((givenPosition >= 1) && (givenPosition <= numberOfEntries))
{
assert !isEmpty();
Node desiredNode = getNodeAt(givenPosition);
T originalEntry = desiredNode.getData();
desiredNode.setData(newEntry);
return originalEntry;
}
else
throw new IndexOutOfBoundsException("Illegal position given to replace operation.");
} // end replace
public T getEntry(int givenPosition)
{
if ((givenPosition >= 1) && (givenPosition <= numberOfEntries))
{
assert !isEmpty();
return getNodeAt(givenPosition).getData();
}
else
throw new IndexOutOfBoundsException("Illegal position given to getEntry operation.");
} // end getEntry
public T[] toArray()
{
// The cast is safe because the new array contains null entries
@SuppressWarnings("unchecked")
T[] result = (T[])new Object[numberOfEntries];
int index = 0;
Node currentNode = firstNode;
while ((index < numberOfEntries) && (currentNode != null))
{
result[index] = currentNode.getData();
currentNode = currentNode.getNextNode();
index++;
} // end while
return result;
} // end toArray
public boolean contains(T anEntry)
{
boolean found = false;
Node currentNode = firstNode;
while (!found && (currentNode != null))
{
if (anEntry.equals(currentNode.getData()))
found = true;
else
currentNode = currentNode.getNextNode();
} // end while
return found;
} // end contains
public int getLength()
{
return numberOfEntries;
} // end getLength
public boolean isEmpty()
{
boolean result;
if (numberOfEntries == 0) // Or getLength() == 0
{
assert firstNode == null;
result = true;
}
else
{
assert firstNode != null;
result = false;
} // end if
return result;
} // end isEmpty
public Iterator<T> iterator()
{
return new IteratorForLinkedList();
} // end iterator
public Iterator<T> getIterator()
{
return iterator();
} // end getIterator
// Initializes the class's data fields to indicate an empty list.
private void initializeDataFields()
{
firstNode = null;
numberOfEntries = 0;
} // end initializeDataFields
// Returns a reference to the node at a given position.
// Precondition: List is not empty;
// 1 <= givenPosition <= numberOfEntries.
private Node getNodeAt(int givenPosition)
{
assert !isEmpty() && (1 <= givenPosition) && (givenPosition <= numberOfEntries);
Node currentNode = firstNode;
// Traverse the chain to locate the desired node (skipped
// if givenPosition is 1)
for (int counter = 1; counter < givenPosition; counter++)
currentNode = currentNode.getNextNode();
assert currentNode != null;
return currentNode;
} // end getNodeAt
//==================================
private class IteratorForLinkedList implements Iterator<T>
{
private Node nextNode; // Node containing next entry in iteration
private IteratorForLinkedList()
{
nextNode = firstNode;
} // end default constructor
public boolean hasNext()
{
return nextNode != null;
} // end hasNext
public T next()
{
if (hasNext())
{
Node returnNode = nextNode; // Get next node
nextNode = nextNode.getNextNode(); // Advance iterator
return returnNode.getData(); // Return next entry in iteration
}
else
throw new NoSuchElementException("Illegal call to next(); " +
"iterator is after end of list.");
} // end next
public void remove()
{
throw new UnsupportedOperationException("remove() is not " +
"supported by this iterator");
} // end remove
} // end IteratorForLinkedList
private class Node
{
private T data; // Entry in list
private Node next; // Link to next node
private Node(T dataPortion)
{
data = dataPortion;
next = null;
} // end constructor
private Node(T dataPortion, Node nextNode)
{
data = dataPortion;
next = nextNode;
} // end constructor
private T getData()
{
return data;
} // end getData
private void setData(T newData)
{
data = newData;
} // end setData
private Node getNextNode()
{
return next;
} // end getNextNode
private void setNextNode(Node nextNode)
{
next = nextNode;
} // end setNextNode
} // end Node
} // end LinkedListWithIterator
Driver.java
import java.util.Iterator;
/**
A driver that demonstrates the class LinkedListWithIterator.
*/
public class Driver
{
public static void main(String[] args)
{
testIterator();
} // end main
public static void testIterator()
{
ListWithIteratorInterface<String> myList = new LinkedListWithIterator<>();
System.out.println("Add to list: 15, 25, 35, 45, 55, 65, 75, 85, 95");
myList.add("15");
myList.add("25");
myList.add("35");
myList.add("45");
myList.add("55");
myList.add("65");
myList.add("75");
myList.add("85");
myList.add("95");
System.out.println(" Testing the displayList method ");
displayListI(myList);
} // end testIterator
public static void displayListI(ListWithIteratorInterface<String> list)
{
////// INSERT YOUR CODE HERE /////////
} // end displayList
} // end Driver
Explanation / Answer
import java.io.IOException;
import java.util.ArrayList;
import java.util.Iterator;
public class CommonItems {
public void findCommon(ArrayList<String> aList, ArrayList<String> bList) {
Iterator<String> ial = aList.iterator();
Iterator<String> ibl = null;
while (ial.hasNext()) {
ibl = bList.iterator();
String value = ial.next();
Boolean found = false;
while (ibl.hasNext()) {
if (value.equals(ibl.next())) {
found = true;
}
}
if (found) {
System.out.println(value);
}
}
}
public static void main(String[] args) throws IOException {
ArrayList<String> alist=new ArrayList<>();
ArrayList<String> blist=new ArrayList<>();
String[] a = {"hi","b","c"};
String[] b = {"x","b","c"};
for(int i=0;i<a.length;i++){
alist.add(a[i]);
}
for(int i=0;i<b.length;i++){
blist.add(b[i]);
}
CommonItems c=new CommonItems();
c.findCommon(alist, blist);
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.