List Class Update

The List class is currently keeping track of the beginning and end of the linked list with a master element. The master element is created when the list is created. A list element contains a previous element and next element link pointers along with the value of the element. The amount of memory allocated for the master element is less the element value using a strange syntax for subtracting the size of the value from the total size of the element – not ideal.

When a list is created, the links of the master element are set to point to the master element itself.  The list is empty when the master element's next and previous pointers are the same as the master element pointer. When linking through the list, the first element is the master element's next pointer. The end of the list is detected when the master element is reached when linking to an element's next pointer.

In considering a design for the token linked list, it was realized that the master element is not really necessary. All that is needed is a pointer to the first element in the list. Or, for a first-in-last-out list, a pointer to the last element. The last pointer method will be used and the variable will be named tail. The list is linked circularly meaning that the last element's next pointer points to the first element in the list and the first element's previous pointer points to the last element. If the list is empty, then tail will be set to NULL.

Using the single tail pointer, the first element in the list is now obtained using tail->next assuming the list is not empty, otherwise NULL will be returned. The last element is now obtained simply by using tail. When appending items to end of the list, the new element is linked into the list and tail is set to the new element. When removing the last element from the list, a check is needed to see if the list is empty after removing the item.