Что такое структура данных?
Структура данных - это способ организации данных, которые хранятся на компьютере, чтобы их можно было эффективно использовать.
Связанный список, который, как следует из названия, представляет собой связанный список узлов, которые представлены заголовком, который является первым узлом в списке, и хвостом, который является последним. Каждый узел имеет ссылку / указатель на предыдущий и следующий узел.
Структура данных связанного списка имеет два типа: первый - это односвязный список, узлы этого типа имеют указатель на следующий, но не на свой предыдущий узел.
В этой статье мы собираемся изучить двусвязный список , в котором узлы имеют следующий и предыдущий указатели (голова имеет следующий указатель, но не предыдущий, а хвостовой узел имеет предыдущий указатель, но не следующий).
Преимущества:
Хотя связанный список похож на массив, он не ограничивается объявленным количеством элементов. Кроме того, в отличие от массива, который хранит данные непрерывно в памяти или на диске, связанный список может легко вставлять или удалять элементы без перераспределения или реорганизации всей структуры, поскольку элементы данных не должны храниться непрерывно.
Недостатки связанного списка:
1) Произвольный доступ не разрешен. Мы должны обращаться к узлам последовательно, начиная с первого. Следовательно, мы не можем выполнять двоичный поиск в связанном списке. Таким образом, поисковый элемент выполняется медленно.
2) Для каждого элемента списка требуется дополнительное место в памяти для ссылки.
Структура данных связанный список часто используется для реализации других структур данных.
В этой статье мы рассмотрим структуру данных связанного списка.
Итак, мы собираемся создать наши две функции-конструкторы:
function LinkedList() {
this.head = null;
this.tail = null;
}
function Node(value, next, prev) {
this.value = value;
this.next = next;
this.prev = prev;
}
Как видите, мы представляем образец изображения в нашем конструкторе. Наша функция LinkedList имеет head и tail, и почему они равны нулю? Потому что вначале нет узла.
Итак, теперь мы собираемся создать наш метод addToTail.
Создание головных узлов
LinkedList.prototype.addToHead = function(value) {
const newNode = new Node(value, this.head, null);
if (this.head) this.head.prev = newNode;
else this.tail = newNode;
this.head = newNode;
};
Как видите, мы создали метод внутри прототипа LinkedList, почему? что ж, эта техника полезна, потому что мы собираемся создать много объектов, и если бы мы не создали наши методы в прототипе, мы бы дублировали все методы для каждого объекта, что означало бы расход памяти, который может быть вредным.
Давайте рассмотрим каждую строку
const newNode = new Node(value, this.head, null); Это будет хранить в переменной newNode новый объект Node. value будет значением, которое мы передаем в методе addToHead, this.head сначала имеет значение NULL, поэтому свойство next имеет значение NULL, а атрибут prev будет иметь значение NULL, потому что мы передаем его в третьем параметре.
if (this.head) this.head.prev = newNode; Хорошо, эта строка означает, что если существует узел head, их предыдущим значением будет newNode (то есть новый заголовок). если узла нет, фактический узел, который мы создаем, будет головой, а также хвостом, как мы видели в примере изображения ТРЕТЬЕ.
Итак, если мы теперь создадим, например, два узла:
const list = new LinkedList(); list.addToHead(100); list.addToHead(200); console.log(list);
У нас будет такой вывод:
Головной узел имеет value 200, свойство next - это хвостовой объект (следующий в списке), и нет объекта prev, потому что head первый.
А теперь представьте себе это:
const otherlist = new LinkedList(); otherlist.addToHead(100); otherlist.addToHead(200); otherlist.addToHead(300); console.log(otherlist);
Результатом будет:
Или что-то вроде этого:
Итак, если вы хотите, чтобы он имел доступ к среднему узлу, вы можете сделать это:
console.log(`Middle node value: ${otherlist.head.next.value}`);
Помните, что метод addToHead добавляет узел в начало, тогда единственное, что вам нужно сделать, это разложить объект в консоли!
Попробуйте!
Итак, теперь мы собираемся создать наш метод addToTail.
Создание хвостовых узлов
Фактически, этот метод почти такой же, как и в примере addToHead.
LinkedList.prototype.addToTail = function(value) {
const newNode = new Node(value, null, this.tail);
if (this.tail) this.tail.next = newNode;
else this.head = newNode;
this.tail = newNode;
}
Используйте ту же логику, что и в последнем примере, суть аналогична, только с использованием обратной логики.
Итак, теперь, если мы сделаем тот же пример, что и в методе addToHead:
const list = new LinkedList(); list.addToTail(100); list.addToTail(200); list.addToTail(300); console.log(list);
Теперь последним добавленным будет Хвост (последний), в отличие от другого метода, в котором последняя запись была добавлена как первый узел (Голова).
Или вот так:
Тестирование обоих методов:
const list = new LinkedList(); list.addToHead(1); list.addToTail(2); console.log(list);
Удаление узлов
Представьте, что у нас есть такие узлы:
const list = new LinkedList(); list.addToHead(200); list.addToHead(100); // remember this is the head now! list.addToTail(300); console.log(list);
Метод удаления головных узлов:
LinkedList.prototype.removeHead = function() {
if (!this.head) return null;
let value = this.head.value;
this.head = this.head.next;
if (this.head) this.head.prev = null;
else this.tail = null;
return value;
}
Не видите, первая строка будет проверять, существует ли какой-либо заголовок, если не вернет null. Затем мы сохраняем значение головного узла и устанавливаем новый головной узел с этой строкой: this.head = this.head.next; Итак, на данный момент у нас есть это:
И в последних строках кода мы просто повторно устанавливаем prev на null, потому что новый заголовок не должен иметь значения prev (потому что это первый узел).
Возвращает значение удаления.
Метод удаления хвостовых узлов:
LinkedList.prototype.removeTail = function() {
if (!this.tail) return null;
let value = this.tail.value;
this.tail = this.tail.prev;
if (this.tail) this.tail.next = null;
else this.head = null;
return value;
}
Применяет ту же логику для этого метода, потому что он такой же, но с противоположным эффектом.
Поиск узлов:
LinkedList.prototype.search = function(searchValue) {
let currentNode = this.head;
while(currentNode) {
if (currentNode.value === searchValue) return currentNode;
currentNode = currentNode.next;
}
return null;
}
Итак, здесь мы сохраняем в переменной currentNode значение this.head, затем пока currentNode не undefined, мы сравниваем, существует ли node с значением, которое мы передаем, в противном случае мы вернем null.
Итак, если у нас есть это:
const list = new LinkedList(); list.addToHead(1); list.addToTail(2); console.log(list.search(1)); // true console.log(list.search(2)); // true console.log(list.search(3000)); // false
Результатом будет:
Надеюсь, вам понравилось!
Полный код: https://github.com/germancutraro/LinkedList-Data-Structure
У вас есть мой Github, если вы хотите подписаться на меня, я буду очень признателен!
Благодаря SoloLearn фантастическое приложение!
Отличные курсы для изучения структур данных и алгоритмов:
◾ Изучение структур данных в JavaScript с нуля
◾ Учебный курс на собеседовании по кодированию: алгоритмы + структуры данных
Спасибо 😊
