linked-list.hpp

// no comment docs because lazy

#pragma once

#include <iostream>
#include <sstream>
#include <concepts>
#include <functional>

namespace darvil {
    template<typename T>
    class LinkedList {
        struct Node {
            T data;
            Node* next = nullptr;
            Node* previous = nullptr;

            void link_to(Node* other) {
                this->next = other;
                other->previous = this;
            }
        };

        struct Iterator {
            Node* current_node = nullptr;

            Iterator& update(Node* new_node) {
                if (!this->current_node)
                    throw std::out_of_range("out of bounds");
                this->current_node = new_node;
                return *this;
            }

            T& operator*() {
                return this->current_node->data;
            }

            Iterator& operator++() {
                return this->update(this->current_node->next);
            }

            Iterator& operator--() {
                return this->update(this->current_node->previous);
            }

            bool operator!=(Iterator& other) {
                return this->current_node != other.current_node;
            }
        };


        Node* head_lookup(size_t index) {
            auto* node = this->head;

            for (
                size_t visitor_index = 0;
                node && visitor_index != index;
                node = node->next, visitor_index++
            ) {}

            if (!node) throw std::invalid_argument("out of bounds");

            return node;
        }

        Node* tail_lookup(size_t index) {
            auto* node = this->tail;

            for (
                size_t visitor_index = 0;
                node && visitor_index != index;
                node = node->previous, visitor_index++
            ) {}

            if (!node) throw std::invalid_argument("out of bounds");

            return node;
        }

        Node* lookup(size_t index) {
            bool backwards = index > (this->size/2);
            return backwards
                ? this->tail_lookup(this->get_size() - index - 1)
                : this->head_lookup(index);
        }

    public:
        LinkedList() = default;

        template<size_t N>
        explicit LinkedList(T (&& array)[N]) {
            for (int i = 0; i < N; ++i) {
                this->push_back(array[i]);
            }
        }

        LinkedList(size_t size, std::function<T(size_t)> provider) {
            for (int i = 0; i < size; ++i) {
                this->push_back(provider(i));
            }
        }

        template<std::convertible_to<T> U>
        LinkedList(size_t size, U&& value) {
            for (int i = 0; i < size; ++i) {
                this->push_back(std::forward<U>(value));
            }
        }

        LinkedList(LinkedList& other) {
            for (auto* node = other.head; node; node = node->next) {
                this->push_back(node->data);
            }
        }

        LinkedList(LinkedList&& other) noexcept {
            this->head = other.head;
            this->tail = other.tail;
            this->size = other.size;

            other.head = nullptr;
            other.tail = nullptr;
            other.size = 0;
        }

        ~LinkedList() {
            Node* next;

            for (auto* node = this->head; node; node = next) {
                next = node->next;
                delete node;
            }
        }

        bool is_empty() const {
            return this->size == 0;
        }

        size_t get_size() const {
            return this->size;
        }

        template<std::convertible_to<T> U>
        void push_back(U&& value) {
            Node* new_node = new Node { value };

            if (this->is_empty()) {
                this->head = new_node;
            } else {
                this->tail->link_to(new_node);
            }

            this->tail = new_node;
            ++this->size;
        }

        template<std::convertible_to<T> U>
        void push_front(U&& value) {
            Node* new_node = new Node { value };

            if (this->is_empty()) {
                this->tail = new_node;
            } else {
                new_node->link_to(this->head);
            }

            this->head = new_node;
            ++this->size;
        }

        template<std::convertible_to<T> U>
        void insert(size_t at, U&& value) {
            if (at == 0) // first
                return this->push_front(std::forward<U>(value));
            if (at == this->get_size() - 1) // last
                return this->push_back(std::forward<U>(value));

            auto* current_node = this->lookup(at);
            Node* new_node = new Node { value };

            current_node->previous->link_to(new_node);
            new_node->link_to(current_node);
        }

        void remove(size_t at) {
            auto* node = this->lookup(at);

            if (at == 0) {
                this->head = node->next;
            }

            if (at == this->get_size() - 1) {
                this->tail = node->previous;

                if (node->previous)
                    node->previous->next = nullptr;
            }

            if (node->previous && node->next)
                node->previous->link_to(node->next);

            delete node;
            --this->size;
        }

        T pop_back() {
            const auto index = this->get_size() - 1;
            auto value = (*this)[index];
            this->remove(index);
            return value;
        }

        T pop_front() {
            auto value = (*this)[0];
            this->remove(0);
            return value;
        }

        T& operator[](size_t index) {
            return this->lookup(index)->data;
        }

        void swap(size_t a, size_t b) {
            std::swap((*this)[a], (*this)[b]);
        }

        std::string to_string() const {
            std::ostringstream buff;

            buff << "[";

            for (auto* node = this->head; node; node = node->next) {
                buff << node->data << (node->next ? ", " : "");
            }

            buff << "]";

            return buff.str();
        }

        auto iterable(bool from_tail = false) {
            return (struct {
                LinkedList& outer;
                bool from_tail;

                Iterator begin() {
                    return { this->from_tail ? this->outer.tail : this->outer.head };
                }

                Iterator end() {
                    return { nullptr };
                }
            }){ *this, from_tail };
        }

        template<typename T_>
        friend std::ostream& operator<<(std::ostream& stream, const LinkedList<T_>& list);

    private:
        Node* head = nullptr;
        Node* tail = nullptr;
        size_t size = 0;
    };

    template<typename T>
    std::ostream& operator<<(std::ostream& stream, const LinkedList<T>& list) {
        stream << list.to_string();
        return stream;
    }
}

ll-example.cpp

#include "linked-list.hpp"


int main() {
	{
		darvil::LinkedList<std::string> more;

		more.push_back("hello!");
		more.push_front("bye!");
		more[1] = "hmmmmm";

		std::cout << more << std::endl;
	}

	{
		auto stuff = darvil::LinkedList({1, 2, 3, 4, 5});

		stuff.push_back(10);
		stuff.push_back(11);
		stuff.push_back(12);

		auto it = stuff.iterable(true).begin(); // <- start from tail
		std::cout << *it << std::endl;
		// now move towards front twice
		--it;
		--it;
		std::cout << *it << std::endl;
		// now move back once
		++it;
		std::cout << *it << std::endl;
	}

	return 0;
}