Структуры данных для самых маленьких

Собственно пример уже приведён — добавление элемента в конец списка.

Посмотрел внимательнее описание списка в статье — нет слов. С чего начинать критику — неясно. Понятно одно. Уверенно говорить о сложности добавления в конец списка из статьи вообще нельзя.

Пойдём по пунктам.

То, что в статье наызвают списком, обычно списком не называется

Списком обычно называют то, что в статье называется связным списком. Обычно список и связный список — синонимы. Это вопрос терминологии, но он очень путает, потому что добавление в конец связного списка — действительно O(1), и если не вчитываться — можно не понять где тут читателя кидают :)

Массивы из статьи — особые уличные джваскриптовые массивы

Дальше интереснее. Список из статьи реализован на основе массива. Этот массив — джаваскриптовый, что означает, что туда можно добавить элемент с любым индексом. Например, если в массиве один элемент, то можно добавить туда элемент с индексом 10 и джаваскрипт это скушает. Правда в массиве будет "дырка" на 9 элементов. Или можно, как в статье, добавить туда элемент с индексом 1 и тогда в массиве будет элемент с индексом 0 и с индексом 1 и дырки не будет. То есть, если в массиве 1 элемент — можно безо всяких проблем добавить второй — массив автоматом вырастет.

Обычные массивы сами по себе не растут

Во многих других языках программирования при создании массива надо задавать его размер, поменять который нельзя — можно только создать новый массив побольше и скопировать туда элементы старого.

Запись в массив по индексу стоит O(1)

Так вот — например у нас есть массив из 20 элементов и на его основе мы сделали список в который пока положили 10 элементов. То есть переменная length равна 10. И вот мы хотим добавить в список ещё один элемент. Тогда мы запишем новый элемент в массив по индексу 10 и увеличим переменную length на еденицу. Она теперь равна 11. Вот эта операция действительно стоит O(1).

Расширение массива стоит O(N)

Но если в списке, внутри которого массив из 20 элементов уже 20 элементов и есть (переменная length равна 20), то мы не можем записать новый элемент в индекс 20 и увеличить значение length, потому что массив слишком маленький. Теперь нам надо сделать новый массив из 40 элементов, скопировать туда элементы из предыдущего массива и уже потом записать новый элемент в новый массив по индексу 20 и увеличить переменную length до 21. И эта операция, как несложно догадаться, происходит за O(N), потому что надо скопировать N элементов.

Можно подумать, что вот этот случай с O(N) — не показателен, так как мы выращиваем массив 2 раза и потом ещё 20 элементов добавим за O(1). Потом нам, конечно, придётся скопировать массив в новый ещё раз. Но ведь после этого мы добавим за O(1) ещё 40 элементов.

Но это иллюзия. Допустим у нас есть пустой массив и мы хотим добавить в
конец 10 элементов. Тогда нам надо сделать следующую последовательность действий.

1. Создаём новый массив на 2 элемента и записываем туда 1 элемент по индексу 0. 1 действие.
2. Записываем в массив элемент по индексу 1. 1 действие.
3. Создаём новый массив из 4 элементов и копируем туда 2 элемента из старого массива. Потом записываем туда элемент по индексу 2. 3 действия.
4. Записываем в массив элемент по индексу 3. 1 действие.
5. Создаём новый массив из 8 элементов и копируем туда 4 элемента из старого массива. Потом записываем туда элемент по индексу 4. 5 действий.
6. Записываем в массив элементы по индексу 5, 6, 7. 3 действия.
7. Создаём новый массив из 16 элементов и копируем туда 8 элементов из старого массива. Потом записываем туда элемент по индексу 8. 9 действий.
8. Записываем в массив элементы по индексу 9. Одно действие.

Итак, нам понадобилось добавить в список 10 элементов.
И для этого нам понадобилось произвести 24 действия.

Посчитаем только операции копирования, из старого массива в новый. Получится 2 + 4 + 8 = 14. Вот где она линейная сложность, то есть O(N). N = 10, надо сделать 14 дополнительных копирований.

Джаваскриптовые массивы — вообще не массивы

В джаваскрипте за массивом стоит очень хитрая структура данных
и если вы делаете так

var memory = [];
var length = 0;
memory[length] = 2;
++length;

то для того, чтобы узнать O(1) у вас или O(N) или O(log(N)) — надо лезть в исходники интерпретатора. Возможно там не массив, а HashTable (чтобы можно было иметь нецифровые индексы и дырки), а может быть там гибридная структура, которая будет массивом, пока вы не начнёте добавлять нецифровые индексы и дырки, а потом распадётся на HashTable и обыкновенный массив. Сложно сказать наверняка, когда в ход идёт уличная магия и коварные оптимизации. Ну и сложность добавлений в конец списка, реализованного автором явным образом такая же как сложность добавления элемента в конец массива. То есть неизвестная.

Такие дела.