C++单链表类（实现丰富）

/* Linked List Declaration Author: Aqua Lo Department of Bio-Engineering South China University of Technology Please use under permission! */ #ifndef __LLink #define __LLink #include <iostream> #include "Link.h" using namespace std; using namespace aqua; namespace aqua { template <typename T> class LList: public Link<T> { private: Link<T>* head; Link<T>* tail; Link<T>* fence; //Pointer to list header //Pointer to last Element in list //Last element on left side int leftcnt,rightcnt; //Size of left partition //Size of right partition void init() //Initializtion routine { fence = tail = head = new Link<T>; leftcnt = rightcnt = 0; } void removeall() //Return link nodes to free store { while(head != NULL) { fence = head; head = head->next; delete fence; } } public: LList() { init(); } ~LList() { removeall(); } //friend istream& operator >> (istream&, T&); //friend ostream& operator << (ostream&, T&); void clear() { removeall(); init();} //Insert at front of right partition bool insert(const T& item) { fence->next = new Link<T>(item, fence->next); if(tail == fence) tail = fence->next; //New tail rightcnt++; return true; } //Append Element to end of the list bool append(const T& item) { tail = tail->next = new Link<T>(item, NULL); rightcnt++; return true; } //Remove and return first element in right partition bool remove(T& it) { if(fence->next == NULL) return false; //Empty right it = fence->next->element; //Remember value Link<T>* ltemp = fence->next; //Remember link node fence->next = ltemp->next; //Remove from list if(tail == ltemp) tail = fence; //Reset tail delete ltemp; //Reclaim space rightcnt--; return true; } void setStart() { fence = head; rightcnt += leftcnt; leftcnt = 0; } void setEnd() { fence = tail; leftcnt += rightcnt; rightcnt = 0; } //Move fence ont step left; no change if left is empty void prev() { Link<T>* temp = head; if(fence == head) return; while (temp->next!=fence) temp = temp->next; fence = temp; leftcnt--; rightcnt++; } void next() { if(fence != tail) //Don't move fence if right empty { fence = fence->next; rightcnt--; leftcnt++; } } int leftLength() const {return leftcnt;} int rightLength() const {return rightcnt;} //Set the size of left partition to pos bool setPos(int pos) { if((pos < 0) || (pos > rightcnt+leftcnt)) return false; fence = head; for(register int(0); i<pos; i++) fence = fence->next; return true; } bool getValue(T& it) const { if(rightLength() == 0) return false; it = fence->next->element; return true; } void print() const { Link<T>* temp = head; cout<<"< "; while(temp != fence) { cout<<temp->next->element<<" "; temp = temp->next; } cout<<"| "; while(temp->next != NULL) { cout<<temp->next->element<<" "; temp = temp->next; } cout<<">\n"; } }; } #endif