Все о структуре данных связанного списка в JavaScript.
Связанные списки, вероятно, самые простые и распространенные списки. Он настолько мощный, что его можно использовать для реализации других списков, таких как очередь, стек, ассоциативные массивы и т. Д. Он позволяет легко вставлять и удалять элементы, и это, безусловно, одна из структур данных, которую стоит изучить перед тем, как погрузиться в дерево или графические структуры данных.
Видеоверсия этой статьи
Этот пост представляет собой улучшенную и более подробную версию статьи из серии Структура данных связанного списка на Youtube, которую вы можете проверить, предпочитаете ли вы видео.
Что такое связанный список?
Связанный список - это линейная структура данных. Это набор элементов, порядок которых не определяется их физическим размещением в памяти. Каждый элемент указывает на другой, чтобы указать, какой элемент будет следующим и / или до, и вместе они образуют последовательность данных.
Его можно использовать для реализации других структур данных, в чем вы можете убедиться, просмотрев статью о структурах данных очередей и стека в этой серии. Это может быть суперэффективным при вставке и удалении элементов, поскольку вам не нужно для этого изменять список, поскольку все, что вам нужно сделать, это изменить несколько указателей элементов, чтобы удалить или добавить новый элемент. Посмотрим, как это сделать позже.
Некоторые из его недостатков заключаются в используемой памяти. Все элементы также должны включать информацию указателя, чтобы указать, какой элемент идет следующим или раньше вместе с данными. Также нет произвольного доступа. Это означает, что если я хочу прочитать 5-й элемент, вы должны начать с начала - с головы - и перейти к 5-му элементу, чтобы прочитать его.
Если это односвязный список, вы можете перемещаться только в одном направлении. Делая это вдвойне, вам нужно больше памяти для хранения обратного указателя, и это дает вам возможность перемещаться в обоих направлениях, что позволяет выполнять еще более быстрое удаление и вставку. Есть также дополнительная работа, чтобы изменить или отсортировать этот список, но это очень увлекательный процесс, в который я буду погружаться позже.
Когда использовать связанный список?
Связанные списки отлично подходят, когда операций чтения не так много или операция чтения обычно выполняется для всего списка путем обхода, а не отдельных элементов. Для произвольного доступа к элементам лучше использовать массив. Эта способность быстро вставлять и удалять элементы делает его отличным для вычислений в реальном времени, поскольку вставка / удаление выполняется постоянно, что делает его более предсказуемым.
Хорошими приложениями, которые извлекают большую пользу из этой структуры данных, может быть, например, ваш музыкальный проигрыватель. Ваш просмотрщик изображений или даже навигация по истории браузера. Эти типы списков могут содержать длинный список элементов и не требуют произвольного доступа после того, как вы представляете все элементы пользователю. В общем, если вам не нужен произвольный доступ и вы не читаете постоянно отдельные элементы, любое приложение, использующее список, может извлечь выгоду из связанных списков.
Связанный список против массива
Разработчики более знакомы с массивами, и, вероятно, это список, который можно использовать в приложениях, но есть много приложений, которые работают медленно из-за неправильного использования списка. Связанный список лучше, если массив плохой, а массив лучше, когда связанный список плохой. Они компенсируют друг друга, и хорошо знать, когда использовать какие.
Элементы массива индексируются и постоянно хранятся в памяти, что означает, что если я знаю, где начинается список и индекс, я могу быстро захватить элемент в этой позиции.
Если я хочу добавить или удалить элемент, мне, возможно, придется переместить небольшую или большую часть списка. Вот почему время доступа к массиву велико, но добавление и удаление элементов происходит медленно.
В связанном списке элементы могут находиться где угодно в памяти, и то, что их связывает, - это их указатели, указывающие, какие элементы будут следующими и / или раньше.
Чтобы вставить или удалить элемент, вам просто нужно обновить указатель элементов до и после. Если ни один элемент не указывает на элемент, он не является частью последовательности. Такой характер указателя делает вставку и удаление быстрыми, поскольку вам не нужно обновлять позицию остальной части списка. Представьте, если бы в списке было 1 миллион пунктов.
Это также удорожает прямой доступ к элементу. Поиск элемента в связанном списке - это то же самое, что и поиск сокровищ. Одна подсказка ведет к другой, и в этом случае элемент может только сказать вам, что будет дальше или раньше, и вы идете оттуда. Доступ к массиву быстрее.
Итак, когда использовать? Если вы много удаляете и добавляете элементы, используйте связанный список. Если вы много читаете и обращаетесь к данным, используйте массив.
Реализация единого связанного списка
Единый связанный список - это список, в котором все элементы имеют один указатель. Обычно все они имеют указатель «следующий», чтобы указать, какой элемент будет следующим. Это хорошо, когда ты знаешь, что идешь идти только в одном направлении. Например, стек может быть реализован с помощью одного связного списка.
Давайте определим класс «LinkedList» со свойством для отслеживания размера и сохранения элемента заголовка, первого элемента. Нам нужно сохранить частный размер, чтобы его можно было обновлять только внутри, и сделать его доступным только для чтения.
class LinkedList {
#size = 0;
head = null;
get size() {
return this.#size;
}
createElement(value) {
return {value, next: null}
}
...
Нам также нужен метод «createElement», который принимает значение добавляемого элемента и включает следующий указатель, который мы обновим позже.
Первый метод, который нам нужен для этого, - это метод «push» для добавления элемента в конец списка.
push(item) {
const element = this.createElement(item);
// handle the first item
if(this.head === null) {
this.head = element;
} else {
let current = this.head;
while (current.next !== null) {
current = current.next;
}
current.next = element;
}
this.#size += 1;
return this.size;
}
Метод проталкивания очень прост. Сначала мы создаем наш элемент с элементом, с которым был вызван «push». Если заголовок равен нулю, это означает, что список получает свой первый элемент, поэтому этот новый элемент становится элементом заголовка. Если в списке есть элементы, нам нужно найти последний элемент, выполняя цикл, начиная с головы, пока указатель «следующий» не равен нулю.
Последний элемент будет иметь нулевое значение «следующий», поскольку у него не будет ни одного элемента, на который можно было бы указать. После завершения метод push вернет размер.
Нам также необходимо иметь возможность вставлять элементы в определенную позицию, и для этого нам нужен метод «вставки». Потребуется элемент для вставки и позиция для вставки.
insert(item, index = 0) {
// quit if index is out of bound
if (index < 0 || index > this.size) return;
const element = this.createElement(item);
// if inserting at start replace head
if (index === 0) {
element.next = this.head;
this.head = element;
} else {
let previous = this.head;
for(let i = 0; i < index - 1; i++) {
previous = previous.next;
}
element.next = previous.next;
previous.next = element;
}
this.size += 1;
return this.size;
}
Метод вставки начинается с преждевременного выхода, если позиция выходит за границы. Он либо ниже нуля, либо выше следующего пустого индекса. Для простоты он также отсчитывается от нуля, как и массив.
Если новый элемент должен идти в начале, мы делаем так, чтобы новый элемент указывал на элемент head - поскольку он идет раньше - а затем устанавливаем новый элемент как элемент head.
Чтобы установить его в любом месте в середине списка, нам нужно выполнить итерацию до элемента перед позицией, в которой мы хотим его установить. Вот почему цикл до индекса минус один. Мы захватываем этот элемент в этой позиции как «предыдущий», заставляем его указывать на наш элемент и заставляем наш элемент указывать на элемент, на который указывал «предыдущий». Затем увеличиваем размер и возвращаем его.
Теперь, чтобы удалить элемент из списка, нам нужно будет найти его, а затем разорвать связь, соединив предыдущий и следующий элемент. Этот процесс просто заставляет элементы до и после того, что мы удаляем, указывать друг на друга.
remove(index = 0) {
if (index < 0 || index > this.size) return null;
let removedElement = this.head;
if (index === 0) {
this.head = this.head.next;
} else {
let previous = this.head;
for(let i = 0; i < index - 1; i++) {
previous = previous.next;
}
removedElement = previous.next;
previous.next = removedElement.next;
}
this.#size -= 1;
return removedElement.value;
}
Нам нужно отслеживать удаляемый элемент и начинать с элемента head. Если первый элемент должен быть удален, это означает, что следующий элемент становится заголовком, в противном случае мы делаем что-то похожее на то, что мы вставляли, чтобы найти элемент, который стоит перед тем, который мы хотим.
Как только мы находим этот элемент, мы заставляем его указывать на элемент, на который указывает элемент, который мы хотим удалить. В конце мы уменьшаем размер и возвращаем значение элемента.
Также было бы неплохо иметь возможность получить элемент из списка, что является более быстрой операцией для массивов, но имеет смысл использовать в связанном списке. Он просто переходит в нужную позицию и захватывает элемент. Он возвращает null, если индекс ниже нуля (недопустимый индекс) или равен или больше размера списка (вне досягаемости).
get(index = -1) {
if (index < 0 || index >= this.size) return null;
let element = this.head;
for(let i = 0; i < index; i++) {
element = element.next;
}
return element.value;
}
Как и в случае с любым списком, было бы неплохо иметь возможность перебирать его. Мы можем добавить такой метод, как forEach, или сделать весь класс LinkedList итеративным, введя концепцию итератора, который представляет собой шаблон проектирования, о котором стоит изучить. Давай попробуем и то, и другое.
forEach(cb) {
let current = this.head;
let index = 0;
while(current) {
cb(current.value, index);
current = current.next;
index += 1;
}
}
// usage
list.forEach((v, i) => console.log('item', v, i))
«forEach» дает нам доступ к элементам и их индексу через обратный вызов, но итератор позволяет нам делать гораздо больше, включая возможность легко преобразовывать связанный список в массив. Чтобы сделать список повторяемым, мы можем добавить итератор, используя функцию генератора в конструкторе.
constructor() {
this[Symbol.iterator] = function* () {
let current = this.head;
while(current) {
yield current.value;
current = current.next;
}
};
}
// usage
const list = new LinkedList();
// use in for loops
for(const item of list) {
console.log(item)
}
// change it into an array
[...list]
Array.from(list)
Примечание. Вы всегда можете зациклить список, используя «головной» узел без специальных методов. Эти стратегии зацикливания просто приятно иметь, и я предпочитаю ярлык.
Мы также можем добавить более мощные методы, чтобы иметь возможность узнать, есть ли элемент в списке и в какой позиции он находится. Для этого мы можем добавить в список методы «find» и «indexOf».
find(cb) {
let current = this.head;
let result = null;
while(current) {
const matched = cb(current.value);
if(matched) {
result = current;
break;
}
current = current.next;
}
return result?.value ?? null;
}
indexOf(item) {
let current = this.head;
if (current.value === item) return 0;
for(let i = 0; i < this.size; i++) {
if (current.value === item) return i;
current = current.next;
}
return -1;
}
Метод find зациклит список из заголовка и прервет его, как только обратный вызов вернет значение «правдиво», а затем вернет это значение. «indexOf» также выполнит цикл и вернет индекс, как только элемент будет соответствовать любому значению элемента в списке.
Как видите, работа со связанным списком дает вам полный контроль над списком, где вы можете вводить новые методы, если хотите найти удобный способ работы с ним. Это также отличный способ узнать, как реализуются потенциальные алгоритмы Array, которые стоят каждой строчки кода.
Исходный код: Проверьте этот полный код на Github
Следующий
Прочтите следующую часть этой статьи, где вы узнаете о как создать двойной и отсортированный связанный список.
Канал YouTube: До точки с запятой
Веб-сайт: beforesemicolon.com
Больше контента на plainenglish.io
