For this Minilab, you will change the singly linked list that we developed in class (SLList.java) to a doubly linked list (DLList.java). Youll then change some of the code to take advantage of the prev link and then test it. Background: Make sure that you understand the SLList that was developed in class. The following methods were implemented in our SLList:

? toString() returns a representation of the list and its elements as a String. ? isEmpty() returns whether or not the linked list is empty.

? getFirst() returns the first element on the list. If the list is empty, throw a NoSuchElementException. Be sure and import java.util.*; so it understands this exception.

? getLast() returns the last element on the list. If the list is empty, throw a NoSuchElementException.

? addFirst(E el) adds the element that is passed in to the head of the list and returns nothing. ? addLast(E el) adds the element that is passed in to the tail of the list and returns nothing. ? add(int index, E elt) adds the element that is passed in at the position indicated by index

? removeFirst() deletes the first node from the list and returns its element. If the list is empty, throw a NoSuchElementException

? removeLast() deletes the last node from the list and returns its element. If the list is empty, throw a NoSuchElementException.

? remove(E trash) deletes the first occurrence of the element that is passed in; returns true or false depending on whether it is successful.

? contains(E elt) returns true if the list contains the given element

? size() returns the length of the list Please do the following:

1. Make a copy of the SLList.java that is given on Canvas and rename it DLList.java. Be sure it compiles (rename things as needed).

2. Change the code so that it implements a doubly linked list. Change every name that contains SLL to contain DLL instead. Your DLLNode class should have links that point to the previous and next nodes (the links are generally named prev and next). Please be sure that comments no longer say that it is a singly linked list.

3. The Canvas version of SLList.java is the same as the one that we developed in class, but has an additional method called backwards(). Currently, this method is just a copy of toString().

4. Change the method called backwards() so that it traverses the list from tail to head, following the prev link. That way, you will be able to tell if the prev links are set correctly.

5. Change the addLast method to correctly update the prev link. This should be done before the other methods since the tester uses it to generate test cases and the test doubly linked list should be correct.

6. Change the methods in DLList that add or remove nodes so that the prev and next links are used and updated correctly. In our removeLast method, we had to traverse the SLList list to find node before the tail so we could update the link. In DLList, there is a .prev link so you must change the code to just use the prev reference (the easier way) instead of traversing the list.

//This class implements a Singly Linked List, using Generics

import java.util.*;

public class SLList

{

//-------- data

private SLLNode head;

private SLLNode tail;

//-------- constructors

public SLList()

{

head = tail = null;

}

//-------- methods

//addLast - adds to the end of the list

public void addLast(E someData)

{

//case1: if its empty, the head and tail become the new node

if (head == null)

head = tail = new SLLNode(someData);

//case 2,3: otherwise, create the new node and adjust the links

else

{

SLLNode temp = new SLLNode(someData);

tail.next = temp;

tail = temp;

}

}

//addFirst - adds to the front of the list

public void addFirst(E someData)

{

//case1: if its empty, the head and tail become the new node

if (head == null)

head = tail = new SLLNode(someData);

//case 2,3: otherwise, create the new node and adjust the links

else

{

SLLNode temp = new SLLNode(someData);

temp.next = head;

head = temp;

}

}

//getFirst - returns the element at the front of the list, without deleting

public E getFirst()

{

if (head == null)

throw new NoSuchElementException("...Can't getFirst from empty list");

return head.data;

}

//getLast - returns the element at the end of the list, without deleting

public E getLast()

{

if (head == null) //empty

throw new NoSuchElementException("Can't getLast from empty list");

return tail.data;

}

//removeFirst - returns the element at the front of the list and deletes it

public E removeFirst()

{

//case1: list is empty

if (head == null)

throw new NoSuchElementException("cannot removeFirst from empty list!");

//case2: list has one element

else if (head == tail)

{

E returnedElt = head.data; //save the data

head = tail = null; //make list empty

return returnedElt; //return it

}

//case3: list has many elements

else

{

E returnedElt = head.data; //save the data

head = head.next; //move head over

return returnedElt;

}

}

//removeLast - returns the element at the end of the list and deletes it

public E removeLast()

{

//case1: list is empty

if (head == null)

throw new NoSuchElementException("cannot removeLast from empty list!");

//case2: list has one element

else if (head == tail)

return removeFirst();

//case3: list has many elements

else

{

E returnedElt = tail.data; //save the data

SLLNode cursor = head; //traverse the whole list

while(cursor.next != tail) //stop at the node BEFORE tail

cursor = cursor.next;

//cursor should be the node before tail. Change the links

cursor.next = null;

tail = cursor;

//return

return returnedElt;

}

}

//size - returns the number of elements in the list

public int size()

{

int count = 0;

SLLNode cursor = head;

while (cursor != null)

{

count++;

cursor = cursor.next;

}

return count;

}

//isEmpty - returns true if the list is empty, false otherwise

public boolean isEmpty()

{

return head == null;

}

//contains - returns true if the list contains what is received, false otherwise

public boolean contains(E elt)

{

SLLNode cursor = head;

while(cursor != null)

{

if (cursor.data.equals(elt))

return true; //done, found it!

else

cursor = cursor.next;

}

//if we finish the while loop, then we ran off of the list and

//did not find it.

return false;

}

//add - adds a new element at the given index.

// throws IllegalArgumentException if the index is out of bounds

public void add(int index, E elt)

{

//is it out of bounds?

if (index < 0 || index > size())

throw new IllegalArgumentException("index " + index + " is out of bounds");

if (index == 0) //index 0 means just put it first

addFirst(elt);

else

{

//have a cursor stop at the node BEFORE the insertion

//count nodes as it traverses it

SLLNode cursor = head;

for (int i=0; i

cursor = cursor.next;

//now cursor should point at the node BEFORE the insertion

//create the new node and change the links

SLLNode temp = new SLLNode(elt);

temp.next = cursor.next;

cursor.next = temp;

}

}

//remove - removes and returns the first occurrance of an element.

// returns true if successful, false otherwise

public boolean remove(E elt)

{

//case1: list is empty

if (head == null)

return false; //did not find it

//case2: one element on the list

else if (head == tail)

{

if (head.data.equals(elt)) //found it

{

head = tail = null;

return true;

}

else

return false; //did not find it

}

//case3: many elements on the list

else

{

if (this.contains(elt))

{

if (head.data.equals(elt)) //it is first

{

removeFirst();

return true;

}

else //it is not first. We must stop at the node in front of it

{

SLLNode cursor = head;

while(!cursor.next.data.equals(elt)) //while the next node does not have elt

cursor = cursor.next; //move on

//at this point, cursor has stopped at the node in front

if (cursor.next == tail) //it was the last element

tail = cursor; //so tail changes

cursor.next = cursor.next.next;

return true;

}

}

else //does not contain elt

return false;

}

}

//toString - returns its representation as a String

public String toString()

{

String returnStr = " ";

SLLNode cursor = head;

while(cursor != null)

{

if (cursor == head)

returnStr = "" + cursor.data;

else

returnStr = returnStr + ", " + cursor.data;

cursor = cursor.next;

}

return "[ " + returnStr + " ]";

}

/* //backwards - returns its representation as a String (backwards, following prev link)

public String backwards()

{

String returnStr = " ";

SLLNode cursor = tail;

while(cursor != null)

{

if (cursor == tail)

returnStr = "" + cursor.data;

else

returnStr = returnStr + ", " + cursor.data;

cursor = cursor.prev;

}

return "[ " + returnStr + " ]";

}

*/

//================================

// SLLNode - holds a node for a linked list

//================================

private class SLLNode

{

//-------- data

protected E data;

protected SLLNode next;

//-------- constructors

public SLLNode(E theData)

{

data = theData;

next = null;

}

//-------- methods

//toString - returns its representation as a String

public String toString()

{

return data.toString(); // or "" + data

}

}

} //end of SLList class