2015-10-12 15 views
5

Devo implementare un elenco collegato singolarmente per il mio progetto e ho difficoltà a far funzionare il metodo di rimozione. Ho cercato qui per le risposte, ma non riesco a trovare nessuno che incorpori il riferimento di coda. Il mio progetto deve avere un riferimento di testa e coda nella lista e deve essere aggiornato ove necessario. Questa è la mia classe e il metodo di rimozione:Elenco di elementi collegati singolarmente che rimuovono il riferimento di testa e di coda

public class BasicLinkedList<T> implements Iterable<T> { 
public int size; 

protected class Node { 
    protected T data; 
    protected Node next; 

    protected Node(T data) { 
     this.data = data; 
     next = null; 
    } 
} 

protected Node head; 
protected Node tail; 

public BasicLinkedList() { 
    head = tail = null; 
} 

public BasicLinkedList<T> addToEnd(T data) { 
    Node n = new Node(data); 
    Node curr = head; 
    //Check to see if the list is empty 
    if (head == null) { 
     head = n; 
     tail = head; 
    } else { 
     while (curr.next != null) { 
      curr = curr.next; 
     } 
     curr.next = n; 
     tail = n; 

    } 
    size++; 
    return this; 
} 

public BasicLinkedList<T> addToFront(T data) { 
    Node n = new Node(data); 
    if(head == null){ 
     head = n; 
     tail = n; 
    } 
    n.next = head; 
    head = n; 
    size++; 
    return this; 
} 

public T getFirst() { 
    if (head == null) { 
     return null; 
    } 
    return head.data; 
} 

public T getLast() { 
    if(tail == null){ 
     return null; 
    } 
    return tail.data; 
} 

public int getSize() { 
    return size; 
} 

public T retrieveFirstElement() { 
    // Check to see if the list is empty 
    if (head == null) { 
     return null; 
    } 
    Node firstElement = head; 
    Node curr = head.next; 
    head = curr; 
    size--; 
    return firstElement.data; 

} 

public T retrieveLastElement() { 
    Node curr = head; 
    Node prev = head; 
    // Check to see if the list is empty 
    if (head == null) { 
     return null; 
    } else { 
     // If there's only one element in the list 
     if (head.next == null) { 
      curr = head; 
      head = null; 
     } else { 
      while (curr.next != null) { 
       prev = curr; 
       curr = curr.next; 
      } 

      tail = prev; 
      tail.next = null; 
     } 
    } 
    size--; 
    return curr.data; 
} 

public void remove(T targetData, Comparator<T> comparator) { 
    Node prev = null, curr = head; 
    while (curr != null) { 
     if (comparator.compare(curr.data, targetData) == 0) { 
      //Check to see if we need to remove the very first element 
      if (curr == head) { 
       head = head.next; 
       curr = head; 
      } 
      //Check to see if we need to remove the last element, in which case update the tail 
      else if(curr == tail){ 
       curr = null; 
       tail = prev; 
       prev.next = null; 
      } 
      //If anywhere else in the list 
      else { 
       prev.next = curr.next; 
       curr = curr.next; 
      } 
      size--; 
     } else { 
      prev = curr; 
      curr = curr.next; 
     } 
    } 
} 

public Iterator<T> iterator() { 
    return new Iterator<T>() { 

     Node current = head; 

     @Override 
     public boolean hasNext() { 
      return current != null; 
     } 

     @Override 
     public T next() { 
      if(hasNext()){ 
       T data = current.data; 
       current = current.next; 
       return data; 
      } 
      return null; 
     } 

     @Override 
     public void remove(){ 
      throw new UnsupportedOperationException("Remove not implemented."); 
     } 

    }; 
} 

}

ho passato attraverso molte iterazioni di questo metodo e ogni volta che sia perdere il riferimento testa, il riferimento coda o io non rimuovere la elemento e sono stumped cercando di capirlo. Per riferimento qui è il test che sto eseguendo su di esso. Non esito nemmeno il test, dice solo la traccia di fallimento.

public void testRemove(){ 
      BasicLinkedList<String> basicList = new BasicLinkedList<String>(); 
    basicList.addToEnd("Blue"); 
    basicList.addToEnd("Red"); 
    basicList.addToEnd("Magenta"); 
    //Blue -> Red -> Magenta -> null 
    basicList.remove("Red", String.CASE_INSENSITIVE_ORDER); 
    //Blue -> Magenta -> null 
    assertTrue(basicList.getFirst().equals("Blue")); 
    //getLast() returns the tail node 
    assertTrue(basicList.getLast().equals("Magenta")); 
    } 

MODIFICA: ha dimenticato di menzionare che il metodo di rimozione dovrebbe rimuovere tutte le istanze dei dati di destinazione dall'elenco.

+0

Ci sono stati così tanti cattivi domande di nuovi utenti ultimamente mi sento obbligato a dirti "buon lavoro!" in un commento. Quindi buon lavoro! +1 – snickers10m

+1

aggiungi il resto del codice 'iteratore',' getFirst', 'getLast',' addToEnd' –

+0

Volevo mantenere il problema isolato nel metodo remove ma immagino che il problema potrebbe esistere anche altrove. Aggiunto l'intera classe ora. @MarquisBlount –

risposta

2

Vedo solo 1 bug. Se l'elenco è inizialmente vuota il seguente metodo causerà un ciclo in cui si dispone di un nodo la cui prossima si riferisce a se stesso:

public BasicLinkedList<T> addToFront(T data) { 
    Node n = new Node(data); 
    // The list was empty so this if is true 
    if(head == null){ 
     head = n; 
     tail = n; 
    } 
    n.next = head; 
    // now head == n and n.next == head == n so you've got a circle 
    head = n; 
    size++; 
    return this; 
} 

È possibile risolvere questo problema in questo modo:

public BasicLinkedList<T> addToFront(T data) { 
    Node n = new Node(data); 
    if(head == null){ 
     tail = n; 
    } 
    n.next = head; 
    head = n; 
    size++; 
    return this; 
} 
+0

Per risolvere questo problema, OP ha semplicemente bisogno di rimuovere 'head = n' nel blocco' if (head == null) '. (non dire che la tua strada è migliore o peggiore: P) –

+0

Grazie. Non l'avevo capito. –

+0

@AdrianShum sì, è una soluzione più semplice. Aggiornerà la mia risposta –

Problemi correlati