Алгоритмы и структуры данных на С++. Аксёнова Е.А - 21 стр.

Глава 2.     Линейные структуры данных

                   2.1. Линейные списки

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

  1) получить доступ к k-му элементу;
  2) включить k-й элемент;
  3) исключить k-й элемент;
  4) найти необходимый элемент.
   Существует два принципиально разных способа представления ли-
нейных списков – последовательное и связное (рис. 2.1).




                              Рис. 2.1

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