template<class T>
Corrade::Containers::LinkedList class

Linked list.

Template parameters
T Item type, derived from LinkedListItem

The list stores pointers to items which contain iterators in itself, not the other way around, so it is possible to operate directly with pointers to the items without any abstraction at constant time. The only downside of this is that the items or list cannot be copied (but they can be moved).

Basic usage

Usage involves creating a subclass of LinkedListItem and then adding them to the list instance. By default, the list instance takes ownership of the added items, calling delete on each on destruction. See Memory management for details and other possibilities.

class Object: public Containers::LinkedListItem<Object> {
    // ...
};

Containers::LinkedList<Object> list;
list.insert(new Object);
list.insert(new Object);

list.erase(list.last());

Traversing through the list can be done using range-based for:

for(Object& o: list) {
    
}

Or, if you need more flexibility, like in the following code. It is also possible to go in reverse order using last() and LinkedListItem::previous().

for(Object* i = list.first(); i; i = i->next()) {
    
}

Making advantage of pointer to the list

Each node stores pointer to the list, which you can take advantage of. For example, if you have group of some objects and want to access the group from each object, you can reuse the LinkedListItem::list() pointer, which will be cast to type you specify as List template parameter of LinkedListItem class:

class ObjectGroup: public Containers::LinkedList<Object> {
    
};

class Object: public Containers::LinkedListItem<Object, ObjectGroup> {
    public:
        ObjectGroup* group() { return list(); }

    
};

Using private inheritance

You might want to subclass LinkedList and LinkedListItem privately and for example provide wrapper functions with more descriptive names. In that case you need to friend both LinkedList and LinkedListItem in both your subclasses.

class ObjectGroup: private Containers::LinkedList<Object> {
    friend Containers::LinkedList<Object>;
    friend Containers::LinkedListItem<Object, ObjectGroup>;

    public:
        Object* firstObject() { return first(); }
        Object* lastObject() { return last(); }

    
};

class Object: private Containers::LinkedListItem<Object, ObjectGroup> {
    friend Containers::LinkedList<Object>;
    friend Containers::LinkedListItem<Object, ObjectGroup>;

    public:
        ObjectGroup* group() { return list(); }
        Object* previousObject() { return previous(); }
        Object* nextObject() { return next(); }

    
};

Memory management

By default, the list takes ownership of all its items. When the list is destructed, clear() or erase() is called, LinkedListItem::erase() is called on each item, which in turn calls delete this. For cases where such behavior is not desirable (e.g. items meant to be owned by something else than the list), LinkedListItem::erase() can be overridden to prevent this behavior. See its documentation for more information.

Constructors, destructors, conversion operators

LinkedList() explicit constexpr noexcept
Default constructor.
LinkedList(const LinkedList<T>&) deleted
Copying is not allowed.
LinkedList(LinkedList<T>&& other) noexcept
Move constructor.
~LinkedList()
Destructor.

Public functions

auto operator=(const LinkedList<T>&) -> LinkedList<T>& deleted
Copying is not allowed.
auto operator=(LinkedList<T>&& other) -> LinkedList<T>&
Move assignment.
auto first() -> T*
First item or nullptr, if the list is empty.
auto first() const -> const T* constexpr
auto last() -> T*
Last item or nullptr, if the list is empty.
auto last() const -> const T* constexpr
auto isEmpty() const -> bool constexpr
Whether the list is empty.
void insert(T* item, T* before = nullptr)
Insert item.
void cut(T* item)
Cut item out.
void move(T* item, T* before)
Move item before another.
void erase(T* item)
Erase item.
void clear()
Clear the list.

Function documentation

template<class T>
Corrade::Containers::LinkedList<T>::LinkedList() explicit constexpr noexcept

Default constructor.

Creates empty list.

template<class T>
Corrade::Containers::LinkedList<T>::~LinkedList()

Destructor.

Clears the list.

template<class T>
const T* Corrade::Containers::LinkedList<T>::first() const constexpr

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

template<class T>
const T* Corrade::Containers::LinkedList<T>::last() const constexpr

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

template<class T>
void Corrade::Containers::LinkedList<T>::insert(T* item, T* before = nullptr)

Insert item.

Parameters
item Item to insert
before Item before which to insert or nullptr, if inserting at the end.

template<class T>
void Corrade::Containers::LinkedList<T>::cut(T* item)

Cut item out.

Parameters
item Item to cut out

The item is disconnected from the list, but not deleted.

template<class T>
void Corrade::Containers::LinkedList<T>::move(T* item, T* before)

Move item before another.

Parameters
item Item to move
before Item before which to move or nullptr, if moving at the end.

Equivalent to the following:

if(item != before) {
    list.cut(item);
    list.move(item, before);
}

template<class T>
void Corrade::Containers::LinkedList<T>::erase(T* item)

Erase item.

Parameters
item Item to erase

Equivalent to calling LinkedListItem::erase(). See its documentation for more information.