Modello mentale per lavorare con l'elenco collegato [chiuso]

-1

Ho fatto alcuni problemi pratici su LinkedList , ma più della metà del mio tempo è dedicato alla gestione di null problema del puntatore nel mio codice, a condizione di tenere traccia di current , previous e runners a volte.

Devo sapere se esiste un modo / modello per affrontare tali problemi?

Esempio:

public void deleteMid() {
    Node n = this;
    if (n.next == null) return;
    Node faster = this;
    Node prev = null;
    while (faster != null && faster.next != null) {
      prev = n;
      n = n.next;
      faster = faster.next.next;
    }
    prev.next = n.next;
  }

Quali sono le insidie più comuni che dovrebbero essere evitate mentre si modifica una lista? ci sono dei modelli in metallo che possono aiutarci ad evitare queste insidie?

    
posta CodeYogi 11.10.2016 - 12:49
fonte

3 risposte

5

Come ho capito il tuo post, ci sono due domande qui. Uno è come costruire un modello mentale di una lista collegata. L'altro è come gestire tutti i controlli per null .

Se vuoi che un modello semplice rifletta sugli elenchi collegati, dovrebbe essere questo:

Hai un nodo importante che è la testa, e da lì inizi a passare da un nodo all'altro fino a raggiungere la fine. È come essere dentro un treno. Vai dal carro al carro fino a raggiungere l'ultimo. Aggiungere ed eliminare nodi è come aggiungere e rimuovere i vagoni dal treno. Devi collegare la fine di un nodo (o carro) al nodo successivo (o carro).

Nell'elenco collegato sono presenti nodi che mantengono un riferimento al nodo successivo. Ecco come ti muovi nella lista. L'ultimo nodo non ha più nodi dopo di esso e devi segnarlo in qualche modo. Nel treno, quando non vedi più carri, sei nell'ultimo carro. Nell'elenco collegato quando vedi un riferimento null sai che non ci sono più nodi.

Quindi null è importante perché segna l'ultimo nodo, il nodo che non si collega a nessun altro nodo. Ma null è anche un po 'pericoloso. Il tuo codice è generale Passi da un node a node.next . E se node.next punta a nulla, se fai node.next.next ottieni una NullPointerException che blocca il tuo programma.

Non c'è molto che puoi fare se vuoi che il tuo codice funzioni, ma per controllare null in vari punti. Puoi separare il controllo Null ed estrarlo in qualche metodo e avere qualcosa come if (hasNext(node)) { o if (node.hasNext()) { , ecc. E spostare lì la verifica null . In questo modo il tuo codice è più esplicito nel dire cosa sta facendo invece di sapere per quali sono tutti quei controlli per null . Ma come ho detto, non c'è molto che tu possa fare. Questa è la natura dell'elenco collegato.

    
risposta data 13.10.2016 - 21:49
fonte
1

Nella mia esperienza, disegnare diagrammi è di grande aiuto. Anche nomi adatti riducono la probabilità di errori ... next e prev sono comprensibili, ma cosa significa più veloce nel tuo codice?

    
risposta data 11.10.2016 - 21:44
fonte
-3

Hai tutto il diritto di sentirti perplesso. La "null hacking" nasconde l'idea centrale di molte strutture di dati. Come hai affermato, il concetto qui è molto semplice: possiamo rappresentare una lista collegata come un diagramma a scatola e un puntatore.

Ma come affrontiamo tutti quei fastidiosi puntatori nulli? Se accettiamo il fatto che una struttura dati è solo un altro tipo, allora possiamo prendere la vista "funzionale" di una lista collegata:

type List a = Nil | Cons of a * List a

Questa definizione è standard. Una lista è o la lista vuota, Nil o Cons (unione) di un elemento (del tipo corretto) con un'altra lista.

Si noti che ci sono nessun puntatore in questa definizione. In particolare, Nil è solo un'etichetta: non è uguale a null , e sicuramente non è un puntatore. L'utilizzo di null per rappresentare una lista vuota è solo un trucco utilizzato dalle lingue che mancano di tipi di somma.

    
risposta data 11.10.2016 - 22:57
fonte