Лабораторная работа №13. Контейнер List. Выполнение операций над списками

Лабораторная работа № 13. Контейнер List. Выполнение операций над списками.

Цель работы: Понять назначение Контейнера List. Выполнение операций над списками.


Теоретическая часть:


Линейные списки
Линейным списком называется упорядоченная последовательность переменного числа элементов. Основными операциями с линейными списками являются:

1. 
   получить доступ к k-му элементу;
   
2. 
   включить k-й элемент;
   
3. 
   исключить k-й элемент;
   
4. 
   найти необходимый элемент.
   

Существует два принципиально разных способа представления линейных списков – последовательное и связное (рис. 1).

Рис. 1 Способы представления линейных списков

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

Некоторые операции со списками эффективнее реализуются при связном представлении, а некоторые – при последовательном, так например:

1. 
   при связном представлении легко включать и исключать элементы, при последовательном для этого необходимо сдвигать информацию;
   
2. 
   доступ к k-му элементу быстрее при последовательном представлении;
   
3. 
   при связном представлении легко объединять списки и разбивать их на части.
   

На практике часто применяются некоторые частные случаи линейных списков.

Стек (LIFO (Last In First Out) список) – это линейный список, в котором все включения и исключения (и обычно всякий доступ) элементов происходят на одном конце списка.
Очередь (FIFO (First In First Out) список) – это линейный список, в котором все включения элементов происходят на одном конце списка, а все исключения (и обычно всякий доступ) – на другом.
Дек – это линейный список, в котором все включения и исключения элементов производятся на обоих концах списка.