Списки как динамические структуры данных
Наиболее простыми динамическими структурами данных являются списки. Список представляет собой линейную последовательность переменных, каждая из которых связана указателями со своими соседями. Списки бывают следующих видов:
-односвязные -каждый элемент списка имеет указатель на следующий;
-двусвязные -каждая элемент списка имеет указатель на следующий и на предыдущий элементы;
-двусвязный циклический список -первый и последний элементы списка ссылаются друг на друга, таким образом цепочка представляет собой кольцо.
Сразу же необходимо отметить основное свойство списков как структур данных. Последовательность обхода списка, естественно, зависит не от физического размещения элементов списка в памяти, а от последовательности из связывания указателями. Точно так же определяется нумерация элементов списка - ЛОГИЧЕСКИЙ НОМЕР элемента в списке - это номер, получаемывй им в процессе движения по списку.
Односвязные списки являются наиболее простыми. Основным их недостатком является возможность просмотра только в одном направлении -от начала к концу. Без дополнительных "ухищрений" нельзя получить указатель на предыдущий элемент списка, который необходим при удалении текущего. Для односвязного списка наиболее простыми являются операции включения и исключения элементов в начале и конце списка, соответственно они используются для моделирования таких структур данных, как стеки и очереди.
Двусвязные списки дают возможность просмотра элементов в обоих направлениях и являются наиболее универсальными. Операции включения и исключения элементов в различные части такого списка имеют примерно одинаковый уровень сложности. Двусвязные списки используются для создания цепочек элементов, которые допускают частые операции включения, исключения, упорядочения, замены и пр..
В односвязных и двусвязных списках последний элемент содержит указатель NULL для обозначения факта окончания последовательности. Аналогично первый элемент двусвязного списка содержит указатель NULL на предыдущий элемент.
В этом случае работа с первым и последним элементом списка имеет свои особенности. В качестве альтернативы может быть предложен циклический список, у которого последний элемент ссылается на первый, а первый -на последний. Даже если данная замкнутая структура используется для представления обычной линейной последовательности, работающие с ним функции являются более простыми.
Рассмотрим преимущества и недостатки списков в сравнении с обычными массивами и массивами указателей. Все эти структуры данных предполагают различные способы организации множества переменных. При этом обычный массив и список имеют противоположные свойства: если массив допускает произвольный доступ к своим элементам и ускоренный (двоичный) поиск при их упорядоченности, то список допускает только последовательный просмотр. Следовательно, массив обладает преимуществами с точки зрения операций поиска. Но, с другой стороны, изменение порядка следования переменных в массиве сопровождается их физическим перемещением, а в списке приводит только к "переброске" соответствующих указателей. Таким образом, списки предпочтительнее для структур данных, в которых операции поиска встречаются значительно реже, чем операции по изменению порядка следования элементов, и наоборот. В отношении массивов указателей и списков можно заметить, что массивы указателей критичны к количеству элементов в структуре данных -при увеличении этого количества их необходимо расширять, при уменьшении -желательно сокращать. Для списков такой проблемы не существует. Таким образом, списки предпочтительнее в структурах, где количество элементов меняется в широких пределах, массивы указателей -в противном случае.
