CS 206: Data Structures
Exercise#10
Due on Thursday, March 20
Implement the List ADT as discussed in class using a linked structure (with both first and last fields). Use it in your List tester program from Exercise#8. Functionally, your program will not change at all. The only changes will be in the use of the List ADT.
Include the operations listed below in black in your ListInterface. Include the additional operations (listed in blue) as public methods in the List class.
public boolean add(object) : adds object at the end of the list
public void add(i, object): adds object
at position i (positions in list start at 0)
boolean addFirst(object): adds object in
the begining of the list
boolean addLast(object): adds object at
the end of the list
void clear(): clears the list
boolean contains(object): returns true if list contains object, false
otherwise
Object get(i): returns ith object in list
Object getFirst(): returns first object
in list
Object getLast(): returns last object in
list
int indexOf(object): returns the index of
object in the list if it occurs, -1 otherwise
boolean isEmpty(): returns true if list is empty, false otherwise
Object remove(i): remove ith element in list
Object removeFirst(): removes first element
in list
Object removeLast(): removes last element
in list
Object set(i,o): changes ith element in
list to be o
int size(): returns the size of the list
String toString(): returns the list as a
string: [object1, object2, ...]
Given the implementation of the list tester, you may not be able to test all of the above operations. Notice that many of the operations can be implemented in terms of already defined, more general operations.
/*
A List Tester program
*/
import java.awt.*;
import java.applet.Applet;
import java.awt.event.*;
public class TestLists extends Applet implements ActionListener
{
// GUI Stuff
TextArea outputArea;
Button clearB, sizeB, emptyB, add1B, add2B, removeB, getB, setB, containsB, displayB;
TextField add1Text, add2ItemText, add2PosText, removeText, getT, setPosText, setItemText, containsText;
// Program variables
ListInterface L;
public void init() {
makeGUI();
L = new AList1();
// print out the current length of the list
outputArea.appendText("The list has " + L.size() + " elements.\n\n");
// add a bunch of numbers to the list
for (int i = 0; i < 10; i++)
L.add(new Integer(i));
// display the contents of the list
displayList();
} // init
public void displayList() {
outputArea.appendText("The list contains the following " + L.size() + " elements...\n");
for (int i = 0; i < L.size(); i++)
outputArea.appendText(L.get(i) + " ");
outputArea.appendText("\n\n");
} // displayList
public void addToList() {
String vs = add1Text.getText();
Integer value = new Integer(vs);
if (L.add(value))
outputArea.appendText("Added " + value + " to the end of list.\n\n");
else
outputArea.appendText("Operation failed.\n\n");
} // addToList
public void addToList2() {
String vs = add2ItemText.getText();
Integer value = new Integer(vs);
String ps = add2PosText.getText();
Integer pI = new Integer(ps);
int position = pI.intValue();
if (L.add(position, value))
outputArea.appendText("Added " + value + " at position " + position + ".\n\n");
else
outputArea.appendText("Operation failed.\n\n");
} // addToList2
public void getFromList() {
String vs = getT.getText();
Integer vI = new Integer(vs);
int value = vI.intValue();
outputArea.appendText("Got item: " + L.get(value) + " from position: " + value + ".\n\n");
} // getFromList
public void actionPerformed(ActionEvent e) {
if (e.getSource() == clearB) {
outputArea.appendText("Clearing the list.\n\n");
L.clear();
}
else if (e.getSource() == sizeB)
outputArea.appendText("The list contains " + L.size() + " elements.\n\n");
else if (e.getSource() == displayB)
displayList();
else if (e.getSource() == add1B)
addToList();
else if (e.getSource() == add2B)
addToList2();
else if (e.getSource() == getB)
getFromList();
else if (e.getSource() == emptyB) {
if (L.isEmpty())
outputArea.appendText("The List is empty.\n\n");
else
outputArea.appendText("The List is not empty.\n\n");
}
} // actionPerformed
public void makeGUI() {
this.setLayout(new BorderLayout());
// Big Panel for controls
Panel mainPanel = new Panel();
mainPanel.setLayout(new GridLayout(4,1));
// Make the clear, size, empty, display panel
Panel p1 = new Panel();
p1.setLayout(new GridLayout(1,3));
clearB = new Button("Clear");
clearB.addActionListener(this);
sizeB = new Button("Size");
sizeB.addActionListener(this);
emptyB = new Button("isEmpty?");
emptyB.addActionListener(this);
displayB = new Button("Display List");
displayB.addActionListener(this);
p1.add(clearB);
p1.add(sizeB);
p1.add(emptyB);
p1.add(displayB);
mainPanel.add(p1);
// make the add panel
Panel p2 = new Panel();
p2.setLayout(new GridLayout(2,1));
Panel add1P = new Panel();
add1B = new Button("Add");
add1B.addActionListener(this);
add1Text = new TextField(5);
add1P.add(add1B);
add1P.add(add1Text);
Panel add2P = new Panel();
add2B = new Button("Add");
add2B.addActionListener(this);
add2ItemText = new TextField(5);
Label add2L = new Label("AT");
add2PosText = new TextField(5);
add2P.add(add2B);
add2P.add(add2ItemText);
add2P.add(add2L);
add2P.add(add2PosText);
p2.setBackground(Color.gray);
p2.add(add1P);
p2.add(add2P);
mainPanel.add(p2);
// make the get and contains Panel
Panel p4 = new Panel();
p4.setLayout(new GridLayout(2, 1));
Panel getP = new Panel();
getB = new Button("Get");
getB.addActionListener(this);
getT = new TextField(5);
getP.add(getB);
getP.add(getT);
Panel containsP = new Panel();
containsB = new Button("Contains");
containsB.addActionListener(this);
containsText = new TextField(5);
containsP.add(containsB);
containsP.add(containsText);
p4.add(getP);
p4.add(containsP);
mainPanel.add(p4);
// make the remove and set panel
Panel p3 = new Panel();
p3.setLayout(new GridLayout(2,1));
Panel removeP = new Panel();
removeB = new Button("Remove");
removeB.addActionListener(this);
removeText = new TextField(5);
removeP.add(removeB);
removeP.add(removeText);
Panel setP = new Panel();
setB = new Button("Set");
setB.addActionListener(this);
setItemText = new TextField(5);
Label setL = new Label("AT");
setPosText = new TextField(5);
setP.add(setB);
setP.add(setItemText);
setP.add(setL);
setP.add(setPosText);
p3.setBackground(Color.gray);
p3.add(removeP);
p3.add(setP);
mainPanel.add(p3);
// add the main panel
this.add(mainPanel, "North");
outputArea = new TextArea("Testing the List ADT\n\n", 400, 200, TextArea.SCROLLBARS_BOTH);
this.add(outputArea, "Center");
outputArea.setBackground(Color.lightGray);
} // makeGUI
} // TestLists