Привет всем, это часть 5.2 из серии блогов о структурах данных и алгоритмах в JavaScript. В предыдущем блоге я рассмотрел push, insert и связанного списка. em>getElementAt методы. Здесь я расскажу об оставшихся методах removeAt, remove и indexOf.
Реализация связанного списка в Javascript
Индекс чего-либо
Этот метод вернет индекс данного элемента, если он существует, иначе вернет -1 ({4}). Чтобы найти индекс элемента, мы начнем с главного элемента ({1}) и будем выполнять цикл до тех пор, пока элемент не будет найден ({2}) и возвращает его индекс ({3}) .
indexOf(element) {
let current = this.head; //1
for (let index = 0; index < this.count && current != null; index++) {
if (current.element == element) { //2
return index;
}
current = current.next; //3
}
return -1; //4
}
RemoveAt
Удаляем элемент по указанному индексу, мы сначала проверяем, является ли связанный список пустым, иначе возвращаем undefined ({1}). После этого мы проверяем ошибку индекса за пределами границы , по проверке - это индекс, который больше нуля и меньше count.
- Мы хотим удалить первый элемент, т.е. индекс, равный нулю ({2}), сдвинуть голову к следующему узлу. Мы будем ссылаться на первый элемент списка, используя текущую переменную. Если мы назначим заголовок текущему следующему элементу, мы удалим первый элемент ({3}).
- Мы хотим удалить последний элемент или элемент из связанного списка, мы будем использовать метод getElementAt, чтобы получить один предыдущий элемент, используя индекс -1 ({4}), текущий будет следующим ({5}) предыдущего. Итак, чтобы удалить текущий узел, все, что нам нужно сделать, это связать previous.next с current.next ({6}).
removeAt(index) {
if (this.isEmpty()) {
return undefined; //1
}
if (index >= 0 && index < this.count) {
let current = this.head
if (index == 0) { // 2
this.head = current.next; //3
} else {
let previous = this.getElementAt(index - 1); //4
current = previous.next; //5
previous.next = current.next; //6
}
this.count--;
return current.element;
}
return undefined;
}
Удалять
Чтобы удалить элемент, мы проверяем, не пуст ли связанный список.
Если нет, то получаем индекс элемента с помощью метода indexOf, если индекс -1, то элемент не существует, иначе используйте индекс и удалите элемент из связанного списка с помощью метода removeAt.
remove(element) {
if (this.isEmpty()) {
return undefined;
}
let index = this.indexOf(element);
if (index != -1) {
this.removeAt(index);
}
return undefined;
}
вы получаете полный источник здесь
Вывод :
Итак, следите за обновлениями в следующем блоге, в котором я расскажу о другом двухсвязном списке DS.