Связанные списки в JavaScript, упрощенный

В JavaScript не так много встроенных структур данных, которые есть в других языках, таких как Java, поэтому может быть сложно понять, как использовать их в JavaScript, если это ваш текущий язык. Этот пост призван демистифицировать современный связанный список JavaScript таким образом, чтобы это имело смысл для интервью и быстрого решения проблем.

Для краткого обзора связанные списки — это структура данных, в которой каждый узел содержит значение и указывает на один другой узел. Он заканчивается на узле, который указывает на ноль, а не на другой узел.

1 — › 2 — › 3 — › 4 — › нет

Чтобы использовать связанные списки, вы можете создать свой собственный класс связанного списка, а затем свой собственный класс узла, и дополнить свой класс связанного списка всеми существующими методами. Но есть способ проще:

class Node {
  constructor(value, next=null){
    this.value = value;
    this.next = next;
  }
}

Используя эту сборку класса Node, создать новый связанный список так же просто:

let root = new Node(1);
root.next = new Node(2);
root.next.next = new Node(3);
root.next.next.next = new Node(4);

Четвертый узел автоматически укажет на ноль, так как это значение по умолчанию параметра «следующий».

Теперь у вас есть быстрый способ создать связанный список, когда вас попросят сделать что-то вроде реверсирования связанного списка на месте:

function reverse(head) {
  let current = head;
  let previous = null;
  while (current) {
    temp = current.next;
    current.next = previous;
    previous = current;
    current = temp;
  }
return previous;
}

Я надеюсь, что это поможет демистифицировать проблемы связанных списков при использовании JavaScript!