//Copyright Dr. Marek A. Suchenek, 2005, 2006, 2007, 2008, 2009


AXIOMATIC DEFINITION OF DLL

1. Empty structure is DLL

2. Non-empty DLL L is L.head followed by DLL L.tail

3. Function .nose is the inverse of function .tail ans is defined for each non-empty DLL L by:

			L.tail.nose = L.nose.tail = L
			
Implementation: L.nose is the position of the head of L on list L.



POSITION is a non-empty list, that is, an element (head) followed by a LIST (tail).

public class POSITION
{
	public Object head;
	public POSITION tail;
	public POSITION nose;

// some methods follow
}


Object of class POSITION always points to the previous element (for an extra level of indirection).

Definition of position of an element x in a list L: a subtail N of list L such that x is the head of tail of N.

Subtail of a list L is either L itself or (if L is non-empty) a subtail of tail of L.

 

A trick

To make functions .tail and .nose total (the inverses of each other), they are extended,
in a circular fasion, beyond last (.tail) and first (.nose) element.