采用尾指针表示的单链表

/*
 * 单链循环链表：终点的指针域改为指向头节点
 * 采用尾指针表示单链循环表：查找开始节点和终端节点都很方便
*/

#include<iostream>
using namespace std;

class Chain;
class Node{
    friend class Chain;
private:
    char  _data;
    Node* _next;
};

class Chain{
public:
    Chain();
    bool Find(int i, Node*& x);
    bool Insert(int i, char& x);
    bool Delete(char x);
    ostream& display( ostream &out );
    friend ostream& operator << (ostream &out, const Chain &x);

private:
    Node* _head;
    int   _length;
    Node* _raear;
};

Chain::Chain()
{
    _head = new Node;
    _head->_next = _head;
    _length=0;
}

bool Chain::Find(int i, Node*& x){
    if(i<0 || i>_length) {cout << "out of index..." << endl; return false;}
    Node* p = _head;
    while(i--)  p=p->_next;
    x = p;
    return true;
}

bool Chain::Insert(int i, char& x){
    Node* pre_node; //store the address of node i-1
    if(Find(i, pre_node)==false) return false;
    Node* tmp = new Node;
    tmp->_data = x;
    tmp->_next = pre_node->_next;
    pre_node->_next= tmp;
    if(tmp->_next== _head) _raear = tmp;   //updata _raear
    _length++;
    return true;
}

ostream& Chain::display(ostream &out){
    //IsEmpty?
    int i= _length;
    if(i==0) return out;
    Node* p = _head->_next;
    while(--i){ cout << p->_data; p=p->_next;}
    return out;
}

ostream& operator<< (ostream &out, Chain &chain){
    chain.display(out);
    return out;
}

int main(){
char str[] = "su fang";
Chain w;
for(int i=0; str[i] != 0; i++)
    w.Insert(i, str[i]); 
cout << "input: " << str << endl;
cout << w << endl;
    return 0;
}