В компьютерном программировании и особенно в Lisp список ассоциаций , часто называемый списком , представляет собой связанный список , в котором каждый элемент списка (или узел ) содержит ключ и значение . Говорят, что список ассоциаций связывает значение с ключом. Чтобы найти значение, связанное с данным ключом, используется последовательный поиск : поиск каждого элемента списка осуществляется по очереди, начиная с головы, до тех пор, пока ключ не будет найден. Ассоциативные списки предоставляют простой способ реализации ассоциативного массива , но эффективны только тогда, когда количество ключей очень мало.
Ассоциативный массив — это абстрактный тип данных , который можно использовать для хранения коллекции пар ключ-значение и поиска значения, связанного с данным ключом. Список ассоциаций обеспечивает простой способ реализации этого типа данных.
Чтобы проверить, связан ли ключ со значением в данном списке ассоциаций, выполните поиск в списке, начиная с его первого узла и продолжая либо до тех пор, пока не будет найден узел, содержащий ключ, либо пока поиск не достигнет конца списка (в этом случае ключа нет). Чтобы добавить новую пару ключ-значение в список ассоциаций, создайте новый узел для этой пары ключ-значение, установите ссылку узла в качестве предыдущего первого элемента списка ассоциаций и замените первый элемент списка ассоциаций на новый узел. [1] Хотя некоторые реализации списков ассоциаций запрещают наличие нескольких узлов с одинаковыми ключами, такое дублирование не является проблемой для этого алгоритма поиска: повторяющиеся ключи, которые появляются позже в списке, игнорируются. [2]
Также возможно удалить ключ из списка ассоциаций, просканировав список, чтобы найти каждое вхождение ключа, и объединить узлы, содержащие ключ, из списка. [1] Сканирование должно продолжаться до конца списка, даже если ключ найден, в случае, если один и тот же ключ мог быть вставлен несколько раз.
Недостатком списков ассоциаций является то, что время поиска составляет O ( n ) , где n — длина списка. [3] Для больших списков это может быть намного медленнее, чем время, которое можно получить, представляя ассоциативный массив в виде двоичного дерева поиска или в виде хеш-таблицы . Кроме того, если список не будет регулярно сокращаться для удаления элементов с повторяющимися ключами, несколько значений, связанных с одним и тем же ключом, будут увеличивать размер списка и, следовательно, время поиска, не предоставляя никаких компенсирующих преимуществ.
Одним из преимуществ списков ассоциаций является то, что новый элемент может быть добавлен за постоянное время. Кроме того, когда количество ключей очень мало, поиск по списку ассоциаций может быть более эффективным, чем поиск по двоичному дереву поиска или хэш-таблице, из-за большей простоты их реализации. [4]
На ранних этапах разработки Lisp списки ассоциаций использовались для разрешения ссылок на свободные переменные в процедурах. [5] [6] В этом приложении удобно дополнять списки ассоциаций дополнительной операцией, которая отменяет добавление пары ключ-значение без сканирования списка на наличие других копий того же ключа. Таким образом, список ассоциаций может функционировать как стек , позволяя локальным переменным временно скрывать другие переменные с такими же именами, не разрушая значения этих других переменных. [7]
Многие языки программирования, включая Lisp, [5] Scheme , [8] OCaml , [9] и Haskell [10] имеют функции для обработки списков ассоциаций в своих стандартных библиотеках .