A template-based singly linked list requires careful handling of type erasure and memory management. Unlike non-template implementations, a generic approach enforces uniform data types across all nodes, including the sentinel head node. Attempting to assign a distinct type to the head node results in template instantiation conflicts and unsafe pointer casts. The following implementation demonstrates a robust, type-safe structure with modernized error handling and corercted memory management patterns.

Core Implementation

The design encapsulates node allocation and traversal logic within a unified template class. Key improvements over legacy patterns include removing static state from append operations, standardizing exception handling, and utilizing std::size_t for size tracking.

#pragma once
#include <iostream>
#include <stdexcept>
#include <cstddef>

template <typename T>
struct ListElement {
    T payload;
    ListElement* link;

    ListElement() : link(nullptr) {}
};

template <typename T>
class SinglyLinkedList {
public:
    SinglyLinkedList() : head_(new ListElement<T>()), count_(0) {}

    ~SinglyLinkedList() {
        Clear();
        delete head_;
    }

    bool IsEmpty() const { return count_ == 0; }
    std::size_t Size() const { return count_; }

    void Clear() {
        ListElement<T>* current = head_->link;
        while (current != nullptr) {
            ListElement<T>* next_node = current->link;
            delete current;
            current = next_node;
        }
        head_->link = nullptr;
        count_ = 0;
    }

    T& GetDataAt(std::size_t position) {
        if (head_->link == nullptr) {
            throw std::runtime_error("Cannot access data in an empty list.");
        }
        if (position >= count_) {
            throw std::out_of_range("Index exceeds current list size.");
        }

        ListElement<T>* cursor = head_->link;
        for (std::size_t i = 0; i < position; ++i) {
            cursor = cursor->link;
        }
        return cursor->payload;
    }

    ListElement<T>* GetNodeAt(std::size_t position) {
        if (head_->link == nullptr) {
            throw std::runtime_error("Cannot locate nodes in an empty list.");
        }
        if (position >= count_) {
            throw std::out_of_range("Index exceeds current list size.");
        }

        ListElement<T>* cursor = head_->link;
        for (std::size_t i = 0; i < position; ++i) {
            cursor = cursor->link;
        }
        return cursor;
    }

    ListElement<T>* SearchNode(const T& target) const {
        ListElement<T>* cursor = head_->link;
        while (cursor != nullptr) {
            if (cursor->payload == target) {
                return cursor;
            }
            cursor = cursor->link;
        }
        return nullptr;
    }

    std::size_t FindIndex(const T& target) const {
        ListElement<T>* cursor = head_->link;
        std::size_t idx = 0;
        while (cursor != nullptr) {
            if (cursor->payload == target) {
                return idx;
            }
            ++idx;
            cursor = cursor->link;
        }
        return static_cast<std::size_t>(-1);
    }

    void InsertAt(std::size_t position, const T& value) {
        if (head_->link == nullptr && position != 0) {
            throw std::runtime_error("Insertion requires a valid position.");
        }
        if (position > count_) {
            throw std::out_of_range("Insertion index out of bounds.");
        }

        ListElement<T>* cursor = head_;
        for (std::size_t i = 0; i < position; ++i) {
            cursor = cursor->link;
        }

        ListElement<T>* new_element = new ListElement<T>();
        new_element->payload = value;
        new_element->link = cursor->link;
        cursor->link = new_element;
        ++count_;
    }

    void RemoveAt(std::size_t position) {
        if (head_->link == nullptr) {
            throw std::runtime_error("Cannot remove from an empty list.");
        }
        if (position >= count_) {
            throw std::out_of_range("Removal index out of bounds.");
        }

        ListElement<T>* cursor = head_;
        for (std::size_t i = 0; i < position; ++i) {
            cursor = cursor->link;
        }

        ListElement<T>* target = cursor->link;
        cursor->link = target->link;
        delete target;
        --count_;
    }

    void Prepend(const T& value) {
        ListElement<T>* new_element = new ListElement<T>();
        new_element->payload = value;
        new_element->link = head_->link;
        head_->link = new_element;
        ++count_;
    }

    void Append(const T& value) {
        ListElement<T>* new_element = new ListElement<T>();
        new_element->payload = value;

        ListElement<T>* cursor = head_;
        while (cursor->link != nullptr) {
            cursor = cursor->link;
        }
        cursor->link = new_element;
        ++count_;
    }

private:
    ListElement<T>* head_;
    std::size_t count_;
};

Integration and Type Handling

Custom data structures require operator overloads to integrate seamlessly with list comparisons and output streams. The example below demonstrates usage with a user-defined Record type alongside primitive integers.

#include <iostream>
#include <string>
#include "SinglyLinkedList.hpp"

struct Record {
    int id;
    std::string label;

    friend std::ostream& operator<<(std::ostream& os, const Record& r) {
        return os << "[ID: " << r.id << ", Label: " << r.label << "]";
    }

    bool operator==(const Record& other) const {
        return id == other.id && label == other.label;
    }
};

int main() {
    try {
        SinglyLinkedList<Record> record_list;
        record_list.Append({101, "Alpha"});
        record_list.Append({102, "Beta"});
        record_list.Prepend({100, "Zero"});

        std::cout << record_list.GetDataAt(1) << "\n";
        record_list.RemoveAt(0);
        std::cout << "New head: " << record_list.GetDataAt(0) << "\n";

        SinglyLinkedList<int> integer_list;
        integer_list.Append(10);
        integer_list.Append(20);
        integer_list.Append(30);

        std::cout << "Index of 20: " << integer_list.FindIndex(20) << "\n";
        integer_list.InsertAt(1, 15);
        std::cout << "Value at index 1: " << integer_list.GetDataAt(1) << "\n";

    } catch (const std::exception& e) {
        std::cerr << "Runtime Error: " << e.what() << "\n";
    }

    return 0;
}

Debugging Considerations

Template-based linked structures commonly encounter two categories of runtime failures during development:

Dangling Pointer Access Attempting to reuse a node pointer after it has been past to a deletion method results in undefined behavior. Once a memory address is deallocated via delete, any subsequent read or write operation on that pointer triggers a heap corruption or access violation. Always intsantiate fresh node objects before re-insertion, or rely on the list's internal allocation methods (e.g., Append, InsertAt) which manage object lifetimes automatically.

Boundary Violations Index-based operations (GetDataAt, RemoveAt, InsertAt) require strict validation against the current element count. If the tracking variable is not synchronized with actual memory operations, traversal loops may dereference nullptr values. Ensure that size counters are incremented only after successful allocation and linkage, and decremented immediately upon node destruction. Modern implementations should favor std::out_of_range exceptions over silent failures to catch boundary errors during the debugging phase.