#include <iostream>
using namespace std;
template<typename T>
class CList;
template<class T>
class Node
{
 friend CList<T>;
private:
 T m_data;
 Node *m_pNext;
};
template<class T>
class CList
{
public:
 CList();
 ~CList();
 bool IsEmpty();
 void Append(const T &data);
 void Delete(const int &pos);
 void Print();
 int GetLength();
 T Find(const int &pos);
 void Insert(const int &pos,const T &data);
private:
 Node<T> *m_pHead;
 Node<T> *m_pEnd;
 int m_len;
 void Create();
 void Destroy();
};
//為頭結點分配空間
template<class T>
void CList<T>::Create()
{
 m_pHead = new Node<T>;
 m_pEnd = new Node<T>;
 m_pHead->m_pNext = NULL;
 m_pEnd->m_pNext = m_pHead->m_pNext;
 m_len = 0;
}
template<class T>
CList<T>::CList()
{
 Create();
}
//刪除所有結點
template<class T>
void CList<T>::Destroy()
{
 Node<T> *pF = m_pHead->m_pNext;
 Node<T> *pT;
 while(pF)
 {
  pT = pF;
  pF = pF->m_pNext;
  delete pT;
 }
}
template<class T>
CList<T>::~CList()
{
 Destroy();
}
//判斷是否為空
template<class T>
bool CList<T>::IsEmpty()
{
 if(!m_pHead->m_pNext)
 {
  return true;
 }
 else
 {
  return false;
 }
}
//從表的最后加入一個元素
template<class T>
void CList<T>::Append(const T &data)
{
 Node<T> *pT = new Node<T>;
 pT->m_data = data;
 pT->m_pNext = NULL;
 if(!m_pHead->m_pNext)
 {
  m_pHead->m_pNext = pT;
 }
 else
 {
  (m_pEnd->m_pNext)->m_pNext = pT;
 }
 m_pEnd->m_pNext = pT;
 ++m_len;
}
//刪除一個元素
template<class T>
void CList<T>::Delete(const int &pos)
{
 if(pos < 0 || pos < m_len)
 {
  cout<<"位置不合法"<<endl;
  return;
 }
 Node<T> *pPre = NULL;//存放前一個結點
 Node<T> *pBehind = NULL;//存放后一個結點
 Node<T> *pT = m_pHead->m_pNext;//目標結點
 int ix = -1;
 while(pT)
 {
  ++ix;
  if(ix == pos - 1 - 1)
  {
   pPre = pT;
  }
  else if(ix == pos - 1)
  {
   pBehind = pT->m_pNext;
   break;
  }
  pT = pT->m_pNext;
 }
 if(!pPre)//如果指針為空則說明pos是指第一個元素
 {
  delete pT;
  m_pHead->m_pNext = pBehind;
  --m_len;
  return;
 }
 if(!pBehind)//如果指針為空則說明pos是指最后一個元素
 {
  m_pEnd = pPre;
  delete pT;
 }
 pPre->m_pNext = pBehind;
 --m_len;
}
//輸出所有數據
template<class T>
void CList<T>::Print()
{
 Node<T> *pT = m_pHead->m_pNext;
 while(pT)
 {
  cout<<pT->m_data<<",";
  pT = pT->m_pNext;
 }
 cout<<endl;
}
template<class T>
int CList<T>::GetLength()
{
 return m_len;
}
//查找數據
template<class T>
T CList<T>::Find(const int &pos)
{
 if(pos <= 0)
 {
  cout<<"輸入不合法"<<endl;
  return NULL;
 }
 if(pos > m_len)
 {
  cout<<"超出表長"<<endl;
  return NULL;
 }
 int i = 0;
 Node<T> *pT = m_pHead->m_pNext;
 while(pT)
 {
  ++i;
  if(i == pos)
  {
   return pT->m_data;
  }
  pT = pT->m_pNext;
 }
 return NULL;
}
template<class T>
void CList<T>::Insert(const int &pos,const T &data)
{
 if(pos <= 0 || pos >m_len)
 {
  cout<<"輸入不合法"<<endl;
  return;
 }
 int i = 0;
 Node<T> *pT = m_pHead->m_pNext;
 Node<T> *pPre = NULL;
 Node<T> *pBehind = NULL;
 while(pT)
 {
  ++i;
  if(i == pos - 1)
  {
   pPre = pT;
  }
  if(i == pos)
  {
   pBehind = pT->m_pNext;
   break;
  }
  pT = pT->m_pNext;
 }
 Node<T> *pNew = new Node<T>;
 pNew->m_data = data;
 if(!pPre)//如果指針為空則說明pos是指第一個元素
 {
  pNew->m_pNext = m_pHead->m_pNext;
  m_pHead->m_pNext = pNew;
  ++m_len;
  return;
 }
 if(!pBehind)//如果指針為空則說明pos是指最后一個元素
 {
  m_pEnd->m_pNext = pNew;
 }
 pPre->m_pNext = pNew;
 pNew->m_pNext = pT;
 ++m_len;
}