Односвязные списки — это тип структуры данных, в которой значения хранятся в виде списка. В списке каждое значение считается узлом, и каждый узел связан со следующим значением в списке (или нулевым, если элемент является последним в списке) через указатель.
Первый элемент списка считается головным, а последний — хвостовым. Как и в случае с массивами, свойство длины определяется как количество элементов, содержащихся в списке.
Основные отличия от массивов следующие:
- Списки не имеют индексов. Каждое значение «знает» только значения, с которыми оно связано через указатели.
- Поскольку у списков нет индексов, мы не можем получить доступ к значениям случайным образом. Когда мы хотим получить доступ к значению, нам всегда приходится искать его, перебирая список, начиная с его головы или хвоста.
- Преимущество отсутствия индексов в том, что вставка/удаление в любой части списка более эффективна, чем с массивами. Нам остается только перенаправить указатели «соседних» значений, а в массивах или более поздних значениях нужно переиндексировать.
Как и в любой структуре данных, в ней реализованы различные методы для работы с данными. Наиболее распространенные из них включают в себя: push, pop, unshift, shift, get, set, insert, remove и reverse.
Толкать()
- Функция, которая принимает значение в качестве входных данных и создает с ним новый узел.
- Если головы нет (пустой список), он назначит новый узел как голову и хвост.
- Если список не пуст, он назначает новый узел хвостом и соединяет предыдущую голову с новым узлом с помощью указателя «следующий».
- Он увеличивает свойство length на единицу и возвращает список с добавленным элементом.
Возможная реализация может быть следующей:
push(val){
var newNode = new Node(val);
if(!this.head){
this.head = newNode;
this.tail = this.head;
} else {
this.tail.next = newNode;
this.tail = newNode;
}
this.length++;
return this;
}Поп()
- Функция, которая стирает последнее значение (хвост) списка.
- Если список пуст, он возвращает undefined.
- Он проходит по списку, пока не достигает хвоста и не стирает его.
- Он изменяет указатель предыдущего значения, чтобы он указывал на ноль, и присваивает предыдущее значение хвосту.
- Он уменьшает свойство длины на единицу и возвращает стертый элемент.
Возможная реализация может быть следующей:
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;}
отменить сдвиг ()
- Функция, которая принимает значение и добавляет его в начало списка.
- Если головы нет (пустой список), он назначит новый узел как голову и хвост.
- Если список не пуст, новый узел назначается головным.
Возможная реализация может быть следующей:
unshift(val){
var newNode = new Node(val);
if(!this.head) {
this.head = newNode;
this.tail = this.head;
} else {
newNode.next = this.head;
this.head = newNode;
}
this.length++;
return this;
}Сдвиг()
- Функция, которая стирает первое значение (заголовок) списка.
- Если список пуст, он возвращает undefined.
- Он присваивает свойству head следующее значение, уменьшает свойство length на единицу и возвращает стертое значение элемента.
Возможная реализация может быть следующей:
shift(){
if(!this.head) return undefined;
var currentHead = this.head;
this.head = currentHead.next;
this.length--;
if(this.length === 0){
this.tail = null;
}
return currentHead;
}получить()
- Функция, которая принимает число (индекс или позицию) и извлекает узел с заданной позицией в списке.
- Если индекс меньше нуля или больше или равен длине списка, он возвращает значение null.
- В противном случае он перебирает список до тех пор, пока не будет достигнут заданный индекс и не вернет это значение.
Возможная реализация может быть следующей:
get(index){
if(index < 0 || index >= this.length) return null;
var counter = 0;
var current = this.head;
while(counter !== index){
current = current.next;
counter++;
}
return current;
}набор()
- Функция, которая принимает число (индекс или позицию) и значение и изменяет значение узла с заданной позицией в списке.
- Если значение не найдено, возвращается false. В противном случае, если операция завершена, она возвращает true.
Возможная реализация может быть следующей:
set(index, val){
var foundNode = this.get(index);
if(foundNode){
foundNode.val = val;
return true;
}
return false;
}вставлять()
- Функция, которая принимает число (индекс или позицию) и значение и вставляет значение как новый узел с заданной позицией в списке.
- Если значение меньше нуля или больше длины списка, вернуть undefined.
- Если индекс совпадает с длиной, добавьте новый узел в список. Если индекс равен нулю, снимите новый узел.
- В противном случае, используя метод get, мы получаем доступ к узлу, предшествующему позиции, в которую мы хотим ввести новый узел, и перенаправляем его указатель на новый узел. Направляем указатель нового узла на следующий по порядку узел.
- Увеличьте длину списка и верните true.
Возможная реализация может быть следующей:
if(index < 0 || index > this.length) return false; if(index === this.length) return !!this.push(val); if(index === 0) return !!this.unshift(val);var newNode = new Node(val); var prev = this.get(index - 1); var temp = prev.next; prev.next = newNode; newNode.next = temp; this.length++; return true;
Удалить()
- Функция, которая принимает число (индекс или позицию), удаляет узел с заданной позицией в списке.
- Если значение меньше нуля или больше длины списка, вернуть undefined.
- Если индекс совпадает с длиной, извлеките последний элемент. Если индекс равен нулю, сдвиньте первый элемент.
- В противном случае, используя метод get, мы получаем доступ к узлу, предшествующему позиции, которую мы хотим удалить, и перенаправляем его указатель на узел, следующий за тем, который мы хотим удалить.
- Уменьшите длину списка и верните значение стертого узла.
Возможная реализация может быть следующей:
if(index < 0 || index >= this.length) return undefined;
if(index === 0) return this.shift();
if(index === this.length - 1) return this.pop();
var previousNode = this.get(index - 1);
var removed = previousNode.next;
previousNode.next = removed.next;
this.length--;
return removed;обеспечить регресс()
- Функция, которая меняет порядок списка на противоположный.
- Меняет голову и хвост.
- Создает переменные с именами next и prev.
- Создает переменную с именем node и инициализирует ее свойством head.
- Затем выполните цикл по списку и: 1) Установите следующую переменную в качестве следующего свойства на любом узле цикла. 2) Установите следующее свойство на узле таким же, как и предыдущее. 3) Установите prev в качестве значения переменной узла. 4) Установите переменную узла в качестве значения следующей переменной.
- После завершения цикла верните список.
Возможная реализация может быть следующей:
var node = this.head;
this.head = this.tail;
this.tail = node;
var next;
var prev = null;
for(var i = 0; i < this.length; i++){
next = node.next;
node.next = prev;
prev = node;
node = next;
}
return this;Полная реализация односвязного списка может быть следующей:
class Node{ constructor(val){ this.val = val; this.next = null; } }class SinglyLinkedList{ constructor(){ this.head = null; this.tail = null; this.length = 0; } push(val){ var newNode = new Node(val); if(!this.head){ this.head = newNode; this.tail = this.head; } else { this.tail.next = newNode; this.tail = newNode; } this.length++; return this; } 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; } shift(){ if(!this.head) return undefined; var currentHead = this.head; this.head = currentHead.next; this.length--; if(this.length === 0){ this.tail = null; } return currentHead; } unshift(val){ var newNode = new Node(val); if(!this.head) { this.head = newNode; this.tail = this.head; } newNode.next = this.head; this.head = newNode; this.length++; return this; } get(index){ if(index < 0 || index >= this.length) return null; var counter = 0; var current = this.head; while(counter !== index){ current = current.next; counter++; } return current; } set(index, val){ var foundNode = this.get(index); if(foundNode){ foundNode.val = val; return true; } return false; } insert(index, val){ if(index < 0 || index > this.length) return false; if(index === this.length) return !!this.push(val); if(index === 0) return !!this.unshift(val);var newNode = new Node(val); var prev = this.get(index - 1); var temp = prev.next; prev.next = newNode; newNode.next = temp; this.length++; return true; } remove(index){ if(index < 0 || index >= this.length) return undefined; if(index === 0) return this.shift(); if(index === this.length - 1) return this.pop(); var previousNode = this.get(index - 1); var removed = previousNode.next; previousNode.next = removed.next; this.length--; return removed; } reverse(){ var node = this.head; this.head = this.tail; this.tail = node; var next; var prev = null; for(var i = 0; i < this.length; i++){ next = node.next; node.next = prev; prev = node; node = next; } return this; } print(){ var arr = []; var current = this.head while(current){ arr.push(current.val) current = current.next } console.log(arr); } }
Сложность
Функции односвязных списков имеют следующие сложности:
- Вставка — О(1)
- Удаление — O(n)
- Поиск по)
- Доступ — O(n)
