Круговой связанный список в C++ (вставить в начале)

Question

Я изучаю старые экзамены на экзамен. Одной из задач является реализация функции вставки и печати, которая вставляет элементы в начале циклического списка. Программа предназначена для тестирования решения студентов.

Мое решение для вставки:

void Circular_List::insert(std::string const& str)
{
    if (entry == nullptr) {
        entry = new Element(str);
        entry -> next = entry;
    }
    else {
        Element* temp = entry;
        entry = new Element(str);
        entry -> next = temp;
    }
}

Мой мыслительный процесс:

Кажется, работает, потому что мой принт:

void Circular_List::print() const
{
    Element* temp = entry;
    while (temp -> next != temp) {
        cout << temp -> name << endl;
        temp = temp -> next; 
    }
}

печатает список в правильном порядке, КРОМЕ для элемента, который я впервые добавил. Я не понимаю, почему не печатается первый элемент. Программа предусматривает печать 20 итераций. Например, если я вставлю a,b,c,d,e, программа напечатает

D-> C-> b-> а-> а-> а-> а-> а-> а-> а-> а-> а-> а-> а-> а-> а-> а- > a-> a-> a->

Это кажется очень странным, не следует ли зацикливаться на передней части списка, вместо того, чтобы просто печатать?

Тестовая программа:

  int j = 0;
  for (Circular_List::Iterator i = l.begin(); i != l.end() && j < 20; ++i, ++j)
  {
    cout << *i << "->";
  }
  cout << endl;

class Iterator
  {
  public:
    Iterator(Element* e) : pos(e) {}
    ~Iterator() = default;
    Iterator(Iterator const&) = default;
    Iterator& operator=(Iterator const&) = default;
    bool operator!=(Iterator const& i) { return pos != i.pos; }
    operator bool() { return pos != nullptr; }
    Iterator& operator++() { pos = pos->next; return *this;}
    std::string operator*() { return pos->name; }
  private:
    Element* pos;
  };

Я предполагаю, что моя вставка неверна, но я не могу понять, что я делаю неправильно?

Answer 1

Когда вы вставляете второй элемент в список, ваш первый элемент сохраняет следующую запись, указывая на себя. Вам необходимо обновить два следующих поля: одно во вставленной записи и другое в списке, чтобы указать на вставленную запись. Вы не в состоянии сделать последнее. Условие else должно быть:

    Element* temp = new Element(str);
    temp->next = entry->next;
    entry->next = temp;
    entry = temp;

Это делает entry указателем на элемент цикла LAST и entry->next - первый элемент цикла;

Кстати, ваш второй рисунок неверен, так как "а" -> следующий должен указывать обратно на "а", а не на вход.