ОСОБЕННОСТИ РАБОТЫ С ЛИНЕЙНЫМИ СПИСКАМИ В РЕАЛИЗАЦИИ С ПОМОЩЬЮ УКАЗАТЕЛЕЙ

Степович-Цветкова Г.С.

Кандидат экономических наук, Ивановский государственный университет

ОСОБЕННОСТИ  РАБОТЫ С ЛИНЕЙНЫМИ СПИСКАМИ В РЕАЛИЗАЦИИ С ПОМОЩЬЮ УКАЗАТЕЛЕЙ

Аннотация

Рассмотрены особенности и некоторые преимущества реализации линейных списков с помощью указателей в сравнении с другими способами реализации.

Ключевые слова: линейные списки, указатели.

Stepovitch-Tsvetkova G.S.

PhD in economic, Ivanovo State University

PECULIARITIES OF WORKING WITH LINEAR LISTS IN IMPLEMENTATION BY POINTERS

Abstract

The peculiarities and some advantages of the pointers implementation of linear lists in comparison with other methods.

Keywords: linear lists, pointers.

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

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

Рассмотрим двунаправленные линейные списки, реализованные с помощью указателей, которые применяются в алгоритмах управления пространством оперативной памяти, в том числе его повторного использования и разделения между несколькими объектами или процессами. К числу таких алгоритмов относятся, например, методы создания связных списков свободного пространства памяти и методы «сборки мусора», при использовании которых происходит подсчет доступной памяти, если появляется нехватка памяти.

Описание одного элемента двунаправленного списка, объединяющего поле данных и указатели на предыдущий и последующий элементы, на языке С++ выглядит следующим образом:

struct Node{

       int info;

       Node *next; // указатель на следующий элемент

       Node *prev; // указатель на предыдущий элемент

};

Весь список задается указателем на его начало, для удобства можно создать дополнительно указатель на конец списка (рис. 1), учитывая, что список двунаправленный и может понадобиться проход по списку в обратном порядке.

Рис.1 – Двунаправленный линейный список

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

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

Алгоритм вставки элемента в список также основан на манипуляции с указателями на предыдущий и последующий элементы у тех членов списка, между которыми добавляется новый элемент. При этом важной особенностью такой реализации списков является то, что при добавлении и удалении элементов из списка никакого физического сдвига элементов в памяти производить не нужно, в отличие от реализации списков с помощью массивов. Поэтому важным преимуществом использования линейных списков в алгоритмах является возможность добавления и удаления элементов в списке за время  O(1).

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