Удаление ссылки на удаленный узел в двусвязном связанном списке - PullRequest
Новая
       5

Удаление ссылки на удаленный узел в двусвязном связанном списке

0 голосов
/ 10 апреля 2020

Я могу успешно удалить узел в моем двусвязном списке, но мой node.next все еще «указывает» на удаленный узел, а предыдущий прежний узел все еще «указывает» на удаленный узел. Когда я печатаю список, узла там нет, а при вызове findNode () возвращаемое значение соответствует ожидаемому («нет узла с этим значением»)

Вот мой класс: 

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

class LinkedList {
  constructor() {
      this.head = null
      this.tail = this.head
      this.size = 0
    }

  findNode(value) {
    let node = this.head
        while(node !== null && node.value !== null) {
       node = node.next
    }
        return node !== null
  }

  remove(value) {
    let node = this.head
    while(node.next !== null) {
      if(node.value === value) {
        const newCurrentNode = node.prev
        const newNextNode = node.next
        newCurrentNode.next = newNextNode
        newNextNode.prev = newCurrentNode
      }
      node = node.next
      if(node.next === null) {
        return 'node node with that value'
      }
    }
    this.size--
    return this.print()
  }

  removeAtIndex(position) {
    let node = this.head
    if(position < 1) this.removeHead(value)
    if(position > this.size) return 'no node at that position'
    let count = 0
    while(count !== position){
      console.log(`${count} is not at position`)
      node = node.next
      count++
    }
    // console.log(`${count} is at position`)
    const prevNode = node.prev
    const newNextNode = node.next
    prevNode.next = newNextNode
    newNextNode.prev = prevNode
    node.next = null
    node.prev = null
    this.size--
    return this.print() // change to return this for LL
}

 insertNewHead(value) {
    const newHead = new Node(value)
    const oldHead = this.head
    if(!this.head) {
      this.head = newHead
      this.size++
    } else {
      newHead.next = oldHead
      oldHead.prev = newHead
      this.head = newHead
      this.size++
    }
    return this.head
  }

  insert(value) {
    const newNode = new Node(value)
    const prevNode = this.tail
    if(!this.head) {
      this.head = newNode
    } else {
      this.tail.next = newNode
      newNode.prev = prevNode
    }
    this.tail = newNode
    this.size++
    return this
  }

insertAtIndex(value, position) {
    const node = new Node(value)
    if(position < 1) this.insertNewHead(value)
    if(position > this.size) {
      this.tail.next = node
      node.prev = this.tail
      this.tail = node
      this.size++
      return this
    }
    let count = 0
    let previous = this.head 
    let current = previous.next
    while(count !== position -1) {
      previous = current
      current = current.next
      count++
    }
    node.next = current
    previous.next = node
    node.prev = previous
    this.size++
    return node
  }

  insertBefore(value, position) {
    return this.insertAtIndex(value, position - 1)
  }

  insertAfter(value, position) {
    return insertAtIndex(value, position + 1)
  }

  forEach(cb) {
    let node = this.head;
    while (node) {
      cb(node.value);
      node = node.next;
    }
  }

  print() {
    let result = [];
    this.forEach(function(value) {
      result.push(value);
      });
    return result.join(', ');
  }
removeHead(){
  let oldHead = this.head;
  let newHead = oldHead.next;
  this.head = newhead;
  oldHead.next = null;
  this.size--;
  return oldHead;
}

}

Перед с print () 7, 5, 1, 2, 3, 8, 6

ll.removeAtIndex (4) 7, 5, 1, 2, 8, 6

Тем не менее, я все еще вижу это, я все еще вижу 6 prev, указывающих на 3 

LinkedList {
  head:
   Node {
     value: 7,
     next: Node { value: 5, next: [Node], prev: [Circular] },
     prev: null },
  tail:
   Node {
     value: 6,
     next: null,
     prev: Node { value: 3, next: null, prev: null } },
  size: 6 }

Правильно ли я сбрасываю указатели узлов? Я это ожидаемый результат? Будет ли этот узел собирать мусор? Разве 6.prev не должен указывать на 8?

Код для добавления элементов в список: 

const ll = new LinkedList()
ll.insert(1)
ll.insert(2)
ll.insert(3)
ll.findNode(1)
ll.insertNewHead(7)
ll.insertAtIndex(5,1)
ll.tail
ll.insertBefore(6, 10)
ll.insertAtIndex(8, 5)
ll.print()
ll.removeAtIndex(4)
console.log(ll)
ll.print()

1 Ответ

1 голос
/ 10 апреля 2020

Проблема не в removeAtIndex, а в insertAtIndex, который присваивает node.next = current, но не current.prev = node. При этом узел 6 по-прежнему ссылается на узел 3, в то время как он действительно должен ссылаться на узел 8.

...