Does a Standard Implementation of a Circular List Exist for C++

Does a standard implementation of a Circular List exist for C++?

There's no standard circular list.

However, there is a circular buffer in Boost, which might be helpful.

If you don't need anything fancy, you might consider just using a vector and accessing the elements with an index. You can just mod your index with the size of the vector to achieve much the same thing as a circular list.

Is std::list circular?

There are actually two levels to this question:

---

The language standard semantics answer

This answer has already been given by Bathsheba, which is basically that the prescribed behavior of an std::list<> does not include any circularities. When you increment the iterator past the end of the list, you enter the territory of undefined behavior, and all bets are off. Your program is allowed to print "You've been pwnd!" instead of the "10".

---

The implementation detail answer

The standard does not prescribe whether an std::list<> is circular or not. It only describes some observable behavior, and leaves some other behavior undefined. This allows the implementators of std::list<> some leeway to implement the list in the way they see fit.

Looking at the requirements of an std::list<>, we see that it

• must support bidirectional iterators and

• must provide an end() iterator in constant time.

Putting the two together, we see that decrementing the end() iterator is well defined on non-empty lists, and must yield an iterator to the last element of that list.

For the implementator, this means that

• the list should be double linked (to support increment and decrement),

• there must be a dummy iterator that end() can return, and

• the dummy iterator must actually contain a pointer to the last element of the list.

It is possible to implement such a double linked list with either:

• A pointer to the first element in the list's own object + a dummy iterator that only contains the pointer to the last element.

• Two dummy iterators, one before the first element, and one after the last element. The iterator at the beginning would only provide a forward pointer, the iterator at the end would only provide a backward pointer.

• Or just fuse the two dummy iterators together into a single object, using both the forward and backward pointers and making it only special in that it does not contain any data. This is the circular list approach.

The first two approaches introduce a lot of special handling of first elements, last elements and empty lists. That's not good. The third approach has no such special handling: The empty list simply links the dummy to itself on the forward and backward reference, and any list item addition/removal is just adding/removing an iterator between two already existing ones. This greatly simplifies the code.

As such, most implementators will opt for a circular implementation. It's the sane choice. The people who wrote the std::list<> you are using, seem to be of the sane kind. But there is no guarantee. They could replace their current implementation with a more complex one for no good reason at all, and ship that with the next release of their standard C++ library implementation. Your program might not print 10 anymore, or even print anything at all. It could also install a bitcoin miner instead. The C++ standard would not care: As long as the std::list<> provides the prescribed behavior, the implementation is free to do any bullshit it likes when you step across the line marked "undefined behavior".

Does standard c library provides linked list etc. data structures?

The C Standard does not provide data structures like linked list and stack.Some compiler implementations might provide their own versions but their usage will be non portable across different compilers.

So Yes, You have to write your own.

Creating a circularly linked list in C#?

As most of these answers don't actually get at the substance of the question, merely the intention, perhaps this will help:

As far as I can tell the only difference between a Linked List and a Circular Linked List is the behavior of iterators upon reaching the end or beginning of a list. A very easy way to support the behavior of a Circular Linked List is to write an extension method for a LinkedListNode that returns the next node in the list or the first one if no such node exists, and similarly for retrieving the previous node or the last one if no such node exists. The following code should accomplish that, although I haven't tested it:

static class CircularLinkedList {
    public static LinkedListNode<T> NextOrFirst<T>(this LinkedListNode<T> current)
    {
        return current.Next ?? current.List.First;
    }

    public static LinkedListNode<T> PreviousOrLast<T>(this LinkedListNode<T> current)
    {
        return current.Previous ?? current.List.Last;
    }
}

Now you can just call myNode.NextOrFirst() instead of myNode.Next and you will have all the behavior of a circular linked list. You can still do constant time removals and insert before and after all nodes in the list and the like. If there's some other key bit of a circular linked list I am missing, let me know.

---

Related Topics