Шаблон класса двусвязный список - C++ - Ответ 1753170

#include <iostream>
 
// базовый класс элемента связного списка
// не содержит данных, содержит часть логики
struct NodeBase {
  NodeBase *prev; // указатель на предыдущий элемент связного списка
  NodeBase *next; // указатель на следующий элемент связного списка
  // при создании объекта класса конструктор по-умолчанию
  // назначает следующий и предыдущий элемент указывать на себя 
  NodeBase() : prev(this), next(this) {}
  // при создании с таким констуктором, элемент добавляет сам себя
  // в связный список, представляя себя предыдущему и следующему элементу
  NodeBase(NodeBase *prev_, NodeBase *next_)
    : prev(prev_), next(next_) { // назначаются предыдущий и следующий элементы
    // у предыдущего элемента следующим элементом назначается данный элемент
    // и у следующего элемента предыдущим элементом назначается данный элемент
    prev->next = next->prev = this;
  }
  // деструктор. при удалении элемента связного списка, 
  // элемент убирает сам себя из списка
  virtual ~NodeBase() {
    prev->next = next;
    next->prev = prev;
  }
};
 
// элемент связного списка, уже содержащий данные.
template <typename ValueType>
struct Node: public NodeBase{
  ValueType value; // то значение, которое хранит класс
  // конструктор подставляет значения и вызывает конструтор предка
  Node(NodeBase *prev_, NodeBase *next_, ValueType value)
    : NodeBase(prev_, next_), value(value) {}
};
 
// собственно, шаблон двусвязного списка
// смотрите, как мало собственно кода, если убрать комментарии
template <typename ValueType>
class List {
 public:
  // конструктору по-умолчанию делать в принципе нечего, он должен быть объявлен
  List() : base() {};
  // деструктор удаляет список функцией Clear
  ~List() {
    Clear();
  }
  // функция проверяет, пустой ли список
  bool Empty() {
    // список пустой, если базовый элемент указывает сам на себя
    return ((base.next == &base) && (base.prev == &base));
  }
  void Clear() {
    // пока список не пуст
    while (!Empty())
      // удаляется первый элемент
      // работу по удалению из списка сделает деструктор класса элемента
      delete base.next;
  }
  // добавление элемента в конец списка
  void PushBack(const ValueType &value) {
    // просто создается новый элемент списка,
    // всё остальное сделает конструктор класса NodeBase
    new Node<ValueType>(base.prev, &base, value);
  }
  // удаление последнего элемента
  void PopBack() {
    // удаляется элемент связного списка 
    // (в данном случае последний, но в принципе, сработает с любым)
    // работу по фактическому удалению элемента из списка выполнит деструктор
    // класса NodeBase
    delete base.prev;
  }
  // плохой стиль, лучше делать через итераторы, но эта концепция, наверно,
  // слишком сложна
  void PrintAll() {
    // перебор всех элементов в одном цикле
    for (NodeBase *node = base.next; node != &base; node = node->next)
      // для получения значения элемент списка приводится к типу Node*
      std::cout << static_cast< Node<ValueType>* >(node)->value;
  }
 private:
  // базовый эелемент.
  // его поле next указывает на первый элемент списка
  // поле prev указываеты на последний элемент списка
  // если список пуст, next == prev == &base
  NodeBase base;
};
 
// класс автобуса
struct Bus {
  int number;
  int route;
  //... тут наверно нужны другие поля
  Bus(int number_, int route_) : number(number_), route(route_) {}
  // переопределенный оператор для вывода на экран
  friend std::ostream& operator<<(std::ostream &stream, const Bus &bus) {
    return stream << "Bus number " << bus.number
                  << ", route: " << bus.route
                  << std::endl;
  }
};
 
int main(int argc, char *argv[]) {
  List<Bus> a; // список автобусов
  // добавим в список сто автобусов
  for (int i = 0; i < 100; ++i)
    a.PushBack(Bus(i + 1, i));
  // вывод его на экран
  a.PrintAll();
}