circular linked lists
-
All, I need to implement a circular linked list of circular linked lists. I can generate the individual linked lists just fine but can't quite figure out how to link the lists together. My node has pointers to a right node and a down node. So, a list would be node->right to node->right etc, but I can't figure out how to link a list using the down pointer without loosing the pointer to the first node. Any advice? Thanks in advance (and I hope this makes sense...) John
-
All, I need to implement a circular linked list of circular linked lists. I can generate the individual linked lists just fine but can't quite figure out how to link the lists together. My node has pointers to a right node and a down node. So, a list would be node->right to node->right etc, but I can't figure out how to link a list using the down pointer without loosing the pointer to the first node. Any advice? Thanks in advance (and I hope this makes sense...) John
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.
ptrNextpoints to the next cell in the primary list, andptrDownpoints 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 inptrNextIn the primary list, thenNumberentry 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'sptrDownvalue 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.