Невозможно удалить первый узел из связанного списка

Question

Ниже приведен мой полный код класса Node для создания узлов в связанном списке вместе с некоторыми методами для добавления дополнительных узлов в список, распечатки всего содержимого списка и удаления узла из списка:

public class Node {
Object data;
Node next;

public Node(Object data) {
    this.data = data;
}

public void printList() {
    Node node = this;
    while (node != null) {
        System.out.println(node.data);
        node = node.next;
    }
}

public void add(Object data) {

    Node node = this;
    while (node.next != null) {
        node = node.next;
    }
    node.next = new Node(data);
}

public void delete(Object data) {
    Node node = this;

    if (node.data.equals(data)) {
        node = node.next;
        return;
    }

    while (node.next != null) {
        if (node.next.data.equals(data)) {
            node.next = node.next.next;
            return;
        }
        node = node.next;
    }
}

}

Все методы работают нормально, за исключением того, что метод delete не удалит узел, если это первый узел. Что я делаю не так?

Answer 1

Вы не можете удалить первый Node с вашей текущей реализацией, потому что первый узел - this, и вы не можете изменить его внутри класса Node. Что вы можете сделать, так это немного изменить метод удаления и вернуть новый экземпляр вашего Node класса.

public Node delete(Object data) {
    Node node = this;
    if (node.data.equals(data)) {
        return node.next;
    }
    while (node.next != null) {
        if (node.next.data.equals(data)) {
            node.next = node.next.next;
            return node;
        }
        node = node.next;
    }
    return null;
}

Так что, если вы хотите удалить первый узел, вам нужно будет поместить его в новую переменную или выполнить повторную проверку. Пример:

 Node node = new Node(1);
 node.add(2);
 node.add(4);
 node.add(3);
 node.delete(3);
 node = node.delete(1);
 node.printList();

Answer 2

Ваша проблема в том, что вы никогда не удаляете узел. Все, что вы делаете в своем методе delete(Object data), это меняете локальную переменную Node node.

Answer 3

Потому что вы вызываете printList на первом узле. Это не правильный способ сделать. Вы можете определить класс LinkedList и внутри него вы можете иметь закрытый статический вложенный класс Node.

class LinkedList{
 private Node head; 
 private static class Node{
   //define the methods here
  }

}

Для текущего решения вы можете изменить метод удаления и вернуть ссылку на узел.

public Node delete(Object data) {
    Node node = this;

    if (node.data.equals(data)) {
        node = node.next;
        return node;
    }

    while (node.next != null) {
        if (node.next.data.equals(data)) {
            node.next = node.next.next;
        }
        node = node.next;
    }
    return node;
}
public static void main(String[] args) {
    Node node = new Node(10);
    node.add(20);
    node.add(30);

    node = node.delete(10);
    System.out.println("After Deletion of 10");

    node.printList();

    node = node.delete(20);
    System.out.println("After Deletion of 20");

    node.printList();


}

Answer 4

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

void deleteNode(int key)
{
    // Store head node
    Node temp = head, prev = null;

    // If head node itself holds the key to be deleted
    if (temp != null && temp.data == key)
    {
        head = temp.next; // Changed head
        return;
    }

    // Search for the key to be deleted, keep track of the
    // previous node as we need to change temp.next
    while (temp != null && temp.data != key)
    {
        prev = temp;
        temp = temp.next;
    }    

    // If key was not present in linked list
    if (temp == null) return;

    // Unlink the node from linked list
    prev.next = temp.next;
}

Источник: https://www.geeksforgeeks.org/linked-list-set-3-deleting-node/