This implements a single linked list consisting of nodes and dataElements. The list itself is made up of nodes. Each node has a pointer to the next node in the list and a pointer to a dataElement. The idea is that dataElements are essentially separate from the list and you can modify the definition of a dataElement at any time. For this example a dataElement has just a char * key and a numeric id.
One design decision I made is to use typedefs for all pointers - in the entire application, the only place you will see a * used for a pointer is in these three lines. That minimizes the chance of removing a * and breaking something. I also believe that it makes the code easier to read and understand.
typedef struct dataElement * pElement;To access a member of a struct accessed by pointer, the arrow notation is used.
typedef struct Node * pNode;
typedef char * pChar;
if (result->data)This is the same as
if ((*result).data)but a lot more readable and the arrow notation is used in C++ for accessing object methods via a pointer.
The list is maintained by two pNode pointers called tail and head. Once the list is built, head always points to the head of it- the first element and tail always points to the last element. It's efficient in that it saves having to loop through all nodes from the head forward to find the last element. Note that this is not a circular list and so the next pointer in the last node must always be 0 (or NULL).
I've given each dataElement a couple of fields- one is id, just a number that starts at 0 and auto increments by 1 for each node. The other is key and the idea is that you can search for a matching key using the function findKey(). This searches the list from head to tail.
On the next page : Example 1 Continued
