C double linked list with abstract data type

Question

i need in double linked list in C, but it must be for different types. In C++ we use templates for it. Where can i find example in C for double linked list with abstract types items.

Thank you

Answer 1

There are a few approaches you can take, one of which involves storing a void* in your ADT.

I've always found this to be a bit of a pain in a linked list since you have to manage it's allocation separately to the list itself. In other words, to allocate a node, you need to alocate both the node and its payload separately (and remember to clean them both up on deletion as well).

One approach I've used in the past is to have a 'variable sized' structure like:

typedef struct _tNode {
    struct _tNode *prev;
    struct _tNode *next;
    char payload[1];
} tNode;

Now that doesn't look variable sized but let's allocate a structure thus:

typedef struct {
    char Name[30];
    char Addr[50];
    char Phone[20];
} tPerson;
tNode *node = malloc (sizeof (tNode) - 1 + sizeof (tPerson));

Now you have a node that, for all intents and purposes, looks like this:

typedef struct _tNode {
    struct _tNode *prev;
    struct _tNode *next;
    char Name[30];
    char Addr[50];
    char Phone[20];
} tNode;

or, in graphical form (where [n] means n bytes):

+------------+
| prev[4]    |
+------------+
| next[4]    |
+------------+ +-----------+
| payload[1] | | Name[30]  | <- overlap
+------------+ +-----------+
               | Addr[50]  |
               +-----------+
               | Phone[20] |
               +-----------+

That is, assuming you know how to address the payload correctly. This can be done as follows:

node->prev = NULL;
node->next = NULL;
tPerson *person = &(node->payload); // cast for easy changes to payload.
strcpy (person->Name, "Richard Cranium");
strcpy (person->Addr, "10 Smith St");
strcpy (person->Phone, "555-5555");

That cast line simply casts the address of the payload character (in the tNode type) to be an address of the actual tPerson payload type.

Using this method, you can carry any payload type you want in a node, even different payload types in each node, if you make the structure more like:

typedef struct _tNode {
    struct _tNode *prev;
    struct _tNode *next;
    int payloadType;       // Allows different payload type at each node.
    char payload[1];
} tNode;

and use payloadType to store an indicator as to what the payload actually is.

This has the advantage over a union in that it doesn't waste space, as can be seen with the following:

union {
    int fourBytes;
    char oneHundredBytes[100];
} u;

where 96 bytes are wasted every time you store an integer type in the list (for a 4-byte integer).

The payload type in the tNode allows you to easily detect what type of payload this node is carrying, so your code can decide how to process it. You can use something along the lines of:

#define PAYLOAD_UNKNOWN     0
#define PAYLOAD_MANAGER     1
#define PAYLOAD_EMPLOYEE    2
#define PAYLOAD_CONTRACTOR  3

or (probably better):

typedef enum {
    PAYLOAD_UNKNOWN,
    PAYLOAD_MANAGER,
    PAYLOAD_EMPLOYEE,
    PAYLOAD_CONTRACTOR
} tPayLoad;

The only thing you need to watch out for is to ensure that the alignment of the payload is correct. Since both my payload placeholder and the payload are all char types, that's not an issue. However, if your payload consists of types with more stringent alignment requirements (such as something more strict than the pointers, you may need to adjust for it).

While I've never seen an environment with alignments more strict than pointers, it is possible according to the ISO C standard.

You can usually get the required alignment simply by using a data type for the payload placeholder which has the strictest alignment requirement such as:

long payload;

---

In retrospect, it occurs to me that you probably don't need an array as the payload placeholder. It's simple enough to just have something you can take the address of. I suspect that particular idiom of mine hearkens back to the days where I just stored an array of characters (rather than a structure) and referenced them directly. In that case, you could use payload[] on its own without casting to another type.