#include <iostream>

using namespace std;

template <class T>
class Node {
public:
    T data;
    Node<T> *next;
    Node(T aData, Node<T> *aNext) {
        data = aData;
        next = aNext;
    }
    T getData() {
        return data;
    };
    Node<T> *Next() {
        return next;
    }
    
    void setNext(Node<T> *aNext) {
        next = aNext;
    }
};

template <class T>
class LList {
    
    Node<T> *head;
    
public:
    LList() {
        head = NULL;
    }
    void Append(T data) {
        Node<T> *newNode = new Node<T>(data, NULL);
        Node<T> *tmp = head;
        if (tmp != NULL) {
            while (tmp->Next() != NULL) {
                tmp = tmp->Next();
            }
            tmp->setNext(newNode);
        }
        else {
            head = newNode;
        }
    }
    void Delete(T data) {
        Node<T> *tmp = head;
        if (tmp == NULL) {
            cout << "Delete " << data << ": Data not found" << endl;
            return;
        }
        Node<T> *prev = NULL;
        do {
            if (tmp->getData() == data)
                break;
            prev = tmp;
            tmp = tmp->Next();
        } while(tmp != NULL);
        
        if( !tmp ) {
            cout << "Delete " << data << ": Data not found" << endl;
            return;
        }
        
        if( tmp == head )
            head = NULL;
        else
            prev->setNext(tmp->Next());
            
        delete tmp;
    }
    
    bool isEmpty() { return !head; }
    
    void Print() {
        Node<T> *tmp = head;
        if (isEmpty()) {
            cout << "Empty list" << endl;
            return;
        }
        while( tmp ) {
            cout << tmp->getData();
            cout << " --> ";
            tmp = tmp->Next();
        }
        cout << "NULL" << endl;
    }
    
};

int main()
{
    LList<string> names;
    names.Append("Raymond");
    names.Print();
    names.Append("David");
    names.Print();
    names.Append("Cynthia");
    names.Print();
    names.Delete("David");
    names.Print();
    names.Delete("Cynthia");
    names.Print();
    names.Delete("Raymond");
    names.Print();
    names.Delete("Raymond");
    return 0;
}