Linked_List.cpp

// I don't like null
#include <optional>
// For to_string()
#include <string>
#include <sstream>
template <typename T>
class SinglyLinkedList
{
private:
    struct SLLNode
    {
        const T data;
        std::optional<SLLNode *> next;
    };
    typedef std::optional<SLLNode *> SLLNodePointer;
    // start pointer.
    SLLNodePointer start, end;
    size_t length = 0;

    /**
     * Resolves the given index value to be within the list element indices [0,length-1], if possible.
     * If is_for_insertion=true then it resolves index to be within [0,length].
     * This fails (returns std::nullopt) if list is empty.
     * 
     * Index starts from 0.
     * Negative index values start from the end. (-1 is last element)
     * 
     * Returns empty optional if list is empty or index out of bounds.
     */
    std::optional<const intmax_t> resolveIndex(intmax_t index, bool is_for_insertion = false)
    {
        const intmax_t upper_incl = length - 1 + is_for_insertion;
        const intmax_t lower_incl = 0;
        // resolve index
        if (index < lower_incl)
            index += upper_incl + 1;
        // check for index out of bounds
        if (index < lower_incl || index > upper_incl)
            return std::nullopt;
        else
            return std::make_optional(index);
    }

public:
    /**
     * Returns  true if list is empty.
     *          false if list has elements.
     */
    bool isEmpty()
    {
        return !start.has_value();
    }

    /**
     * Returns the element at the given index.
     * Index starts from 0.
     * Negative index values start from the end. (-1 is last element)
     * Returns empty optional if index out of bounds.
     */
    std::optional<const T> operator[](intmax_t index) { return elementAt(index); }
    std::optional<const T> elementAt(intmax_t index)
    {
        // resolve index
        index = resolveIndex(index).value_or(-1);
        if (index == -1)
            return std::nullopt;
        // iterate to reach index
        auto p = *start;
        while (index--)
            p = *(p->next);
        return std::make_optional(p->data);
    }

    /**
     * Inserts the given element at the given index,
     *  by pushing other elements forwards towards the end of the list.
     * 
     * Resolves the given index value to be within the list, if possible.
     * Index starts from 0.
     * Negative index values start from the end. (-1 inserts at end of list)
     * 
     * Returns false if insertion fails, or index out of bounds.
     */
    bool insert(intmax_t index, const T &data)
    {
        // resolve index
        index = resolveIndex(index, true).value_or(-1);
        if (index == -1)
            return false; // index resolution failed

        // insert element
        auto node = (new SinglyLinkedList<T>::SLLNode{data});

        // Update end if applicable, done here since we will use index to iterate
        if (index == length)
            end = node;

        // Update start else update node at index-1
        if (index == 0)
        {
            // insertion at start of list
            node->next = start;
            start = node;
        }
        else
        {
            auto iterator = start;
            while (index-- > 1) // iterate to node before insertion index, i.e. node at index-1
                iterator = (*iterator)->next;
            node->next = (*iterator)->next;
            (*iterator)->next = node;
        }

        // Update length and return
        ++length;
        return true;
    }

    /**
     * Appends the element to the end of the list.
     * See this::insert()
     */
    bool append(const T &data)
    {
        return insert(length, data);
    }

    /**
     * Removes the element at the given index.
     * Returns  true if element removed.
     *          false if index out of bounds.
     */
    bool remove(intmax_t index)
    {
        // resolve index
        index = resolveIndex(index).value_or(-1);
        if (index == -1)
            return false; // index resolution failed

        SLLNodePointer toRemove;

        // remove element
        // Update start else update node at index-1
        if (index == 0)
        {
            // insertion at start of list
            toRemove = start;
            start = (*start)->next;
        }
        else
        {
            auto iterator = start;
            while (index-- > 1) // iterate to node before insertion index, i.e. node at index-1
                iterator = (*iterator)->next;
            toRemove = (*iterator)->next;
            // Update end if applicable
            if (!toRemove.has_value())
            {
                end = iterator;
            }
            (*iterator)->next = (*toRemove)->next;
        }
        // Remove node and Free memory
        delete *toRemove;
        // Update length and return
        --length;
        return true;
    }

    /**
     * Reverses the linked list.
     * Complexity: O(n)
     */
    void reverse()
    {
        if (length > 1)
        {
            // setup sliding window
            auto p1 = start;
            auto p2 = (*start)->next;

            // setup end pointer and new last node
            (*start)->next = (*end)->next;
            end = start;

            // reverse
            while (p2)
            {
                auto temp = std::move((*p2)->next);
                (*p2)->next = p1;
                p1 = p2;
                p2 = temp;
            }

            // setup new start
            start = p1;
        }
    }

    /**
     * Accumulates the list elements into the given initial_value by applying the given function to all elements in order.
     */
    template <typename ACC>
    ACC accumulate(ACC initial_value, ACC func(ACC, const T &))
    {
        auto ptr = start;
        while (ptr)
        {
            initial_value = func(std::move(initial_value), (*ptr)->data);
            ptr = (*ptr)->next;
        }
        return initial_value;
    }

    /**
     * To string.
     */
    std::string to_string(bool internal_only = false)
    {
        std::stringstream buffer;
        if (!internal_only)
            buffer << "SinglyLinkedList(length: " << length << ") | ";
        // print list
        buffer = accumulate<std::stringstream>(
            std::move(buffer),
            [](auto buffer, const T &data) {
                buffer << data << " ";
                return buffer;
            });
        if (!internal_only)
            buffer << "<" << std::endl;
        return buffer.str();
    }
};

#include <iostream>
int main()
{
    int a[] = {1, 2, 3, 4};
    SinglyLinkedList<int> l;
    l.append(12);
    l.insert(-1, 13);
    l.insert(-2, 17);
    for (auto e : a)
        l.append(e);

    std::cout << l.to_string();
    std::cout << *l[-1] << " " << *l[3] << std::endl;
    std::cout << *l[0] << " " << l[30].has_value() << std::endl;

    l.remove(-1);
    std::cout << l.to_string();

    l.remove(0);
    std::cout << l.to_string();

    l.remove(1);
    std::cout << l.to_string();

    l.reverse();
    std::cout << l.to_string();
}