Download SLList.java and rename it to DLList.java. You will change it from a sin
ID: 3810732 • Letter: D
Question
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<E>
{
//-------- data
private SLLNode<E> head;
private SLLNode<E> 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<E>(someData);
//case 2,3: otherwise, create the new node and adjust the links
else
{
SLLNode<E> temp = new SLLNode<E>(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<E>(someData);
//case 2,3: otherwise, create the new node and adjust the links
else
{
SLLNode<E> temp = new SLLNode<E>(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<E> 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<E> 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<E> 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<E> cursor = head;
for (int i=0; i<index-1; i++)
cursor = cursor.next;
//now cursor should point at the node BEFORE the insertion
//create the new node and change the links
SLLNode<E> temp = new SLLNode<E>(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<E> 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<E> 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<E> 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<E>
{
//-------- data
protected E data;
protected SLLNode<E> 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
Explanation / Answer
//This class implements a Singly Linked List, using Generics
import java.util.*;
public class DLList<E>
{
//-------- data
private DLLNode<E> head;
private DLLNode<E> tail;
//-------- constructors
public DLList()
{
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 DLLNode<E>(someData);
//case 2,3: otherwise, create the new node and adjust the links
else
{
DLLNode<E> temp = new DLLNode<E>(someData);
tail.next = temp;
temp.prev = tail;
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 DLLNode<E>(someData);
//case 2,3: otherwise, create the new node and adjust the links
else
{
DLLNode<E> temp = new DLLNode<E>(someData);
temp.next = head;
head.prev = temp;
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
tail = tail.prev; //moving tail node to previous node
tail.next = null; //making the next to null so that this is the last node
//return
return returnedElt;
}
}
//size - returns the number of elements in the list
public int size()
{
int count = 0;
DLLNode<E> 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)
{
DLLNode<E> 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
DLLNode<E> cursor = head;
for (int i=0; i<index-1; i++)
cursor = cursor.next;
//now cursor should point at the node BEFORE the insertion
//create the new node and change the links
DLLNode<E> temp = new DLLNode<E>(elt);
temp.next = cursor.next;
temp.prev = cursor;
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
{
DLLNode<E> 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 = " ";
DLLNode<E> 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 = " ";
DLLNode<E> cursor = tail;
while(cursor != null)
{
if (cursor == tail)
returnStr = "" + cursor.data;
else
returnStr = returnStr + ", " + cursor.data;
cursor = cursor.prev;
}
return "[ " + returnStr + " ]";
}
//================================
// DLLNode - holds a node for a linked list
//================================
private class DLLNode<E>
{
//-------- data
protected E data;
protected DLLNode<E> next;
protected DLLNode<E> prev;
//-------- constructors
public DLLNode(E theData)
{
data = theData;
next = null;
prev = null;
}
//-------- methods
//toString - returns its representation as a String
public String toString()
{
return data.toString(); // or "" + data
}
}
} //end of DLList class
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.