#include <iostream>
#include <assert.h>
using namespace std;


template< class T >
class List
{
public:
List()
{
m_pHead = m_pRear = nullptr; //初始化头结点和尾节点
m_uSize = 0; 
}
virtual ~List(){}
private:
struct Node
{
Node( T data, Node* pPrev, Node* pNext )
{
this->data = data;
this->pPrev = pPrev;
this->pNext = pNext;
}
T data; //数据
Node* pPrev, * pNext;  //前节点、后节点
};
public:
bool empty() { return !m_pHead || !m_pRear; } //判断链表是否为空
void Push_back( T data ) //末端插入数据
{
m_pRear = new Node( data, m_pRear, nullptr ); //新建节点并在构造时设置该节点的前节点为尾节点、后节点为空，同时该节点自己被赋为尾节点
if( m_pRear->pPrev ) //判断尾节点是否有前节点
{
m_pRear->pPrev->pNext = m_pRear; //把尾节点的前节点的后节点设置为尾节点
}
if( empty() ) //判断该链表是否为空
{
m_pHead = m_pRear; //头结点等于尾节点
}
m_uSize++; //链表节点数增加
}
void Push_front( T data ) //头端插入数据
{
m_pHead = new Node( data, nullptr, m_pHead ); //新建节点并在构造时设置该节点的后节点为头节点、前节点为空，同时该节点自己被赋为头节点
if( m_pHead->pNext ) //判断头结点是否有后节点
{
m_pHead->pNext->pPrev = m_pHead; //把头结点的后节点的前节点设置为头结点
}
if( empty() ) //判断该链表是否为空
{
m_pRear = m_pHead; //尾节点等于头结点
}
m_uSize++; //链表节点数增加
}
void Pop_back() //末端删除数据
{
assert( !empty() ); //断言，如果该链表为空成立，报错
auto ReplaceNode( m_pRear ); //定义一个临时节点等于尾节点
m_pRear = m_pRear->pPrev; //尾节点等于尾节点的前节点
if( m_pRear ) //判断为节点是否位空
{
m_pRear->pNext =  nullptr; //尾节点的后节点赋值为空
}
else
{
m_pHead = nullptr; //头结点赋值为空
}
delete ReplaceNode; //删除该节点
ReplaceNode = nullptr;  
m_uSize--; //链表节点数减少
}
void Pop_front() //头端删除数据
{
assert( !empty() ); //断言，如果该链表为空成立，报错
auto ReplaceNode( m_pHead );  //定义一个临时节点等于头节点
m_pHead = m_pHead->pNext; //头结点等于头结点的后节点
if( pHead ) //判断头结点是否为空
{
m_pHead->pPrev = nullptr; //头结点的前节点等于空
}
else
{
m_pRear = nullptr; //尾节点赋值为空
}
delete ReplaceNode; //删除该节点
ReplaceNode = nullptr;
m_uSize--; //链表节点数减少
}
T Back() //返回该链表的末端数据
{
return m_pRear->data; //返回尾节点的数据
}
unsigned int Size() //返回该链表的节点数
{
return m_uSize;
}
private:
Node* m_pHead, *m_pRear; //头结点、尾节点
unsigned int m_uSize; //该链表的节点数
};


void main()
{
List< int >l;
l.Push_back( 12 ); //末端插入
l.Push_back( 13 ); //末端插入
l.Push_front( 77 ); //头端插入
l.Push_back( 55 ); //末端插入
while( !l.empty() ) //如果链表为空，跳出循环
{
cout << l.Back() <<endl; //打印链表末端数据
l.Pop_back(); //删除链表末端数据
}
while( 1 );
}