Creating a Circular List (STL/Scratch)

[blindedhunter]

I want to create a circular linked list (forward or doubly linked). I'm not certain how to do this.
I understand in concept, the linked list (forward and doubly) and making it circular, but I can't seem to figure out how to actually implement either idea I have for writing one.

My main trouble with creating a linked list is, I think, that I don't understand the actual creation part - instantiating it and adding to it. If anyone out there could give an example of that at least, that would be great.

My idea to use the STL to create one is a little simpler: I think I'd like to just use the stl::list class, put my actions involving it in a for loop going from the beginning to the end, and then put that in a while loop so that I can keep circling around over and over. My problem there is that I don't quite get how to use the stl::list class with a class of my own, particularly calling actions from it, so if anyone could demonstrate that that would be great too.

Thank you all for looking. If you're interested in answering but need more details, please just ask.

[zwA4jE8b]

if (list_position % list_size == 0)
  ..Then you are at the end of the list, wrap around to the front

[Gaminic]

Creating a linked list is easiest if you have two separate classes, a Node/Item and a List class. The List class simply keeps track of the head of the list (and other metrics if you wish, like item count etc). The Node class does the actual linking by means of a Next and Prev pointer, and keeps the data of the item itself. This can easily be done as such:

struct Node {
     myItem* Data; // Points to whatever class you wanted a LL of.
     Node* next, *prev; // Links
};
struct List {
    Node* head;
};

Second problem: data management. In most cases, a linked list is used for "an unknown amount of items", thus you can't initialize a fixed size container for it. Generally, new items are added on the Heap using dynamic allocation.

List mylist;
mylist.push(new Node(InitData));

This is handy, because memory is only allocated when a new item appears. More difficult, however, is keeping track of it. After all, the only way to find the items is by the pointers in the next/prev pointers of other nodes. If you decide to delete an item from the list by relinking its neighbors, you best make sure you keep a pointer to the deleted item, or you'll have lost it forever (= memory leak!).

Secondly, once you're done, you need to delete all the items. Sadly, you don't have a pointer to all the items, and once you delete a single item, you lose the links to the other items, and those links are the only way to find the items!

Often, this is done by a recursive deletion algorithm that is called in the destructor:

void List::empty(void) {
    head->prev->next = nullptr; // Break forward-circularity.
    head->delete(); // Call recursive deleter.
}
void Node::delete(void) {
    if(next != nullptr) next->delete(); // Recursively destroy the next item;
    delete this; // Clear memory of this Node.
}

The recursion first deletes the next item, then itself. This means the last item will be deleted first (it is the only item where next = nullptr, because we enforced it!), before the recursion walks back.

Do mind, this is untested; I'm simply trying to explain the basics. I'm not sure if you can call delete on 'this'. Most likely, you're going to call "delete next;" and a final "delete head;" instead.

[o1vk4iN6]

There's no need to use a list as you can use a fixed size array. STL already provides a Queue which might be what you are looking for.

[Gaminic]

@xerzi: What on earth are you talking about? Are you saying lists are useless? Are you saying fixed size arrays are a valid alternative to lists? If anything, they are the exact opposite of each other.

To validate this post a bit further, some basic info on the STL list class:

Lists are 'weird' in the sense that they are the first container class a beginner encounters that doesn't allow random access (read: index notation). There is no such thing as myList[5], because the entire point of a List is that it doesn't require contiguous memory.

The way you access lists is by using an iterator. An iterator is basically a pointer to "the current Item". You can increase an iterator (e.g. myIterator++), which is basically equivalent to "myIterator = myIterator->next". All it does is provide an intuitive interface to access elements.

With that information, it should be easy to get how to access elements: if the iterator is a pointer, dereferencing an iterator gives you the element! (Do mind: I think you have to explicitly dereference the iterator; I don't think the arrow (->) operator will cut it.)

[o1vk4iN6]

No, in this case it seems a bit redundant, why would you use a std::list in your own linked list? He also wants it to be circular which makes it even more redundant as you can access both the front and the back using std::list. So what I interpreted he wanted was something like a Circular Array Queue, since it seems he doesn't know what he actually wants.

[Gaminic]

No, I think he was doubting whether to make his own version of a doubly-linked list, or use the STL version. A Circular Array Queue wouldn't be stretchable, would it?

[o1vk4iN6]

Which is why I said fixed size array ;)

[blindedhunter]

Okay. So. Sorry I didn't get back to this sooner. I tried, but two times poor internet on campus ate my posts.

Gaminic: what you said about arrow operators ended up helping, at least with the usage of the STL list. I must have been doing something silly, but now I think I can get all the functionality I want out of the STL list in a for loop and while loop.
I'm still not clear on a lot of parts about the creation of an actual circular list, but with what you said I'll try to keep working at it. What I mostly don't get is how to implement a push_back() function for it. And I suppose how I would delete a list that is circular.

xerzi: As Gaminic said, the STL list and circular list are two different examples, and I do not want an array.
The STL list with a for loop and a while loop to jump from the end to the beginning over and over again is one implementation of a circular list that would work, and creating a circular list class would do this same thing but in a slightly different, and I suspect more elegant way.
I do not want an array, as I need to be able to (or I guess would at least like to be able to) add and delete elements at will from any place in the list.