Хранение данных с использованием линейных списков

Введение

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

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

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

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

Хранение данных с использованием линейных списков

Главными преимуществами линейных списков считаются следующие аспекты:

1. Простота добавления и удаления компонентов.
2. Размеры списков ограничены лишь объёмом доступной памяти персонального компьютера и разрядностью указателей.
3. Возможность динамического добавления и удаления компонентов.
4. Задача оптимального управления данными считается наиболее важной для любых реализаций списков. Список является совокупностью связанных между собой узлов. Каждый узел является структурой, которая содержит минимум два поля, а именно:

• Поле, предназначенное для хранения данных.
• Поле, предназначенное для указателей.

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

• Основной тип.
• Составной тип.
• Указательный тип.

Описание простейшего компонента (узла) может выглядеть так:

struct Node

{

Data d; // тип данных Data должен определяться заранее

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

Node *prev; // указатель на следующий компонент, в случае использования двусвязного списка

};

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

Рисунок 1. Структура односвязного списка. Автор24 — интернет-биржа студенческих работ

На этом рисунке поле INF означает информационное поле, то есть, данные, а NEXT является указателем на следующий компонент списка. Любой список обязан обладать особым компонентом, именуемым указателем начала списка или головой списка, который, как правило, имеет формат отличный от остальных компонентов. В поле указателя последнего компонента списка расположен специальный признак null, который обозначает конец списка.

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

Рисунок 2. Структура линейного двухсвязного списка. Автор24 — интернет-биржа студенческих работ

Здесь поле NEXT является указателем на следующий компонент, а поле PREV является указателем на предыдущий компонент. В крайних компонентах необходимые указатели содержат признак null, как и изображено на рисунке выше.

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

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

Рисунок 3. Список. Автор24 — интернет-биржа студенческих работ

При обработке списков могут быть использованы следующие главные операции:

1. Первоначальное создание списка, то есть, формирование первого компонента.
2. Прибавление компонента в конец списка.
3. Прочтение компонента с определённым ключом.
4. Выполнение вставки компонента в нужное место списка, то есть, до или после компонента с заданным ключом.
5. Ликвидация компонента с заданным ключом.
6. Осуществление упорядочивания списка по ключу.