// 鏈表類模板
template <class Elem> class LList {
private:
  CLink<Elem>* head;       // 指向頭結點的指針
  CLink<Elem>* tail;       // 尾指針 
  CLink<Elem>* fence;      // 鏈表中的自由指針
  int leftcnt;            // fence指向元素左側的元素數目
  int rightcnt;           // fence指向元素右側的元素數目
  void init() {
    fence = tail = head = new CLink<Elem>;
    leftcnt = rightcnt = 0;
  }
 
 
// 釋放鏈表 
void removeall() {   
    while(head != NULL) {
      fence = head;
      head = head->next;
      delete fence;
    }
  }
public:

  LList() { init(); }

  ~LList() { removeall(); }

  void clear() { removeall(); init(); }
  

 
 // 在fence指針指向元素的下一個元素前插入一個新的元素  
  bool insert(const Elem& item) 
 {
  fence->next = new CLink<Elem>(item, fence->next);  
  if (tail == fence) tail = fence->next;
  rightcnt++;
  return true;
}

  

// 在鏈表末尾添加新的節點 
  bool append(const Elem& item)
 {
  tail = tail->next = new CLink<Elem>(item, NULL);
  rightcnt++;
  return true;
}
  

  
// 移除fence指針指向元素的下一個元素，并返回所移除元素的值
 bool remove(Elem& it) {
  if (fence->next == NULL) return false; // 如果fence指針指向的元素是末節點，則不做任何改變
  it = fence->next->element;       // 記住節點中的數據
  CLink<Elem>* ltemp = fence->next; // 記住將要移除的節點
  fence->next = ltemp->next;       // 將節點從鏈表中移除
  if (tail == ltemp) tail = fence; // 重新設置尾指針
  delete ltemp;                    // 釋放空間
  rightcnt--;
  return true;
}


 // 判斷鏈表是否為空
 bool is_empty()
{ 
  if(head->next==NULL)  return true;
  else return false;
}


 void setStart()  // 將fence指針指向頭節點
    { fence = head; rightcnt += leftcnt; leftcnt = 0; }
 
 
 
 void setEnd()   // 將fence指針指向末節點
    { fence = tail; leftcnt += rightcnt; rightcnt = 0; }
 

 
 // 將fence指針向左移動一個節點，如果其左邊沒有節點，則不移動 
  void prev()
{
  CLink<Elem>* temp = head;
  if (fence != head){
	while (temp->next!=fence) temp=temp->next;
	fence = temp;
	leftcnt--; rightcnt++;
  }
} 

  
// 將fence指針向右移動一個節點，如果其右邊沒有節點，則不移動
  void next()
{
    if (fence != tail)
      { fence = fence->next; rightcnt--; leftcnt++; }
}
  
  int leftLength() const  { return leftcnt; }   // 返回fence指針指向元素左側的元素數目
  
  int rightLength() const { return rightcnt; }    // 返回fence指針指向元素右側的元素數目
 
 


// 設置fence指向元素左側的元素數目  
  bool setPos(int pos)
{
  if ((pos < 0) || (pos > rightcnt+leftcnt)) return false;
  fence = head;
  for(int i=0; i<pos; i++) fence = fence->next;
  return true;
}

 
  
// 返回fence指向元素右側的第一個元素
bool getValue(Elem& it) const {
    if(rightLength() == 0) return false;
    it = fence->next->element;
    return true;
}
  
  
// 將fence指針指向指定值的元素 
bool Locate( Elem& it)
{
 fence= head;
 while((fence->next != NULL)&&(fence->next->element!=it))  fence=fence->next;
 if( fence->next==NULL) return false;
 else return true;
}

};