Skip to content

Instantly share code, notes, and snippets.

@ruurdadema

ruurdadema/linked_node.hpp

Created November 24, 2025 21:19
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save ruurdadema/9cb6234671a159e894dc823bd6482fed to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save ruurdadema/9cb6234671a159e894dc823bd6482fed to your computer and use it in GitHub Desktop.
Download ZIP
LinkedNode
Raw
linked_node.hpp
/*
* Owllab License Agreement
*
* This software is provided by Owllab and may not be used, copied, modified,
* merged, published, distributed, sublicensed, or sold without a valid and
* explicit agreement with Owllab.
*
* Copyright (c) 2024 Owllab. All rights reserved.
*/
#pragma once
#include <functional>
namespace rav {
/**
* A node which can be linked together into a linked-list, and which can hold data of any type.
* @tparam T The type of the data to be stored in the linked node.
*/
template<class T>
class LinkedNode {
public:
/**
* Iterator for linked nodes.
*/
class Iterator {
public:
explicit Iterator(LinkedNode* node) : current(node) {}
LinkedNode& operator*() const {
return *current;
}
Iterator& operator++() {
if (current) {
current = current->next_;
}
return *this;
}
bool operator==(const Iterator& other) const {
return current == other.current;
}
bool operator!=(const Iterator& other) const {
return current != other.current;
}
private:
LinkedNode* current {};
};
LinkedNode() = default;
/**
* Creates a new linked node with the given data.
* @param data The data to be stored in the linked node.
*/
explicit LinkedNode(T data) : value_(data) {}
/**
* Destructor which removes itself from the linked list if linked.
*/
~LinkedNode() {
unlink();
}
LinkedNode(const LinkedNode&) = delete;
LinkedNode& operator=(const LinkedNode&) = delete;
/**
* Constructs a linked node replacing other. After returning, this will have happened:
* - This will replace other in its linked list. This will now be part of the linked list of other.
* - Other will be unlinked.
* - The value contained in other will be moved to this.
* @param other The linked node to replace.
*/
LinkedNode(LinkedNode&& other) noexcept {
if (other.prev_) {
other.prev_->next_ = this;
prev_ = other.prev_;
other.prev_ = nullptr;
}
if (other.next_) {
other.next_->prev_ = this;
next_ = other.next_;
other.next_ = nullptr;
}
value_ = std::move(other.value_);
other.value_ = T();
}
/**
* Move assigns other to this. After returning, this will have happened:
* - This will remove itself from its linked list (if linked).
* - This will replace other in its linked list. This will now be part of the linked list of other.
* - The value contained in other will be moved to this.
* @param other Other node to be moved.
*/
LinkedNode& operator=(LinkedNode&& other) noexcept {
if (this == &other) {
return *this;
}
unlink();
if (other.prev_) {
other.prev_->next_ = this;
prev_ = other.prev_;
other.prev_ = nullptr;
}
if (other.next_) {
other.next_->prev_ = this;
next_ = other.next_;
other.next_ = nullptr;
}
value_ = std::move(other.value_);
other.value_ = T();
return *this;
}
/**
* Assigns a new value to the linked node.
* @param value The new value to be assigned.
* @return this
*/
LinkedNode& operator=(T value) {
value_ = std::move(value);
return *this;
}
/**
* Returns the first node in the linked list.
* @return The first node in the linked list, or this if not linked.
*/
LinkedNode* front() {
auto* current = this;
while (current->prev_ != nullptr) {
current = current->prev_;
}
return current;
}
/**
* Returns the last node in the linked list.
* @return The last node in the linked list, or this if not linked.
*/
LinkedNode* back() {
auto* current = this;
while (current->next_ != nullptr) {
current = current->next_;
}
return current;
}
/**
* Pushes a node to the back of the linked list. If the node is already linked, it will be removed from its current
* position.
* @param node The node to push to the back of the linked list.
*/
void push_back(LinkedNode& node) {
if (node.is_linked()) {
node.unlink();
}
auto* last_node = back();
last_node->next_ = &node;
node.prev_ = last_node;
}
/**
* Unlinks the node from the linked list.
*/
void unlink() {
if (prev_) {
prev_->next_ = next_;
}
if (next_) {
next_->prev_ = prev_;
}
prev_ = nullptr;
next_ = nullptr;
}
/**
* @returns The data stored in the linked node.
*/
T& operator*() {
return value_;
}
/**
* @returns The data stored in the linked node.
*/
const T& operator*() const {
return value_;
}
/**
* @returns The data stored in the linked node.
*/
T* operator->() {
return &value_;
}
/**
* @returns The data stored in the linked node.
*/
const T* operator->() const {
return &value_;
}
/**
* @returns The data stored in the linked node.
*/
T& value() {
return value_;
}
/**
* @returns The data stored in the linked node.
*/
const T& value() const {
return value_;
}
/**
* Resets the data stored in the linked node to its default value. Does not unlink the node.
*/
void reset_value() {
value_ = T();
}
/**
* Unlinks this node and resets the value it holds.
*/
void reset() {
unlink();
reset_value();
}
/**
* @returns An iterator to the first node in the linked list.
*/
Iterator begin() {
return Iterator(front());
}
/**
* @returns An iterator to the end of the linked list.
*/
Iterator end() {
return Iterator(nullptr);
}
/**
*
* @returns An iterator to the first node in the linked list.
*/
Iterator begin() const {
return Iterator(back());
}
/**
* @returns An iterator to the end of the linked list.
*/
Iterator end() const {
return Iterator(nullptr);
}
/**
* @returns True if this is the first node in the linked list, false otherwise.
*/
[[nodiscard]] bool is_front() const {
return prev_ == nullptr && next_ != nullptr;
}
/**
* @returns True if this is the last node in the linked list, false otherwise.
*/
[[nodiscard]] bool is_back() const {
return next_ == nullptr && prev_ != nullptr;
}
/**
* @returns True if this node is linked to another node, false otherwise.
*/
[[nodiscard]] bool is_linked() const {
return prev_ != nullptr || next_ != nullptr;
}
/**
* @param f The function to be called for each node in the linked list.
*/
void foreach (const std::function<void(LinkedNode&)>& f) {
for (auto& node : *this) {
f(node);
}
}
private:
T value_ {};
LinkedNode* prev_ = nullptr;
LinkedNode* next_ = nullptr;
};
} // namespace rav
Raw
linked_node.test.cpp
/*
* Owllab License Agreement
*
* This software is provided by Owllab and may not be used, copied, modified,
* merged, published, distributed, sublicensed, or sold without a valid and
* explicit agreement with Owllab.
*
* Copyright (c) 2024 Owllab. All rights reserved.
*/
#include "ravennakit/core/util/linked_node.hpp"
#include <iostream>
#include <catch2/catch_all.hpp>
namespace {
template<class T>
std::vector<T> list_of_node_values(rav::LinkedNode<T>& nodes) {
std::vector<T> values;
for (const auto& node : nodes) {
values.push_back(node.value());
}
return values;
}
template<class T>
std::vector<T*> list_of_node_pointers(T& nodes) {
std::vector<T*> pointers;
for (auto& node : nodes) {
pointers.push_back(&node);
}
return pointers;
}
} // namespace
TEST_CASE("rav::Linked Node") {
SECTION("Build a list") {
rav::LinkedNode n1(1);
rav::LinkedNode n2(2);
rav::LinkedNode n3(3);
SECTION("Single node") {
REQUIRE(n1.value() == 1);
REQUIRE(n1.is_front() == false);
REQUIRE(n1.is_back() == false);
REQUIRE(n1.is_linked() == false);
REQUIRE(n2.value() == 2);
REQUIRE(n2.is_front() == false);
REQUIRE(n2.is_back() == false);
REQUIRE(n2.is_linked() == false);
REQUIRE(n3.value() == 3);
REQUIRE(n3.is_front() == false);
REQUIRE(n3.is_back() == false);
REQUIRE(n3.is_linked() == false);
REQUIRE(list_of_node_values(n1) == std::vector {1});
}
n1.push_back(n2);
SECTION("Two nodes") {
REQUIRE(n1.value() == 1);
REQUIRE(n1.is_front() == true);
REQUIRE(n1.is_back() == false);
REQUIRE(n1.is_linked() == true);
REQUIRE(n2.value() == 2);
REQUIRE(n2.is_front() == false);
REQUIRE(n2.is_back() == true);
REQUIRE(n2.is_linked() == true);
REQUIRE(n3.value() == 3);
REQUIRE(n3.is_front() == false);
REQUIRE(n3.is_back() == false);
REQUIRE(n3.is_linked() == false);
REQUIRE(list_of_node_values(n1) == std::vector {1, 2});
}
n1.push_back(n3);
SECTION("Three nodes") {
REQUIRE(n1.value() == 1);
REQUIRE(n1.is_front() == true);
REQUIRE(n1.is_back() == false);
REQUIRE(n1.is_linked() == true);
REQUIRE(n2.value() == 2);
REQUIRE(n2.is_front() == false);
REQUIRE(n2.is_back() == false);
REQUIRE(n2.is_linked() == true);
REQUIRE(n3.value() == 3);
REQUIRE(n3.is_front() == false);
REQUIRE(n3.is_back() == true);
REQUIRE(n3.is_linked() == true);
REQUIRE(list_of_node_values(n1) == std::vector {1, 2, 3});
}
n2.unlink();
SECTION("Two nodes again") {
REQUIRE(n1.value() == 1);
REQUIRE(n1.is_front() == true);
REQUIRE(n1.is_back() == false);
REQUIRE(n1.is_linked() == true);
REQUIRE(n2.value() == 2);
REQUIRE(n2.is_front() == false);
REQUIRE(n2.is_back() == false);
REQUIRE(n2.is_linked() == false);
REQUIRE(n3.value() == 3);
REQUIRE(n3.is_front() == false);
REQUIRE(n3.is_back() == true);
REQUIRE(n3.is_linked() == true);
REQUIRE(list_of_node_values(n1) == std::vector {1, 3});
}
n1.unlink();
SECTION("One node again") {
REQUIRE(n1.value() == 1);
REQUIRE(n1.is_front() == false);
REQUIRE(n1.is_back() == false);
REQUIRE(n1.is_linked() == false);
REQUIRE(n2.value() == 2);
REQUIRE(n2.is_front() == false);
REQUIRE(n2.is_back() == false);
REQUIRE(n2.is_linked() == false);
REQUIRE(n3.value() == 3);
REQUIRE(n3.is_front() == false);
REQUIRE(n3.is_back() == false);
REQUIRE(n3.is_linked() == false);
REQUIRE(list_of_node_values(n1) == std::vector {1});
REQUIRE(list_of_node_values(n2) == std::vector {2});
REQUIRE(list_of_node_values(n3) == std::vector {3});
}
}
SECTION("Removing nodes from front and back") {
rav::LinkedNode n1(1);
rav::LinkedNode n2(2);
rav::LinkedNode n3(3);
n1.push_back(n2);
n1.push_back(n3);
REQUIRE(list_of_node_values(n1) == std::vector {1, 2, 3});
SECTION("From back") {
n3.unlink();
REQUIRE(list_of_node_values(n1) == std::vector {1, 2});
REQUIRE(list_of_node_values(n3) == std::vector {3});
n2.unlink();
REQUIRE(list_of_node_values(n1) == std::vector {1});
REQUIRE(list_of_node_values(n2) == std::vector {2});
REQUIRE(list_of_node_values(n3) == std::vector {3});
}
SECTION("From front") {
n1.unlink();
REQUIRE(list_of_node_values(n1) == std::vector {1});
REQUIRE(list_of_node_values(n2) == std::vector {2, 3});
n2.unlink();
REQUIRE(list_of_node_values(n1) == std::vector {1});
REQUIRE(list_of_node_values(n2) == std::vector {2});
REQUIRE(list_of_node_values(n3) == std::vector {3});
}
}
SECTION("try to break it") {
rav::LinkedNode n1(1);
rav::LinkedNode n2(2);
rav::LinkedNode n3(3);
std::vector<int> nodes;
n1.push_back(n2);
n1.push_back(n3);
SECTION("Adding a node twice should keep integrity") {
n1.push_back(n2);
for (const auto& node : n1) {
nodes.push_back(node.value());
}
REQUIRE(nodes == std::vector {1, 3, 2});
}
SECTION("When a node goes out of scope it should remove itself") {
{
rav::LinkedNode n4(4);
n1.push_back(n4);
for (const auto& node : n1) {
nodes.push_back(node.value());
}
REQUIRE(nodes == std::vector {1, 2, 3, 4});
}
nodes.clear();
for (const auto& node : n1) {
nodes.push_back(node.value());
}
REQUIRE(nodes == std::vector {1, 2, 3});
}
}
SECTION("Assign new value") {
rav::LinkedNode n1(1);
n1 = 4;
REQUIRE(n1.value() == 4);
}
SECTION("Move semantics") {
rav::LinkedNode<std::string> n1("n1");
rav::LinkedNode<std::string> n2("n2");
rav::LinkedNode<std::string> n3("n3");
n1.push_back(n2);
n1.push_back(n3);
REQUIRE(list_of_node_values(n1) == std::vector<std::string> {"n1", "n2", "n3"});
SECTION("Move assignment") {
rav::LinkedNode<std::string> l1("l1");
rav::LinkedNode<std::string> l2("l2");
rav::LinkedNode<std::string> l3("l3");
l1.push_back(l2);
l1.push_back(l3);
REQUIRE(list_of_node_values(l1) == std::vector<std::string> {"l1", "l2", "l3"});
l2 = std::move(n2);
REQUIRE(n2.is_linked() == false);
REQUIRE(list_of_node_values(n1) == std::vector<std::string> {"n1", "n2", "n3"});
REQUIRE(list_of_node_values(n2) == std::vector<std::string> {{}});
REQUIRE(list_of_node_values(n3) == std::vector<std::string> {"n1", "n2", "n3"});
REQUIRE(list_of_node_values(l1) == std::vector<std::string> {"l1", "l3"});
REQUIRE(list_of_node_values(l2) == std::vector<std::string> {"n1", "n2", "n3"});
REQUIRE(list_of_node_values(l3) == std::vector<std::string> {"l1", "l3"});
REQUIRE(list_of_node_pointers(n1) == std::vector<rav::LinkedNode<std::string>*> {&n1, &l2, &n3});
REQUIRE(list_of_node_pointers(n2) == std::vector<rav::LinkedNode<std::string>*> {&n2});
REQUIRE(list_of_node_pointers(n3) == std::vector<rav::LinkedNode<std::string>*> {&n1, &l2, &n3});
REQUIRE(list_of_node_pointers(l1) == std::vector<rav::LinkedNode<std::string>*> {&l1, &l3});
REQUIRE(list_of_node_pointers(l2) == std::vector<rav::LinkedNode<std::string>*> {&n1, &l2, &n3});
REQUIRE(list_of_node_pointers(l3) == std::vector<rav::LinkedNode<std::string>*> {&l1, &l3});
}
SECTION("Move construction") {
// The next operation should replace n2 with l2
rav::LinkedNode new_node(std::move(n2));
// Now new_node is linked to n1 and n3 and n2 is not linked to anything
REQUIRE(n2.is_linked() == false);
REQUIRE(list_of_node_values(n1) == std::vector<std::string> {"n1", "n2", "n3"});
REQUIRE(list_of_node_values(n2) == std::vector<std::string> {{}});
REQUIRE(list_of_node_values(n3) == std::vector<std::string> {"n1", "n2", "n3"});
REQUIRE(list_of_node_pointers(n1) == std::vector<rav::LinkedNode<std::string>*> {&n1, &new_node, &n3});
REQUIRE(list_of_node_pointers(n2) == std::vector<rav::LinkedNode<std::string>*> {&n2});
REQUIRE(list_of_node_pointers(n3) == std::vector<rav::LinkedNode<std::string>*> {&n1, &new_node, &n3});
REQUIRE(list_of_node_values(new_node) == std::vector<std::string> {"n1", "n2", "n3"});
REQUIRE(
list_of_node_pointers(new_node) == std::vector<rav::LinkedNode<std::string>*> {&n1, &new_node, &n3}
);
}
SECTION("Swap") {
rav::LinkedNode<std::string> l1("l1");
rav::LinkedNode<std::string> l2("l2");
rav::LinkedNode<std::string> l3("l3");
l1.push_back(l2);
l1.push_back(l3);
std::swap(n2, l2);
REQUIRE(n2.value() == "l2");
REQUIRE(l2.value() == "n2");
REQUIRE(list_of_node_values(n1) == std::vector<std::string> {"n1", "n2", "n3"});
REQUIRE(list_of_node_values(l1) == std::vector<std::string> {"l1", "l2", "l3"});
REQUIRE(list_of_node_pointers(n1) == std::vector<rav::LinkedNode<std::string>*> {&n1, &l2, &n3});
REQUIRE(list_of_node_pointers(l1) == std::vector<rav::LinkedNode<std::string>*> {&l1, &n2, &l3});
}
}
SECTION("Inside a container") {
SECTION("Survive reallocation") {
rav::LinkedNode<std::string> l2("n2");
rav::LinkedNode<std::string> l3("n3");
std::vector<rav::LinkedNode<std::string>> nodes;
auto& it = nodes.emplace_back("n1");
it.push_back(l2);
it.push_back(l3);
REQUIRE(list_of_node_values(it) == std::vector<std::string> {"n1", "n2", "n3"});
// Now resize the vector to force re-allocation
nodes.resize(nodes.capacity() + 1);
REQUIRE(list_of_node_values(nodes.front()) == std::vector<std::string> {"n1", "n2", "n3"});
REQUIRE(
list_of_node_pointers(nodes.front())
== std::vector<rav::LinkedNode<std::string>*> {&nodes.front(), &l2, &l3}
);
}
SECTION("Survive move construction") {
std::vector<rav::LinkedNode<std::string>> nodes;
nodes.emplace_back("n1");
nodes.emplace_back("n2");
nodes.emplace_back("n3");
nodes.front().push_back(nodes.at(1));
nodes.front().push_back(nodes.at(2));
REQUIRE(list_of_node_values(nodes.at(0)) == std::vector<std::string> {"n1", "n2", "n3"});
REQUIRE(list_of_node_values(nodes.at(1)) == std::vector<std::string> {"n1", "n2", "n3"});
REQUIRE(list_of_node_values(nodes.at(2)) == std::vector<std::string> {"n1", "n2", "n3"});
std::vector new_nodes(std::move(nodes));
REQUIRE(list_of_node_values(new_nodes.at(0)) == std::vector<std::string> {"n1", "n2", "n3"});
REQUIRE(list_of_node_values(new_nodes.at(1)) == std::vector<std::string> {"n1", "n2", "n3"});
REQUIRE(list_of_node_values(new_nodes.at(2)) == std::vector<std::string> {"n1", "n2", "n3"});
}
SECTION("Survive move assignment") {
std::vector<rav::LinkedNode<std::string>> nodes;
nodes.emplace_back("n1");
nodes.emplace_back("n2");
nodes.emplace_back("n3");
nodes.front().push_back(nodes.at(1));
nodes.front().push_back(nodes.at(2));
REQUIRE(list_of_node_values(nodes.at(0)) == std::vector<std::string> {"n1", "n2", "n3"});
REQUIRE(list_of_node_values(nodes.at(1)) == std::vector<std::string> {"n1", "n2", "n3"});
REQUIRE(list_of_node_values(nodes.at(2)) == std::vector<std::string> {"n1", "n2", "n3"});
std::vector<rav::LinkedNode<std::string>> new_nodes;
new_nodes = std::move(nodes);
REQUIRE(list_of_node_values(new_nodes.at(0)) == std::vector<std::string> {"n1", "n2", "n3"});
REQUIRE(list_of_node_values(new_nodes.at(1)) == std::vector<std::string> {"n1", "n2", "n3"});
REQUIRE(list_of_node_values(new_nodes.at(2)) == std::vector<std::string> {"n1", "n2", "n3"});
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment