Удаление элемента из связанного списка с ограничениями

Question

Это довольно простой вопрос, но я запутался:

Учитывая односвязанны список, написать функцию, чтобы удалить данный узел.

1) Он должен принимать указатель на узел запуска в качестве первого параметра и узла, подлежащего удалению, в качестве второго параметра, то есть указатель на головной узел не является глобальным. 2) Он не должен возвращать указатель на головной узел. 3) Он не должен принимать указатель на указатель на головной узел.

Решение в Java заключается в следующем:

void deleteNode(Node node, Node n) { 

    if (node == n) { 
     if (node.next == null) { 
      System.out.println("There is only one node. The list " 
          + "can't be made empty "); 
      return; 
     } 

     node.data = node.next.data; 
     n = node.next; 
     node.next = node.next.next; 
     System.gc(); 

     return; 
    } 

    // When not first node, follow the normal deletion process 
    // find the previous node 
    Node prev = node; 
    while (prev.next != null && prev.next != n) { 
     prev = prev.next; 
    } 
    if (prev.next == null) { 
     System.out.println("Given node is not present in Linked List"); 
     return; 
    } 
    prev.next = prev.next.next; 
    System.gc(); 

    return; 
} 

Я смущен о том, почему при удалении узла головы, мы не изменяя указатель головы, но копировать поля вместо (изменения содержания), но при удалении других узлов это просто prev.next = prev.next.next Это работает, если мы просто делаем head = head.next вместо удаления головного узла?

Спасибо!

Answer 1

Причина, по которой код копирует данные, а не изменяет переменную, ссылающуюся на голову, заключается в том, что другие пользователи списка будут иметь ссылку на головной узел. Изменение локальной переменной не повлияет на их ссылки, поэтому вы фактически не удалите узел. Копирование данных в головной узел эффективно удаляет его.

Так, например, если у вас код, который сделал следующее:

Node head = new Node("A"); 
Node tail = new Node("B"); 
head.next = tail; 
deleteNode(head, head); 

Тогда можно было бы ожидать head.data быть «B», так как исходный узел был удален. Если вы просто делаете node = node.next, то head по-прежнему укажет на исходный удаленный узел.

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

Один из вопросов, о которых вы спрашивали, это использование System.gc. Это не обязательно. Есть редкие случаи, когда Java-код должен явно контролировать сбор мусора. Это не один из них. Это хорошее объяснение этому в принятом ответе this question.

Вы спрашивали в комментариях, почему удаление головы требует перемещения данных, а удаление других узлов требует перенаправления вокруг узла. Причина в том, что у вас нет доступа к ссылкам на голову (как объясняется в ответе выше). У вас есть доступ к ссылкам на другие узлы (то есть предыдущий узел next), поэтому их можно изменить напрямую, а не копировать данные.

Для вашей справки гораздо более стандартная реализация состоит в том, чтобы в самом списке хранилась ссылка на голову. Тогда можно полностью избежать копирования данных узлов. Также обратите внимание, что это сравнивается со значением, поскольку класс node является закрытым.

static class LinkedList<T> { 
    private class Node { 
     private final T value; 
     private Node next = null; 

     public Node(T value) { 
      this.value = value; 
     } 
    } 

    private Node head = null; 

    public void add(T value) { 
     Node node = new Node(value); 
     node.next = head; 
     head = node; 
    } 

    public void remove(T value) { 
     while (head != null && head.value.equals(value)) 
      head = head.next; 
     Node prev = head; 
     while (prev != null && prev.next != null) { 
      if (prev.next.value.equals(value)) 
       prev.next = prev.next.next; 
      else 
       prev = prev.next; 
     } 
    } 
} 

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