What is a linked list that defines no data storage called? [closed]

Question

As it currently stands, this question is not a good fit for our Q&A format. We expect answers to be supported by facts, references, or expertise, but this question will likely solicit debate, arguments, polling, or extended discussion. If you feel that this question can be improved and possibly reopened, visit the help center for guidance.

Closed 9 years ago.

I'm using singly linked lists, in C, without the pointer to the node value. So, instead of:

struct _node 
{
  struct _node * next;
  void* value;
} node;

I have

struct _node 
{
   struct _node * next;
} node;

Is there a special name for lists like that?

EDIT:

Just to explain why these lists are useful (I really don't understand why the downvotes):

struct 
{
  node node;
  int i;
} s;

When I do this, I'm forcing struct s to have a node, but without having to set the void* value.

I'm using this scheme to save my tasks information, which will be on a FIFO list.

Answer 1

This is how the linux kernel implements linked lists for example. Check out this link or this link or many others describing their linked list implementation

As to your actual question, I don't believe that there is an actual name to that pattern. It's simply a way of doing a generic linked list in C.

Answer 2

I'm not sure that this has a name. Still it's a useful way to build a linked list, because you can put the link with the data but still keep the two separated.

typedef struct _payload
{
    int x;
    double y;
    char * z;
} payload;

struct _node * pNode;
payload * pData;
pNode = malloc(sizeof(struct _node)+sizeof(payload));
pData = (payload *)(((char*)p)+sizeof(struct _node));

Answer 3

Are you talking about moving the "list mechanics" to a separate structure:

struct Single_Link;
struct Single_Link
{
    Single_Link * next;
};

From the above structure, you can derive:

struct Double_Link_Node
: public Single_Link_Node
{
    Single_Link * previous;
};

Using the above structure, you can define a generic node:

template <class Value_Type>
struct Node_Contains_Value
: public Single_Link
{
    Value_Type value;
};

Or you could use a generic pointer to a value:

struct Node_Contains_Pointer
: public Single_Link
{
    void * pointer_to_value;
};

The Linked List would maintain a pointer to the first node:

template <class Value_Type>
struct Linked_List
{
    Node_Contains_Value * ptr_to_head_node;
    Node_Contains_Value * ptr_to_last_node;
};

If this is not homework, I highly recommend using the std::list as it has been thorougly tested.

Answer 4

I think C programmers just refer to this as a "linked list" and consider it the "normal" form of a linked list. It's only in languages that encourage more bloated idioms that having a pointer to your data in list nodes, rather than just storing the node and the data together, is the norm.