Причина - «традиционная» реализация списков в Лиспе.В других местах списки иногда реализуются аналогично массиву.Итак, когда вы создаете список, это отдельная отдельная вещь.
An array-like list: [ 1 2 3 4 5 6 ]
Если вы хотите прикрепить элемент - например, «0» - к началу этого списка (и предполагая, что реализация списка упрощена), все элементы в списке будут сдвинуты вверх (вправо).Затем в новом месте будет установлен '0'.
Step 0. [ 1 2 3 4 5 6 ]
Step 1. [ 1 2 3 4 5 6 ] (Shift Right)
Step 2. [ 0 1 2 3 4 5 6 ] (Insert)
Это совсем не так (традиционные) списки Лиспа.Каждый элемент списка - это отдельный элемент, который указывает на следующий элемент.Части списка называются «conses».(Это называется связанным списком.)
[1] -> [2] -> [3] -> [4] -> [5] -> [6] -> nil
А?Ну, каждый из этих пунктов является клеткой против.И в каждой ячейке минусов есть два значения: car и cdr.(Когда ячейки cons используются со списками, лучше называть «car» и «cdr» как «first» и «rest». «First» содержит любые данные, которые вы хотите сохранить в списке, такие как числа или даже ссылки надругие списки. "Rest" содержит остальную часть списка. Вы также можете поместить все, что вы хотите, в часть "rest", но мы проигнорируем это здесь.) "Nil" - это "пустой список", который в основномозначает «список закончен!»
Так что, если мы хотим снова поставить «0» на передний план?
[0] -> [1] -> [2] -> [3] -> [4] -> [5] -> [6] -> nil
Видите?Мы только что создали новую ячейку cons, которая указывала на начало старого списка.Вы услышите, как люди называют это «употреблением» значения на фронте.Но вы заметите, что остальная часть списка остается нетронутой.
Хорошо, но зачем кому-то это нужно?Вы можете поделиться списками.Представьте, что вы хотели два в основном одинаковых списка.Только теперь вы хотели, чтобы один список начинался с «7», а другой - с «4»?Что касается массива, у нас должно быть два списка.
[ 7 0 1 2 3 4 5 6 ]
[ 4 0 1 2 3 4 5 6 ]
Что если вы замените '5' на '13' и поделитесь этим изменением?
[ 7 0 1 2 3 4 13 6 ]
[ 4 0 1 2 3 4 5 6 ]
У вас есть два совершенно разных списка.Если вы хотите поделиться изменениями, вам придется внести изменения в оба списка.
Что происходит с традиционными списками Lisp?Во-первых, наклейте «7» и «4» вперед:
[7]
\
----> [0] -> [1] -> [2] -> [3] -> [4] -> [5] -> [6] -> nil
/
[4]
Да.Мы только что сделали два утверждения, которые оба указывают на старый список.Остальная часть списка является общей.И, если мы заменим «5» на «13»:
[7]
\
----> [0] -> [1] -> [2] -> [3] -> [4] -> [13] -> [6] -> nil
/
[4]
Оба списка получат изменение, потому что остальные разделены.
Суть всего этого в том, что, в отличие от того, чтоМногие ожидают, что традиционные списки Lisp - это не единственная вещь.Это куча маленьких вещей (понятий), которые указывают друг на друга, образуя цепочку, которая является списком.Если вы хотите получить длину цепи, вы должны следовать всем маленьким ссылкам, пока не дойдете до конца, ноль.Таким образом, длина O (n).
Списки Lisp могут быть сделаны O (1), если они сделаны как массивы.Я уверен, что некоторые непонятные Лиспы делают это и вообще избавляются от связанных списков.Но conses, кажется, одна из вещей, которая пробивается в основном на каждом популярном диалекте Lisp.Если вам нужна длина O (1) и поиск, большинство из них также предоставляют массивы или векторы.
Прикол со связанным списком:
-----------------<------------------------<----------
| |
--> [0] -> [1] -> [2] -> [3] -> [4] -> [5] -> [6] -->
Этот связанный список в конечном итоге указывает насам.Если вы используете свою функцию длины, она зациклится навсегда, ищет конец, но никогда не найдет его.