Итак, расскажите мне о связанных списках
Недавно окончив курс для начинающих по кодированию, я глубоко изучил структуры данных и алгоритмы, чтобы улучшить свои фундаментальные знания. Связанные списки представляют собой относительно простую структуру данных, но они являются основой для дальнейшего развития более сложных структур данных. В этой статье мы обсудим связанные списки - их сильные и слабые стороны и способы их реализации.
Проще говоря, структуры данных - это способы организации и эффективного хранения данных.
Что такое структуры данных?
Проще говоря, структуры данных - это способы организации и эффективного хранения данных. Они позволяют нам хранить информацию, чтобы мы могли получить к ней доступ в дальнейшем - поиск определенного элемента или сортировку по определенному порядку или даже управление большими наборами данных. В JavaScript есть структуры данных, с которыми вы, вероятно, очень хорошо знакомы - массивы и объекты. Это примитивные структуры данных, родные для языка. Непримитивные структуры данных - это структуры данных, определяемые программистом. Примеры включают стеки, очереди, деревья, графики и хеш-таблицы.
Что такое связанные списки?
Связанный список - это линейная структура данных, содержащая элементы в последовательном порядке. Звучит знакомо? Они похожи на массивы, но не совсем то же самое. Массивы имеют нулевой индекс , то есть каждый индекс сопоставляется со значением, а первый элемент массива начинается с индекса 0. Вы можете легко извлекать элементы из массива, если вам известен индекс.
С другой стороны, связанный список состоит из узлов, которые указывают на другие узлы. Каждый узел знает только себя и следующий узел. В линейной структуре данных элементы расположены по порядку. Вы можете думать об этом как о поезде - каждый железнодорожный вагон соединен с другим железнодорожным вагоном и так далее. Связанные списки не индексируются , поэтому вы не можете напрямую получить доступ к 5-му элементу. Вам нужно будет начать с начала, перейти к следующему и перейти к следующему, пока не найдете 5-й элемент. Первый узел называется головой, а последний узел - хвостом. Существуют различные типы связанных списков - односвязный список, двусвязный список и кольцевой связанный список. В этой статье я сосредоточусь на односвязном списке.
Доступ к элементам во всем массиве проще, но за это приходится платить.
Зачем использовать связанные списки вместо массивов?
Вам может быть интересно, но зачем это использовать, если я могу получить доступ к элементам напрямую с помощью массивов? Это правда! Доступ к элементам во всем массиве проще, но за это приходится платить.
Массивы индексируются, поэтому всякий раз, когда вам нужно удалить элемент с начала или с середины, необходимо сдвинуть все следующие индексы. Это также верно, если вам нужно вставить элемент - все следующие элементы необходимо переиндексировать. При вставке или удалении элементов из связанного списка вам не нужно переиндексировать - все, о чем он заботится, это узел, на который он указывает .
Реализация односвязного списка
Существуют различные типы связанных списков - одиночные, двойные и кольцевые. Односвязные списки - это тип связного списка, в котором каждый узел имеет значение и указатель на следующий узел (ноль, если это хвостовой узел). С другой стороны, двусвязные списки имеют дополнительный указатель на предыдущий узел. В списках с круговой связью хвостовой узел указывает на головной.
Примечание. Если вы визуально обучаетесь , VisuAlgo - отличное место, чтобы поиграть и увидеть, как структура данных претерпевает изменения.
Если вы хотите пропустить полный код: ознакомьтесь с этой статьей на GitHub .
Создание узла
Начнем с создания узла для использования. У него будет значение и следующий указатель, который укажет на его последующего соседа.
class Node {
constructor(val) {
this.val = val;
this.next = null;
}
}
Мы начнем с создания класса SinglyLinkedList и дадим ему основу для заголовка, хвоста и длины списка.
class SinglyLinkedList {
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
}
Чтобы добавить узел в конец, мы проверим, есть ли уже объявленная в списке голова. Если нет, установите голову и хвост как вновь созданный узел. Если свойство head уже существует, установите следующее свойство в хвосте для нового узла, а свойство tail в качестве нового узла. Мы увеличим длину на 1.
push(val) {
var newNode = new Node(val)
if (!this.head) {
this.head = newNode
this.tail = newNode
} else {
this.tail.next = newNode
this.tail = newNode
}
this.length++;
return this;
}
Чтобы удалить узел в конце, мы должны сначала проверить, есть ли узлы в списке. Если есть узлы, то мы должны пройти по списку, пока не дойдем до хвоста. Мы установим следующее свойство предпоследнего узла равным нулю, установим свойство tail для этого узла, уменьшим длину на 1 и вернем значение удаленного узла.
pop() {
if (!this.head) return undefined;
var current = this.head
var newTail = current
while (current.next) {
newTail = current
current = current.next;
}
this.tail = newTail;
this.tail.next = null;
this.length--;
if (this.length === 0) {
this.head = null;
this.tail = null;
}
return current;
}
Чтобы удалить узел с самого начала, мы проверяем, есть ли узлы в списке. Мы сохраним текущее свойство головы в переменной и установим головку в качестве следующего узла текущей головы. Уменьшите длину на 1 и верните значение удаленного узла.
shift() {
if (!this.head) return undefined
var oldHead = this.head;
this.head = oldHead.next;
this.length--
if (this.length===0) {
this.head = null;
this.tail = null;
}
return oldHead
}
Чтобы добавить узел в начало, мы сначала создаем узел и проверяем, есть ли в списке свойство head. Если это так, установите следующее свойство вновь созданного узла на текущий заголовок, установите заголовок на новый узел и увеличьте длину.
unshift(val) {
var newNode = new Node(val)
if (!this.head) {
this.head = newNode;
this.tail = newNode;
} else {
newNode.next = this.head;
this.head = newNode;
}
this.length++
return this
}
Чтобы получить доступ к узлу на основе его позиции в списке, мы сначала проверим, является ли индекс допустимым. После этого мы пройдемся по списку, сохраняя при этом переменную счетчика. Как только переменная счетчика соответствует индексу, мы вернем найденный узел
get(idx) {
if (idx < 0 || idx >= this.length) return null
var counter = 0;
var current = this.head
while (counter !== idx) {
current = current.next;
counter++;
}
return current;
}
Чтобы изменить узел в зависимости от его положения, мы сначала находим узел, используя метод get, и устанавливаем новое значение.
set(idx, val) {
var foundNode = this.get(idx)
if (foundNode) {
foundNode.val = val
return true;
}
return false;
}
Чтобы вставить узел, мы сначала проверяем индекс. Если он равен 0, мы используем наш метод unshift. Если он равен длине, мы помещаем его в список. В противном случае мы получим узел before, используя метод get на единицу меньше индекса. По сути, нам нужно отслеживать узел до и после выбранного индекса, чтобы наши указатели были направлены на правильный узел.
insert(idx, val) {
if (idx < 0 || idx > this.length) return false;
if (idx === 0) {
this.unshift(val)
return true;
};
if (idx === this.length) {
this.push(val);
return true;
};
var newNode = new Node(val);
var beforeNode = this.get(idx-1);
var afterNode = beforeNode.next;
beforeNode.next = newNode;
newNode.next = afterNode;
this.length++;
return true;
}
Чтобы удалить узел на основе позиции, мы снова будем использовать наш метод get и использовать тот же принцип, который мы использовали для вставки узла. Отслеживая узел, предшествующий выбранному индексу, мы можем перемещать наши указатели.
remove(idx) {
if (idx < 0 || idx > this.length) return undefined;
if (idx === this.length-1) {
this.pop()
}
if (idx === 0) {
this.shift()
}
var prevNode = this.get(idx-1)
var removeNode = prevNode.next
prevNode.next = removeNode.next
this.length--;
return removeNode;
}
Сильные стороны связанных списков
Преимущество использования связанного списка - возможность быстро вставлять и удалять элементы. Поскольку связанные списки не индексируются, вставка элементов выполняется относительно быстро и легко.
Добавление в конец связанного списка просто требует, чтобы старый хвост указывал на новый узел, а свойство хвоста было установлено на новый узел. Добавление в начало связанного списка - та же предпосылка, но новый узел указывает на старую голову, а свойство head устанавливается на новый узел. Принципиально те же действия, поэтому вставка выполняется за O (1).
Примечание. Для вставки в середину связанного списка требуется выполнить поиск, чтобы найти ваш узел (O (N)), а затем вставить узел (O (1)).
Удалить узел из связанного списка может быть легко… но тоже нет. Это зависит от того, где. Удалить узел из начала списка очень просто - второй узел становится новым заголовком, и мы устанавливаем следующий указатель старого заголовка на нуль. Удаление с конца сложнее, потому что для этого нужно пройти весь список и остановиться на предпоследнем узле. В худшем случае O (N) и в лучшем случае O (1).
Слабые стороны связанных списков
Слабые стороны связного списка вызваны отсутствием переиндексации. Поскольку вы не можете получить доступ к элементам напрямую, это затрудняет поиск и доступ к элементам.
Для поиска и доступа к узлу в связанном списке необходимо начать с начала списка и следовать по цепочке хлебных крошек вниз по списку. Если мы ищем узел в конце списка, нам придется пройти через весь связанный список, фактически сделав временную сложность O (N). По мере роста списка растет количество операций. По сравнению с массивом с произвольным доступом - для доступа к элементу требуется постоянное время.
Это оно!
Связанные списки - отличная альтернатива массивам, когда вставка и удаление в начале являются ключевыми действиями. Массивы индексируются, а связанные списки - нет. Связанные списки также являются базовой структурой данных, на основе которой строятся стеки и очереди, о которых я расскажу в следующей статье. Если вы прошли здесь весь путь, слава вам, и я надеюсь, что вы научились маленькому самородку вместе с вашим путешествием по программированию!
