написать впереди
В этой статье мы сначала обсудим, что такое связанный список и что такое связанный список в JavaScript, затем мы будем использовать язык JavaScript для реализации дизайна различных типов связанных списков, и, наконец, мы зададим несколько общих вопросов и ответим на них из различных Короче говоря, цель состоит в том, чтобы полностью получить связанный список
Получив концепцию, мы можем выбрать классификацию связанных списков и завершить их в соответствии со степенью сложности. Название связанного списка относительно простое. Если вы полностью прочитали дизайн связанного списка в этой статье, по крайней мере, вы можете легко избавиться от него.Вопросов 20, а количество вопросов со связанным списком относительно невелико.Всего около 50 вопросов, и есть десять вопросов, которые требуют членов, то есть, если вы напишите 40 вопросов, вы можете получить предварительное представление о структуре данных связанного списка. Если вы не хотите находить Вопросы, можно отсортировать по порядку в моем репозитории алгоритмов GitHub. Если у вас есть вопросы или концепции, которые вы не знаете Не понял, вы можете прочитать решения, которые я написал. Параллельно я также записал видео. В конце статьи есть ссылка, поэтому приступим к изучению связанного списка.
Что такое связанный список
Обычно мы хотим хранить в программе несколько элементов. Массив, вероятно, наиболее часто используемая структура данных. Массив - очень удобная структура данных. Это можно сделать даже очень простым способом, а именно[]этот синтаксис для доступа к его элементам
Связный список также хранит упорядоченный набор элементов, но в отличие от массивов элементы в связанном списке не являются смежными в памяти.Каждый элемент состоит из узла, в котором хранится сам элемент и ссылка на следующий элемент (также может называться указатель) композиция
Далее рассмотрим структуру данных массива.У нее есть недостаток.В большинстве языков размер массива фиксированный.Вставка или удаление элементов из начала или середины массива накладно,потому что элементы нужно перемещать , как показано на следующем рисунке.
Приведенный выше массив удаляет элемент с индексом 2 и значением 3, тогда нам нужно сначала удалить элемент 3, потому что элемент с индексом 2 и значением 3 удаляется, а индекс 2 пуст, поэтому тогда , нам нужно также удалить элемент по индексу 3. То есть элемент 4 сдвигается вперед на одно место, и в то же время следующий за ним элемент 5 также нужно перемещать вперед на одно место.Вставка элемента в массив также то же самое.Пока в массиве на одну позицию меньше или на одну больше, следующие элементы должны быть перемещены вперед или назад на одну позицию по очереди, поэтому возможно, что при большой длине массива эффективность вставки и удаления будут постепенно уменьшаться
Давайте снова посмотрим на связанный список
То же самое относится и к удалению элемента 3. Связанному списку нужно только выполнить итерацию к узлу со значением 3 и указать узел 2 на узел 4. Если узел 3 не имеет отношения ссылки, он будет рассматриваться как мусор механизмом сборки мусора, даже когда узел очень во многих случаях удалить элемент все равно можно только изменив ссылочное отношение, при этом вставка элемента реверсируется, то есть сначала разъединяются элементы по обе стороны от позиции вставки, а затем предыдущая элемент указывает на вставленный элемент, а вставленный элемент указывает на следующий элемент, то есть чем больше элементов, тем эффективнее будет массив сравнения.
По сравнению с традиционными массивами одним из преимуществ связанных списков является то, что вам не нужно перемещать другие элементы при добавлении или удалении элементов, но в массиве мы можем напрямую обращаться к любому элементу в любой позиции, что невозможно в связанном списке. список, потому что в связанном списке каждый узел имеет ссылку только на следующий узел, поэтому, если вы хотите получить доступ к элементу в середине связанного списка, вы должны выполнить итерацию связанного списка с начальной точки (головной узел узла). связанный список) до тех пор, пока не найдете нужный элемент, требующий внимания
Связанные списки в JavaScript
Выше мы кратко представили концепцию обычного связанного списка, но как мы можем представить связанный список на языке JavaScript?
Поскольку в JS нет встроенной структуры данных связанного списка, нам нужно использовать объекты для имитации реализации связанных списков, так же, как мы представили связанный список выше, на самом деле это односвязный список, в дополнение к двусвязному списку. , круговой связанный список и т. д. Мы будем вводить их один за другим и использовать JavaScript для реализации следующих
Односвязный список
Давайте сначала посмотрим на базовый односвязный список.Каждый элемент односвязного списка состоит из узла, в котором хранится сам элемент, и указателя на следующий элемент, как показано на следующем рисунке.
Чтобы реализовать структуру данных связанного списка, ключом является сохранение элемента head (то есть элемента head связанного списка) и следующего указателя каждого элемента, С помощью этих двух частей мы можем легко перемещаться по связанному списку чтобы управлять всеми элементами.Вы можете поместить связанный список.Подумайте об этом как о железной цепи.Каждый узел в цепочке связан друг с другом.Нам нужно только найти главу цепочки,и можно найти всю цепочку. Итак, как смоделировать односвязный список в JS?, идем пошагово
Прежде всего нам нужно создать класс.Функция этого класса состоит в описании узлов связанного списка.Это очень просто.Ему нужно всего два атрибута,один используется для сохранения значения этого узла,а other используется для сохранения значения, указывающего на следующий node.pointer, как показано ниже.
/**
* @description: 创建链表单节点类
* @param {*} val 节点值
* @return {*}
*/
function ListNode(val) {
this.val = val
this.next = null
}
Далее нам нужно написать класс связанного списка, где свойство length представляет длину связанного списка, а свойство head представляет головной узел связанного списка.
/**
* @description: 创建链表类
* @param {*}
* @return {*}
*/
function LinkedList() {
this.length = 0
this.head = null
}
Давайте подумаем об этом, так как мы моделируем класс связанного списка, мы должны поместить в этот класс все функции, которые он может использовать, такие как массивы сpush/splice/indexOf/...Мы также должны иметь эти полезные методы в связанном списке.Давайте сначала тщательно подумаем, какие практические функции или методы добавить в связанный список.Сначала мы создадим базовый скелет.Я перечислил здесь много.Давайте реализуем их один на один. вниз, добро пожаловать, чтобы добавить
// 向链表中追加节点
LinkedList.prototype.append = function (val) { }
// 在链表的指定位置插入节点
LinkedList.prototype.insert = function (index, val) { }
// 删除链表中指定位置的元素，并返回这个元素的值
LinkedList.prototype.removeAt = function (index) { }
// 删除链表中对应的元素
LinkedList.prototype.remove = function (val) { }
// 获取链表中给定元素的索引
LinkedList.prototype.indexOf = function (val) { }
// 获取链表中某个节点
LinkedList.prototype.find = function (val) { }
// 获取链表中索引所对应的元素
LinkedList.prototype.getElementAt = function (index) { }
// 判断链表是否为空
LinkedList.prototype.isEmpty = function () { }
// 获取链表的长度
LinkedList.prototype.size = function () { }
// 获取链表的头元素
LinkedList.prototype.getHead = function () { }
// 清空链表
LinkedList.prototype.clear = function () { }
// 序列化链表
LinkedList.prototype.join = function (string) { }
getElementAt(index)
Давайте сначала получим элемент, соответствующий индексу в связанном списке.getElementAtметод и получить элемент связанного списка через значение узла, а именноfindметод, потому что они будут использоваться много раз позже, скажем,getElementAtметод, выше мы сказали, что если мы хотим найти элемент, мы должны выполнить итерацию с самого начала, поэтому мы можем выполнять итерацию непосредственно по входящему индексу
Сначала определитесь с параметрамиindexграниц, если значение выходит за границы индекса (меньше 0 или большеlength - 1), затем вернутьсяnull, начинаем со связанного спискаheadНачните с узла, пройдитесь по всему связанному списку, пока не найдете узел, соответствующий позиции индекса, а затем вернитесь к этому узлу, не правда ли, это очень просто? Как и все упорядоченные наборы данных, индекс связанного списка также начинается с 0. Пока есть головной узел связанного списка, вы можете пройти, чтобы найти элемент в позиции индекса, поэтому мы вызываем его в конструктор то естьLinkedListкласс сохраненheadстоимость
// 获取链表中索引所对应的元素
LinkedList.prototype.getElementAt = function (index) {
if (index < 0 || index >= this.length) return null
let cur = this.head
while (index--) {
cur = cur.next
}
return cur
}
find(val)
findМетоды иgetElementAtМетод аналогичен, один находит элементы по индексу, а другой находит элементы по значению узла, поэтому мы можем выполнять итерацию и сравнивать напрямую.
// 获取链表中某个节点
LinkedList.prototype.find = function (val) {
let cur = this.head
while (cur) {
if (cur.val == val) return cur
cur = cur.next
}
return null
}
append(val)
имеютgetElementAtПосле метода мы можем легко реализоватьappendметод, функция этого метода заключается в добавлении элементов в конец связанного списка
Этот метод передается в значении, мы можем передать указанный выше конструкторListNodeчтобы создать новый узел
Затем нам нужно рассмотреть, если связанный списокheadдляnull, эта ситуация указывает на то, что связанный список пуст, поэтому необходимоheadУзел указывает на вновь добавленный элемент, чтобы убедиться, что головной узел сохранен.Если он не пуст, мы передаемgetElementAtМетод находит последний узел связанного списка, а индекс последнего узла — это длина связанного списка, который мы сохранили в конструкторе.lengthАтрибут минус 1, затем последний узелnextУказатель указывает на вновь добавленный элемент
недавно добавленный элементnextУказатель по умолчаниюnull, последний элемент связанного спискаnextзначениеnull, кроме того, после присоединения узла к связному списку необходимо прибавить 1 к длине связанного списка, чтобы убедиться, чтоlengthАтрибут равен длине связанного списка, как показано ниже.
// 向链表中追加节点
LinkedList.prototype.append = function (val) {
let node = new ListNode(val)
if (!this.head) {
this.head = node
} else {
let cur = this.getElementAt(this.length - 1)
cur.next = node
}
this.length++
}
insert(index, val)
Далее будем реализовыватьinsertметод, то есть добавление узла в любую позицию в связанном списке
Чтобы вставить элемент в указанную позицию, в первую очередь нам еще нужно оценить входящийindexНе выходит ли индекс за пределы
Тогда рассмотрим два случая
когдаindexКогда значение равно 0, это означает, что новый узел должен быть вставлен в начало связанного списка, аnextуказатель на настоящееhead, затем обновитеheadЗначение вновь вставленного узла может быть, как показано на следующем рисунке.
когдаindexКогда значение не равно 0, то есть вставленный узел находится в середине или конце связанного списка, мы сначала находим предыдущий узел в позиции, которую нужно вставить.prevNode, затем поместите новый узелnewNodeизnextуказатель наprevNodeизnextсоответствующий узел, а затемprevNodeизnextуказатель наnewNode, чтобы новый узел был вставлен в связанный список.Когда вставленный узел находится в конце связанного списка, этот метод также применим, как показано на следующем рисунке.
Наконец, мы вставили узел, и нам также нужно добавить длину связанного списка вlengthДобавьте 1 к длине, код выглядит следующим образом
// 在链表的指定位置插入节点
LinkedList.prototype.insert = function (index, val) {
if (index < 0 || index > this.length) return false
let node = new ListNode(val)
if (index === 0) {
node.next = this.head
this.head = node
} else {
let prev = this.getElementAt(index - 1)
node.next = prev.next
prev.next = node
}
this.length++
return true
}
removeAt(index)
Точно так же мы можем легко написатьremoveAtСпособ удаления узла в указанном положении в связанном списке
Тем не менее, сначала оцените входящиеindexНе выходит ли индекс за пределы
или в двух случаях
Если удаляемый узел находится в начале связанного списка,headПросто перейдите к следующему узлу.Если текущий связанный список имеет только один узел, то следующий узелnull, тоheadУказание на следующий узел эквивалентно размещениюheadустановлен вnull, связанный список пуст после удаления
Если удаляемый узел находится в середине связанного списка, нам нужно выяснитьindexпредыдущий узел на месте, поместите егоnextуказатель наindexСледующий узел в локации.Короче говоря, чтобы удалить узел, вам нужно всего лишь изменить указатель соответствующего узла, отключить соседние узлы слева и справа от удаленного местоположения, а затем снова подключить его.
Удаленный узел не имеет отношения ссылки, и механизм сборки мусора JavaScript справится с этим.Что касается механизма сборки мусора, то он также не входит в рамки этой статьи.Если вы его знаете, удалите элемент узла.Нам также нужно уменьшить длина связанного списка на 1. Окончательный код выглядит следующим образом
// 删除链表中指定位置的元素，并返回这个元素的值
LinkedList.prototype.removeAt = function (index) {
if (index < 0 || index >= this.length) return null
let cur = this.head
if (index === 0) {
this.head = cur.next
} else {
let prev = this.getElementAt(index - 1)
cur = prev.next
prev.next = cur.next
}
this.length--
return cur.val
}
indexOf(val)
Получить индекс данного элемента в связанном списке, это относительно просто, вы можете выполнить итерацию напрямую, если он совпадает, вернуть соответствующий индекс, если он не совпадает, вернуть -1
// 获取链表中给定元素的索引
LinkedList.prototype.indexOf = function (val) {
let cur = this.head
for (let i = 0; i < this.length; i++) {
if (cur.val === val) return i
cur = cur.next
}
return -1
}
remove(val)
Удалить соответствующий элемент в связанном списке, с предыдущим предзнаменованием, здесь это относительно просто, мы можем напрямую использоватьindexOfметод, чтобы получить соответствующий индекс, а затем использоватьremoveAtметод удаления узла
// 删除链表中对应的元素
LinkedList.prototype.remove = function (val) {
let index = this.indexOf(val)
return this.removeAt(index)
}
isEmpty()
Чтобы судить, пуст ли связанный список, нам нужно только оценить длину связанного списка.lengthПодождите, пока он не будет равен 0
// 判断链表是否为空
LinkedList.prototype.isEmpty = function () {
return !this.length
}
size()
Какой длина списка получаетсяlength
// 获取链表的长度
LinkedList.prototype.size = function () {
return this.length
}
getHead()
Получить главный элемент связанного списка и вернутьсяheadхарактеристики
// 获取链表的头元素
LinkedList.prototype.getHead = function () {
return this.head
}
clear()
Чтобы очистить связанный список, нам нужно толькоheadпусто, то пустьlengthРавно 0, просто подождите, пока механизм сборки мусора переработает неиспользуемый отброшенный связанный список.
// 清空链表
LinkedList.prototype.clear = function () {
this.head = null
this.length = 0
}
join(string)
Сериализация связанного списка означает вывод связанного списка в указанном формате, аналогичном формату массива.joinМетод, это облегчить наше тестирование
// 序列化链表
LinkedList.prototype.join = function (string) {
let cur = this.head
let str = ''
while (cur) {
str += cur.val
if (cur.next) str += string
cur = cur.next
}
return str
}
Итак, на данный момент наш класс односвязного списка разработан, приходите и тестируйте его, мы вводим следующий код для тестирования
let linkedList = new LinkedList()
linkedList.append(10)
linkedList.append(20)
linkedList.append(30)
console.log(linkedList.join("--"))
linkedList.insert(0, 5)
linkedList.insert(2, 15)
linkedList.insert(4, 25)
console.log(linkedList.join("--"))
console.log(linkedList.removeAt(0))
console.log(linkedList.removeAt(1))
console.log(linkedList.removeAt(2))
console.log(linkedList.join("--"))
console.log(linkedList.indexOf(20))
linkedList.remove(20)
console.log(linkedList.join("--"))
console.log(linkedList.find(10))
linkedList.clear()
console.log(linkedList.size())
Окончательный вывод выглядит следующим образом
// 10--20--30
// 5--10--15--20--25--30
// 5
// 15
// 25
// 10--20--30
// 1
// 10--30
// ListNode { val: 10, next: ListNode { val: 30, next: null } }
// 0
В приведенном выше коде отсутствует проверка некоторых параметров, но нам достаточно изучить, дополнить код и прикрепить ссылку в конце текста.
Двусвязный список
Мы говорили об односвязном списке выше, а теперь поговорим о двусвязном списке, так что же такое двусвязный список? На самом деле, вы можете услышать название, каждый элемент в односвязном списке имеет только одинnextУказатель, используемый для указания на следующий узел, мы можем пройти весь связанный список только из головы связанного списка, любой узел может найти только его следующий узел, но не его предыдущий узел, каждый элемент в двусвязном списке имеет два указателя, один используется для указания на следующий узел, а другой используется для указания на предыдущий узел.В двусвязном списке, в дополнение к обходу из головы, как в односвязном списке, его также можно пройти из хвост, как показано на следующем рисунке
С односвязным списком мы сначала создаем класс узла связанного списка, разница в том, что ему нужен еще одинprevатрибут используется для указания на предыдущий узел
/**
* @description: 创建双向链表单节点类
* @param {*} val 节点值
* @return {*}
*/
function ListNode(val) {
this.val = val
this.next = null
this.prev = null
}
Двусвязный список похож на односвязный список с добавлением еще одного хвостового узла.tail
/**
* @description: 创建双向链表类
* @param {*}
* @return {*}
*/
function DoubleLinkedList() {
this.length = 0
this.head = null
this.tail = null
}
Далее реализуем метод-прототип двусвязного списка
getElementAt(index)
Во-первых, получить элемент, соответствующий индексу в двусвязном списке.Поскольку двусвязный список можно итеративно искать в обоих направлениях, здесьgetElementAtметод, который мы можем оптимизировать, когда индекс больше, чем длина связанного спискаlength/2, мы можем искать сзади вперед, в противном случае мы можем искать спереди назад, чтобы элемент узла можно было найти быстрее
// 获取双向链表中索引所对应的元素
DoubleLinkedList.prototype.getElementAt = function (index) {
if (index < 0 || index >= this.length) return null
let cur = null
if(index > Math.floor(this.length / 2)){
// 从后往前
cur = this.tail
let i = this.length - 1
while (i > index) {
cur = cur.prev
i--
}
}else{
// 从前往后
cur = this.head
while (index--) {
cur = cur.next
}
}
return cur
}
find(val)
findМетоды иgetElementAtМетод аналогичен,getElementAtметод можно оптимизировать, тоfindЕго также можно оптимизировать после того, как он станет двусвязным списком. Мы думаем, что, поскольку его можно повторять в обоих направлениях, не будет ли нам быстрее выполнять итерацию с обеих сторон одновременно. В случае двунаправленной итерации, весь связанный список будет повторяться только тогда, когда его невозможно найти, что более эффективно.
// 获取双向链表中某个节点
DoubleLinkedList.prototype.find = function (val) {
let curHead = this.head
let curTail = this.tail
while (curHead) {
if (curHead.val == val) return curHead
curHead = curHead.next
if (curTail.val == val) return curTail
curTail = curTail.prev
}
return null
}
append(val)
Снова вернитесь к нашему элементу узла добавления, все еще есть некоторая разница между добавлением двусвязного списка и односвязным списком.
Когда связанный список пуст, помимоheadУказание на текущий добавленный узел, но также и наtailтакже указывает на текущий добавляемый узел
Когда связанный список не пуст, непосредственноtailизnextУказывает на текущий узел, который нужно добавитьnode, затем изменитеnodeизprevуказать на старыйtail,Последний отзывtailдля вновь добавленного узла
Операция добавления двусвязного списка не требует обхода всего связанного списка с самого начала.tailХвост связного списка можно найти напрямую, что удобнее, чем работа с односвязным списком.lengthДобавьте 1 к значению, чтобы изменить длину связанного списка.
// 向双向链表中追加节点
DoubleLinkedList.prototype.append = function (val) {
let node = new ListNode(val)
if (this.head === null) {
// 链表为空，head 和 tail 都指向当前添加的节点
this.head = node
this.tail = node
}
else {
// 链表不为空，将当前节点添加到链表的尾部
this.tail.next = node
node.prev = this.tail
this.tail = node
}
this.length++
}
insert(index, val)
Далее способ вставки узловых элементов, идея такая же, это не сложно, обращаем внимание наtailа такжеprevУказатели обсуждаются по ситуации, после вставки добавляем к длине 1.
// 在双向链表的指定位置插入节点
DoubleLinkedList.prototype.insert = function (index, val) {
if (index < 0 || index > this.length) return false
// 插入到尾部
if (index === this.length) {
this.append(val)
} else {
let node = new ListNode(val)
if (index === 0) { // 插入到头部
if (this.head === null) {
this.head = node
this.tail = node
} else {
node.next = this.head
this.head.prev = node
this.head = node
}
} else { // 插入到中间位置
let curNode = this.getElementAt(index)
let prevNode = curNode.prev
node.next = curNode
node.prev = prevNode
prevNode.next = node
curNode.prev = node
}
this.length++
}
return true
}
removeAt(index)
Удалить элемент в указанной позиции в двусвязном списке, также обратите вниманиеtailа такжеprevУказатели обсуждаются по регистру, а длина может быть уменьшена на 1 после последнего удаления.
// 删除双向链表中指定位置的元素，并返回这个元素的值
DoubleLinkedList.prototype.removeAt = function (index) {
if (index < 0 || index >= this.length) return null
let current = this.head
let prevNode
if (index === 0) { // 移除头部元素
this.head = current.next
this.head.prev = null
if (this.length === 1) this.tail = null
} else if (index === this.length - 1) { // 移除尾部元素
current = this.tail
this.tail = current.prev
this.tail.next = null
} else { // 移除中间元素
current = this.getElementAt(index)
prevNode = current.prev
prevNode.next = current.next
current.next.prev = prevNode
}
this.length--
return current.val
}
indexOf(val)
Найдите индекс элемента в двусвязном списке с указанным вышеfindМетод заключается в том, чтобы проложить путь, здесь все просто, идея та же,
// 获取双向链表中给定元素的索引
DoubleLinkedList.prototype.indexOf = function (val) {
let curHead = this.head
let curTail = this.tail
let idx = 0
while (curHead !== curTail) {
if (curHead.val == val) return idx
curHead = curHead.next
if (curTail.val == val) return this.length - 1 - idx
curTail = curTail.prev
idx++
}
return -1
}
join(string)
Сериализованный связанный список может по-прежнему соответствовать односвязному списку выше.
// 序列化双向链表
DoubleLinkedList.prototype.join = function (string) {
let cur = this.head
let str = ''
while (cur) {
str += cur.val
if (cur.next) str += string
cur = cur.next
}
return str
}
Мы так много ввели про двусвязный список, а остальные методы относительно просты, поэтому я не буду вдаваться в подробности Полный код в случае двусвязного списка в конце статьи
Аналогично, давайте просто проверим, правда это или нет.
let doubleLinkedList = new DoubleLinkedList()
doubleLinkedList.append(10)
doubleLinkedList.append(15)
doubleLinkedList.append(20)
doubleLinkedList.append(25)
console.log(doubleLinkedList.join("<->"))
console.log(doubleLinkedList.getElementAt(0).val)
console.log(doubleLinkedList.getElementAt(1).val)
console.log(doubleLinkedList.getElementAt(5))
console.log(doubleLinkedList.join("<->"))
console.log(doubleLinkedList.indexOf(10))
console.log(doubleLinkedList.indexOf(25))
console.log(doubleLinkedList.indexOf(50))
doubleLinkedList.insert(0, 5)
doubleLinkedList.insert(3, 18)
doubleLinkedList.insert(6, 30)
console.log(doubleLinkedList.join("<->"))
console.log(doubleLinkedList.find(10).val)
console.log(doubleLinkedList.removeAt(0))
console.log(doubleLinkedList.removeAt(1))
console.log(doubleLinkedList.removeAt(5))
console.log(doubleLinkedList.remove(10))
console.log(doubleLinkedList.remove(100))
console.log(doubleLinkedList.join("<->"))
Вывод приведенного выше кода выглядит следующим образом
// 10<->15<->20<->25
// 10
// 15
// null
// 10<->15<->20<->25
// 0
// 3
// -1
// 5<->10<->15<->18<->20<->25<->30
// 10
// 5
// 15
// null
// 10
// null
// 18<->20<->25<->30
Ну ошибки нет, простое сравнение правильное, Нет Проблем
круговой связанный список
Давайте посмотрим на другой связанный список, циклический связанный список.Как следует из названия, хвостовой узел циклического связанного списка указывает на его собственный головной узел.
Циклический связанный список имеет односторонний циклический связанный список, а также может иметь двусторонний циклический связанный список, как показано ниже.
Список цепочек с одним двойным кольцом Здесь мы не будем писать один, вы можете попробовать сами, сравните вершину нашего аннигиляции, вам нужно только обратить внимание на нижний хвостовой узел, чтобы указать на головной узел
Почему бы не встроенный список JavaScript?
Согласно тому, что мы сказали выше, связанный список имеет так много преимуществ, так почемуJavaScriptРазве в этом языке нет встроенной структуры данных, такой как связанный список?
На самом деле в JS массивы реализуют почти все функции связанных списков, так что не стоит лишний раз заморачиваться.Вы можете растеряться, услышав это.Вышесказанное не говорит о том, что производительность массивов в некоторых случаях (таких как вставка головы и т. д.) А не связанный список?
Давайте поговорим с фактами, теперь мы используем класс односвязного списка, завершенный выше.LinkedList, выполните простой тест времени с собственным массивом
let linkedList = new LinkedList()
let arr = []
// 测试 分别尝试 「总数100 插入节点50」/「总数100000 插入节点50000」
let count = 100
let insertIndex = 50
// let count = 100000
// let insertIndex = 50000
console.time('链表push操作')
for (let i = 0; i < count; i++) {
linkedList.append(i)
}
console.timeEnd('链表push操作')
console.time('数组push操作')
for (let i = 0; i < count; i++) {
arr.push(i)
}
console.timeEnd('数组push操作')
console.time('链表insert操作')
linkedList.insert('test节点', insertIndex)
console.timeEnd('链表insert操作')
console.time('数组insert操作')
arr.splice(insertIndex, 0, 'test节点')
console.timeEnd('数组insert操作')
console.time('链表remove操作')
linkedList.removeAt(insertIndex)
console.timeEnd('链表remove操作')
console.time('数组remove操作')
arr.splice(insertIndex, 1)
console.timeEnd('数组remove操作')
Давайте посмотрим на результаты
Добавить 100 данных, вставить элемент с индексом 50 и удалить вставленный элемент
Добавить 100000 данных, вставить элемент с индексом 50000 и удалить вставленный элемент
какие? ? ? ? ? ?
Из результатов теста видно, что производительность нативного массива по-прежнему подавляет связный список, независимо от того, составляет ли база всего 100 или больше 100 000.
То есть, если эффективность связанного списка выше, чем у массива, в JS его нет. Добавьте промежуточные элементы,console.timeВзгляните на время, вы обнаружите, что используемое время не имеет ничего общего с длиной массива, а это означает, что массив JS соответствует требованиям эффективности связанного списка.
И в массиве мы также можем использоватьsplice()Метод добавляет и удаляет элементы в указанную позицию массива.После тестирования требуемое время также не зависит от длины массива, и он также может удовлетворять требованиям связанного списка, а индекс массива может полностью заменить значение связанного списка.head,tail,next,prevи другие методы, и это удобнее в большинстве случаев, и сценариев использования структуры данных связного списка в работе не так уж много, поэтому можно сказать, что массивы в JS — это полностью связанные списки.
Конечно, это ограничивается только языком JavaScript, который связан с механизмом реализации внутреннего массива JS.На самом деле массив в JS просто называется массивом, что отличается от концепции массива в обычных языках. Итак, что касается концепции массива и его внутренней реализации, это не входит в рамки нашего обсуждения в этой главе.Позвольте мне сначала оставить вопрос.Я напишу еще одну статью о массивах JS, когда у меня будет время через несколько дней.На самом деле , лучше всего найти ответ самому.Мы говорим, что JS интерпретирующий тип.Язык высокого уровня, его базовая реализация не так проста, как нам кажется, следуя правилам, немного нарушая правила
Здесь вы можете жаловаться, что эта статья наконец закончена, и теперь вы говорите мне, что она бесполезна. . . Не волнуйся, убери тухлые яйца
Связанный список бесполезен в JavaScript?
Как мы сказали выше, этоJavaScriptДействительно ли связанный список в нем бесполезен?
На самом деле не так, как один из трех волшебных оружийReactсерединаFiberСтруктура использует структуру данных связанного списка
Fiberзначит на английском纤维化, то есть доработка, которая уточняет задачу. Она делит трудоемкую задачу на множество маленьких частей. Время выполнения каждой маленькой части очень короткое. Хотя общее время все еще очень велико, после выполнения каждой маленькой части, она будет передана другим задача имеет шанс на выполнение, так что единственный поток не будет монополизирован, а другие задачи все еще имеют шанс на выполнение,ReactсерединаFiberположить весьVDOMФрагментация процесса обновления
доReactсерединаrender()метод получит虚拟DOMобъект и реальный容器DOMтак как虚拟DOMОсновная функция узла монтирования после завершения рендеринга —虚拟DOMРендеринг真实DOMИ монтировать его под контейнер.Этот метод выполняет рекурсивную операцию при обновлении.Если в процессе обновления нужно обновить большое количество узлов, то основной поток JS будет занят надолго, и весь рекурсивный процесс не может быть Прервано, потому что поток JS и поток графического интерфейса являются взаимоисключающими (см. 👉«Хардкорный JS» понимает механизм работы JS одновременно), поэтому в случае большого количества обновлений вы можете увидеть некоторое отставание в интерфейсе
FiberАрхитектура фактически решает две задачи, одна — обеспечить выполнение задачи при бездействии браузера, а другая — фрагментировать задачу, о ней мы и поговорим далее.Fiber
В JS есть экспериментальный методrequestIdleCallback(callback), он может передаваться в функцию обратного вызова, а функция обратного вызова может получатьdeadlineобъект, через объектtimeRemaining()Метод может получить время простоя текущего браузера.Если время простоя есть, можно выполнить короткую задачу.Если времени недостаточно, продолжитьrequestIdleCallback, подождите, пока у браузера не будет времени простоя, а затем снова запустите его, чтобы браузер мог выполняться, когда он бездействует.
но虚拟DOMЭто древовидная структура. Когда задача прерывается, древовидная структура не может возобновить предыдущую задачу и продолжить выполнение, поэтому необходима новая структура данных, то есть наш связанный список. Связанный список может содержать несколько указателей.FiberИспользуемый связанный список содержит три указателя,parentсвоему родителюFiberузел,childУказывая на своего сынаFiberузел,siblingуказать на своего братаFiberузел, аFiberУзел соответствует узлу задачи, так что следующий узел можно легко найти, а затем можно возобновить выполнение задачи.
Этот простой абзац известенFiberАрхитектура, значит, вы говорите, что связанный список полезен?
Сказав так много, на самом деле, для обычных нужд наш JS не нуждается в использовании связанных списков, и массивы могут полностью его разнести, но в особых случаях связанные списки имеют свои определенные преимущества.Сейчас мы используем JS для объяснения связанных списки, но другие обычные языки не такие мощные, как массивы в JS, и если мы изучим связанные списки, мы будем более удобными, когда будем изучать древовидную структуру дальше.
наконец
Полный код корпуса в тексте следующий 👇
Одно- и двухсвязный список DEMO
В этой статье представлен связный список, одна из структур данных, в качестве небольшого знания перед очисткой связанного списка.
Ходить на работу хуже, чем трогать рыбу и чистить алгоритм. Байли безвреден. Придерживайтесь ежедневной чистки вопросов. Давай.
GitHub создал хранилище алгоритмов для обновления вопросов по алгоритмам/решения текстовых/видео задач с нуля, давайте вместе почистим его 👉Портал GitHub
Смотрите видеоверсию этой статьи 👉Портал станции Б
Увидев это, давайте сделаем тройку, пожалуйста, поправьте меня, если есть какие-то ошибки, и вы можете обратить внимание на паблик «Нерегулярный интерфейс», и сформировать группу с друзьями из группы алгоритма, чтобы почистить алгоритм , что эффективнее