49. Списки, технология списков, операции вставить, удалить узел списка

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

Технология связных списков

Рассматривается технология решения задач, основанная на технике связных списков. В данном случае, списковая структура определяется как набор узлов (ячеек), связанных в цепочку.

Односвязный список. Каждый узел списка, исключая последний узел, указывает на следующий узел. Такой список называется односвязным. Для работы с односвязным списком мы должны знать адрес первого узла. Любой другой узел списка можно получить последовательным перебором предшествующих узлов.

Start

→

Эл. 1

→

Эл. 2

→....→

Эл. N

→

Nul

Значение Start указывает на первый узел списка, Nul – пустой указатель. Указатель Nul не указывает никуда, но должен быть приведен, поскольку указание на следующий узел обязательное свойство любого узла связного списка. Кроме ссылки на следующий узел, узел списка может хранить любую информацию.

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

Для вставки узла в список меняют указатель предшествующего узла на адрес вставляемого узла, а указателю вставляемого дают значение адреса следующего узла списка.

Двусвязный список Если существует необходимость двигаться по списку в обоих направлениях, формируется двусвязный список. От односвязного списка он отличается добавочной – обратной связью. Обратная связь устроена по тем же законам, что и прямая связь.

Start Nul

→ ←

Эл. 1

→ ←

Эл. 2

→…. ←....

→ ←

Эл. N

→ ←

Nul Start

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

50. Класс List, свойства и методы класса

Двусвязный список, элементы которого хранятся в произвольных кусках памяти, в отличие от контейнера vector, где элементы хранятся в непрерывной области памяти. Поиск перебором медленнее, чем у вектора из за большего времени доступа к элементу. Доступ по индексу за O(n). В любом месте контейнера вставка и удаление производятся очень быстро - за O(1).

Описание класса List

В классе List определено два конструктора и довольно много различных методов. Ниже мы привели краткое описание класса List:

Конструкторы

Конструктор без параметров

public List();

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

public List(int rows,

boolean multipleSelections);

template <class T> class std::list

{

public:

list();

// Конструктор по умолчанию; создает пустой список.

bool empty() const;

// Распознает, пуст ли список.

// Предусловие: нет.

// Постусловие: если список пуст, возвращает значение true.

//' В противном случае возвращает значение false

size_type size () const;

// Вычисляет длину списка.

// Тип size_type является целочисленным.

// Предусловие: нет.

// Постусловие: возвращает количество элементов,

// хранящихся в списке в данный момент.

size_type max_size();

// Определяет максимально возможное количество элементов,

// которые могут храниться в списке.

// Предусловие: нет.

// Постусловие: возвращает максимально возможное // количество элементов

iterator erase(iterator i);

// Удаляет из списка элемент, на который установлен

// итератор i.

iterator begin();

//Возвращает итератор, установленный

//на первый элемент списка.

iterator end ();

// Возвращает значение итератора, которое можно использовать

// для проверки, достигнут ли конец списка.

// Предусловие: нет.

// Постусловие: возвращается итератор, установленный

// на конец списка

} // Конец шаблонного класса