Question: Our homework assignment asks us to prove that the Java `LinkedList` implementation is doubly-linked and not singly-linked. However, list operations such as adding elements, removing elements, and looking elements up seem to have the same complexity for both implementations, so there doesn't seem to be a way to use a performance argument to demonstrate the doubly-linked nature of Java's `LinkedList`. Anyone know of a better way to illustrate the difference between the two?

Answer: 
Look at iterating in forward or backward direction, removing the "before-last" element, and such.
Consider the following nodes, single and double.

class SingleLinkedNode {
 E data;
 SingleLinkedNode next;
}

class DoubleLinkedNode {
 E data;
 DoubleLinkedNode prev;
 DoubleLinkedNode next;
}

If we want to remove from a DoubleLinkedList (assuming we have already FOUND the node, which is very different) what do we need to do?

1. Make the node before the deleted
one point to the one after.
2. Make the node after the deleted one point to the one before.

If we want to remove from a SingleLinkedList (assuming we have already FOUND the node, which is very different) what do we need to do?

1. Make the node before the deleted one point to the one after.

You'd think that means it's even faster in a single linked list than a double.

But, how are we doing to delete the node if we don't have a reference to the one before it? We only have a reference to the next. Wouldn't we have to do a whole other search on the list just to find prev? :-O