Out: 18 October, 2001 Due: 1 November, 2001A linked list with only a next pointer makes it difficult to traverse a list backwards. If traversing the list backwards will be a common operation, than linking the list in both forwards and backwards directions is a possibility. The backwards links are customarily called prev.
class NodeDoublyLinked
{
NodeDoublyLinked next ;
NodeDoublyLinked prev ;
Object v ;
}
Here I've defined a node capable of storing arbitrary objects
in a doubly linked list, because the value slot v requires only
that the object be of type Object. Recall that in Java all objects
inherit from Object, and so are of type Object.
Inserting and removing items from a doubly linked list requires
updates to both the next and prev fields. Just as the end of a
list is marked by (next==null), you may want to mark the head
of a list by (prev==null).
Rewrite Homework 2 for doubly linked lists.
Here are some Data Structure Invariants to think about:
(n.next==null) || (n.next.prev==n)
(n.prev==null) || (n.prev.next==n)
Any time a doubly linked list has a node in it which doesn't
fit the invariant, you've got a sick list. Doing a delete, you
can assume that the invariant is satisfied, and make sure you fix
up the list after the delete so that the invariant is satisfied
again. You will just have to look at nodes that directly touch
the deleted node.
Consider what special cases you will have and how you will handle them. For instance, a node in the middle of the list will require an update to some node's prev field, while deleting the last node affects no prev fields. Somehow, an if statement will be necessary to split the code flow according to these cases.
Good luck.