#include <iostream>
#include <string>
#include <iterator>

using namespace std;

template <typename T>
class List
{
    private:
        // 노드갯수
        int         node_num;
        // NODE데이터를 저장할 구조체 
        struct Node
        {
            T    Data;
            Node *NextNode;
        };
        Node *mNode;  // 노드 할당을 위해서 사용한다. 
        Node *SNode;  // 시작노드를 포인트한다.
        Node *NNode;  // 다음노드를 포인트한다.  
        Node *ENode;  // 마지막노드를 포인트한다.

    public:
        // 생성자
        List()
        {
            node_num = 0;
        };

        // 삽입관련 메서드 ------------------------

        // 가장뒤에 노드를 추가한다. 
        // 마지막 노드 정보를 가지고 있음으로 
        // 새로운 노드를 할당하고 기존의 마지막노드가 
        // NULL대신 새로할당된 노드를 가리키게 하면 된다. 
        void push_back(T data)
        {
            mNode = new Node;
            mNode->Data     = data;
            mNode->NextNode = NULL;

            if (node_num == 0)
            {
                SNode = mNode;
                ENode = mNode;
            }
            else
            {
                ENode->NextNode = mNode;
                ENode = mNode;
            }
            node_num++;
        };

        // 가장앞에 노드를 추가한다. 
        // 만약 처음으로 노드가 추가되는거라면 
        // 이 노드는 다음노드로 NULL을 가리키게 된다. 
        // 그렇지 않을경우 기존에 가장 처음에 있던 노드를 
        // 가리키게 된다. 
        void push_front(T data)
        {
            mNode = new Node;
            mNode->Data     = data;
            mNode->NextNode = NULL;
            if (node_num == 0)
            {
                SNode =  mNode;
            }
            else
            {
                mNode->NextNode = SNode;
                SNode =  mNode;
            }
            node_num++;
        };

        // 임의의 위치에 노드를 삽입한다.  
        int insert(T data, int position)
        {
            Node *PNode;
            int i = 0;
            if (position > node_num)
            {
                return -1;
            }

            // 처음과 마지막 위치에 
            // 삽입할때는 이미 만들어진 메서드를
            // 활용한다.
            if (position == 0)
            {
                push_front(data);
                return 1;
            }
            if (position == node_num)
            {
                push_back(data);
                return 1;
            }

            mNode = new Node;
            mNode->Data     = data;
            mNode->NextNode = NULL;

            NNode = SNode;
            while(NNode)
            {
                if (i == position)
                {
                    mNode->NextNode = NNode;
                    PNode->NextNode = mNode;
                    node_num++;
                    break;
                }
                PNode = NNode;
                NNode = NNode->NextNode;
                i++;
            }
            return 1;
        }


        // 삭제 관련 메서드 -------------------------
        // 가장앞에 있는 노드를 삭제
        void pop_front()
        {
            NNode = SNode->NextNode;
            delete SNode;
            SNode = NNode;
            node_num--;
        }

        // 가장뒤에 있는 노드를 삭제
        // 싱글 링크드 리스트라서 가장뒤에 있는 노드를 
        // 지울경우 어쩔수 없이 처음부터 노드를 검색하는 수 
        // 밖에 없다. 
        // 더블링크드 리스트라면 좀더 쉽게 삭제 가능할것이다.  
        void pop_back()
        {
            int i = 0;
            Node *PNode;
            NNode = SNode;

            while(1)
            {
                if(i == node_num - 1)
                {
                    PNode->NextNode = NULL;
                    delete(NNode);
                    break;
                }
                PNode = NNode;
                NNode = NNode->NextNode;
                i++;
            }
            node_num--; 
        }


        // 값 가져오기 메서드 -----------------------

        // 가장앞의 노드에서 데이터를 가져온다.
        T front()
        {
            return SNode->Data; 
        }

        // 가장뒤의 노드에서 데이터를 가져온다.
        T back()
        {
            return ENode->Data;
        }

        // 노드를 순환하면서 모든 데이터를 출력한다.
        void show()
        {
            NNode = SNode;

            while(NNode)
            {
                cout << NNode->Data << endl;
                NNode = NNode->NextNode;
            }
        }

        // 임의의 위치에 있는 노드의 데이터를 
        // 가져온다.  
        // 이 메서드는 비효율적이고 깔끔하지 못하다. 
        // 바꿔보자. 
        T get(int num)
        {
            int i = 0;
            if (num > node_num)
            {
                return NULL;
            }
            NNode = SNode;
            while(i < num)
            {
                NNode = NNode->NextNode;
                i++;
            }
            return NNode->Data;
        }

        // 부가 메서드 ----------------------------- 
        int size()
        {
            return node_num;
        }
};

int main()
{
    List<string> list;

    // 테스트
    list.push_back("A");
    list.push_back("B");
    list.push_back("C");
    list.push_front("D");
    list.insert("100", 1);
    list.push_front("101");

    cout << "Size " << list.size() << endl;
    cout << "First Data is " << list.front() << endl;
    cout << "Last Data is " << list.back() << endl;
    list.show();

    list.pop_front();
    list.show();

    list.pop_back();
    list.show();

    cout <<"GET DATA" << list.size() << endl;
    for (int i =0; i < list.size(); i++)
    {
        cout << list.get(i) << endl;
    }
}