Я заметил, что в функциональных языках, таких как Haskell и OCaml, вы можете выполнять 2 действия со списками.Сначала вы можете сделать x:xs, где x - это элемент, а xs - это список, и в результате мы получим новый список, где x добавляется в начало xs в постоянное время.Вторым является x++y, где и x, и y являются списками, и в результате мы получаем новый список, в котором y добавляется в конец x за линейное время по отношению к числу элементов в x.Сейчас я не разбираюсь в том, как спроектированы языки и построены компиляторы, но мне это очень похоже на простую реализацию связанного списка с одним указателем на первый элемент.Если бы я реализовал эту структуру данных на языке, подобном C ++, я бы нашел тривиальным добавить указатель на последний элемент.В этом случае, если эти языки были реализованы таким образом (при условии, что они используют связанные списки, как описано), добавление «указателя» на последний элемент сделало бы намного более эффективным добавление элементов в конец списка и позволило бы сопоставить шаблон споследний элемент.
Мой вопрос заключается в том, действительно ли эти структуры данных реализованы в виде связанных списков, и если да, то почему они не добавляют ссылку на последний элемент?