List

1. Find your Num class from the queues day. It has the following methods and instance variables.

2. Make another file. Paste this into it. Save it to the same folder as Num.

public class List
{
private Num data[] = new Num [50];
int count;
int head;

public List ()
{
count = 0;
head = 0;
}

public void addToTail (int value)
{ //Pre: list is not full
//Post: item is added to end of list
int tail = (head + count) % data.length;
data [tail] = new Num (value);
count++;
}

public void addToTail (Num value)
{ //Pre: list is not full
//Post: item is added to end of list
int tail = (head + count) % data.length;
data [tail] = value;
count++;
}

public void addToHead (int item)
{ //Pre: List is not full
//Post: item is added to start of the list
Num p = new Num (item);
int newSpot = head - 1;
if (newSpot < 0)
newSpot = 49;
data [newSpot] = p;
head = newSpot;
count++;
}

public void addToHead (Num item)
{ //Post: item is added to start of the list
int newSpot = head - 1;
if (newSpot < 0)
newSpot = 49;
data [newSpot] = item;
head = newSpot;
count++;
}

public Num removeFromHead ()
{ //Pre: list is not empty
//Post: item at the head is removed and returned
Num temp = data [head];
count--;
head = (head + 1) % data.length;
return temp;
}

public Num removeFromTail ()
{ //Pre: stack is not empty
//Post: most recently pushed item is removed and returned

count--;
int tail = (head + count) % data.length;
return data [tail];
}

public Num peek ()
{ //Pre: list is not empty
//Post: returns the first item in the list
return data [head];
}

public Num tailPeek ()
{ //post: returns the last item in the list
int tail = (head + count) % data.length;
return data [tail];
}

public int size ()
{ //Post: returns the number of elements in the list
return count;
}

public boolean isFull ()
{ //Post: returns true iff the list is full
return (count == 50);
}

public boolean isEmpty ()
{ //Post: returns true iff the list is empty
return (count == 0);
}

public boolean empty ()
{ //Post: returns true iff the list is empty
return isEmpty ();
}

public void clear ()
{ //Post: removes all elements from list
while (!isEmpty ())
removeFromHead ();
}

public boolean contains (int n)
{ //Post: returns true iff the list contains n
boolean there = false;
for (int i = 0 ; i < count ; i++)
{
Num temp = removeFromHead ();
if (temp.getNum () == n)
there = true;
addToTail (temp);
}
return there;
}

public boolean contains (Num n)
{ //Post: returns true iff the list contains n
boolean there = false;
for (int i = 0 ; i < count ; i++)
{
Num temp = removeFromHead ();
if (temp.getNum () == n.getNum ())
there = true;
addToTail (temp);
}
return there;
}

public Num remove (Num n)
{ //Post: removes and returns element equal to value, otherwise Null
Num x = null;
int count2 = count;
for (int i = 0 ; i < count2 ; i++)
{
Num temp = removeFromHead ();
if (temp.getNum () != n.getNum ())
addToTail (temp);
else
x = temp;

}
return x;
}

public int remove (int n)
{ //Post: returns and returns element equal to value, otherwise 0
int n1 = 0;
int count2 = count;
for (int i = 0 ; i < count2 ; i++)
{
Num temp = removeFromHead ();
if (temp.getNum () != n)
addToTail (temp);
else
n1 = temp.getNum ();

}
return n1;
}

public String toString ()
{ //Post: the contents of the list are displayed.
//First element is first on the left.
int size = count;
String hold = "";
for (int i = 0 ; i < size ; i++)
{
Num temp = removeFromHead ();
hold += temp + " ";
addToTail (temp);
}
return hold;
}
}

3. Make a third file. Save it to the same place as Num.
a. What does this file print on the screen?
b. Adding to the tail is like what function in a queue?

public class ListRunner
{
public static void main (String args[])
{
new ListRunner ();
}

public ListRunner ()
{
List l = new List ();
l.addToTail (4);
System.out.println (l);
l.addToTail (5);
System.out.println (l);
l.addToTail (6);
System.out.println (l);
l.addToTail (7);
System.out.println (l);
}
}

4. Run this code.
a. Write down the input.
b. beside each line write down what happened (eg. removed 4 from tail)

public class ListRunner
{
public static void main (String args[])
{
new ListRunner ();
}

public ListRunner ()
{
List l = new List ();
l.addToTail (4);
System.out.println ("1. " +l);
l.addToHead (5);
System.out.println ("2. " +l);
l.addToHead (6);
System.out.println ("3. " +l);
l.removeFromHead ();
System.out.println ("4. " +l);
l.removeFromTail ();
System.out.println ("5. " +l);
l.addToHead (7);
System.out.println ("6. " +l);
l.addToHead (8);
System.out.println ("7. " +l);
l.addToTail (9);
System.out.println ("8. " +l);
l.remove (8);
System.out.println ("9. " +l);
}
}

5. Write two different sets of code that make a list that looks like: 6 7 8 9

6. Write out the name of the List function that corresponds to:

a. A Stack's push
b. A Stack's pop
c. A Queue's enqueue
d. A Queue's dequeue
e. A Queue's size
f. A Stack's peek
g. A Queue's peek
h. A Stack's is empty

7. Is a List FIFO or LIFO? Explain your response.

8. Over time, 1, 2, and 3 are added to the tail of a list in that order. If you vary the times you remove them, is it possible to print out each of the following? Prove it.

123, 231, 213, 132, 321, 312