Иллюстрированный самоучитель по Perl
Ассоциативные массивы - часть 5
Это только простейший пример, который может навести читателя на более плодотворные идеи применения хеш-массивов, одну из которых нам хотелось бы сейчас наметить: создание связанного списка.
Связанный список —
это простейшая динамическая структура данных, расположенных в определенном порядке. Каждый элемент связанного списка состоит из некоторого значения, ассоциированного с данным элементом, и ссылки на следующий элемент списка. Последний элемент списка не имеет ссылки на следующий, что обычно реализуется в виде пустой ссылки. Для окончательного задания связанного списка следует объявить переменную, указывающую на первый элемент списка, которую называют заголовком. Для связанного списка определяются операции выбора, удаления и добавления элемента списка относительно заданного. Графически связанный список можно представить так, как показано на рис. 3.1, где указатель на следующий элемент обозначен серым цветом.
Рис 3.1. Графическое представление связанного списка
С помощью хеш-массивов связанный список реализуется просто. Для этого следует значение элемента задать в качестве ключа для следующего за ним элемента списка, определив таким образом указатель на следующий элемент. Значением последнего элемента в хеш-массиве (с ключом, равным значению последнего элемента связанного списка) будет пустая строка "". Переменная-заголовок должна иметь значение, равное ключу первого элемента списка. В примере 3.8 показана реализация связанного списка, а также добавление нового элемента.
%linked_list = ( "начало" => "первый", "первый" => "третий",
"третий" => ""
);
$header = "начало";
# Добавление элемента со значением "второй"
# после элемента со значением "первый".
$temp = $linked_lis.t{ "первый"};
# Запомнили старый, указатель ., $linked_list{"второй"} = $temp;
# Добавили новый элемент. $linked_list{"первый"} = "второй";
