Структуры данных
Прежде чем мы начнем наше глубокое погружение в связанные списки, важно иметь четкое представление о том, что такое структура данных. Согласно Википедии,
«структура данных — это набор значений данных, взаимосвязей между ними и функций или операций, которые можно применять к данным».
Структуры данных — это способы организации, управления и хранения данных на компьютере, чтобы к ним можно было эффективно обращаться и изменять их. Структуры данных можно найти почти во всех программах и программных системах, в которых обрабатываются данные.
Некоторые распространенные структуры данных включают массивы, стеки, очереди, хэш-таблицы, деревья, кучи и графы. Решение о том, какая структура данных лучше всего подходит для конкретного проекта, обычно зависит от типа данных, операций, которые необходимо выполнить с данными, и от того, сколько данных будет. Несмотря на то, что существует ряд структур данных на выбор, мы будем говорить конкретно о связанном списке.
Связанные списки
Теперь, когда мы поняли, что такое структура данных, давайте углубимся в связанные списки. Возвращаясь к Википедии за определением, они определяют связанные списки как
«линейный набор элементов данных, порядок которых не определяется их физическим размещением в памяти. Вместо этого каждый элемент указывает на следующий».
Что-то вроде массива, верно?
Как и массивы, связанный список представляет собой линейную структуру данных. В отличие от массивов, элементы связанного списка не хранятся в непрерывном месте; элементы связаны с помощью указателей.
В связанном списке есть несколько ключевых элементов.
- Заголовок: первый элемент в списке.
- Хвост: последний элемент в списке.
- Узел: хранит часть данных и указатель/ссылку на следующий узел.
- Ссылка: указатель, указывающий, какой элемент следующий.
*важно отметить, что голова и хвост - это не узлы, а указатели, указывающие на начало и конец списка**
Давайте разберем это с помощью аналогии.
Представьте себе поезд с несколькими вагонами, в каждой из которых находится груз.
У поезда есть ряд обязанностей, включая погрузку, разгрузку, высадку и сбор груза.
Вагон с двигателем в начале — это «головной» вагон, который будет соединяться с первым вагоном поезда.
Каждая из кареток представляет собой «узел», несущий груз (данные), и «связь» или указатель на следующую каретку.
Если бы мы стартовали в голове поезда, нам пришлось бы переходить из каждого вагона в следующий, чтобы добраться до конца поезда.
Последний вагон в поезде — это «хвост», у которого есть ссылка, указывающая ни на что (null).
Типы связанных списков
Существует 3 типа связанных списков:
- Единый связанный список
Простейший тип связанного списка, в котором каждый узел содержит некоторые данные и указатель на следующий узел того же типа данных.
2. Двойной связанный список
Мы добавляем указатель на предыдущий узел в двусвязном списке. Таким образом, мы можем двигаться в любом направлении: вперед или назад.
3. Круговой связанный список
Циклический связанный список — это вариант связанного списка, в котором последний элемент связан с первым элементом. Это образует круговую петлю.
Определения из: https://www.geeksforgeeks.org/types-of-linked-list/
Для простоты мы сосредоточимся на односвязных списках, но полезно знать и о двух других.
Основные операции
Теперь, когда мы в целом понимаем, что такое связанные списки и как они работают, давайте рассмотрим некоторые основные операции и способы их реализации с помощью Javascript.
Вставка
Вставка в конец списка
Добавление элемента в конец списка требует, чтобы вы начали с головы и прошлись по всему списку, пока не дойдете до хвостового элемента, элемента в списке, указывающего на ноль.
Если список пуст, то новый элемент будет просто установлен как элемент заголовка.
// adds an element at the end of list
add(element)
{
// creates a new node
const node = new Node(element);
// to store current node
let current;
// if list is Empty add the element and make it head
if (this.head == null)
this.head = node;
else {
current = this.head;
// iterate to the end of the list
while (current.next) {
current = current.next;
}
// add node
current.next = node;
}
}
Удаление
Удаление элемента по заданному элементу.
В этом примере мы хотим удалить определенный элемент (X) из нашего списка. Мы пройдемся по всему списку и остановимся на элементе непосредственно перед элементом, который мы хотим удалить (X — 1). Оттуда мы обновим узел X-1. > и измените его значение next на current.next.next, пропуская узел, который мы хотим удалить.
Если узел, который мы хотим удалить, является узлом head, нам нужно обязательно обновить значение заголовка, поскольку оно не может быть пустым.
// removes a given element from the list
removeElement(element) {
let current = this.head;
//if our list is empty, return null
if (head == null) return;
//if we are deleting the head element
//set the next value to be the head
if (this.head.element === element) {
head = head.next;
return;
}
//iterate over list
while (current.next !== null) {
//if the next element is our target element
//set the pointer to the element after the target element
if (current.next.element === element) {
current.next = curent.next.next;
return;
}
//otherwise, move on to the next element
current = current.next;
}
}
Посмотрите это видео от автора «Cracking The Coding Interview», Гейл Макдауэлл, где она рассказывает о кодировании этих примеров.
Существует ряд операций, которые вы можете выполнять со связанными списками, включая отображение, поиск, вставку и удаление в определенных точках индекса. Как только вы почувствуете себя более комфортно со связанными списками, полезно попробовать выполнить некоторые другие операции, чтобы закрепить свое понимание.
Почему связанные списки?
Изучив приведенные выше примеры, вы можете подумать про себя: «Связанные списки кажутся очень сложными, почему я не могу использовать массив?» Хотя массивы являются мощными структурами данных, важно понимать, что в разных ситуациях следует использовать разные структуры данных. Выбор эффективной структуры данных для хранения данных и доступа к ним может сэкономить ваше время, память и ресурсы.
Эта концепция называется вычислительной сложностью и выражается в нотации Big-O.
Cвычислительная сложность или просто сложность алгоритма — это количество ресурсов, необходимых для его выполнения. Особое внимание уделяется требованиям к времени и памяти.
Чтобы ответить на наш вопрос «почему связаны списки», мы должны сначала спросить «когда использовать связанные списки?». Глядя на приведенную ниже таблицу, мы видим, что связанные списки чрезвычайно эффективны при добавлении или удалении элементов в начало и конец списка.
Возвращаясь к нашему примеру с поездом, мы видим, что если бы мы хотели удалить головной узел, это было бы довольно просто, потому что мы знаем местоположение первого элемента. Точно так же вставка в головной узел потребует просто добавления элемента и перемещения указателя на старую головку.
Это сложность O(1), потому что независимо от того, насколько велики наши данные, это не влияет на нашу работу. Или, независимо от того, сколько вагонов в нашем поезде, это не повлияет на то, сколько времени нам потребуется, чтобы вставить или удалить (при условии, что мы знаем расположение хвоста).
Возвращаясь к таблице, мы видим, что индексация для связанных списков имеет сложность O(n). Это означает, что мы должны пройти через каждый элемент списка, чтобы выполнить действие, такое как поиск или добавление в середину нашего списка.
Поскольку все наши элементы в связанном списке связаны, мы должны проходить через них один за другим. В нашем примере с небольшим поездом 5 элементов не займут много времени и не займут много места в памяти. Однако при работе с большими наборами данных это может значительно увеличить количество ресурсов, которые нам потребуются для выполнения этой операции.
Некоторые другие ключевые преимущества связанных списков включают в себя:
- Связанные списки представляют собой динамическую структуру данных — они могут увеличиваться и уменьшаться во время выполнения путем выделения и освобождения памяти. Поэтому нет необходимости указывать начальный размер связанного списка.
- Эффективное распределение памяти/отсутствие потери памяти. В случае массива происходит много потерь памяти, например, если мы объявим массив размером 10 и сохраним в нем только 6 элементов, тогда пространство из 4 элементов будет потрачено впустую. В связном списке такой проблемы нет, так как память выделяется только тогда, когда это необходимо.
Точки, на которые ссылается Fullstack Cafe
Реальное применение связанных списков
Чтобы наглядно представить, как можно использовать связанные списки, приведем несколько примеров из реальных приложений.
Музыкальный проигрыватель
Песни в музыкальном проигрывателе — хороший пример того, как выгодно иметь связь между двумя сущностями. Когда мы нажимаем кнопки ⏪ и ⏩, мы можем вызывать song.prev и song.next, потому что они связаны друг с другом.
Слайд-шоу изображений
В слайд-шоу изображений предыдущее и следующее изображения связаны между собой, поэтому мы можем перемещаться вперед и назад и сохранять порядок слайдов.
Вывод
Поздравляем! Теперь вы знаете основы связанных списков!
Для обзора связанные списки — это «линейный набор элементов данных, порядок которых не определяется их физическим размещением в памяти. Вместо этого каждый элемент указывает на следующий».
Ключевые преимущества связанных списков:
- Связанные списки — это динамические структуры данных. Они могут увеличиваться и уменьшаться во время выполнения за счет выделения и освобождения памяти. Поэтому нет необходимости указывать начальный размер связанного списка.
- Вставка и удаление просты в реализации — в отличие от массива здесь нам не нужно сдвигать элементы после вставки или удаления элемента. В связанном списке нам просто нужно обновить адрес, присутствующий в следующем указателе узла.
- Эффективное распределение памяти/отсутствие потери памяти — в случае массива происходит много потерь памяти, например, если мы объявим массив размером 10 и сохраним в нем только 6 элементов, тогда пространство для 4 элементов будет потрачено впустую. В связанных списках такой проблемы нет, так как память выделяется только тогда, когда это необходимо.
Вопросы для интервью
Вопросы о связанных списках, как правило, возникают в интервью. Попробуйте ответить на приведенные ниже вопросы, чтобы укрепить свое понимание.
- Удалить повторяющийся элемент из отсортированного связанного списка
Дан односвязный список, состоящий из N узлов. Задача состоит в том, чтобы удалить дубликаты (узлы с повторяющимися значениями) из заданного списка (если они существуют).
"Отвечать"
2. Как бы вы перевернули односвязный список (без цикла)?
"Отвечать"
Для получения дополнительных вопросов интервью здесь больше ресурсов:
