use of generic list

Question

struct node 
{ 
    void *data; 
    struct node *link;    
};

Given such a structure we call it as generic linked list.what is the use of such a list in terms of its real time application use.

can you please reformulate your question and give a bit of context to understand what you mean with "what is the use of such a list in terms of its real time application use" ? Thanks. — Manuel Salvadores, Dec 20 '10 at 11:07

score 2 · Answer 1 · answered Dec 20 '10 at 11:08

It's genericness allows you to create some (tested and reliable) library code around it, which can then be reused.

Of course it's not typesafe this way, that's why C++ introduced (among other things) generic template classes.

As for the use of a linked list per se: you use it where you want to store and retrieve a variable number of similar objects. Typically you don't know the number of the objects in advance and you are fine with getting them in the order you stored them. It's also quite efficient to delete an object from a linked list (once you have a pointer to its list entry).

score 1 · Answer 2 · answered Dec 20 '10 at 11:29

what is the use of such a list in terms of its real time application use

If all you have is that definition and a pointer to the head of the list, then its only good for creating a arbitrary stack of objects. This is because to do anything except add or remove an object to the head of the list you have to iterate through it. Even with this limited "efficiency", such a list has its uses e.g. as a cache for unused heap objects that you are going to recycle to avoid mallocs.

If you also have a pointer to the tail of the list, you can add objects to either end in O(1) time. This means you can use it as a queue.

If each item has a pointer to its predecessor as well as successor, you can also insert/delete items from any point in the list in O(1) time. Of course, you still need to find the object which might involve a linear scan.

score 1 · Accepted Answer · edited May 23 '17 at 12:04

You have a service which accepts requests from multiple applications and provides handle to each of them. The service can maintain the contexts per request in a linked list and when its done serving them delete the node from the list. A empty linked list in that case would mean no application has registered to the service.

For Eg, Consider the service built over SIP stack and multiple applications like IM, Presence information can register with the service which uses the SIP stack for signalling. Now the service maintains the data pertaining to each of the application in a linked list(well that is again a question of design but lets assume we have a limit to serve 5 applications). The SIP response has to be redirected to the application sending the request and say you hold the callback pointer as one value of the node it is simple to call it once you find the corresponding node for the response.

Each node saves lot of information about every application and uses it for sending back the response to the application.

Probably you may want to have a look at this.

use of generic list

3 Answers3