Il puntatore Head (inizio) dell'elenco Doubly Linked punta in precedenza al nodo (ultimo) della coda

3

Ho una domanda nella mia mente che in caso di lista circolare doppiamente collegata il puntatore della testa dell'elenco doppiamente collegato punta anche logicamente al prossimo puntatore del nodo di coda della lista collegata e il prossimo puntatore della coda punta anche al precedente puntatore di testa.

Per favore, rispondi a questa domanda Sono un po 'confuso.

    
posta Chitrank Dixit 28.09.2012 - 07:47
fonte

3 risposte

4

Dipende.

È un elenco circolare o lineare?

Se si tratta di una lista circolare, non vi è alcuna "testa" o "coda" poiché verranno impostati i puntatori next e prev di ciascun elemento. Puoi iniziare a percorrere l'elenco ovunque e ricordare dove hai iniziato in modo da sapere quando fermarti.

Se è un elenco lineare, il puntatore prev dell'elemento head sarà null e il puntatore next dell'elemento tail sarà null . Utilizzi queste informazioni per sapere quando smettere.

    
risposta data 28.09.2012 - 10:07
fonte
2

Supponiamo di avere una lista circolare doppiamente collegata con tre nodi nelle posizioni 1, 2 e 3:

[1] next->2 prev->3
[2] next->3 prev->1
[3] next->1 prev->2

In un certo senso non ci sono "testa" e "coda" in una lista circolare doppiamente collegata. Sebbene tu abbia un puntatore all'esterno come punto di accesso per accedere all'elenco come head- > 1, che sarebbe identico a 3: next- > 1.

Quindi le teste prev indicano la "coda"

La coda successiva punta alla "testa"

    
risposta data 28.09.2012 - 09:21
fonte
1

Ho usato una lista circolare doppiamente collegata come questa:

typedef struct List {
  struct List *next;
  struct List *prev;
  void *data;
} List;

Ho deciso di definire la testa di una lista come una che ha dati == NULL. Quindi una lista vuota è una dove il prossimo e il precedente puntano a se stessa e data == NULL. È quindi possibile inserire prima o dopo la testa a volontà. Puoi eseguire l'iterazione della lista iniziando da head- > next and going fino a quando non premi di nuovo la testa.

Ed ecco la parte divertente: puoi avere più teste. Niente ti impedisce di inserire una seconda lista con dati == NULL. Ora ci sono due modi per scorrere l'elenco: puoi scorrere fino a toccare la testa successiva (dati == NULL) o saltare le teste e andare avanti fino a colpire di nuovo la testa originale.

    
risposta data 04.06.2015 - 12:27
fonte

Leggi altre domande sui tag