Клонирование односвязного списка

Вопрос-ответ JavaScript
1

Помогите, если знаете как, исправить клонирование односвязного списка.
Если необходимо, можно метод clone вынести за пределы класса, лишь бы клонировал.

class LinkedList {
  constructor() {
    this.head = null;
    this.length = 0;
  }

  get(position) {
    if (position > this.length) {
      throw new Error("Position is out of list");
    }

    var current = this.head;

    for (let i = 0; i < position; i++) {
      current = current.next;
    }

    return current;
  }

  add(value, position) {
    var node = {
      value: value,
      next: null
    };

    if (position === 0) {
      node.next = this.head;
      this.head = node;
    } else {
      var previous = this.get(position - 1);
      var current = previous.next;
      node.next = current;
      previous.next = node;
    }

    this.length++;
  }

  remove(position) {
    if (position === 0) {
      this.head = this.head.next;
    } else {
      var prev = this.get(position - 1);
      prev.next = prev.next.next;
    }

    this.length--;
  }

  clone() {
    var cloned = new LinkedList();

    for (var s = 0; s < this.length; s++) {
      cloned.add(this.get(s), s);
    }

    return cloned;
  }
}

var first = new LinkedList();
first.add("a", 0);
first.add("b", 1);
first.add("c", 2);

var copy;
var line = "";

for (let w = 0; w < 5; w++) {
  copy = first.clone();
  copy.add(w, w + 1);
  line = copy + "\n";
}

console.log(line);
2

Нюанс в том как реализован метод get. Он возвращает не значение элемента списка ("a", например), а объект представляющий элемент списка, ячейку: {value: "a", next: null}. Метод add же ожидает что в аргументе будет значение элемента списка. clone выражен через get и add, и как следствие, добавляет в клонируемый список не значение элемента откуда клонируешь, а саму ячейку списка ({value: "a", next: null}).

Быстрая демонстрация как сделать чтобы код заработал.

// было
cloned.add(this.get(s), s);

// стало
cloned.add(this.get(s).value, s);

Мне кажется концептуально спутаны задачи метода get (получение значение элемента списка и ячейки списка). Я бы подумал о том чтобы сделать 2 get-а. Ячейки и самого значения.

1 лайк
3

Как я понял, список не клонировался, т.к. я просто скопировал ячейки, но ссылки .next между ними не сделал.

4

Да

1 лайк