Перевернутый связанный список - Javascript - Использование класса или просто определить функцию? и как рассчитать время / пространство сложности - PullRequest
Новая
       33

Перевернутый связанный список - Javascript - Использование класса или просто определить функцию? и как рассчитать время / пространство сложности

0 голосов
/ 14 марта 2019

Я понимаю, что есть несколько вопросов с обратным связным списком, использующих javascript, но я надеялся на большую ясность в отношении решения, предоставленного кем-то другим.

Является ли использование class LinkedList необходимым для объявления связного списка, или просто будет делать это, как в данном примере с данной работой?

Мне просто не ясно, как эта функция просто объявляет переменную с именем reverseLinkedList и решает ее в отличие от фактического использования класса.

Не уверен, имеет ли это какой-то смысл, но в противном случае, будет ли это решение достаточно ясным, чтобы решить обратную проблему связанного списка?

Кроме того, будет ли это рассматриваться как O (n) для сложности времени? Так как он имеет цикл while, который устанавливается на конечное количество времени для запуска. И я не уверен насчет космической сложности. 

// reverse a linked list
const reverseLinkedList = (linkedlist) => {
  let node = linkedlist;
  let previous = null;

  while(node) {
// save next or you lose it!!!
  let save = node.next;
// reverse pointer
  node.next = previous;
// increment previous to current node
  previous = node;
// increment node to next node or null at end of list
  node = save;
}
  return previous;   // Change the list head !!!
}
linkedlist = reverseLinkedList(linkedlist);

Ответы [ 2 ]

1 голос
/ 14 марта 2019

В любом случае это хорошо. Создание класса LinkedList позволит вам добавить к нему методы, но это излишне для решения проблемы с одним обратным связанным списком.

Связанный список - это просто набор узлов, где каждый узел ссылается на следующий со свойством объекта next.

Если вы хотите добавить несколько удобных методов в LinkedList, тогда да, класс будет полезен. Но для одной проблемы, такой как обращение к списку, опубликованное вами решение предполагает, что функция принимает в качестве входных данных первый узел в списке и что каждый узел (просто объект JavaScript) имеет свойство next.

Например, скажем, я решал проблемы со множеством связанных списков, и мне также нужно было создать связанный список из массива значений. Скажем, я также хотел легко проверить, возвращает ли функция (например, reverseLinkedList) правильный список. Я мог бы использовать класс как this

Тогда для проверки вышеуказанного решения будет так же просто, как:

Во-первых, переписать обратное решение так, чтобы оно принимало связанный список, а не только заголовок, и чтобы вы могли изменить свойство head списка после его обращения: 

const reverseLinkedList = (linkedlist) => {
  let node = linkedlist.head;
  let previous = null;

  while(node) {
// save next or you lose it!!!
  let save = node.next;
// reverse pointer
  node.next = previous;
// increment previous to current node
  previous = node;
// increment node to next node or null at end of list
  node = save;
}
  linkedlist.head = previous
  return previous;   // Change the list head !!!
}

Затем вы можете запустить этот тест: 

var inputList = new LinkedList([1,2,3,4])
var expectedReversedList = new LinkedList([4,3,2,1])
var actualReversedList = reverseLinkedList(inputList)
console.log(inputList.isEqualTo(actualReversedList))

Кроме того, с точки зрения пространственной и временной сложности, поскольку вышеприведенное решение мутирует объекты, это пространство O (1), а поскольку оно повторяется через узлы только один раз, это O (N) сложность времени

1 голос
/ 14 марта 2019

Здесь происходит несколько вещей

Первая эта декларация

let reverseLinkedList = function(linkedlist) {

похожа на эту декларацию

function reverseLinkedList(linkedList) {

за исключением того, что вы не можете вызвать reverseLinkList, пока это не будет объявлено в первом примере.Вы можете узнать больше о подъеме здесь

var functionName = function () {} vs function functionName () {}

Second с использованием классаили функция не имеет большого значения.Вы увидите, что классы в Javascript на самом деле просто синтаксический сахар (но есть некоторые ошибки, о которых вы можете прочитать здесь)

Являются ли классы es6 просто синтаксическим сахаром для прототипа в javascript?

Наконец временная сложность этой функции равна O (n), потому что она просто перебирает список один раз.

Надеюсь, это поможет!

...