Most elegant way to implement a circular list (FIFO)

Question

What is the most elegant and simple way to implement a circular list, FIFO style? I'm looking for a solution that doesn't resort to hacks like catching exceptions.

No, this is not for homework.

For a little background, I want to use a circular list within GWT; so using a 3rd party lib is not what I want.

Edit: In order to clarify, I referred to FIFO because I basically need a cache. Instead of expiring by oldest/youngest/whatsoever, I thought on evicting the first inserted element, but a circular list already gives me that :) So ignore the FIFO stuff.

Answer 1

FIFO is a property of queues, not circular lists.

Circular lists doesn't have a tail (where new nodes will enter) nor header (where the nodes will be removed) sistematicaly.

Can you give more information about it?

Answer 2

Use a linked list. Maintain separate pointers for the head and tail. Pop from the head of the list, push onto the tail. If you want it circular, just make sure the new tail always points to the head.

I can understand why you might want to implement a FIFO using a linked list, but why make it a circular list?

Answer 3

Use an array and keep a variable P with the first available position.

Increase P every time you add a new element.

To know the equivalent index of P in your array do (P % n) where n is the size of your array.

Answer 4

A very simple implementation, expressed in C. Implements a circular buffer style FIFO queue. Could be made more generic by creating a structure containing the queue size, queue data, and queue indexes (in and out), which would be passed in with the data to add or remove from the queue. These same routines could then handle several queues. Also note that this allows queues of any size, although speedups can be used if you use powers of 2 and customize the code further.

/* Very simple queue
 * These are FIFO queues which discard the new data when full.
 *
 * Queue is empty when in == out.
 * If in != out, then 
 *  - items are placed into in before incrementing in
 *  - items are removed from out before incrementing out
 * Queue is full when in == (out-1 + QUEUE_SIZE) % QUEUE_SIZE;
 *
 * The queue will hold QUEUE_ELEMENTS number of items before the
 * calls to QueuePut fail.
 */

/* Queue structure */
#define QUEUE_ELEMENTS 100
#define QUEUE_SIZE (QUEUE_ELEMENTS + 1)
int Queue[QUEUE_SIZE];
int QueueIn, QueueOut;

void QueueInit(void)
{
    QueueIn = QueueOut = 0;
}

int QueuePut(int new)
{
    if(QueueIn == (( QueueOut - 1 + QUEUE_SIZE) % QUEUE_SIZE))
    {
        return -1; /* Queue Full*/
    }

    Queue[QueueIn] = new;

    QueueIn = (QueueIn + 1) % QUEUE_SIZE;

    return 0; // No errors
}

int QueueGet(int *old)
{
    if(QueueIn == QueueOut)
    {
        return -1; /* Queue Empty - nothing to get*/
    }

    *old = Queue[QueueOut];

    QueueOut = (QueueOut + 1) % QUEUE_SIZE;

    return 0; // No errors
}

Answer 5

If you want a fixed length circular list. You can use a (dynamic) array. Use two variables for houskeeping. One for the position of the next element, one to count the number of elements.

Put: put element on free place. move the position (modulo length). Add 1 to the count unless count equals the lengtht of the list. Get: only if count>0. move the position to the left (modulo length). Decrement the count.