/*
 * http://otvety.google.ru/otvety/thread?tid=6c39c9a906b76726
 * v1.0
 */

#include <iostream>
#include <string>

using namespace std;

class CircularStringList {

 public:

  explicit CircularStringList() : tail_(NULL) {}
  ~CircularStringList();

  void Add(const string& value);
  void Delete(const string& value);
  bool Has(const string& value);
  void Print();

 private:

  struct Element {
    string value;
    Element* next;
  };

  Element* tail_;

};

void CircularStringList::Add(const string& value) {
  Element* e = new Element();
  e->value = value;
  if (!tail_) {  // пустой список - начать
    e->next = e;
    tail_ = e;
  } else {       // не пустой - вставить в хвост, передвинуть хвост
    e->next = tail_->next;
    tail_->next = e;
    tail_ = e;
  }
}

void CircularStringList::Delete(const string& value) {
  if (!tail_) return;
  Element* prev = tail_;
  Element* e = tail_->next;
  while (true) {
    if (e->value == value) {  // будем удалять
      if (e == tail_) tail_ = prev;  // удаляем хвост - отодвигаем его назад
      prev->next = e->next;
      delete e;
      if (e == prev) {  // удалили последний элемент - обнулить хвост и на выход
        tail_ = NULL;
        break;
      }
      e = prev->next;
    } else {                 // не будем удалять, идём дальше
      prev = e;
      e = e->next;
      if (e == tail_->next) break;  // сделали круг, вышли на начало списка
    }
  }
}

bool CircularStringList::Has(const string& value) {
  if (!tail_) return false;
  Element* e = tail_;
  do {
    if (e->value == value) return true;
    e = e->next;
  } while (e != tail_);
  return false;
}

void CircularStringList::Print() {
  cout << "List: ";
  if (tail_) {
    // начинаем со следующего после хвоста элемента, т.е. с головы
    Element* e = tail_->next;
    do {
      cout << e->value << " ";
      e = e->next;
    } while (e != tail_->next);
  }
  cout << endl;
}

CircularStringList::~CircularStringList() {
  Element* e = tail_;
  while (e) {
    Element* next = e->next;
    delete e;
    if (next == tail_) break;
    e = next;
  }
}

int main(void) {
  CircularStringList l;
  l.Print();
  l.Add("foo"); l.Print();
  cout << l.Has("foo") << " " << l.Has("bar") << endl;
  l.Add("bar"); l.Print();
  cout << l.Has("foo") << " " << l.Has("bar") << endl;
  l.Delete("foo"); l.Print();
  cout << l.Has("foo") << " " << l.Has("bar") << endl;
  l.Delete("bar"); l.Print();
  cout << l.Has("foo") << " " << l.Has("bar") << endl;
  l.Add("a"); l.Add("b"); l.Add("a"); l.Add("b"); l.Print();
  l.Delete("b"); l.Print();
  l.Add("c"); l.Print();
  l.Delete("a"); l.Print();
  l.Add("c"); l.Print();
  l.Delete("c"); l.Print();
  return 0;
}