singly linked list and doubly linked list

[firattag]

Hi everyone,
I have configured singly linked list and doubly linked list but I could not understand the following concepts.Could you explain briefly with an example this concepts to me?



1.Intrusive singly linked list
2.Intrusive doubly linked list

thanks in advance...

[Lindley]

In a normal linked list, the nodes are allocated on the heap and look something like this:

template <typename T>
struct Node
{
    T data;
    Node *next;
};

In an intrusive list, the next pointer is assumed to be part of the T datatype, so there's no need to create a wrapper structure to store it separately. This also means there's no particular need for the nodes of the list to be on the heap; you can create a linked list of T objects "in-place", wherever the objects happen to already be, just by modifying their next pointers.

[firattag]

In a normal linked list, the nodes are allocated on the heap and look something like this:

template <typename T>
struct Node
{
    T data;
    Node *next;
};

In an intrusive list, the next pointer is assumed to be part of the T datatype, so there's no need to create a wrapper structure to store it separately. This also means there's no particular need for the nodes of the list to be on the heap; you can create a linked list of T objects "in-place", wherever the objects happen to already be, just by modifying their next pointers.

template <typename T>
struct Node
{
    T data;
    Node *next;
};

this is now intrusive linked list,

Will you give an example for nonintrusive ???

[JohnW@Wessex]

In an intrusive linked list, the data also plays the part of the node.

struct Data
{
    // Other data members...

    Data *next;
};

[firattag]

what is nonitriusive linked list?

[JohnW@Wessex]

As posted above.
The data is stored in a node, but takes no part in the linking of the list of nodes.

struct Node
{
    Data data;
    Node *next;
};