Download SLList.java and rename it to DLList.java. You will change it from a singly linked list to a doubly linked list.

- change all comments and names to show that it is a DLList

- add a .prev link to the DLLNode

- make sure all methods set the .prev link as well as the .next link correctly

- uncomment the backwards() method so that the tester can call it to traverse the list backwards (so it can check the .prev links)

- in the removeLast method, the code traversed the list to find the node right before the tail. Now that it is a DLList, it can use the .prev node instead of traversing the list. Change

the removeLast method to use the .prev link instead of traversing the list.

Code SLL:

//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