C double linked list with abstract data type

Question

Hello,

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

Handling arbitrary data in C is usually done by using pointers - specifically void * in most cases.

Answer 2

The closest think in C to an "object" base class or templated types is a void pointer. A void * represents a pointer to something, but it does not specify what type of data is being pointed to. If you want to access the data, you need to use a cast.

A doubly linked list node could look like this:

struct DoubleLinkedListNode {
    struct DoubleLinkedListNode *previous, *next;
    void *data;
};

To assign a node a string, for example, you could do:

char myString[80] = "hello, world";
struct DoubleLinkedListNode myNode;
myNode.data = myString;

To get the string back from a node, you use a cast:

char *string = (char *)myNode.data;
puts(string);

To store a non-pointer, you need to make a pointer from the data. For structures, you may be able to simply dereference the instance if its lifetime is long enough (similar to the above example). If not, or if you're dealing with a primitive type (e.g. an int or float), you need to malloc some space. Just be sure to free the memory when you're done.

Answer 3

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.

Answer 4

You could use macros as demonstrated here (this particular example implements generic hash-tables).

Answer 5

Obviously, the linux kernel uses linked lists in many, many places both in the kernel itself and in the many device driver modules. Almost all of these are implemented using the same a set of macros defined in linux/list.h

See http://isis.poly.edu/kulesh/stuff/src/klist/ or http://kernelnewbies.org/FAQ/LinkedLists for a good explanation.

The macros look a bit strange at first but are easy to use and soon become second nature. They can trivially be adapted for use in user space (see list.h).