Как бы я мог удалить узел в связанном списке, не повреждая список? - PullRequest
Новая
       28

Как бы я мог удалить узел в связанном списке, не повреждая список?

1 голос
/ 06 марта 2012 
template <class T>
bool LinkedList<T>::remove(const T object){
  Node<T> *cur = head;
  while(cur->next != NULL){
    if(cur->next->value == object){
      Node<T>* temp = cur->next->next;
      delete cur->next;
      cur->next = temp;
      s--;
      return true;
    }
    cur = cur->next;
  }
  return false;
}

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

Ответы [ 2 ]

2 голосов
/ 06 марта 2012

Деструктор узлов просто "удалить следующий".

Oooops. Если каждый узел удаляет следующий в своем деструкторе, это приводит к удалению всего списка с этой точки! 

  Node<T>* temp = cur->next->next; // the node temp points to is clearly after cur
  delete cur->next; // deletes everything after cur
  cur->next = temp; // temp no longer points to a valid node
0 голосов
/ 06 марта 2012

Рабочая версия будет выглядеть примерно так: 

template <class T>
bool LinkedList<T>::remove(const T object) {

    // Iterate through the list.
    for(Node<T> **cur = &head;; cur = &((*cur)->next)) {
        // Check for list end.
        if(!*cur)
            return false;
        // Check for match.
        if((*cur)->value == object)
            break;
    }

    // Knock out the node.
    Node<T> *temp = (*cur)->next;
    delete *cur;
    *cur = temp;

    // No idea what s does.
    --s;

    return true;
}
...