//************************  intSLList.h  **************************
//           singly-linked list class to store integers

#ifndef INT_LINKED_LIST
#define INT_LINKED_LIST

class IntSLLNode {
public:
    IntSLLNode() {
        next = 0;
    }
    IntSLLNode(int el, IntSLLNode *ptr = 0) {
        info = el; next = ptr;
    }
    int info;
    IntSLLNode *next;
};

class IntSLList {
public:
    IntSLList() {
        head = tail = 0;
    }
    ~IntSLList();
    int isEmpty() {
        return head == 0;
    }
    void addToHead(int);
    void addToTail(int);
    int  deleteFromHead(); // delete the head and return its info;
    int  deleteFromTail(); // delete the tail and return its info;
    void deleteNode(int);
    bool isInList(int) const;
    void printAll() const;
private:
    IntSLLNode *head, *tail;
};

#endif

//************************  intSLList.cpp  **************************

#include <iostream>
#include "intSLList.h"

using namespace std;

IntSLList::~IntSLList() {
    for (IntSLLNode *p; !isEmpty();) {
        p = head->next;
        delete head;
        head = p;
    }
}

void IntSLList::addToHead(int el) {
    head = new IntSLLNode(el, head);
    if (tail == 0)
        tail = head;
}

void IntSLList::addToTail(int el) {
    if (tail != 0) {      // if list not empty;
        tail->next = new IntSLLNode(el);
        tail = tail->next;
    }
    else head = tail = new IntSLLNode(el);
}

int IntSLList::deleteFromHead() {
    int el = head->info;
    IntSLLNode *tmp = head;
    if (head == tail)     // if only one node on the list;
        head = tail = 0;
    else head = head->next;
    delete tmp;
    return el;
}

int IntSLList::deleteFromTail() {
    int el = tail->info;
    if (head == tail) {   // if only one node on the list;
        delete head;
        head = tail = 0;
    }
    else {                // if more than one node in the list,
        IntSLLNode *tmp; // find the predecessor of tail;
        for (tmp = head; tmp->next != tail; tmp = tmp->next);
        delete tail;
        tail = tmp;      // the predecessor of tail becomes tail;
        tail->next = 0;
    }
    return el;
}

void IntSLList::deleteNode(int el) {
    if (head != 0)                     // if non-empty list;
    if (head == tail && el == head->info) { // if only one
        delete head;                       // node on the list;
        head = tail = 0;
    }
    else if (el == head->info) {  // if more than one node on the list
        IntSLLNode *tmp = head;
        head = head->next;
        delete tmp;              // and old head is deleted;
    }
    else {                        // if more than one node in the list
        IntSLLNode *pred, *tmp;
        for (pred = head, tmp = head->next; // and a non-head node
            tmp != 0 && !(tmp->info == el);// is deleted;
            pred = pred->next, tmp = tmp->next);
        if (tmp != 0) {
            pred->next = tmp->next;
            if (tmp == tail)
                tail = pred;
            delete tmp;
        }
    }
}

bool IntSLList::isInList(int el) const {
    IntSLLNode *tmp;
    for (tmp = head; tmp != 0 && !(tmp->info == el); tmp = tmp->next);
    return tmp != 0;
}

void IntSLList::printAll() const {
    for (IntSLLNode *tmp = head; tmp != 0; tmp = tmp->next)
        cout << tmp->info << " ";
    cout << endl;
}

#include <iostream>
#include "intSLList.h"

using namespace std;

int main(int argc, char* argv[])
{
    int end;
    
    IntSLList *list = new IntSLList();

    list->addToHead(100);
    list->addToHead(200);
    list->addToHead(300);
    list->addToHead(400);
    list->addToHead(500);
    list->addToHead(999);

    list->printAll();

    delete list;

    cout << "-----------------------------------------------------------" << endl;

    IntSLList *list2 = new IntSLList();

    list2->addToTail(100);
    list2->addToTail(200);
    list2->addToTail(300);
    list2->addToTail(400);
    list2->addToTail(500);
    list2->addToTail(999);

    list2->printAll();

    delete list2;

    cout << "Press Any Key to Continue ... " << endl;
    cin >> end;

    return 0;
}