Войти
| Список ассоциаций | |||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Тип | ассоциативный массив | ||||||||||||||||||||
| Временная сложность в нотации большого O | |||||||||||||||||||||
| |||||||||||||||||||||
In компьютерное программирование и особенно в Lisp, список ассоциаций, часто называемый alist - это связанный список, в котором каждый элемент списка (или узел ) содержит ключ и значение. Говорят, что список ассоциаций связывает значение с ключом. Чтобы найти значение, связанное с данным ключом, используется последовательный поиск : поиск каждого элемента списка выполняется по очереди, начиная с заголовка, до тех пор, пока ключ не будет найден. Ассоциативные списки обеспечивают простой способ реализации ассоциативного массива , но эффективны только тогда, когда количество ключей очень мало.
Ассоциативный массив - это абстрактный тип данных, который можно использовать для поддержки коллекции пар ключ-значение и поиска значения, связанного с данным ключом. Список ассоциаций предоставляет простой способ реализации этого типа данных.
Чтобы проверить, связан ли ключ со значением в данном списке ассоциаций, выполните поиск в списке, начиная с его первого узла и продолжая либо до тех пор, пока узел, содержащий ключ, не будет найден, либо пока поиск не достигнет конца список (в этом случае ключ отсутствует). Чтобы добавить новую пару «ключ-значение» в список ассоциаций, создайте новый узел для этой пары «ключ-значение», установите ссылку узла как предыдущий первый элемент списка ассоциаций и замените первый элемент списка ассоциаций на новый узел. Хотя некоторые реализации ассоциативных списков запрещают иметь несколько узлов с одинаковыми ключами, такие дублирования не являются проблемой для этого алгоритма поиска: повторяющиеся ключи, которые появляются позже в списке, игнорируются.
Также возможно удалить ключ из списка ассоциаций, просмотрев список, чтобы найти каждое вхождение ключа, и вырезать узлы, содержащие ключ, из списка. Сканирование должно продолжаться до конца списка, даже если ключ найден, если один и тот же ключ мог быть вставлен несколько раз.
Недостатком ассоциативных списков является то, что время поиска составляет O (n), где n - длина списка. Для больших списков это может быть намного медленнее, чем время, которое можно получить, представив ассоциативный массив в виде двоичного дерева поиска или хэш-таблицы . Кроме того, если список регулярно не сокращается для удаления элементов с повторяющимися ключами, несколько значений, связанных с одним и тем же ключом, увеличивают размер списка и, следовательно, время для поиска, не обеспечивая никаких компенсационных преимуществ.
Одним из преимуществ ассоциативных списков является то, что новый элемент может быть добавлен за постоянное время. Кроме того, когда количество ключей очень мало, поиск в списке ассоциаций может быть более эффективным, чем поиск в двоичном дереве поиска или хеш-таблице, из-за большей простоты их реализации.
На ранней стадии развития Лиспа списки ассоциаций использовались для разрешения ссылок на свободные переменные в процедурах. В этом приложении удобно дополнять списки ассоциаций дополнительной операцией, которая отменяет добавление пары ключ-значение без сканирования списка на предмет других копий того же ключа. Таким образом, список ассоциаций может функционировать как стек, позволяя локальным переменным временно затенять другие переменные с такими же именами, не разрушая значения этих переменных. другие переменные.
Многие языки программирования, включая Lisp, Scheme, OCaml и Haskell, имеют функции для обработки списков ассоциаций в своих стандартные библиотеки.
