FIFO implementation

Question

While implementing a FIFO I have used the following structure:

struct Node
{
    T info_;
    Node* link_;
    Node(T info, Node* link=0): info_(info), link_(link)
    {}
};

I think this a well known trick for lots of STL containers (for example for List). Is this a good practice? What it means for compiler when you say that Node has a member with a type of it's pointer? Is this a kind of infinite loop?

And finally, if this is a bad practice, how I could implement a better FIFO.

EDIT: People, this is all about implemenation. I am enough familiar with STL library, and know a plenty of containers from several libraries. Just I want to discuss with people who can gave a good implementation or a good advice.

Answer 1

Is this a good practice?

I don't see anything in particular wrong with it.

What it means for compiler when you say that Node has a member with a type of it's pointer?

There's nothing wrong with a class storing a pointer to an object of the same class.

And finally, if this is a bad practice, how I could implement a better FIFO.

I'd use std::queue ;)

Answer 2

Obviously you are using linked-list as the underlying implementation of your queue. There's nothing particularly bad about that.

Just FYI though, that in terms of implementation, std::queue itself is using std::deque as its underlying implementation. std::deque is a more sophisticated data structure that consists of blocks of dynamic arrays that are cleverly managed. It ends up being better than linked list because:

1. With linked-list, each insertion means you have to do an expensive dynamic memory allocation. With dynamic arrays, you don't. You only allocate memory when the buffer has to grow.
2. Array elements are contiguous and that means elements access can be cached easily in hardware.