Практикум по курсу "Алгоритмизация и программирование". Часть 2. Андрианова А.А - 52 стр.

А.А. Андрианова, Л.Н. Исмагилов, Т.М. Мухтарова                     .
           Глава 2. Линейные динамические структуры данных

                                            Раздел 3. Односвязные списки

    Связные списки – это способ хранения данных, который применяется в
тех случаях, когда заранее неизвестно количество элементов или когда размер
хранимых данных постоянно меняется. Например, списки удобно использо-
вать в приложении, имитирующем работу телефонного автоответчика. Сооб-
щения, которые поступают на автоответчик, должны сохраняться в некоторой
структуре данных. Прослушанные сообщения требуется из этой структуры
удалять.
    Если использовать для этих целей массив, то нужно сразу указывать его
размер достаточным для хранения максимального количества возможных эле-
ментов, что не всегда получается оценить. Если выделенной памяти не хвата-
ет для хранения всех элементов, приходится производить реорганизацию мас-
сива – выделение новой памяти необходимого размера, перенос всех элемен-
тов из прежней памяти в новую и освобождение той области памяти, которую
ранее занимал массив.
    Главное достоинство динамических структур данных, самым простым
примером которых является связный список, состоит в том, что только в мо-
мент добавления нового элемента под него выделяется память. Соответствен-
но, в момент удаления элемента память, занятая им, освобождается. Часто
элемент списка называют также узлом.
    Однако, по сравнению с массивами, здесь имеется и недостаток - заранее
неизвестно местоположение каждого элемента. Поэтому приходится вместе с
самими данными хранить дополнительную информацию об их местоположе-
нии. Таким образом, для хранения динамических структур данных требуется
больше памяти.
    Поскольку связный список должен хранить вместе данные и информацию
об их местоположении, при применении списков в программе используют
структурный тип данных, в который входят переменные, хранящие информа-
ционные поля, и переменная, содержащая адрес памяти следующего (или пре-
дыдущего) узла списка. Для хранения адресов памяти в большинстве языков
программирования существуют специальные типы данных. Например, в язы-
ке С++ для этих целей применяется тип данных, который называется указа-
тель.
    Односвязным называют список, каждый узел которого содержит адрес

                                            52