It depends.
Is it a circular or linear list?
If it's a circular list then there is no "head" or "tail" as each element's next
and prev
pointers will be set. You can start traversing the list anywhere and have to remember where you started so you know when to stop.
If it's a linear list then the prev
pointer of the head element will be null
and the next
pointer of the tail element will be null
. You use this information to know when to stop.
I hope it's ok to answer my own question.
I believe I have found the optimal (without overcomplicating the problem) data structure for my problem. There was at least minor idiocy on my part for not recognising this earlier. The data doesn't need to be accessed by (x,y,z) but instead by (x, y, range of z (say 0 - 3)). This give a C++ struct as follows:
struct node {
struct node *next;
int zGroup;
int z;
50 bytes of misc data };
I can then address this through a 3D dynamic array (vectors):
vector< vector < vector < node* > > > Data;
Any given Data[x][y][zGroup]
points to the first element of a linked list, the entirety of which is needed every time one element of it is needed. No value of this array is NULL, every one contains a linked-list of at least one element.
The third dimension of the array - the zGroup has jagged dimensions, but with dynamic arrays this isn't an issue. Given the data and computations being performed on it, I know that the max x and y values are set when the file is read and do not change, neither does the number of z groups on any given (x,y) line, the actual z-values of nodes may change, but they will remain inside the same z-groups, giving a constant-sized, fully populated array.
With the way that the file is structured it is also easy enough to page it in and out of memory if I am brought to do this with much larger data sets.
Best Answer
You are correct, a tail pointer never hurts and can only help. However, there is a situation where one does not need a tail pointer at all.
If one is using a linked list to implement a stack, there is no need for a tail pointer because one can guarantee that all accesses, insertions, and removals occur at the head. That being said one might use a doubly-linked list with a tail pointer anyway because that is the standard implementation in a library or platform and memory is cheap, but one does not need it.