#ifndef LINKLIST_H_
#define LINKLIST_H_
/////////////////////////////////////////////////////////////////////////////

#include <iostream>
#include "Node.h"
using namespace std;

template<class T>
class LinkList {
public:
    LinkList();
    ~LinkList();

    void addfront(T _data);  //Done O(1)
    T showfront();           //Done O(1)
    void erasefront();          //Done O(1)

    void addend(T _data);    //Done O(1)
    T showend();             //Done O(1)
    void eraseend();            //Done O(n)

    bool find(T _data);      //Done O(n)
    void erase(T _data);     //Done O(n)
    bool isempty();             //Done O(1)

    void print();               //Done O(n)
    void clear();               //Done O(n)

private:
    Node<T> *head, *tail;
    int sz;
};

template<class T>
LinkList<T>::LinkList() {
    head = tail = 0;
    sz = 0;
}

template<class T>
LinkList<T>::~LinkList() {
    Node<T> *tp;
    while (head != 0) {
        tp = head->next;
        delete head;
        head = tp;
    }
}

/////////////////////////////////////////////////////////
template<class T>
void LinkList<T>::addfront(T _data) {
    Node<T> *tp = new Node<T>(_data);
    if (head == 0)
        head = tp;
    else {
        tp->next = head;
        head = tp;
    }
    if (tail == 0)
        tail = tp;
    sz++;
}

template<class T>
T LinkList<T>::showfront() {
    if (head == 0)
        return 0;
    return head->data;
}

template<class T>
void LinkList<T>::erasefront() {
    Node<T> *tp = head;
    if (head == tail)
        head = tail = 0, sz = 0;
    else
        head = head->next, sz--;
    delete tp;
}

template<class T>
void LinkList<T>::addend(T _data) {
    Node<T> *tp = new Node<T>(_data);
    if (tail == 0) {
        head = tp;
        tail = tp;
    } else {
        tail->next = tp;
        tail = tp;
    }
    sz++;
}

template<class T>
T LinkList<T>::showend() {
    if (tail == 0)
        return -1;
    return tail->data;
}

template<class T>
void LinkList<T>::eraseend() {
    Node<T> *tp;
    for (tp = head; tp->next != tail; tp = tp->next)
        ;
    delete tail;
    tail = tp;
    tail->next = 0;
    sz == 0 ? sz = 0 : sz--;
}

template<class T>
bool LinkList<T>::find(T _data) {
    Node<T> *tp;
    for (tp = head; tp->next != 0; tp = tp->next) {
        if (tp->data == _data)
            return true;
    }
    return (tail->data == _data);
}

template<class T>
void LinkList<T>::erase(T _data) {
    if (head == tail)
        head = tail = 0;
    else if (tail->data == _data)
        eraseend();
    else if (head->data == _data)
        erasefront();
    else {
        Node<T> *tp;
        int cnter1 = 0, cnter2 = 0;
        for (tp = head; tp->next != 0; tp = tp->next) {
            if (tp->data == _data)
                break;
            cnter1++;
        }
        Node<T> *tp1;
        for (tp1 = head; tp1->next != 0; tp1 = tp1->next) {
            cnter2++;
            if (cnter1 == cnter2)
                break;
        }
        tp1->next = tp->next;
        delete tp;
        sz--;
    }
}

template<class T>
bool LinkList<T>::isempty() {
    if (head == 0)
        return true;
    return false;
}

template<class T>
void LinkList<T>::print() {
    if (head == 0)
        return;
    Node<T> *tp;
    for (tp = head; tp->next != 0; tp = tp->next) {
        cout << tp->data << " ";
    }
    if (sz > 1)
        cout << tail->data << endl;
}

template<class T>
void LinkList<T>::clear() {
    Node<T> *tp;
    while (head != 0) {
        tp = head->next;
        delete head;
        head = tp;
    }
    head = tail = 0;
}



/////////////////////////////////////////////////////////////////////////////
#endif /* LINKLIST_H_ */