Reversing a doubly linked list

[Luke Stamper]

I've been asked to make some modifications to a linked list.

1) make it doubly linked.
2) Add a copy constructor
3) Add a clone method
4) Replace outputList with toString
5) Code an iterator method
6) Keep track of the tail and add a method outputBackwards to prove the list is doubly linked.

I pretty much have everything covered except for #6. I'm having trouble with this. Can anyone provide some assistance? Thanks in advance.

import java.util.NoSuchElementException;
public class LinkedList3<T> implements Cloneable
{
private class TwoWayNode<T>
{
private T item;
private TwoWayNode<T> next;
private TwoWayNode<T> prev;
public TwoWayNode()
{
item = null;
next = null;
prev = null;
}
public TwoWayNode(T newItem, TwoWayNode<T> previousNode, TwoWayNode<T> nextNode)
{
item = newItem;
prev = previousNode;
next = nextNode;
}
}
public TwoWayNode<T> head;
//Deep copy clone method
public LinkedList3()
{
head = null;
}
public LinkedList3(LinkedList3<T> otherList)
{
if(otherList == null)
throw new NullPointerException();
if (otherList.head == null)
head = null;
else
head = copyOf(otherList.head);
}
public LinkedList3<T> clone()
{
try
{
LinkedList3<T> copy = (LinkedList3<T>)super.clone();
if (head == null)
copy.head = null;
else
copy.head= copyOf(head);
return copy;
}
catch(CloneNotSupportedException e)
{
return null;
}
}
public TwoWayNode<T> copyOf(TwoWayNode<T> otherHead)
{
TwoWayNode<T> position = otherHead;
TwoWayNode<T> newHead;
TwoWayNode<T> end = null;
newHead = new TwoWayNode<T>(position.item, position.prev, null);
end = newHead;
position = position.prev;
while(position != null)
{
end.prev = new TwoWayNode<T>(position.item, position.prev, null);//position.prev
end = end.prev;
position = position.prev;
}
return newHead;
}
public boolean equals(Object otherObject)
{
if (otherObject == null)
return false;
else if (getClass( ) != otherObject.getClass( ))
return false;
else
{
LinkedList3<T> otherList = (LinkedList3<T>)otherObject;
if (size( ) != otherList.size( ))
return false;
TwoWayNode<T> position = head;
TwoWayNode<T> otherPosition = otherList.head;
while (position != null)
{
if (!(position.item.equals(otherPosition.item)))
return false;
position = position.prev;
otherPosition = otherPosition.prev;
}
return true; //no mismatch was not found
}
}
public String toString()
{
TwoWayNode<T> position = head;
String theString = "";
while (position != null)
{
theString = theString + position.item + "\n";
position = position.prev;//changed linked to prev (possibly head?)
}
return theString;
}
//Iterator Method
public class LinkedList3Iterator{
private TwoWayNode position = null;
public LinkedList3Iterator()
{
position = head;
}
public void restart(){
position = head;
}
public T next(){
if(!hasNext( ))
throw new IllegalStateException();
T toReturn = (T)position.item;
position = position.next;
return toReturn;
}
public boolean hasNext( )
{
return(position != null);
}
public void insertHere(T newData)
{
if (position == null && head != null)
{
TwoWayNode<T> temp = head;
while (temp.next != head)
temp = temp.next;
temp.next = new TwoWayNode<T>(newData, temp, null);
}
else if (head == null || position.prev == null)
LinkedList3.this.addToStart (newData);
else
{
TwoWayNode<T> temp = new TwoWayNode(newData, position.prev, position);
position.prev.next = temp;
position.prev = temp;
}
}
public void delete()
{
if(position == null)
throw new IllegalStateException();
else if(position.prev == null)
{
head = head.next;
position = null;
}
else if(position.next == null)
{
position.prev.next = null;
position = null;
}
else
{
position.prev.next = position.next;
position.next.prev = position.prev;
position = position.next;
}
}
public T peek()
{
if(!hasNext())
throw new IllegalStateException();
return (T)position.item;
}
}
public void addToStart(T itemName)
{
TwoWayNode<T> newHead = new TwoWayNode(itemName, null, head);
if (head != null)
{
head.prev = newHead;
}
head = newHead;
}
/**
Adds a node at the start of the list with the specified data.
The added node will be the first node in the list.
*/
private TwoWayNode next() {
if(head.next != null) return head.next;
else return head.prev;
}
public void reverse()
{
if(head.next == null)
return;
TwoWayNode previous = head;
TwoWayNode current = head.next;
head.next = null;
head.prev = current;
while(current != null)
{
TwoWayNode next = current.next;
current.next = previous;
current.prev = next;
previous = current;
current = next;
}
//Switch head and tail.
}
/**
Removes the head node and returns true if the list contains at least
one node. Returns false if the list is empty.
*/
public boolean deleteHeadNode( )
{
if (head != null)
{
head = head.prev;
return true;
}
else
return false;
}
/**
Returns the number of nodes in the list.
*/
public int size( )
{
int count = 0;
TwoWayNode<T> position = head;
while (position != null)
{
count++;
position = position.prev;
}
return count;
}
public boolean contains(T item)
{
return (find(item) != null);
}
/**
Finds the first node containing the target item, and returns a
reference to that node. If target is not in the list, null is returned.
*/
private TwoWayNode<T> find(T target)
{
TwoWayNode<T> position = head;
T itemAtPosition;
while (position != null)
{
itemAtPosition = position.item;
if (itemAtPosition.equals(target))
return position;
position = position.prev;
}
return null; //target was not found
}
/**
Finds the first node containing the target and returns a reference
to the data in that node. If target is not in the list, null is returned.
*/
public T findItem(T target)
{
return find(target).item;
}
public boolean isEmpty( )
{
return (head == null);
}
public void clear( )
{
head = null;
}
public LinkedList3Iterator iterator(){
return new LinkedList3Iterator();
}
}
public class LinkedList3Demo {
public static void main(String[] args) {
LinkedList3 list = new LinkedList3();
LinkedList3.LinkedList3Iterator i = list.iterator();
list.addToStart("shoes");
list.addToStart("hat");
list.addToStart("coat");
System.out.println("List contains: ");
i.restart();
while (i.hasNext())
System.out.println(i.next());
System.out.println();
i.restart();
i.next();
i.next();
System.out.println("Delete " + i.peek());
i.delete();
System.out.println("List now contains:");
i.restart();
while(i.hasNext())
System.out.println(i.next());
System.out.println();
i.restart();
i.next();
System.out.println("Inserting socks before " + i.peek());
i.insertHere("socks");
i.restart();
System.out.println("List now contains: ");
while (i.hasNext())
System.out.println(i.next());
System.out.println();
i.restart();
System.out.println("Reversing the list.");
list.reverse();
while (i.hasNext())
System.out.println(i.next());
System.out.println();
}
}

[Jeff Verdegan]

 

Luke Stamper wrote:6) Keep track of the tail and add a method outputBackwards to prove the list is doubly linked.

I pretty much have everything covered except for #6. I'm having trouble with this. Can anyone provide some assistance? Thanks in advance.

So what problems are you having? You have a head element and know how to iterate forward, right? If so, then you know how to create a tail element and iterate backward.

[Luke Stamper]

You would think that...but I am getting confused iterating backwards.

[Luke Stamper]

Do I have to do everything the same with the tail as I did with the head? Every method?

[Jeff Verdegan]

 

Luke Stamper wrote:Do I have to do everything the same with the tail as I did with the head? Every method?

Well, no, I wouldn't say that. Certainly just don't blindly copy and paste everywhere you see "head". The point is, you understand how the head is used, what it means, and you understand how to iterate from the front using head. Right? I mean, you wrote this code yourself, yes?

So, given that understanding, you need to ask yourself, what does a "tail" variable mean? How do I set it, and when do I update it? How can I use it to iterate backwards? All the while, using head as an example (but not as the source for a pure mechanical duplication).

You should at least be able to give it a try, and as a more specific question if you get stuck.

[Luke Stamper]

So my outputBackwards and insertAfter methods aren't working.

And yes, this is my code. I wrote it with the help of my java tutor.

import java.util.NoSuchElementException;
public class LinkedList3<T> implements Cloneable
{
private class TwoWayNode<T>
{
private T item;
private TwoWayNode<T> next;
private TwoWayNode<T> prev;
public TwoWayNode()
{
item = null;
next = null;
prev = null;
}
public TwoWayNode(T newItem, TwoWayNode<T> previousNode, TwoWayNode<T> nextNode)
{
item = newItem;
prev = previousNode;
next = nextNode;
}
public TwoWayNode (T item) {
this(item, null, null );
}
}
public TwoWayNode<T> head;
public TwoWayNode<T> tail;
public LinkedList3()
{
head = null;
tail = null;
}
public LinkedList3(LinkedList3<T> otherList)
{
if(otherList == null)
throw new NullPointerException();
if (otherList.head == null)
head = null;
else
head = copyOf(otherList.head);
}
public LinkedList3<T> clone()
{
try
{
LinkedList3<T> copy = (LinkedList3<T>)super.clone();
if (head == null)
copy.head = null;
else
copy.head= copyOf(head);
return copy;
}
catch(CloneNotSupportedException e)
{
return null;
}
}
public TwoWayNode<T> copyOf(TwoWayNode<T> otherHead)
{
TwoWayNode<T> position = otherHead;
TwoWayNode<T> newHead;
TwoWayNode<T> end = null;
newHead = new TwoWayNode<T>(position.item, position.prev, null);
end = newHead;
position = position.prev;
while(position != null)
{
end.prev = new TwoWayNode<T>(position.item, position.prev, null);//position.prev
end = end.prev;
position = position.prev;
}
return newHead;
}
public boolean equals(Object otherObject)
{
if (otherObject == null)
return false;
else if (getClass( ) != otherObject.getClass( ))
return false;
else
{
LinkedList3<T> otherList = (LinkedList3<T>)otherObject;
if (size( ) != otherList.size( ))
return false;
TwoWayNode<T> position = head;
TwoWayNode<T> otherPosition = otherList.head;
while (position != null)
{
if (!(position.item.equals(otherPosition.item)))
return false;
position = position.prev;
otherPosition = otherPosition.prev;
}
return true; //no mismatch was not found
}
}
public String toString()
{
TwoWayNode<T> position = head;
String theString = "";
while (position != null)
{
theString = theString + position.item + "\n";
position = position.prev;//changed linked to prev (possibly head?)
}
return theString;
}
//Iterator Method
public class LinkedList3Iterator{
private TwoWayNode position = null;
public LinkedList3Iterator()
{
position = head;
}
public void restart(){
position = head;
}
public T next(){
if(!hasNext( ))
throw new IllegalStateException();
T toReturn = (T)position.item;
position = position.next;
return toReturn;
}
public boolean hasNext( )
{
return(position != null);
}
public void insertBefore(T newData)
{
if (position == null && head != null)
{
TwoWayNode<T> temp = head;
while (temp.next != head)
temp = temp.next;
temp.next = new TwoWayNode<T>(newData, temp, null);
}
else if (head == null || position.prev == null)
LinkedList3.this.addToStart (newData);
else
{
TwoWayNode<T> temp = new TwoWayNode(newData, position.prev, position);
position.prev.next = temp;
position.prev = temp;
}
}
public void insertAfter(T newData)
{
if (position == null && tail != null)
{
TwoWayNode<T> temp = tail;
while (temp.next != tail)
temp = temp.next;
temp.next = new TwoWayNode<T>(newData, temp, null);
}
else if (tail == null || position.prev == null)
LinkedList3.this.addToEnd (newData);
else
{
TwoWayNode<T> temp = new TwoWayNode(newData, position.prev, position);
position.prev.next = temp;
position.prev = temp;
}
}
public void delete()
{
if(position == null)
throw new IllegalStateException();
else if(position.prev == null)//changed previous to prev
{
head = head.next;
position = null;
}
else if(position.next == null)
{
position.prev.next = null;
position = null;
}
else
{
position.prev.next = position.next;
position.next.prev = position.prev;
position = position.next;
}
}
public T peek()
{
if(!hasNext())
throw new IllegalStateException();
return (T)position.item;
}
}
public void addToStart(T itemName)
{
TwoWayNode<T> newHead = new TwoWayNode(itemName, null, head);
if (head != null)
{
head.prev = newHead;
}
head = newHead;
}
public void addToEnd (T itemName)//********************
{
TwoWayNode<T> newTail = new TwoWayNode (itemName, null, tail);
if (tail != null)
{
tail.prev = newTail;
}
tail = newTail;
}
/**
Adds a node at the start of the list with the specified data.
The added node will be the first node in the list.
*/
private TwoWayNode next() {
if(head.next != null) return head.next;
else return head.prev;
}
private TwoWayNode last() {
if(tail.next != null) return tail.next;
else return tail.prev;
}
public void outputBackwards()
{
if(tail.next == null)
return;
TwoWayNode previous = tail;
TwoWayNode current = tail.next;
tail.next = null;
tail.prev = current;
while(current != null)
{
TwoWayNode next = current.next;
current.next = previous;
current.prev = next;
previous = current;
current = tail;
}
}
/**
Removes the head node and returns true if the list contains at least
one node. Returns false if the list is empty.
*/
public boolean deleteHeadNode( )
{
if (head != null)
{
head = head.prev;
return true;
}
else
return false;
}
/**
Returns the number of nodes in the list.
*/
public int size( )
{
int count = 0;
TwoWayNode<T> position = head;
while (position != null)
{
count++;
position = position.prev;
}
return count;
}
public boolean contains(T item)
{
return (find(item) != null);
}
/**
Finds the first node containing the target item, and returns a
reference to that node. If target is not in the list, null is returned.
*/
private TwoWayNode<T> find(T target)
{
TwoWayNode<T> position = head;
T itemAtPosition;
while (position != null)
{
itemAtPosition = position.item;
if (itemAtPosition.equals(target))
return position;
position = position.prev;
}
return null; //target was not found
}
/**
Finds the first node containing the target and returns a reference
to the data in that node. If target is not in the list, null is returned.
*/
public T findItem(T target)
{
return find(target).item;
}
public boolean isEmpty( )
{
return (head == null);
}
public void clear( )
{
head = null;
}
public LinkedList3Iterator iterator(){
return new LinkedList3Iterator();
}
}
public class LinkedList3Demo {
public static void main(String[] args) {
LinkedList3 list = new LinkedList3();
LinkedList3.LinkedList3Iterator i = list.iterator();
list.addToStart("shoes");
list.addToStart("hat");
list.addToStart("coat");
System.out.println("List contains: ");
i.restart();
while (i.hasNext())
System.out.println(i.next());
System.out.println();
i.restart();
i.next();
i.next();
System.out.println("Delete " + i.peek());
i.delete();
System.out.println("List now contains:");
i.restart();
while(i.hasNext())
System.out.println(i.next());
System.out.println();
i.restart();
i.next();
System.out.println("Inserting socks before " + i.peek());
i.insertBefore("socks");
i.restart();
System.out.println("List now contains: ");
while (i.hasNext())
System.out.println(i.next());
System.out.println();
i.restart();
i.next();
System.out.println("Inserting shoes after " + i.peek());
i.insertAfter("shoes");
i.restart();
System.out.println("List now contains: ");
while (i.hasNext())
System.out.println(i.next());
System.out.println();
i.restart();
System.out.println("Reversing the list.");
list.outputBackwards();
while (i.hasNext())
System.out.println(i.next());
System.out.println();
}
}

[Luke Stamper]

Does anything about those two methods look correct?

[Luke Stamper]

So it appears my outputBackwards method doesn't outputBackwards at all, it just outputs the list as is. Can anyone tell me why that is?

Also, i've gotten rid of the insertAfter method.

[Steve Luke]

When I do these sorts of things it always helps me to visualize what I need to do. I usually do it with pencil and paper, so I can redraw lines where needed. For example, I might start with something like this:



That would be my starting point, so I would use that the re-work where all my variables should point as I proceed.

The next thing to do is get a clear understanding of the requirements. What exactly is outputBackwards supposed to do? Is it supposed to reverse the direction of the list in-place? Is it supposed to return a new list with the order reversed? Or is it simply supposed to print the list like the toString() method, but backwards? You have to be clear on that before you do anything else.

Finally, you have this line as the first line in yur outputBackwards method:

if(tail.next == null)
return;

Looking at the picture above, can you see why that will always end the method before any other work is done?

[Luke Stamper]

It will always be null.

This is all I know about what I have to do....keep track of the tail and add a method outputBackwards to prove the list is doubly linked.

[Luke Stamper]

This still prints it in order. Ugh.

public void outputBackwards()
{
TwoWayNode head = null;
TwoWayNode temp = null;
TwoWayNode current = tail;
while(current != null)
{
temp = current.prev;
current.prev = current.next;
current.next = temp;
current = current.prev;
}
if(temp != null)
tail = temp.prev;
}

[Steve Luke]

Did you do the pencil/paper redrawing?

I got this after following the instructions you wrote line for line:



@edit: Last image had TAIL pointing to wrong spot.

[Luke Stamper]

I don't see why this method isn't working? I start at the tail, then display data until start of list moving to each link.

public void outputBackwards()
{
TwoWayNode current = tail; // start at end
while(current != null) // until start of list,
{
current.displayLink(); // display data
current = current.prev; // move to previous link
}
}

[Steve Luke]

i modified your TwoWayNode class to add the displayLink() method since you didn't show it:

 private class TwoWayNode<T> {
private T item;
private TwoWayNode<T> next;
private TwoWayNode<T> prev;
public TwoWayNode() {
item = null;
next = null;
prev = null;
}
public TwoWayNode(T newItem, TwoWayNode<T> previousNode, TwoWayNode<T> nextNode) {
item = newItem;
prev = previousNode;
next = nextNode;
}
public TwoWayNode(T item) {
this(item, null, null);
}
public void displayLink() {
System.out.println(this.item.toString());
}
}

I used your last posted outputBackwards() method:

 public void outputBackwards() {
TwoWayNode current = tail; // start at end
while (current != null) // until start of list,
{
current.displayLink(); // display data
current = current.prev; // move to previous link
}
}

And I changed your demo main method to remove unneeded tests (for this particular scenario):

public class LinkedList3Demo {
public static void main(String[] args) {
LinkedList3 list = new LinkedList3();
LinkedList3.LinkedList3Iterator i = list.iterator();
list.addToStart("shoes");
list.addToStart("hat");
list.addToStart("coat");
System.out.println("List contains: ");
i.restart();
while (i.hasNext())
System.out.println(i.next());
System.out.println();
i.restart();
System.out.println("Reversing the list.");
list.outputBackwards();
i.restart();
System.out.println("List now contains: ");
while (i.hasNext())
System.out.println(i.next());
System.out.println();
}
}

And the output is this:
List contains:
coat
hat
shoes
Reversing the list.
List now contains:
coat
hat
shoes

The key point in the output is between the "Reversing the list" line and the "List now contains:" line. Notice there is nothing there. Why would you get no output there if displayLink() method gets called and it prints the link value?

[Luke Stamper]

I don't have the link value anywhere.

I am not instructing my program to print the correct thing.

[Luke Stamper]

I have to pass the current data item into the print output to print the current item and then each additional item.

[Steve Luke]

 

Luke Stamper wrote:I don't have the link value anywhere.

You do have the value (item), because you can print it both before and after the 'reversal'

I am not instructing my program to print the correct thing.

That is close. in the code I posted it does tell it to print the item. But no items show up in the output... hmmm... maybe the displayLink() method never gets called. Why would the displayLink() method never get called? Looking at your outputBackwards() method, you have this:

public void outputBackwards() {
TwoWayNode current = tail; // start at end
while (current != null) // until start of list,
{
current.displayLink(); // display data
current = current.prev; // move to previous link
}
}

Why would current.displayLink() never get called? Not even once?

[Luke Stamper]

I've been staring at this for way too long.

It's not the loop. The tail is not null so it should go through the loop and print.

There is something wrong with the displayLink method. Something with the passing of arguments?

[Steve Luke]

 

Luke Stamper wrote:...The tail is not null...

Incorrect. When do you set the tail? Not in addToStart(), and addToStart() is the base for all your object inserts.

[Luke Stamper]

So I need to add the tail to addToStart?

[Luke Stamper]

I figured since I have TwoWayNode tail = current, that sets the current node to the tail, meaning the tail is not null.

[Luke Stamper]

I chaned my addToStart method to include the tail.

public void addToStart(T itemName)
{
TwoWayNode<T> newHead = new TwoWayNode(itemName, null, head);
TwoWayNode<T> newTail = new TwoWayNode(itemName, null, tail);
if (head != null)
{
head.prev = newHead;
}
head = newHead;
if (tail != null)
{
tail.prev = newTail;
}
tail = newTail;
}

[Steve Luke]

Almost there. Use pencil and paper to see where things point after one, two, three positions get added to the list this way. The final code for this method will be simpler than what you have, as far as the tail is concerned. For example, ask yourself: When do you have to worry about the tail when all you are doing is adding to the start of the list?

[Luke Stamper]

I think I have a better handle on my doublylinked list now...although I am experiencing a few errors still...

I am not sure if I should use the list or iterator before outputBackwards in linkedlist3demo class.

Am I on the right track with my outputBackwards method?

--------------------Configuration: <Default>--------------------
G:\Object Java\LinkedList3.java:217: error: ';' expected
return T position;
^
G:\Object Java\LinkedList3.java:217: error: not a statement
return T position;
^
G:\Object Java\LinkedList3.java:217: error: cannot find symbol
return T position;
^
symbol: variable T
location: class LinkedList3<T>
where T is a type-variable:
T extends Object declared in class LinkedList3
Note: Some input files use unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
3 errors

Process completed.

import java.util.NoSuchElementException;
public class LinkedList3<T> implements Cloneable {
private class TwoWayNode<T> {
public T item;
public TwoWayNode<T> next;
public TwoWayNode<T> previous;
public TwoWayNode(T it, TwoWayNode<T> previousNode, TwoWayNode<T> nextNode) {
item = it;
previous = previousNode;
next = nextNode;
}
public T displayItem() // display this link
{
return item;
}
}
private TwoWayNode<T> head;
private TwoWayNode<T> tail;
public LinkedList3() {
head = null;
tail = null;
}
public boolean isEmpty() {
return head == null;
}
public LinkedList3(LinkedList3<T> otherList) {
if (otherList == null) {
throw new NullPointerException();
}
if (otherList.head == null) {
head = null;
} else {
head = copyOf(otherList.head);
}
}
public LinkedList3<T> clone() {
try {
LinkedList3<T> copy = (LinkedList3<T>) super.clone();
if (head == null) {
copy.head = null;
} else {
copy.head = copyOf(head);
}
return copy;
} catch (CloneNotSupportedException e) {
return null;
}
}
public TwoWayNode<T> copyOf(TwoWayNode<T> otherHead) {
TwoWayNode<T> position = otherHead;
TwoWayNode<T> newHead;
TwoWayNode<T> end = null;
newHead = new TwoWayNode<T>(position.item, position.previous, null);
end = newHead;
position = position.previous;
while (position != null) {
end.previous = new TwoWayNode<T>(position.item, position.previous, null);
end = end.previous;
position = position.previous;
}
return newHead;
}
public boolean equals(Object otherObject) {
if (otherObject == null) {
return false;
} else if (getClass() != otherObject.getClass()) {
return false;
} else {
LinkedList3<T> otherList = (LinkedList3<T>) otherObject;
if (size() != otherList.size()) {
return false;
}
TwoWayNode<T> position = head;
TwoWayNode<T> otherPosition = otherList.head;
while (position != null) {
if (!(position.item.equals(otherPosition.item))) {
return false;
}
position = position.previous;
otherPosition = otherPosition.previous;
}
return true;
}
}
public class LinkedList3Iterator {
private TwoWayNode position = null;
public LinkedList3Iterator() {
position = head;
}
public void restart() {
position = head;
}
public T next() {
if (!hasNext()) {
throw new IllegalStateException();
}
T toReturn = (T) position.item;
position = position.next;
return toReturn;
}
public boolean hasNext() {
return (position != null);
}
public void insertBefore(T item) {
if (position == null && head != null) {
TwoWayNode<T> temp = head;
while (temp.next != head) {
temp = temp.next;
}
temp.next = new TwoWayNode<T>(item, temp, null);
} else if (head == null || position.previous == null) {
LinkedList3.this.addToStart(item);
} else {
TwoWayNode<T> temp = new TwoWayNode(item, position.previous, position);
position.previous.next = temp;
position.previous = temp;
}
}
public void delete() {
if (position == null) {
throw new IllegalStateException();
} else if (position.previous == null)
{
head = head.next;
position = null;
} else if (position.next == null) {
position.previous.next = null;
position = null;
} else {
position.previous.next = position.next;
position.next.previous = position.previous;
position = position.next;
}
}
public T peek() {
if (!hasNext()) {
throw new IllegalStateException();
}
return (T) position.item;
}
}
public void addToStart(T item) {
TwoWayNode<T> newHead = new TwoWayNode(item, null, head);
if (head != null) {
head.previous = newHead;
}
head = newHead;
}
/**
Adds a node at the start of the list with the specified data.
The added node will be the first node in the list.
*/
private TwoWayNode next() {
if (head.next != null) {
return head.next;
} else {
return head.previous;
}
}
public T outputBackwards() {
TwoWayNode position = tail; // start at end
while (position != null) // until start of list,
{
position.displayItem(); // display data
position = position.previous; // move to previous link
}
System.out.println("");
return T position;
}
/**
Removes the head node and returns true if the list contains at least
one node. Returns false if the list is empty.
*/
public boolean deleteHeadNode() {
if (head != null) {
head = head.previous;
return true;
} else {
return false;
}
}
/**
Returns the number of nodes in the list.
*/
public int size() {
int count = 0;
TwoWayNode<T> position = head;
while (position != null) {
count++;
position = position.previous;
}
return count;
}
public boolean contains(T item) {
return (find(item) != null);
}
/**
Finds the first node containing the target item, and returns a
reference to that node. If target is not in the list, null is returned.
*/
private TwoWayNode<T> find(T target) {
TwoWayNode<T> position = head;
T itemAtPosition;
while (position != null) {
itemAtPosition = position.item;
if (itemAtPosition.equals(target)) {
return position;
}
position = position.previous;
}
return null; //target was not found
}
/**
Finds the first node containing the target and returns a reference
to the data in that node. If target is not in the list, null is returned.
*/
public T findItem(T target) {
return find(target).item;
}
public void clear() {
head = null;
tail = null;
}
public LinkedList3Iterator iterator() {
return new LinkedList3Iterator();
}
}
public class LinkedList3Demo {
public static void main(String[] args) {
LinkedList3 list = new LinkedList3();
LinkedList3.LinkedList3Iterator i = list.iterator();
list.addToStart("shoes");
list.addToStart("hat");
list.addToStart("coat");
System.out.println("List contains: ");
i.restart();
while (i.hasNext())
System.out.println(i.next());
System.out.println();
i.restart();
i.next();
i.next();
System.out.println("Delete " + i.peek());
i.delete();
System.out.println("List now contains:");
i.restart();
while(i.hasNext())
System.out.println(i.next());
System.out.println();
i.restart();
i.next();
System.out.println("Inserting socks before " + i.peek());
i.insertBefore("socks");
i.restart();
System.out.println("List now contains: ");
while (i.hasNext())
System.out.println(i.next());
System.out.println();
i.restart();
System.out.println("Reversing the list.");
list.outputBackwards(); //should I use i or list?
while (i.hasNext())
System.out.println(i.next());
System.out.println();
}
}

[Steve Luke]

A few things:

1) the line you are having problems with is this:

 return T position;

Does that line look correct to you? For example, in the public boolean deleteHeadNode() method you return a boolean. Do you use this code?

 return boolean true;

2) The type of the return for the outputBackwards() method is T. T is the type of the item stored in a node. You are trying to return the position object, which is of type TwoWayNode, not of type T.

3) Does it make sense to return anything from the outputBackwards() method? If so, what should you return? The position as you are trying to do - which will be null by nature of the while() loop ending?

[Luke Stamper]

How about this?

public TwoWayNode<T> outputBackwards() {
TwoWayNode current = tail;
while (current != null)
{
current.displayItem();
current = current.previous;
}
return tail;
}

Do I also have to add something to actually print the nodes in the displayItem() method?

Such as...

public T displayItem()
{
System.out.print(item + " ");
return item;
}

[Luke Stamper]

Well, I don't think one can fully understand doublylinked lists until they force themselves to understand them until they 'actually' understand them.

In any case, for anyone following this entirely too long of a thread, here is my working code

import java.util.NoSuchElementException;
public class DoublyLinkedList<T> implements Cloneable {
private class TwoWayNode<T> {
public T item;
public TwoWayNode<T> next;
public TwoWayNode<T> previous;
public TwoWayNode(T it, TwoWayNode<T> previousNode, TwoWayNode<T> nextNode) {
item = it;
previous = previousNode;
next = nextNode;
}
public T displayItem()
{
return item;
}
}
private TwoWayNode<T> head;
private TwoWayNode<T> tail;
public DoublyLinkedList() {
head = null;
tail = null;
}
public boolean isEmpty() {
return head == null;
}
public DoublyLinkedList(DoublyLinkedList<T> otherList) {
if (otherList == null) {
throw new NullPointerException();
}
if (otherList.head == null) {
head = null;
} else {
head = copyOf(otherList.head);
}
}
public DoublyLinkedList<T> clone() {
try {
DoublyLinkedList<T> copy = (DoublyLinkedList<T>) super.clone();
return copy;
} catch (CloneNotSupportedException e) {
return null;
}
}
public TwoWayNode<T> copyOf(TwoWayNode<T> otherHead) {
TwoWayNode<T> position = otherHead;
TwoWayNode<T> newHead;
TwoWayNode<T> end = null;
newHead = new TwoWayNode<T>(position.item, position.previous, null);
end = newHead;
position = position.previous;
while (position != null) {
end.previous = new TwoWayNode<T>(position.item, position.previous, null);//position.prev
end = end.previous;
position = position.previous;
}
return newHead;
}
public boolean equals(Object otherObject) {
if (otherObject == null) {
return false;
} else if (getClass() != otherObject.getClass()) {
return false;
} else {
DoublyLinkedList<T> otherList = (DoublyLinkedList<T>) otherObject;
if (size() != otherList.size()) {
return false;
}
TwoWayNode<T> position = head;
TwoWayNode<T> otherPosition = otherList.head;
while (position != null) {
if (!(position.item.equals(otherPosition.item))) {
return false;
}
position = position.next;
otherPosition = otherPosition.next;
}
return true;
}
}
public class DoublyLinkedListIterator {
private TwoWayNode position = null;
public DoublyLinkedListIterator() {
position = head;
}
public void restart() {
position = head;
}
public T next() {
if (!hasNext()) {
throw new IllegalStateException();
}
T toReturn = (T) position.item;
position = position.next;
return toReturn;
}
public boolean hasNext() {
return (position != null);
}
public void insertBefore(T item) {
if (position == null && head != null) {
TwoWayNode<T> temp = head;
while (temp.next != head) {
temp = temp.next;
}
temp.next = new TwoWayNode<T>(item, temp, null);
} else if (head == null || position.previous == null) {
DoublyLinkedList.this.addToStart(item);
} else {
TwoWayNode<T> temp = new TwoWayNode(item, position.previous, position);
position.previous.next = temp;
position.previous = temp;
}
}
public void delete() {
if (position == null) {
throw new IllegalStateException();
} else if (position.previous == null)
{
head = head.next;
position = null;
} else if (position.next == null) {
tail = position.previous;
position.previous.next = null;
position = null;
} else {
position.previous.next = position.next;
position.next.previous = position.previous;
position = position.next;
}
}
public T peek() {
if (!hasNext()) {
throw new IllegalStateException();
}
return (T) position.item;
}
}
public void addToStart(T itemName) {
TwoWayNode<T> newHead = new TwoWayNode(itemName, null, head);
if (head != null) {
head.previous = newHead;
}
if(tail == null)
tail = newHead;
head = newHead;
}
private TwoWayNode next() {
if (head.next != null) {
return head.next;
} else {
return head.previous;
}
}
public void outputBackwards() {
TwoWayNode current = tail;
while (current != null)
{
System.out.println(current.displayItem());
current = current.previous;
}
}
public boolean deleteHeadNode() {
if (head != null) {
head = head.previous;
return true;
} else {
return false;
}
}
public int size() {
int count = 0;
TwoWayNode<T> position = head;
while (position != null) {
count++;
position = position.next;
}
return count;
}
public boolean contains(T item) {
return (find(item) != null);
}
private TwoWayNode<T> find(T target) {
TwoWayNode<T> position = head;
T itemAtPosition;
while (position != null) {
itemAtPosition = position.item;
if (itemAtPosition.equals(target)) {
return position;
}
position = position.previous;
}
return null;
}
public T findItem(T target) {
return find(target).item;
}
public void clear() {
head = null;
tail = null;
}
public DoublyLinkedListIterator iterator() {
return new DoublyLinkedListIterator();
}
public String toString(){
String output = "";
TwoWayNode<T> position = head;
while (position != null) {
output = output + position.item + " ";
position = position.next;
}
return output;
}
}
public class DoublyLinkedListDemo {
public static void main(String[] args) {
DoublyLinkedList list = new DoublyLinkedList();
DoublyLinkedList copyList = new DoublyLinkedList();
DoublyLinkedList.DoublyLinkedListIterator i = list.iterator();
list.addToStart("guitar");
list.addToStart("mandolin");
list.addToStart("fiddle");
System.out.println("List contains: ");
i.restart();
while (i.hasNext())
System.out.println(i.next());
System.out.println();
i.restart();
i.next();
i.next();
System.out.println("Deleting " + i.peek());
i.delete();
System.out.println("List now contains: ");
i.restart();
while(i.hasNext())
System.out.println(i.next());
System.out.println();
i.restart();
i.next();
System.out.println("Inserting banjo before " + i.peek());
i.insertBefore("banjo");
i.restart();
System.out.println("List now contains: ");
while (i.hasNext())
System.out.println(i.next());
System.out.println();
i.restart();
System.out.println("Reversing the list...");
list.outputBackwards();
System.out.println();
i.restart();
System.out.println("Printing clone of DoublyLinkedList ");
copyList = list.clone();
System.out.println(copyList);
System.out.println();
System.out.println("Are they equal? " + list.equals(copyList));
System.out.println();
i.restart();
System.out.println("Size of list is...");
System.out.println("list has " + list.size() + " nodes");
System.out.println();
i.restart();
System.out.println("Searching for " + i.peek());
System.out.println(list.contains("fiddle"));
System.out.println(i.peek() + " is in the list");
System.out.println();
i.restart();
System.out.println("Searching for guitar");
System.out.println(list.contains("guitar"));
System.out.println("guitar is not in the list");
System.out.println();
System.out.println("List contains: ");
i.restart();
while (i.hasNext())
System.out.println(i.next());
System.out.println();
}
}