#ifndef XHSX_LINKLIST_H
#define XHSX_LINKLIST_H

template <class T>
class LinList;
template <class T>
class DuLNode
{
	friend class LinList<T>;
	private:
		DuLNode<T> *next;
		DuLNode<T> *pre;
		T data;
	public:
		DuLNode(DuLNode<T> *ptrNext=NULL, DuLNode<T> *prior=NULL)
		{
			next=ptrNext;
			pre=prior;
		    data=NULL;
		}
		DuLNode(const T& item,DuLNode<T> *ptrNext=NULL,DuLNode<T> *prior=NULL)
		{
			data=item;
			next=ptrNext;
			pre=prior;
		}
		~DuLNode(void){}
};

//雙鏈表的定義
template <class T>
class LinList
{
	private:
		DuLNode<T> *head;
		int size;
		DuLNode<T> *Index(int i);//定位
	public:
		LinList(void);
		~LinList(void);
		int Size(void) const;
		void Insert(const T& item,int i);//插入
		T Delete(int i);//刪除
		T GetData(int i);//取數據元素
};

template <class T>
LinList<T>::LinList()
{
	head=new DuLNode<T>();
	head->next=head;
	head->pre=head;
	size=0;
}

template <class T>
LinList<T>::~LinList(void)
{
	DuLNode<T> *p,*q;
	p=head;//p指向第一個結點
	while(p->next!=head)
	{
		q=p;
		p=p->next;
		delete q;
	}
	size=0;
	head=NULL;
}

template <class T>
DuLNode<T> *LinList<T>::Index(int i)//定位
{
	if(i<-1||i>size-1)
	{
		cout<<"參數i越界!"<<endl;
		exit(0);
	}
	if(i==-1) return head;
	DuLNode<T> *p=head->next;
	int j=0;
	while(j<i)
	{
		p=p->next;
		j++;
	}
	return p;//返回第i個結點的指針
}

template <class T>
int LinList<T>::Size(void) const
{
	return size;
}

template <class T>
void LinList<T>::Insert(const T& item,int i)//插入
{
	if(i<0||i>size)
	{
		cout<<"參數i越界出錯!"<<endl;
		exit(0);
	}
	DuLNode<T> *p=Index(i-1);//p為指向第i-1個結點的指針
	DuLNode<T> *q= new DuLNode<T>(item,p->next);
	q->pre=p;
	q->next=p->next;
	p->next->pre=q;
	p->next=q;
	size++;
}

template <class T>
T LinList<T>::Delete(int i)//刪除
{
	if(size==0)
	{
		cout<<"The Double is empty!"<<endl;
		exit(0);
	}
	if(i<0||i>size-1)
	{
		cout<<"參數i越界出錯"<<endl;
	exit(0);
	}
	DuLNode<T> *s, *p=Index(i-1);
	s=p->next;
	T x=s->data;
	p->next=(p->next)->next;
	(p->next)->pre=p;
	delete s;
	size--;
	return x;
}

template <class T>//取數據元素
T LinList<T>::GetData(int i)
{
	if(i<0||i>size-1)
	{
		cout<<"參數i越界出錯"<<endl;
		exit(0);
	}
	DuLNode<T> *p=Index(i);
	return p->data;
}

#endif