Lista enlazada a Java: método de adición

Question

Clase de estructuras de datos, que implementa una lista única enlazada con nodos de cabeza, cola y corriente. Si tiene problemas con un método, podría usar un pequeño empujón en la dirección correcta.

A partir de la asignación, escribir el método:

add (artículo): agrega el elemento (String) después de que el nodo actual en ese momento y define el puntero actual para referirse al nuevo nodo.

Mi intento:

Mi método add sólo parece funcionar cuando estoy añadiendo elementos a la mitad de la lista, no en cualquiera de los extremos. Si lo uso para agregar algunos elementos y luego imprimir la lista, solo el primero que agregue estará en la lista, mientras que mis métodos de anteponer y anexar han probado muy bien.

¿Hay algún problema evidente con mi código? Siento que me falta algo obvio.

Todos:

public class LinkedList { 
    Node head = null; /* Head of the list */ 
    Node tail = null; /* Tail of the list */ 
    Node curr = null; /* Current node in the list */ 

    public void prepend(String item) { 
     if (head == null) { 
      head = tail = new Node(item, null); 
      curr = head; 
     } else { 
      head = new Node(item, head); 
      curr = head; 
     } 
    } 

    public void append(String item) { 
     if (head == null) { 
      head = tail = new Node(item, null); 
      curr = tail; 
     } else { 
      tail.next = new Node(item, null); 
      tail = tail.next; 
      curr = tail; 
     } 
    } 

    public void add(String item) { 
     if (curr != null) { 
      Node newNode = new Node(item, curr.next); 
      curr.next = newNode; 
      curr = newNode; 
     } else { 
      head = tail = new Node(item, null); 
      curr = head; 
     } 
    } 

    public void delete() { 
     if (curr.next == null) { 
      Node temp = head; 
      while (temp.next != curr) { 
       System.out.println(temp.item); 
       temp = temp.next; 
      } 
      temp.next = null; 
      curr = head; 
     } 
    } 

    public void find(String item) { 
     Node temp = new Node(curr.item, curr.next); 
     if (item.equals(temp.item)) 
      curr = temp; 
     else { 
      temp = temp.next; 
      while (temp.next != null && temp != curr) { 
       if (item.equals(temp.item)) 
        curr = temp; 
      } 
     } 
    } 

    public String get() { 
     if (curr != null) 
      return curr.item; 
     else 
      return ""; 
    } 

    public boolean next() { 
     if (curr != tail) { 
      curr = curr.next; 
      return true; 
     } else 
      return false; 
    } 

    public void start() { 
     curr = head; 
    } 

    public void end() { 
     curr = tail; 
    } 

    public boolean empty() { 
     if (head == null) 
      return true; 
     else 
      return false; 
    } 
} 

Node clase:

class Node { 
    Node next; 
    String item; 

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

Answer 1

Creo que el problema es

if (curr != null) { 
    Node newNode = new Node(item, curr.next); //<-- here (curr.next) 

//and 

Node(String item, Node next) { 
    this.next = next; //<-- here 

Try (Editado):

Node newNode = new Node(item, curr); // pass curr to the constructor of Node 
curr = newNode; 

Answer 2

No veo ningún problema aquí, así que supongo que el problema está en otra parte.

bien, el único problema que veo que hay en delete:

public void delete() 
{ 
    Node temp = head; 

    while(temp != null && temp.next != curr) { 
     System.out.println(temp.item); 
     temp=temp.next; 

    } 

    if (temp != null && temp.next != null) { 
     temp.next = temp.next.next; 
    } 
    curr = head; 

} 

Answer 3

Creo que he encontrado el problema. Si usa append() lo agrega directamente después de la cola. Pero cuando ha agregado nodos previos después de la cola, no establece la cola en el nuevo nodo. Esto significa que una vez que llame a append() dos veces, perderá todos los nodos que haya agregado después del primer append().

ejemplo Breve:

public static void main(String[] args) { 
    LinkedList list = new LinkedList(); 
    list.add("First add"); 
    list.append("First Append"); 
    list.add("Second add"); 
    list.prepend("First prepend"); 
    list.add("Third add"); 
    list.prepend("Second prepend"); 
    list.add("fourth add"); 
    list.append("Second Append"); 
    list.add("Fifth add"); 
    list.add("Sixth add"); 

    list.start(); 
    do { 
     System.out.println(list.get().toString()); 

    } while (list.next()); 
} 

Salida:

Second prepend 
fourth add 
First prepend 
Third add 
First add 
First Append 
Second Append 

Conclusión: "En segundo lugar Añadir" se pierde, así como "Quinta añadir" y "Sexto añadir" debido a que su método next() se detiene tan pronto como alcanza la cola. Siempre debe actualizar la cola si agrega un nuevo nodo al final.

Espero que esto ayude. Cheers, Chnoch

Answer 4

De hecho hay un problema en add: no se actualiza tail cuando los nodos ya existen.Considere esta secuencia de acciones:

LinkedList list = new LinkedList(); 
list.add("one"); 
list.add("two"); 
list.append("three"); 

Si se va a continuación, imprimir usando esto:

public void print() { 
    Node curr = this.head; 
    while(curr != null) { 
     System.out.println(curr.item); 
     curr = curr.next; 
    } 
} 

De esta manera:

list.print(); 

Te obtener el siguiente resultado:

one 
three 

Esto sucede bec ause tail - de la cual se basa append - continúa apuntándose al primer Node después de que se realiza la segunda operación add.