C double linked list with abstract data type

Question

I need a double list in C, but it should be for different types. In C ++, we use templates for this. Where can I find an example in C for a double linked list with elements of an abstract type.

thanks

Answer 1

There are several approaches you can take, one of which involves saving void* in your ADT.

I always thought this was a bit of a pain in a linked list, since you need to distribute it separately for the list itself. In other words, to highlight a node, you need to isolate both node and your payload separately (and remember to also clear both of them when deleting).

One approach I've used in the past is to have a variable-sized structure, for example:

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

Now it does not look variable in size, but it allows you to highlight the structure in this way:

 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, which for all purposes and goals 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, if you know how to handle 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"); 

This cast line simply passes the payload symbol address (in type tNode ) as the address of the actual payload type tPerson .

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

 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 of what the payload really is.

This has the advantage over combining that it does not waste space, as can be seen from the following:

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

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

The payload type in tNode allows you to easily determine what type of payload this node carries, so your code can decide how to handle it. You can use something line by line:

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

or (maybe better):

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

The only thing you need to pay attention to is to make sure that the payload alignment is correct. Since both my mailbox and payload are all char types, this is not a problem. However, if your payload consists of types with more stringent alignment requirements (for example, something more stringent than pointers, you might need to tweak it).

So far, I have never seen an environment with stricter settings than pointers, this is possible in accordance with the ISO C standard.

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

 long payload; 

---

In retrospect, it occurs to me that you probably don't need an array as a payload placeholder. It is simple enough to just get something that you can accept at the address. I suspect that my particular idiom dates back to the times when I just kept an array of characters (not a structure) and referenced them directly. In this case, you can use payload[] yourself without dropping another type.

Answer 2

Processing arbitrary data in C is usually done using pointers - especially void * in most cases.

Answer 3

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

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

Macros at first look a little strange, but easy to use and will soon become second nature. They can be trivially adapted for use in user space (see list.h ).

Answer 4

The closest look at C to an object's base class or template types is the void pointer. A void * is a pointer to something, but does not indicate what type of data is being indicated. If you want to access data, you need to use a listing.

A bidirectional node list might look like this:

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

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

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

To return a string from node, you use cast:

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

To save a non pointer, you need to make a pointer to the data. For structures, you can simply dereference an instance if its service life is long enough (similar to the example above). If not, or if you are dealing with a primitive type (like int or float ), you need some malloc space. Just remember to free your memory when you're done.

Answer 5

You can use macros as shown here (this particular example implements shared hash tables).