Какова среда выполнения Node.insertBefore?

Question

Я понимаю, что каждый браузер будет реализовывать его по-своему, но есть ли какие-либо ссылки или тесты, которые указывают это?

Казалось бы, простейшая реализация - O(n) по количеству дочерних элементов Node

РЕДАКТИРОВАТЬ: я провел несколько тестов.Вот результаты

FireFox 3.6.10 в Linux

inserted 1000 elements into   1000 elements in  131.44 ms (average over 101 trials,  291.31 ms inc appendChild) while in dom: true
inserted 1000 elements into  10000 elements in  235.91 ms (average over  11 trials, 1311.36 ms inc appendChild) while in dom: true
inserted 1000 elements into 100000 elements in 2349.00 ms (average over  2 trials, 14150.50 ms inc appendChild) while in dom: true

inserted 1000 elements into   1000 elements in  13.13 ms (average over 101 trials,   267.00 ms inc appendChild) while in dom: false
inserted 1000 elements into  10000 elements in  67.45 ms (average over  11 trials,  1517.09 ms inc appendChild) while in dom: false
inserted 1000 elements into 100000 elements in 617.00 ms (average over   2 trials, 15214.50 ms inc appendChild) while in dom: false

Chrome 7 в Linux:

inserted  1000 elements into    1000 elements in      0.65 ms (average over   101 trials,     30.34 ms inc appendChild) while in dom: true
inserted  1000 elements into   10000 elements in      1.55 ms (average over    11 trials,    175.09 ms inc appendChild) while in dom: true
inserted  1000 elements into  100000 elements in     12.00 ms (average over     2 trials,   2255.00 ms inc appendChild) while in dom: true
inserted  1000 elements into    1000 elements in      0.49 ms (average over   101 trials,     41.13 ms inc appendChild) while in dom: false
inserted  1000 elements into   10000 elements in      1.36 ms (average over    11 trials,    301.18 ms inc appendChild) while in dom: false
inserted  1000 elements into  100000 elements in     12.00 ms (average over     2 trials,   2565.50 ms inc appendChild) while in dom: false

Я создал dom Node, заполнил его N элементы, а затем вызывается insertBefore(newchild, randominitialchild) M раз.

in dom: false означает, что родительский узел не был добавлен в дерево документов, поэтому браузер не должен пересчитывать макет (надеюсь?)

Результаты показывают, что вставка составляет O(n)

Answer 1

a.insertBefore(b)

Если узлы хранятся в связанном списке, то процесс так же прост, как поиск узла до b, который занимает O (n) времени, поскольку нет обратных указателей, только указатели на следующий узел.Затем мы изменяем следующий указатель узла до b на a.

Так что да, вы правы, процесс берет O (n) в лучшем случае со связанным списком, если список не является двойным-связанной.

Answer 2

Время, необходимое для фактического добавления узла в дерево, будет минимальным.Для обновления и перерасчета макета потребуется время.

Answer 3

Я бы предположил, что узлы хранятся в двусвязном списке, и в этом случае insertBefore будет занимать постоянное время. Односвязные списки редко используются в практических приложениях.