Как добавить в список js

Класс списка так же хранит указатели на первый — beg и последний — end его узел. Существует несколько способов интерпретации этих указателей. Мы подробнее рассмотрим более быстрый вариант, когда beg и end — это фиктивные узлы, а реальные находятся между ними.

Определим функцию, которая будет конструктором класса List: Функция List будет вызвана при объявлении объекта (экземпляра класса List) при помощи оператора new когда мы напишем: var lst = new List(); Теперь объект lst будет хранить данные списка, доступ к которым производится через точку: (lst.length и т.д.). Такие данные будет помнить каждый экземпляр класса (и у каждого они будут иметь свои значения). Выше подобным образом объявлены 3 переменные-свойства класса (end, beg и length).

В конструкторе класса List введен фиктивный указатель end, следующий за последним элементом списка. Фиктивный указатель beg через свойство beg.nxt ссылается на первый элемент списка. Так как список пока пустой, beg.nxt ссылается на end. Функцию (метод класса) push мы определим ниже.

Отметим, что поля nm и nxt инициализированы нулевым указателем null (напомним, что между undefined и null существует заметная разница). Фиктивный указатель end, при вставке в конец списка, будет превращаться в реальный последний узел. Поэтому, таким объявлением, мы предлагаем движку JavaScript сразу выделить память под объект с соответствующими полями, чтобы не пересоздавать его потом (при вставке). Это ускоряет работу с объектами (иногда в разы).

Методы класса

Кроме хранения данных, список должен выполнять определённые действия (иметь методы). Напишем, например, функцию, которая выводит список как строку в круглых скобках: Конструкция (условие? значение_если_истина : значение_если_ложь), являющаяся компактной записью условного оператора if, служит для «ликвидации» запятой после последнего узла в списке.

Функция с именем toString может быть в любом классе. Если она определена, то экземпляр класса, когда этого требует соответствующий контекст, преобразуется в строку. Например, следующий скрипт: так как список пока пустой, выведет строку: . Функция toString есть и у массивов, поэтому их элементы можно выводить аналогичным образом.

Вставка элементов

Напишем теперь функцию, вставляющую элемент с именем nm в начало списка: Так как мы хотим, чтобы список был похож на массив, при добавлении увеличивается переменная length (число элементов в списке). Затем (читая справа-налево) создаётся новый элемент-узел, который по указателю nxt ссылается на прежний первый элемент списка beg.nxt, а фиктивный узел beg по beg.nxt начинает ссылается на вновь добавленный узел. Аналогично выглядит функция, вставляющая элемент в конец списка: Последнюю строку также необходимо читать справа-налево: сначала создаётся новый фиктивный последний узел, на который по указателю end.nxt ссылается реальный последний узел (которым становится «старый» фиктивный). Затем указатель на новый фиктивный сохраняется в this.end.

Графически, последовательная вставка 0, 1, 2 в начало и конец списка выглядит следующим образом: (первые картинки в каждой строке изображают пустые списки):

Удаление элементов

Обсудим алгоритмы удаления элементов из списка. Удаление в правосторонних списках (есть только ссылки nxt) из начала не представляет труда: Отметим одну тонкость. Возвращаемый функцией указатель на имя первого узла nm остаётся в фиктивном узле nm, даже, если вызывающей функцию shift программе он уже не нужен. При необходимости (если данные, хранимые в списке занимают много памяти) его можно освободить, написав lst.beg.nm=null.

Удаление из конца одностороннего списка, существенно более затратная операция, так как необходимо получить последний элемент (реальный) о котором указатель end ничего не знает: При частом выполнении этой операции, лучше использовать класс двунаправленного списка List2, в котором фиктивный финальный узел end (как и остальные узлы) хранит указатель на предыдущий элемент end.prv.

Ещё немного функций

Приведём несколько функций класса List, эффективность которых не столь высока, по сравнению с вставкой в начало или конец списка. Так, получение узла под номером pos (начиная с нуля) выглядит следующим образом:

Упорядоченная вставка

Добавим ещё функцию, которая вставляет элемент в начало списка, но при этом следит за упорядоченностью элементов: Предполагается, что в общем случае имя узла nm не является числом или строкой, поэтому в цикле используется функция сравнения lt(a, b), которая должна возвращать true, если a < b, иначе (больше или равны) — false. Она задаётся извне (хотя по умолчанию она определена так, как в закомментированной строке):

Нефиктивные указатели

Рассмотрим кратко ещё один способ работы со списком, когда указатели beg и end реально ссылаются на первый и последний элементы списка (напрямую, а не через поле nxt). Оформим его в виде класса List1 Для удобства рядом с функциями-методами этого класса повторим аналогичные функции класса List. Добавление в начало списка имеет вид:

Двухсторонние списки

Элементы (узлы) двухcторонних списков хранят в себе указатели, как на следующий элемент (nxt), так и на предыдущий (prv): Они реализованы классом List2, конструктор которого выглядит так: Функции добавления в начало и конец реализованы следующим образом:

Тестирование быстродействия

Ниже тестируется вставка в начало и конец списка, реализованного массивом (медленный unshift) и правосторонними (List, List1) и двухсторонним списком (List2). Как организовать процесс тестирования описано в документе Speed.

добавлений раз: (ms) ( цикл: )

Ещё один тест связан с последовательной вставкой всех элементов в конец, а затем их удалением из конца и начала списка:

добавлений раз: (ms) ( цикл: )

Общий вывод такой: для операций push, unshift и shift, которые активно используются в алгоритмах поиска в ширину или глубину, стоит использовать класс List. Однако, если необходимо часто удалять элементы из конца списка pop, то List лучше не использовать.

Работа со списками

Подытожим. Методы работы со списками полностью аналогичны методам работы с массивами:

Структурирование данных с помощью JavaScript: Односвязные и двусвязные списки

Одними из основных структур данных, рассматриваемых в информатике, являются односвязные и двусвязные списки.

Когда мы проходили эти структуры, я попросил своих однокурсников привести мне несколько примеров, которые бы отражали суть этих списков. Они привели такие аналогии, как список бакалейных товаров и нумерация вагонов поезда. Эти примеры, как я позже узнал, являлись неточными. Список бакалейных товаров более похож на очередь, а вагоны поезда на массив.

Односвязный список

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

Узлы односвязного списка очень похожи на этапы игры » Охота за сокровищами «. Каждый этап содержит сообщение ( например, «Вы достигли Франции» ) и указатели на следующий этап ( например, «Посетите эти координаты широты и долготы» ).

Операции с односвязными списками

Можно выделить такие основные операции с односвязными списками: Node и SinglyList .

• data — здесь хранятся значения;
• next — указывает на следующий узел в списке.

SinglyList

• _length — извлекает количество узлов в списке;.
• head — определяет узел, как головной элемент списка;
• add(value) — добавляет в список узел;
• searchNodeAt(position) — ищет в списке узел на n-ной позиции;
• remove(position) — удаляет узел из списка.

Реализация односвязных списков

Для конкретного примера реализации мы сначала определим конструктор с именем Node , а затем конструктор с именем SinglyList . Каждый экземпляр узла должен « уметь » хранить данные и указывать на другой узел. Чтобы добавить эти функции, мы создадим два свойства: data и next , соответственно:

Далее, мы должны определить SinglyList :

Каждый экземпляр SinglyList будет иметь два свойства: _length и head . Первое устанавливает число узлов в списке; второй — указывает на головной элемент списка ( узел в начале списка ). Так как каждый новый экземпляр SinglyList не содержит узла, то значение по умолчанию для head и для _length будет null .

Методы односвязных списков

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

Метод add(value)

Теперь реализуем функционал для добавления узлов в список:

Добавление узла в список включает в себя множество этапов. Мы используем аргумент для add(value) , чтобы создать новый экземпляр Node , который присваивается переменной с именем node . Мы также объявляем переменную с именем currentNode и инициализируем ее в _head нашего списка. Если в списке нет узлов, тогда значение head будет null .

После этого мы обрабатываем в коде два возможных случая. В первом случае рассматривается добавление узла в пустой список. Если head не указывают на узел, тогда node назначается головным элементом списка, длина списка увеличивается на один узел, и возвращается node.

Во втором случае рассматривается добавление узла в непустой список. Мы входим в цикл while , и во время каждой итерации проверяем, указывает ли currentNode.next на другой узел. Во время первой итерации currentNode всегда указывает на головной элемент списка.

Если нет, мы назначаем для currentNode.next — node и возвращаем node .

Если ответ да, мы входим в тело цикла while . В теле цикла мы переопределяем currentNode как currentNode.next до тех пор, пока currentNode.next не перестанет указывать на другой узел. Другими словами, currentNode указывает на последний узел списка.

Цикл while разрывается. И в конце мы назначаем для currentNode.next — node , увеличиваем _length на один элемент, а затем возвращаем node.

Метод searchNodeAt(position)

Теперь мы можем добавлять узлы в список, но не можем производить поиск узлов на определенной позиции в списке. Для этого создадим метод с именем searchNodeAt(position) , который принимает аргумент с именем position . Этот аргумент должен быть целым числом, которое указывает на узел на n -ной позиции в списке:

Оператор if проверяет на соответствие первому случаю: в качестве аргумента передается неверная позиция.

Если индекс, переданный в searchNodeAt(position) , верен, тогда мы переходим ко второму случаю — циклу while . Во время каждой итерации цикла while , currentNode , который сначала всегда указывает на head , переназначается, как следующий узел в списке до тех пор, пока количество итераций не станет равно индексу позиции. Тогда цикл разрывается, и возвращается currentNode .

Метод remove(position)

Последний метод, который мы создадим, называется remove(position) :

Реализация remove(position) включает в себя три возможных варианта:

1. В качестве аргумента передается неверная позиция;
2. В качестве аргумента передается первая позиция (head списка) ;
3. В качестве аргумента передается существующая (не первая) позиция.

Первый и второй варианты являются самыми простыми. По первому сценарию, если список пуст или была передана несуществующая позиция, выдается ошибка.

При втором случае обрабатывается удаление первого узла в списке, который также является head . Если это так, то применяется следующая логика:

1. head устанавливается в currentNode.next ;
2. deletedNode указывает на currentNode ;
3. currentNode устанавливается в null ;
4. _length списка уменьшается на один;
5. Возвращается deletedNode .

Третий сценарий самый трудный для понимания. Эта сложность возникает из-за необходимости отслеживания двух узлов во время каждой итерации цикла while . Во время каждой итерации цикла мы отслеживаем элемент, находящийся перед узлом, который должен быть удален, и элемент, который должен быть удален. Когда While достигает позиции узла, который мы хотим удалить, цикл завершается.

К этому моменту мы учитываем ссылки на три узла: beforeNodeToDelete , nodeToDelete и deletedNode . Перед тем как удалить nodeToDelete , мы должны установить его значение next следующему значению beforeNodeToDelete . Если вы не до конца понимаете, в чем цель этого действия, вспомните, что у нас есть список связанных узлов; удаление любого узла разрушает связь, которая должна быть непрерывной от первого узла в списке до последнего.

Далее мы присваиваем значение deletedNode в nodeToDelete . Затем мы устанавливаем значение nodeToDelete на null , уменьшаем длину списка на один элемент и возвращаем deletedNode .

Полная реализация односвязного списка

Полная реализация нашего списка выглядит следующим образом:

От односвязных к двусвязным

Мы завершили реализацию односвязного списка. Теперь мы можем использовать структуру данных, которая добавляет, удаляет и ищет в списке узлы, которые располагаются не на смежных позициях.

Сейчас все наши операции стартуют с начала списка и продвигаются дальше к концу. Другими словами, они являются однонаправленными.

Двусвязный список

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

Операции двусвязных списков

Наш список будет включать в себя два конструктора: Node и DoublyList . Возможные операции:

• data — здесь хранятся значения;
• next — указывает на следующий узел в списке;
• previous — указывает на предыдущий узел в списке.

DoublyList

• _length — извлекает количество узлов в списке;
• head — назначает узел в качестве головного элемента списка;
• tail — назначает узел в качестве конечного элемента списка;
• add(value) — добавляет узел в список;
• searchNodeAt(position) — ищет узел на n-ной позиции в списке;
• remove(position) — удаляет узел из списка.

Реализация двусвязного списка

Для реализации мы создадим конструктор с именем Node :

Для создания двунаправленной обработки двусвязного списка нам нужны свойства, которые указывают в двух направлениях. Эти свойства мы назовем previous и next .

Далее нам необходимо реализовать DoublyList и добавить три свойства: _length , head и tail . В отличие от односвязного, двусвязный список содержит ссылку, как на начало, так и на конец списка. Так как каждый экземпляр DoublyList изначально создается без узлов, то значения по умолчанию для head и tail будут установлены на null :[/HTML]

Методы двусвязного списка

Рассмотрим следующие методы: add(value) , remove(position) и searchNodeAt(position) . Все эти методы мы использовали для односвязного списка, но теперь их нужно переписать для двунаправленной обработки.

Метод add(value)

В этом методе у нас реализованы два сценария. Во-первых, если список пуст, тогда в качестве head и tail мы назначаем добавляемый узел. Во-вторых, если список содержит узлы, тогда мы находим конечный элемент и устанавливаем добавляемый узел в качестве tail.next . Также нам нужно задать для нового конечного элемента двунаправленную обработку. Другими словами, нам необходимо установить первоначальный конечный элемент в качестве tail.previous .

Метод searchNodeAt(position)

Реализация searchNodeAt(position) идентична односвязному списку:

Метод remove(position)

Этот метод наиболее сложный для понимания. Я сначала приведу код, а затем поясню его:

remove(position) обрабатывает четыре возможных случая:

1. Позиция, передаваемая в качестве аргумента remove(position) , не существует. В этом случае, мы выдаем ошибку;
2. Позиция, передаваемая в качестве аргумента remove(position) , является первым узлом (head) списка. Если это так, то мы устанавливаем head в качестве deletedNode , а затем в качестве head назначаем следующий узел в списке. Далее мы должны проверить, содержит ли наш список более одного узла. Если нет, то head будет установлен на null и мы переходим к части if оператора if-else . В теле if мы также должны установить tail на null . Таким образом, мы возвращаем список в исходное состояние пустого двусвязного списка. Если мы удаляем первый узел в списке и у нас остается более одного узла, то мы входим в раздел else оператора if-else . В этом случае мы устанавливаем свойство previous для head на null , потому что у нас нет узлов перед головным элементом списка;
3. Позиция, передаваемая в качестве аргумента remove(position) , является конечным элементом списка. Во-первых, tail устанавливается в качестве deletedNode . Во-вторых, в качестве tail переустанавливается узел, расположенный перед конечным элементом списка. В-третьих, после нового конечного элемента не будет узлов, расположенных после него, и его свойство next должно быть равно null ;
4. Мы разрываем цикл while , как только currentNode указывает на узел, расположенный в позиции, передаваемой в качестве аргумента remove(position) . После этого мы переназначаем значение beforeNodeToDelete.next на узел, расположенный после nodeToDelete и, наоборот, мы переназначаем значение afterNodeToDelete.previous на узел, расположенный перед nodeToDelete . Другими словами, мы убираем ссылки на удаленный узел и переназначаем их на правильные узлы. Далее мы устанавливаем nodeToDelete в качестве значения deletedNode . Затем мы устанавливаем значение nodeToDelete на null .

В конце мы уменьшаем длину списка и возвращаем deletedNode .

Полная реализация двусвязного списка

Вот полная реализация:

Заключение

В этой статье мы рассмотрели много информации. Если что-либо из этого вам не до конца понятно, прочитайте материал еще раз и поэкспериментируйте с кодом. Когда вы поймете смысл всего изложенного, то сможете добавлять эти структуры данных в код своих проектов.

Как добавить в список js

• Open with Desktop
• View raw
• Copy raw contents Copy raw contents

Copy raw contents

Copy raw contents

Мультивставка: insertAdjacentHTML и DocumentFragment

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

Оптимизация вставки в документ

Рассмотрим задачу: сгенерировать список UL/LI .

Есть две возможных последовательности:

Сначала вставить UL в документ, а потом добавить к нему LI :

Полностью создать список «вне DOM», а потом — вставить в документ:

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

Почему же? Иногда говорят: «потому что браузер перерисовывает каждый раз при добавлении элемента». Это не так. Дело вовсе не в перерисовке.

Браузер достаточно «умён», чтобы ничего не перерисовывать понапрасну. В большинстве случаев процессы перерисовки и сопутствующие вычисления будут отложены до окончания работы скрипта, и на тот момент уже совершенно без разницы, в какой последовательности были изменены узлы.

Тем не менее, при вставке узла происходят разные внутренние события и обновления внутренних структур данных, скрытые от наших глаз.

Что именно происходит — зависит от конкретной, внутренней браузерной реализации DOM, но это отнимает время. Конечно, браузеры развиваются и стараются свести лишние действия к минимуму.

Добавление множества узлов

Продолжим работать со вставкой узлов.

Рассмотрим случай, когда в документе уже есть большой список UL . И тут понадобилось срочно добавить еще 20 элементов LI .

Как это сделать?

Если новые элементы пришли в виде строки, то можно попробовать добавить их так:

Но операцию ul.innerHTML += «. » можно по-другому переписать как ul.innerHTML = ul.innerHTML + «. » . Иначе говоря, она не прибавляет, а заменяет всё содержимое списка на дополненную строку. Это и нехорошо с точки зрения производительности, но и будут побочные эффекты. В частности, все внешние ресурсы (картинки) внутри перезаписываемого innerHTML будут загружены заново. Если в каких-то переменных были ссылки на элементы списка — они станут неверны, так как содержимое полностью заменяется. В общем, так лучше не делать.

А если нужно вставить в середину списка? Здесь innerHTML вообще не поможет.

Можно, конечно, вставить строку во временный DOM-элемент и перенести оттуда элементы, но есть и гораздо лучший вариант: метод insertAdjacentHTML !

Метод insertAdjacentHTML позволяет вставлять произвольный HTML в любое место документа, в том числе и между узлами!

html : Строка HTML, которую нужно вставить

where : Куда по отношению к elem вставлять строку. Всего четыре варианта:

Например, вставим пропущенные элементы списка перед <li>5</li> :

У этого метода есть «близнецы-братья»:

— вставляет в произвольное место не строку HTML, а элемент newElem . — создаёт текстовый узел из строки text и вставляет его в указанное место относительно elem .

Синтаксис этих методов, за исключением последнего параметра, полностью совпадает с insertAdjacentHTML . Вместе они образуют «универсальный швейцарский нож» для вставки чего угодно куда угодно.

До этого мы говорили о вставке строки в DOM. А что делать в случае, когда надо в существующий UL вставить много DOM-элементов?

Можно вставлять их один за другим, вызовом insertBefore/appendChild , но при этом получится много операций с большим живым документом.

Вставить пачку узлов единовременно поможет DocumentFragment . Это особенный кросс-браузерный DOM-объект, который похож на обычный DOM-узел, но им не является.

Синтаксис для его создания:

В него можно добавлять другие узлы.

Его можно клонировать:

У DocumentFragment нет обычных свойств DOM-узлов, таких как innerHTML , tagName и т.п. Это не узел.

Его «Фишка» заключается в том, что когда DocumentFragment вставляется в DOM — то он исчезает, а вместо него вставляются его дети. Это свойство является уникальной особенностью DocumentFragment .

Например, если добавить в него много LI , и потом вызвать ul.appendChild(fragment) , то фрагмент растворится, и в DOM вставятся именно LI , причём в том же порядке, в котором были во фрагменте.

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

Понять текущее положение вещей вы можете, запустив следующий небольшой бенчмарк.

append/prepend, before/after, replaceWith

Сравнительно недавно в стандарте появились методы, которые позволяют вставить что угодно и куда угодно.

• node.append(. nodes) — вставляет nodes в конец node ,
• node.prepend(. nodes) — вставляет nodes в начало node ,
• node.after(. nodes) — вставляет nodes после узла node ,
• node.before(. nodes) — вставляет nodes перед узлом node ,
• node.replaceWith(. nodes) — вставляет nodes вместо node .

Эти методы ничего не возвращают.

Во всех этих методах nodes — DOM-узлы или строки, в любом сочетании и количестве. Причём строки вставляются именно как текстовые узлы, в отличие от insertAdjacentHTML .

Пример (с полифиллом):

Манипуляции, меняющие структуру DOM (вставка, удаление элементов), как правило, быстрее с отдельным маленьким узлом, чем с большим DOM, который находится в документе.

Конкретная разница зависит от внутренней реализации DOM в браузере.

Семейство методов для вставки HTML/элемента/текста в произвольное место документа:

• elem.insertAdjacentHTML(where, html)
• elem.insertAdjacentElement(where, element)
• elem.insertAdjacentText(where, text)

DocumentFragment позволяет минимизировать количество вставок в большой живой DOM. Эта оптимизация особо эффективна в старых браузерах, в новых эффект от неё меньше или наоборот отрицательный.

Элементы сначала вставляются в него, а потом — он вставляется в DOM. При вставке DocumentFragment «растворяется», и вместо него вставляются содержащиеся в нём узлы.

DocumentFragment , в отличие от insertAdjacent* , работает с коллекцией DOM-узлов.

Современные методы, работают с любым количеством узлов и текста, желателен полифилл: