Класс итераторов для односвязных списков

После того, как мы написали классы узла и непосредственно списка, нужно добавить класс итераторов. Итераторы используются для перемещения по списку. Концепция итераторов широко распространена и используется со многими структурами данных.

код на языке с++
class SListIterator
{
public:
  SListNode* node;
  SLinkedList* list;
};

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

Методы класса итераторов

Все методы класса чрезвычайно просты.

Класс Iterator содержит конструктор с двумя аргументами.

код на языке с++
SListIterator(SListNode*,SLinkedList*);

SListIterator::SListIterator(SListNode* n, SLinkedList* l)
{
  node = n;
  list = l;
}

В конструктор передаются указатели на узел и список. Заполняются соответствующие поля.

Когда итератор добегает до конца списка, что должно происходить? Итератор не может вернуться в предыдущий элемент. Нужно уничтожать итератор и создавать новый? Вместо этого мы создадим функцию в которой итератор вернётся в начало списка.

код на языке с++
void Start();

void SListIterator::Start()
{
  node = list->head;
}

Тут всё просто, полю node мы присваиваем поле head переменной list. Здесь и list, и node являются членами класса Iterator.

Следующая функция передвигает итератор в следующий узел.

код на языке с++
void Forward();

void SListIterator::Forward()
{
if (node != NULL)
  node = node->next;
}

Обратите внимание на проверку условия. Мы можем продвинуть итератор вперёд на один узел дальше узла tail списка. Этот узел содержит значение NULL.

Следующая функция возвращает значение текущего узла.

код на языке с++
int& Item();

int& SListIterator::Item()
{
  return node->data;
}

Метод возвращает значение по ссылке.

И последняя функция итератора проверяет его значение. Если в итераторе содержится NULL (список закончился или в нём нет элементов), то функция вернёт 0. Если в итераторе содержится корректное значение, то функция вернёт 1.

код на языке с++
bool Valid();

bool SListIterator::Valid()
{
  return (node != NULL);
}

Теперь перепишем программу. Итератор может добавлять значение, обращаясь к своему полю node. Кроме того, теперь очень легко вывести все элементы списка.

код на языке с++
SLinkedList list;

list.PushBack(5);
list.PushBack(6);
list.PushBack(7);
list.PushFront(3);
list.PushFront(2);

SListIterator itr(list.head, &list);

itr.Forward();
itr.node->InsertAfter(4);

for (itr.Start(); itr.Valid(); itr.Forward())
{
  cout << itr.Item() << ", ":
}

Вывод:

2, 3, 4, 5, 6, 7,
Хотя, с помощью итераторов и можно добавлять узлы к списку (метод InsertAfter класса SListNode), делается это чудовищно криво. Если итератор указывает на последний узел, и мы вызываем функцию InsertAfter, то список испортится, так как в InsertAfter никак не обрабатывается проверка tail списка. Поэтому для итераторов более правильным решением будет написать собственную функцию. Причём лучше эту функцию сделать не для итераторов а для списков, а итераторы можно передавать в функцию в виде аргументов:

код на языке с++
void SLinkedList::Insert(SListIterator&, int);

void Insert( SListIterator& itr, int d)
{
  if (itr.Valid())
  {
    itr.node->InsertAfter(d);
    if (itr.node == tail)
    {
      tail = itr.node->next;
    }
    count++;
  }
}

Мы делаем проверку, на что указывает итератор. Если он указывает на NULL, то ничего не происходит. Если же в итераторе содержится корректное значение, то мы добавляем узел с помощью функции InsertAfter. И теперь нужно проверить, если мы добавили узел после последнего, нужно передвинуть tail.

И последняя функция которую мы рассмотрим: функция удаления узла из связного списка:

код на языке с++
void Remove(SListIterator&);

void SLinkedList::Remove(SListIterator& itr)
{
  SListNode* temp = head;

  if (itr.node == head)
  {
    itr.Forward();
    PopFront();
  }
  else
  {
    while (temp->next != itr.node)
      temp = temp->next;

    itr.Forward();
    if (temp->next == tail)
      tail = temp;

    delete temp->next;
    temp->next = itr.node;
  }
  count--;
}

Данный метод похож на метод удаления последнего элемента списка, здесь также используется временная переменная для хранения указателя на элемент списка.
Двусвязные (двунаправленные) списки

В двусвязных списках (doubly linked list) к узлам добавляется ещё один указатель - на предыдущий узел. Это существенно повышает гибкость структуры данных по сравнению с односвязными списками.

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

В узле двусвязного списка содержатся два указателя. Помимо указателя на следующий узел, есть указатель и на предыдущий. Это резко увеличивает функциональность двусвязного списка по сравнению с односвязным.

Во-первых следует заметить, что для создания методов двусвязного списка требуется немного больше усилий, та как теперь нужно менять два указателя в отличие от односвязных списков.

Как я уже написал выше, рассматривать методы двусвязных списков мы не будем. Классы необходимые для реализации двусвязных списков вы можете посмотреть здесь. Это заголовочный файл, поэтому достаточно добавить его к проекту и вы сможете пользоваться двусвязными списками.

Пожалуйста, внимательно изучите все классы представленные в файле. Именно на основе этой реализации списков в дальнейшем будут создаваться многие структуры данных. Я постарался как можно сильнее упростить код (в коде почти нет комментариев, и так всё понятно), надеюсь, получилось. Кроме того, обязательно выполните упражнения для двусвязных списков.

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

Ещё один вид списков (частный случай двусвязного списка) - замкнутый или ещё встерачающееся название - кольцевой или закольцованный список. Это, кстати, наиболее полезный и часто встречающийся вариант связных списков. При этом у последнего элемента списка в поле next хранится head, а у первого элемента в поле previous - tail.

Заключение.

Ну, вот в общем-то, по спискам и всё. Несколько заключительных слов:

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

Также можно без проблем изменить размер списков, добавив/удавлив новые узлы.

У списков есть конечно же и слабые стороны. Получить доступ к какому-либо элементу не так просто. Необходимо пройти до этого элемента от начала списка, в то время как в массивах доступ к любому элементу можно получить с помощью индекса.

Кроме того, для хранения списков требуется больше памяти.

В списках удобно хранить объекты больших сложных классов. Если у вас множество мелких объектов, будет эффективнее сохнанить их в массиве. Кроме того, доступ к элементам списков происходит медленнее чем к элементам массива, так как узлы списков хранятся в разных участках памяти.

Мы ещё вернёмся к связным спискам когда будем рассматривать создание игрового ландшафта на основе клеток.

На сегодня всё.

Упражнения (односвязные списки):

1. Для односвязного списка реализуйте интерфейс взаимодействия с пользователем. Примерно как на картинке:

Пользователь вводит какую-нибудь команду, и программа должна корректно обработать эту команду.

Во время выполнения программы, загляните в отладчик и понаблюдайте значения переменных, хранящих список и итераторы.

Во время написания данной программы вы увидите все слабости данной реализации односвязных списков. Откровенно говоря, данная реализация написана довольно паршиво.