#ifndef STACKLINKEDLIST_H
#define STACKLINKEDLIST_H

// A simple linkedk list that does not perform any memory allocation.
// Callers are responsible for wrapping the objects of type T into
// within objects of type Node.
template <class T>
class StackLinkedList {
public:
    // Wraps objects of the target type.
    union Node {
        T data;
        Node* next;
    };

    Node* head = nullptr;
public:
    StackLinkedList() = default;
    StackLinkedList(StackLinkedList& stackLinkedList) = delete;

    // Insets the given node into the linked list. The next pointer of
    // the node will be modified.
    void push(Node* newNode);

    // Removes one node from the linked list. Returns null if the list is empty.
    Node* pop();
};

template <class T>
void StackLinkedList<T>::push(Node* newNode) {
    newNode->next = head;
    head = newNode;
}

template <class T>
typename StackLinkedList<T>::Node* StackLinkedList<T>::pop() {
    if (head == nullptr) {
        return nullptr;
    }
    Node* top = head;
    head = head->next;

    // This is a cleanup to avoid incorrect usage by the caller.
    top->next = nullptr;

    return top;
}

#endif /* STACKLINKEDLIST_H */

