The solution is to think in 3D. First, consider that you have a circle of cells. This represents the top level linked list. Each cell contains an index number (integer) and a pointer to the next node of the circle. This linked list is called 'primary list'. Now, enhance each of these cells so that they also contain a second pointer. Each of these cells becomes the first cell of a secondary linked list that rotates from the 2D plane up, does a circle, and returns down again. The second pointer points to the next cell of the secondary linked list. Here is a declaration of the cell structure
struct Node {
int nNumber;
element_type* ptrNext;
element_type* ptrDown;
};
The primary linked list has valid values in all entries. ptrNext points to the next cell in the primary list, and ptrDown points to the next cell in the secondary list. The secondary list has two types of cells: a) Members of the primary and secondary lists, with valid values in all entires b) Members of the secondary list only, with a NULL value in ptrNext In the primary list, the nNumber entry contains an index number that identifies an individual list from the chain, e.g. list at index position 1. In order to keep it simple, you could use negative values in the primary chain, and positive values in secondary chains. This would make it easy to identify any given cell: if it's value is negative, it's the linking cell between a secondary and a primary list. If it's positive, it's an individual cell in some secondary list. If the above was implemented, then those cells with negative values would be the headers of the secondary lists, as stated in ADT language. The primary linked list might also have a header. This header's ptrDown value should be NULL, or index value should be 0, to seperate it from the other members of the primary list and the members of the secondary lists. -Antti Keskinen ---------------------------------------------- The definition of impossible is strictly dependant on what we think is possible.
