Связанные списки

812
1 Звезда2 Звезды3 Звезды4 Звезды5 Звезд (Пока оценок нет)
Загрузка...
  • Название: Связанные списки (Linked list);
  • Применение: Способ хранения данных;
  • Время выполнения: зависит от конкретной операции;
  • Сложность: Средний;
  • Входные параметры: Массив или Динамическая память;
  • Результат: Представление данных в виде связанной стуктуры, не ограниченной конкретным размером

Пример из жизни:

Очень часто бывают случаи, когда ограничения в чем-либо могут сыграть злую шутку. Например, Вы спешите в метро, но точно не помните сколько поездок осталось на карте. Момент истины — Карта не сработала! (Лимит по карте исчерпан, наверное нужно было покупать проездной на месяц) Вы с друзьями собираетесь на отдых и естественно хотите провести дорогу вместе. Вы покупаете 4 места в одном купе, но неожиданно кто-то заболел, а билеты уже куплены и, конечно, жаль потраченных средств (Наверное, лучшее решение было бы бронирование мест на заданное число). Вы решили сделать дорогой подарок любимой девушке, но банковская карта ограничена средствами в определенную сумму и не хватает всего несколько рублей! Что делать ? Ехать домой за деньгами, но  ваш подарок могут купить другие! И тут вспоминате, что Ваш банковский агент предлагал Вам подключил услугу кредитования для банковской карты, но уже поздно, увы! Из вышеизложенных примеров нетрудно заключить, что очень часто требуется прорабатывать решения, учитывая неопределенность количества или размера хранимых или используемых ресурсов.

Постановка задачи:

Требуется сформировать структуру данных, размер которой заранее неизвестен. Соотвественно, необходимо предусмотреть различные манипуляции с такой структурой, как например, удаление, добавление, чтение и т.д.

Линвистическое описание:

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

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

Видя связанных списков:

Односвязный линейный список

Кольцевой связный список

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

Cсылка в каждом узле указывает на следующий узел в списке. В односвязном списке можно передвигаться только в сторону конца списка. Узнать адрес предыдущего элемента, опираясь на содержимое текущего узла, невозможно. Последний элемент кольцевого списка содержит указатель на первый, а первый (в случае двусвязного списка) — на последний. Cсылки в каждом узле указывают на предыдущий и на последующий узел в списке. 

В нешем случе будет рассмотрен односвязный линейный список (ОЛС).

Реализация:

В некоторых высокоуровневых языках программирования уже существуют встроенные возможности (в виде классов или библиотек) для работы со связанными списками. В скриптовых языках программирования надобность в связанных списках практически отстуствует. Например, в php можно не указывать размерность массива, а сам массив не поддерживает работу с указателями и адресацией. Т.к. ссылки в php не похожи на указатели в C; например, вы не можете делать вычисления над указателями, они не являются реальными адресами в памяти и пр. Таким образом, связанные списки теряют актуальность в скриптовых языках программирования, хотя их реализация безусловно возможна. Тем не менее, в php предусмотрен класс SplDoublyLinkedList, который обеспечивает основные функциональные возможности двусвязного списка. Т.к. связанные списки широко используются в работе операционных систем или баз данных, понимание их работы вызывает интерес.

Мы рассмотрми создание ОЛС программными средствами через структуру или класс. Формируется структура ( добавляется два поля: поле данных и указатель на следующий элемент ) очень показательный пример на языке Си. Возможна реализация через классы, тогда определяется класс узла, в котором как правило указывается два поля: поле данных и указатель на следующий элемент. Реализуется конструктор, который принимает новое значение узла. Подводя предварительные итоги реализации ОЛС — необходимо выделить участок хранения памяти для узла и предусмотреть по крайней мере два поля для хранения данных (поле данных и указатель на следующий элемент). Последний элемент списка должен содержать указатель со значением NULL.

Программная разработка:

Так как структуры осутствуют в php, напишем простой класс для узла. Для этого определим следующие свойства: $valueNode (значение узла), $nextNode (ссылка на следующий узел), $prevNode (ссылка на предыдущий элемент). А так же конструктор, принимающий значение узла. Этот класс является заготовкой узла, но для полноценного функционирования данной структуры необходимо предусмотреть различные операции: добавление в конец списка, добаление в начало списка, вставить узел перед заданным узлом, вставить узел после заданного узла, удаление элемента.   

Добавление узла в конец и начало списка. Сложные для понимания становятся строчки с 8-13.  На 8 строчке переменной $lastNode присваивается ОЛС $list. 9-13 Производится извлечение последнего элемента и его присваение $lastNode. Соотвественно на 12 и 13 производится присваивание следующему элементу ссылку на новый узел (3) и на предыдущий.

Аналогично добавлению элемента в конец списка производится операция добавления элемента в начало ОЛС.

Обычно функциональные возможности списка сравнивают с массивом. Давайте подумаем, если в массив добавить новый элемент, то какие операции прийдется выполнить? ну во-первый прийдется переиндексировать все элементы массива, а если не хватить места в памяти, то прийдется скопировать все элементы массива в новый участок памяти. Со связанными списками таких проблем не возникает. При добавлении элемента достаточно перезаписать указать на новый элемент. Соотвественно, Время выполнения: О (1);

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

Получение списка элементов ОЛС.  Доступ к элементам списка производится последовательный доступ, потому что необходимо извлечь указатели в порядке их очередности. Т.к. каждый элемент списка содержит указать на следующий и т.д. Таким образом, если нужно прочитать 10-й элемент ОЛС, прийдется прочитать первые 9 элементов и перейти по ссылкам к 10-му элементу. Соотвественно, если рассматривать массивы, то они требуют произвольный доступ. При таком доступе не нужно производить перебор элементов по ссылка, потому что доступ к элементу массива производится практически мгновенно. Таким образом,  время выполнения операции получения элемента(ов) списка — О (n).

Что еще почитать:

Поделиться

Отправить ответ

avatar
wpDiscuz