kittensfurdays kittensfurdays - 19 days ago 4
Java Question

Trouble Transversing a string for DLList

Im supposed to create a method called "Backwards" that transverses the list from tail to head, however when I run my code it comes up saying that (line 88) it cannot find the cursor = cusor.prev; symbol. Do I need to set the prev link again in the loop? Thank you for any help

import java.util.*;

public class DLList<E>{
//data
private DLLNode<E> head;
private DLLNode<E> tail;
private DLLNode<E> prev;
private DLLNode<E> next;

//constructor(s)
public DLList()
{
head = tail = null;
}

// ------------ methods

//addFirst - adds a node with theData to the front of the list
public void addFirst(E theData)
{
//case where the list was empty
if (head == null)
{
head = tail = new DLLNode<E>(theData);
}
else
{
DLLNode<E> temp = new DLLNode<E>(theData);
temp.next = head;
head = temp;
}
}

// addLast - adds a node with theData to the end of the list
public void addLast(E theData)
{
//case where the list was empty
if (head == null)
{
head = tail = new DLLNode<E>(theData);
}
else //case where there was only 1 OR there are many element(s)
{
DLLNode<E> temp = new DLLNode<E>(theData); //create the new node
tail.next = temp; //reset the last link
tail = temp; // tail is reset to the new last node
}
}

//toString - returns the DLList as a String
public String toString()
{
String retString = " ";


//traverse through the whole list (starting at head, until last link is null)
DLLNode<E> cursor = head;
while (cursor != null)
{
if (cursor == head)
retString = retString + "" + cursor.data;
else //not first element so put in the comma
retString = retString + ", " + cursor.data;
cursor = cursor.next;
}


return "[" + retString + " ]";
}


//backwards - returns the DLList as a String (BACKWARDS)
public String backwards()
{

String retString = " ";


//traverse through the whole list (starting at tail, until last link is null)
DLLNode<E> cursor = tail;
while (cursor != null)
{
if (cursor == tail)
retString = retString + "" + cursor.data;
else //not first element so put in the comma
retString = retString + ", " + cursor.data;
cursor = cursor.prev;
}


return "[" + retString + " ]";
}

//recursive toString - this is the method that is called from "outside"
//and just calls the recursive version
public String anotherToString()
{
return recursiveToString(head);
}

//recursive version - calls itself
private String recursiveToString(DLLNode<E> subList)
{
if (subList == null)
return "";
else
return recursiveToString(subList.next) + " " + subList.data;
}


//getFirst - returns the first element on the list (without deleting it)
public E getFirst()
{
if (head == null) //empty
throw new NoSuchElementException("can't getFirst from empty list");
return head.data;
}

//getLast - returns the last element on the list (without deleting it)
public E getLast()
{
if (head == null) //empty
throw new NoSuchElementException("can't getLast from empty list");
return tail.data;
}

//contains - returns true if what is received is on the list
public boolean contains(E something)
{
DLLNode<E> cursor = head;

while (cursor != null)
{
if (cursor.data.equals(something))
return true; // found it so return now!
cursor = cursor.next;
}

return false; // if we got through the whole loop and didn't return, its not there
}

//size - returns the size of the DLList
public int size()
{
int count = 0;
//traverse through the whole list (starting at head, until last link is null)
DLLNode<E> cursor = head;
while (cursor != null)
{
count++;
cursor = cursor.next;
}

return count;
}

//add - adds a new element at a given index
public void add(int index, E elt)
{
//is index OK?
if (index < 0 || index > size())
throw new IllegalArgumentException("index " + index + " is out of bounds");

if (index == 0) //goes at the head
addFirst(elt); //call our own method
else if (index == size()) //goes at the tail
addLast(elt); //call our own method
else //goes in the middle somewhere
{
DLLNode<E> cursor = head; //set up a cursor
for (int i=1; i<index; i++)
cursor = cursor.next; //move the cursor over index times

//the cursor should have stopped at the node right before the insertion
//so just create the new node and then change the link
DLLNode<E> temp = new DLLNode<E>(elt);
temp.next = cursor.next;
cursor.next = temp;
}
}


//removeFirst - removes and returns the first element on the list
public E removeFirst()
{
//case1: list is empty
if (head == null)
throw new NoSuchElementException("cannot removeFirst from empty list");

//case2: list only has 1 element
else if (head == tail)
{
E whatToReturn = head.data; //keep track of it
head = tail = null;
return whatToReturn;
}

//case3: list has many element
else
{
E whatToReturn = head.data; //keep track of it
head = head.next; //move head over
return whatToReturn;
}
}

//removeLast - removes and returns the last element on the list
public E removeLast()
{
//case1: list is empty
if (head == null)
throw new NoSuchElementException("cannot removeLast from empty list");

//case2: list only has 1 element
else if (head == tail)
{
E whatToReturn = head.data; //keep track of it
head = tail = null;
return whatToReturn;
}

//case3: list has many elements
else
{
E whatToReturn = tail.data; //keep track of it

//cycle through whole list, stopping at the node right BEFORE the tail
DLLNode<E> cursor = head;
while (cursor.next != tail)
cursor = cursor.next;

//at this point, cursor should point at the node right before tail
//make changes...
tail = cursor;
tail.next = null;

//return what was the last data
return whatToReturn;
}
}

//remove - remove and return the first occurrance of an element
public boolean remove(E doomedElt)
{
//if the list is empty, then it obviously can't be removed
if (head == null)
return false;

//if the list has 1 or more elements
else
{
//find it (if it exists)
DLLNode<E> cursor = head;
while (cursor != null && !cursor.data.equals(doomedElt))
{
cursor = cursor.next;
}

//if its got all the way through the list (so it points at null now)
//then it did not find doomedElt
if (cursor == null)
return false;

//otherwise, we found it and cursor points to it
else
{
//if its the first element to be removed, then call our own method
if (cursor == head)
{
removeFirst();
return true;
}

//if its not the first element, then we have to traverse the list again
//so we know the element in front of it
else
{
DLLNode<E> followCursor = head;
while (!followCursor.next.equals(cursor))
followCursor = followCursor.next;
followCursor.next = cursor.next;
return true;
}
}
}
}

//isEmpty - returns true if it is empty
public boolean isEmpty()
{
return head == null;
}


//we need a Node to hold the data - it is its own class
private class DLLNode<E>
{
//data
protected E data; //protected so it is visible inside the DLList class
protected DLLNode<E> next; //(so I won't need .getData, .setData...)

//constructor(s)
public DLLNode(E theData)
{
this.data = theData;
next = null;
}

//methods
public String toString()
{
return data.toString();
}
}
} //end of DLList class

Answer

Well, if we look at DLLNode, it doesn't have any member called prev.

Just add one:

private class DLLNode<E>
{
    //data
    protected E data;                       //protected so it is visible inside the DLList class
    protected DLLNode<E> next;    //(so I won't need .getData, .setData...)
    protected DLLNode<E> prev;
    //constructor(s)
    ...
Comments