Структуру данных, которая точнее всех соответствует диаграмме последовательности в библиотеке STL, называют связанным списком (linked list). Стрелки в абстрактной модели обычно реализуются как указатели. Элемент связанного списка — это часть узла, состоящего из элемента и одного или нескольких указателей. Связанный список, в котором узел содержит только один указатель (на следующий узел), называют односвязным списком (singly-linked list), а список, в которой узел ссылается как на предыдущий, так и на следующий узлы, — двусвязным списком (doubly-linked list). Мы схематично рассмотрим реализацию двухсвязных списков, которые в стандартной библиотеке языка С++ имеют имя list. Графически список можно изобразить следующим образом.

В виде кода он представляется так:

template struct Link {

  Link* prev; // предыдущий узел

  Link* succ; // следующий узел

  Elem val;   // значение

};

template struct list {

  Link* first;

  Link* last; // узел, находящийся за последним узлом

};

Схема класса Link приведена ниже.

Существует много способов реализации и представления связанных списков. Описание списка, реализованного в стандартной библиотеке, приведено в приложении Б. Здесь мы лишь кратко перечислим основные свойства списка — возможность вставлять и удалять элементы, не трогая существующие элементы, а также покажем, как перемещаться по списку с помощью итератора, и приведем пример его использования.

Мы настоятельно рекомендуем вам, размышляя о списках, рисовать диаграммы, иллюстрирующие операции, которые вы рассматриваете. Манипуляции связанным списком — это тема, в которой один рисунок может заменить тысячу слов. 

20.4.1. Операции над списками

  Какие операции необходимы для списка?

• Операции, эквивалентные операциям над векторами (создание, определение размера и т.д.), за исключением индексирования.

• Вставка (добавление элемента) и стирание (удаление элемента).

• Нечто, что можно использовать для ссылки на элементы и перемещения по списку: итератор.

В библиотеке STL тип итератора является членом своего класса, поэтому и мы поступим так же.

template class list {

// детали представления и реализации

public:

  class iterator;      // тип — член класса :iterator

  iterator begin();    // итератор, ссылающийся на первый элемент

  iterator end( );     // итератор, ссылающийся на последний элемент

  iterator insert(iterator p, const Elem& v); // вставка v

                       // в список после элемента,

                       // на который установлен итератор p

  iterator erase(iterator p);     // удаление из списка элемента,

                       // на который установлен итератор p

  void push_back(const Elem& v);  // вставка v в конец списка

  void push_front(const Elem& v); // вставка v в начало списка

  void pop_front();               // удаление первого элемента

  void pop_back();                // удаление последнего элемента

  Elem& front();                  // первый элемент

  Elem& back();                   // последний элемент

  // ...

}

Так же как наш класс vector не совпадал с полной версией стандартного вектора, так и класс list — это далеко не полное определение стандартного списка. В этом определении все правильно; просто оно неполное. Цель “нашего” класса list — объяснить устройство связанных списков, продемонстрировать их реализацию и показать способы использования их основных возможностей. Более подробная информация приведена в приложении Б и в книгах о языке С++, предназначенных для экспертов.

Итератор играет главную роль в определении класса list в библиотеке STL. Итераторы используются для идентификации места вставки или удаления элементов. Кроме того, их используют для “навигации” по списку вместо оператора индексирования. Такое применение итераторов очень похоже на использование указателей при перемещении по массивам и векторам, описанном в разделах 20.1 и 20.3.1. Этот вид итераторов является основным в стандартных алгоритмах (разделы 21.1–21.3).