197-577-902

Лекции по информатике - Список

Список - динамическая структура данных, которая представляет собой последовательность (цепочку) элементов.

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

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

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

type
  PL1Item = ^TL1Item;
{ элемент односвязного списка }
  TL1Item = record
    Data: Integer; { сами данные }
    Next: PL1Item;
      { указатель указывает на следующий
        элемент списка или равен nil,
        когда следующего элемента нет }
  end;

Двусвязный список можно изобразить так:

Рис 3. Двусвязный список

При работе с односвязными списками очень важно не потерять указатель на голову списка - его первый элемент. Т.к. иначе вы потеряете все или часть элементов. Поэтому обычно при работе со списком заводят два указателя. Первый постоянно указывает на голову списка, и не меняется. А второй - является "рабочим" указателем, и может указывать на произвольный элемент списка.

Добавление элемента в список проходит в несколько шагов. Например, добавление элемента после головы списка может выглядеть так:

выделяем память под элемент Item и заполняем поле Data данными
связываем новый элемент с элементов следующим за Head
связываем Head с новым элементом