Список представляет собой последовательность элементов, каждый из которых содержит значение некоторого типа и адрес следующего элемента (причем для последнего из них адрес может быть нулевым). К любой такой последовательности всегда можно добавить еще один элемент (хотя реальная попытка подобного добавления может закончиться неудачно, если отведенная программе свободная память исчерпана). Список, в котором нет ни одного элемента, называется пустым.
Какие операции должен поддерживать список? Добавление (insert), удаление (remove) и поиск (find) определенных элементов. Кроме того, можно запрашивать размер списка (size), распечатывать его содержимое (display), проверять равенство двух списков. Мы покажем также, как инвертировать (reverse) и сцеплять (concatenate) списки.
Простейшая реализация операции size() перебирает все элементы, подсчитывая их количество. Более сложная реализация сохраняет размер как член данных; она намного эффективнее, однако требует некоторого усложнения операций insert() и remove() для поддержки размера в актуальном состоянии.
Мы выбрали второй вариант реализации функции size() и храним размер списка в члене данных. Мы предполагаем, что пользователи будут достаточно часто применять эту операцию, поэтому ее необходимо реализовать как можно более эффективно.
(Одним из преимуществ отделения открытого интерфейса от скрытой реализации является то, что если наше предположение окажется неверным, мы сможем переписать реализацию, сохранив открытый интерфейс – в данном случае тип возвращаемого значения и набор параметров функции size() – и программы, использующие эту функцию, не нужно будет модифицировать.)
Операция insert() в общем случае принимает два параметра: указатель на один из элементов списка и новое значение, которое вставляется после указанного элемента. Например, для списка
1 1 2 3 8
вызов
mylist.insert (pointer_to_3, 5);
изменит наш список так:
1 1 2 3 5 8
Чтобы обеспечить подобную возможность, нам необходимо дать пользователю способ получения адреса определенного элемента. Одним из способов может быть использование функции find() – нахождение элемента с определенным значением:
pointer_to_3 = mylist.find( 3 );
find() принимает в качестве параметра значение из списка. Если элемент с таким значением найден, то возвращается его адрес, иначе find() возвращает 0.
Может быть два специальных случая вставки элемента: в начало и в конец списка. Для этого требуется только задание значения:
insert_front( value );
insert_end( value );
Предусмотрим следующие операции удаления элемента с заданным значением, первого элемента и всех элементов списка:
remove( value );
remove_front();
remove_all();
Функция display() распечатывает размер списка и все его элементы. Пустой список можно представить в виде:
(0)( )
а список из семи элементов как:
(7) ( 0 1 1 2 3 5 8 )
reverse() меняет порядок элементов на противоположный. После вызова
mylist.reverse();
предыдущий список выглядит таким образом:
(7) ( 8 5 3 2 1 1 0 )
Конкатенация добавляет элементы второго списка в конец первого. Например, для двух списков:
(4)( 0 1 1 2 ) // listl
(4)( 2 3 5 8 ) // list2
операция
listl.concat( list2 );
превращает list1 в
(8) ( 0 1 1 2 2 3 5 8 )
Чтобы сделать из этого списка последовательность чисел Фибоначчи, мы можем воспользоваться функцией remove():
listl.remove( 2 );
Мы определили поведение нашего списка, теперь можно приступать к реализации. Пусть список (list) и элемент списка (list_item) будут представлены двумя разными классами. (Ограничимся теми элементами, которые способны хранить только целые значения. Отсюда названия наших классов – ilist и ilist_item.)
Наш список содержит следующие члены: _at_front – адрес первого элемента, _at_end – адрес последнего элемента и _size – количество элементов. При определении объекта типа ilist все три члена должны быть инициализированы 0. Это обеспечивается конструктором по умолчанию:
class ilist_item;
class ilist {
public:
// конструктор по умолчанию