ultimo - insertar ordenado lista enlazada java

Eliminar el último nodo de una lista vinculada

Question

Estoy practicando el trabajo con nodos de listas vinculadas y me he encontrado con un problema que no sé cómo responder. ¿Cómo se puede eliminar el último nodo en una lista vinculada? El siguiente código funciona para todas las entradas del último nodo. El último no se borra.

Clase de nodo

public class Node {

    private String data;
    private Node next;

    Node(String data, Node next)
    {
        this.data = data;
        this.next = next;
    }

    public void setData(String d)
    {
        data = d;
    }

    public void setNext(Node n)
    {
        next = n;
    }

    public String getData()
    {
        return data;
    }

    public Node getNext()
    {
        return next;
    }

Principal

Node list = new Node("NODE 1",new Node("NODE 2",new Node("NODE 3", null)));
        list = insertSecond(list,"New Node");
        list = addLast(list,"LAST NODE");

        printList(list);
        System.out.println();
        deleteNode(list,"LAST NODE");
        printList(list);    
    }

    public static Node deleteNode(Node list,String str)
    {
        Node temp = list;
        Node prev = list;

        while(temp.getNext() != null)
        {
            if(temp.getData().equals(str))
            {
                if(prev.getNext() == null)
                    prev.setNext(null);
                else{
                prev.setNext(prev.getNext().getNext());
                }

            }
            prev = temp;
            temp = temp.getNext();
        }

Answer 1

Eliminar un nodo en una lista individualmente vinculada

Suposiciones

1. Cada nodo en la lista tiene un puntero nextNode .
2. El puntero headOfList apunta al primer nodo en la lista.
3. El siguiente puntero de cada nodo, que ya está en la lista, es correcto.
4. El siguiente puntero del último nodo en la lista es algún valor significativo (por ejemplo, nulo).

Pasos para implementar

1. Si la lista está vacía, hecho. Nodo deseado no encontrado.
2. Si el primer nodo es el nodo deseado, establezca el puntero headOfList en el valor headOfList->nextNode . Hecho. Nodo deseado encontrado.
3. Establezca el puntero currentNode igual al valor del puntero headOfList .
4. Si el nodo currentNode es el último nodo. Hecho. Nodo deseado no encontrado.
5. Si el nodo currentNode->nextNode es el nodo deseado, establezca el valor currentNode->nextNode en el valor currentNode->nextNode->nextNode . Hecho. Nodo deseado encontrado.
6. ve al paso 4.

Notas

Como se trata de una lista vinculada por separado, no puede hacer una copia de seguridad. Debido a esto, debe apuntar al nodo principal y verificar si el nodo hijo es el nodo que desea eliminar. Habrá condiciones de boundry.

Cierto código

Esta es una función miembro de una clase LinkedList. startOfList es un miembro de la clase y apunta al comienzo de la lista vinculada.

 public boolean delete(final String target)
    {
        if (startOfList != null)
        {
            if (StringUtils.equals(startOfList.getData(), target))
            {
                startOfList = startOfList.getNext();
                return true;
            }

            Node current = startOfList;

            for (Node next = current.getNext(); next != null; next = current.getNext())
            {
                if (StringUtils.equals(next.getData(), target))
                {
                    current.setNext(next.getNext());
                    return true;
                }
                else // advance one node.
                {
                    current = next;
                }
            }
        }

        return false;
    }

Answer 2

Es más fácil si usa una Lista doblemente enlazada, donde su lista conoce tanto el inicio como el final.

Entonces puedes hacer algo como esto:

public void removeLastItem(){
    this.lastNode = this.lastNode.prev;
}

Answer 3

Esta es una técnica muy simple que utilicé para eliminar el último nodo.

public void deleteLast() {
    Node curr = null;

    for (curr = this.first; curr.next.next != null;curr = curr.next) {

    }

    curr.next = null;
}

Answer 4

Este es mi intento con la suposición de que la siguiente variable del último nodo siempre será nula:

public class LastNodeRemoval {

  private static class Node {
      String item;
      Node next;
  }

  public static void main(String[] args) {
      Node third = new Node();
      third.item = "Third";

      Node second = new Node();
      second.item = "Second";
      second.next = third;

      Node first = new Node();
      first.item = "First";
      first.next = second;

      removalLastNode(first);
   }

   private static void removalLastNode(Node first) {
      Node temp = first;

      while(temp.next.next != null) {
          temp = temp.next;
      }

      temp.next = null;

      System.out.println("Last node: "+temp.item);
   }

}

Answer 5

Este trabajó para mí ...

public void removeLastNode(){
    System.out.println("/n Inside removeLastNode");
    next=firstLink;
    prev=firstLink;
    if(next == null) System.out.println("/n The link List is Empty");
    while(next.getNext()!=null) { 
        prev=next;
        next=next.getNext();
    }
    prev.setNext(null);  
}

Answer 6

Esto se puede hacer de una manera mucho más simple usando la clase contenedor de Java "LinkedList". La clase LinkedList en Java implementa la interfaz Deque (cola de doble finalización) que admite obtener / agregar / eliminar métodos Primero / Último. Un fragmento de código elemental sigue:

LinkedList<Integer> list = new LinkedList<Integer>();
list.addFirst(1);
list.addLast(2);
System.out.println(list.removeLast());

Answer 7

La lógica es simple aquí y es lo mismo que obtener el último nodo. Lo difícil aquí es cuando llegue al último nodo, tendrá que recordar el nodo antes de la última y establecerlo en nulo para que sea el último nodo nuevo. En el siguiente código cuando llegue al último elemento que será n2, obtenga n1 y establézcalo en nulo.

public void removeLast(){
    if(head==null) System.out.println("List is empty");
    else {
    Node n1 = null;
    Node n2 = head;
        while(n2.next != null)
        {
            n1 = n2;
            n2 = n2.next;
        }
        n1.next = null;
    }

Answer 8

Necesitas algo como esto:

public static Node deleteNode(Node list, String str) {
  Node temp = list;
  Node prev = list;

  do {
    if (temp.getData().equals(str)) {
      if (prev.getNext() == null) {
        prev.setNext(null);
      } else {
        prev.setNext(prev.getNext().getNext());
      }
    }
    prev = temp;
    temp = temp.getNext();
  } while (temp != null);

  return list;
}

Estabas deteniendo tu ciclo demasiado temprano.

Por cierto: if (prev.getNext() == null) { prev.setNext(null); ... if (prev.getNext() == null) { prev.setNext(null); ... no tiene sentido, pero te dejaré ese error.

Answer 9

Supongo que while(temp.getNext() != null) falla para su último elemento. El último elemento no tendrá un next elemento. Entonces el último elemento no se compara con la cadena pasada. Debe rastrear esto con el depurador.

Answer 10

while(temp != null){
  prev = temp;
  temp = temp.getNext();

}

prev.next = null;

Prueba esto: