Complessità del tempo di elenco collegato

C'è un elenco singolarmente collegato e c'è un elenco doppiamente collegato. Esistono altri tipi di elenco collegati ma in questo articolo vengono trattati solo i tipi singolarmente e doppiamente.

Elenco singolarmente collegato

Il seguente diagramma mostra un elenco singolarmente collegato di tre elementi:

Ogni elemento ha due parti. La prima parte ha i dati. La seconda parte ha un puntatore che indica l'elemento successivo. Il secondo e il terzo elementi sono simili al primo. L'ultimo elemento ha un puntatore nullo. Con l'elenco singolarmente collegato, la attraversamento può andare in una sola direzione: la direzione in avanti.

Gli elementi di un elenco collegato non sono affrontati dai riferimenti (abbonamenti tra parentesi quadrate), tutto uguale. A loro si accede agli iteratori (puntatori). Nel caso dell'elenco singolarmente collegato, l'iteratore deve iniziare dall'inizio e spostarsi dall'elemento per elemento, al fine di raggiungere l'elemento previsto.

Elenco doppiamente collegato

Il seguente diagramma mostra un elenco doppiamente collegato di tre elementi:

Qui, ogni elemento ha tre parti. La prima parte ha un puntatore che indica l'elemento precedente. La seconda parte ha i dati. La terza parte ha un puntatore che indica l'elemento successivo. La prima parte del primo elemento ha un puntatore che indica null. La terza parte dell'ultimo elemento ha un puntatore che indica null. Con l'elenco doppiamente collegato, la attraversamento può andare in entrambe le direzioni: la direzione in avanti o la direzione inversa.

Gli elementi di un elenco collegato non sono affrontati dai riferimenti (abbonamenti in parentesi quadrate). A loro si accede agli iteratori (puntatori). Nel caso di un elenco doppiamente collegato, l'iteratore può spostarsi in entrambe le direzioni ma deve iniziare da entrambe le estremità. Il movimento non può iniziare ufficialmente dall'interno dell'elenco.

Lo scopo di questo articolo è determinare ciò che è noto come complessità temporale per l'elenco collegato.

Complessità temporale in generale

La complessità del tempo è il runtime relativo di qualche codice. La complessità del tempo può anche essere vista come il numero di operazioni principali del codice.

Tempo costante

Si dice che un'operazione principale come inserto o eliminazione abbia una complessità temporale di tempo costante perché l'azione può essere vista come una volta che si verifica. È scritto come:
O (1)

dove 1 significa tempo o azione costante una volta. Questo utilizza la notazione Big-O che inizia con O in maiuscolo seguito da parentesi. All'interno delle parentesi c'è il numero di operazioni principali per l'attività.

Tempo lineare

Leggere un array dall'inizio- un elemento dopo l'altro alla ricerca di un particolare elemento- viene definita una ricerca lineare.

L'elemento ricercato può essere trovato da qualche parte nel mezzo e la ricerca si fermerebbe. Questa è ancora una ricerca lineare. La complessità temporale per la ricerca lineare è scritta come:
SU)

dove n è il numero massimo possibile di operazioni.

Operazioni principali dell'elenco collegato

Ricerca
Per l'elenco singolarmente collegato, per passare da un elemento all'altro, il codice deve utilizzare il puntatore dell'elemento corrente, che indica l'elemento successivo. Questo non è il caso di array. Per l'elenco doppiamente collegato, per passare da un elemento all'altro, il codice deve utilizzare il puntatore dell'elemento corrente che indica l'elemento successivo. Questo non è il caso di array. Per l'elenco doppiamente collegato, per passare da un elemento al precedente, il codice deve utilizzare il puntatore dell'elemento corrente che punta all'elemento precedente. Questo non è il caso di array.

Cancellazione
Quando viene eliminato un elemento corrente, il puntatore dell'elemento precedente che lo stava puntando, deve essere fatto per indicare l'elemento successivo. Quindi, il puntatore dell'elemento successivo è stato indicato ad esso deve essere fatto per indicare l'elemento precedente.

Inserimento
Quando viene inserito l'elemento corrente, il puntatore dell'elemento precedente che indicava l'elemento successivo deve essere fatto per indicare l'elemento corrente. Il puntatore dell'elemento successivo che indicava l'elemento precedente deve essere fatto per indicare l'elemento corrente.

Il puntatore anteriore dell'elemento corrente deve essere fatto per indicare il nuovo elemento successivo. Il puntatore posteriore dell'elemento corrente deve essere fatto per indicare il nuovo elemento precedente.

Complessità temporale per l'elenco collegato

Quando si parla della complessità del tempo per un elenco collegato, è la complessità del tempo per la ricerca, l'inserto ed elimina che si parla. Non è la complessità temporale per la costruzione dell'elenco collegato. La complessità del tempo per la costruzione di un elenco collegato è un problema diverso.

Ricerca
Affinché un elenco singolarmente collegato sia la ricerca di un particolare elemento (dati), il codice di ricerca deve scansionare l'elemento elenco per elemento dall'inizio. Per una lista doppiamente collegata per essere alla ricerca di un elemento particolare, il codice di ricerca deve scansionare l'elemento elenco per elemento- dall'inizio. O scansionare l'elenco, elemento per elemento, dalla fine. La complessità del tempo di ricerca per un elenco collegato (singolarmente o doppiamente) è:
SU)

dove n è il numero di elementi nell'elenco. Non importa se l'elemento è stato trovato, da qualche parte all'interno dell'elenco.

Inserimento
L'inserimento è considerato come un'operazione principale. Al fine di inserire un elemento in un elenco collegato, la ricerca deve aver luogo, per arrivare alla posizione, per l'inserimento. La complessità temporale per la ricerca è O (n). La complessità temporale per l'azione dell'inserimento è O (1). Quindi, la complessità del tempo per l'inserimento in un elenco collegato è O (N + 1). Per semplicità, la complessità temporale per l'inserimento di un elemento, in un elenco collegato, è scritta come:
SU)

Cancellazione
La cancellazione è considerata come un'operazione principale. Al fine di eliminare un elemento in un elenco collegato, la ricerca deve avvenire, per arrivare alla posizione per la cancellazione. La complessità temporale per la ricerca è O (n). La complessità temporale per l'azione di eliminazione è O (1). Quindi, la complessità del tempo per la cancellazione in un elenco collegato è O (N + 1). Per semplicità, la complessità temporale per la cancellazione di un elemento, fuori da un elenco collegato, è scritta come:
SU)

Costruire un elenco collegato in C

Per creare un elenco doppiamente collegato in C, utilizzare l'oggetto struct. Il primo membro dei dati dovrebbe avere un puntatore che indica la struttura precedente. Il terzo membro dei dati dovrebbe avere un puntatore che indica la struttura successiva. Il membro dei dati intermedi dovrebbe avere i dati. Il primo membro dei dati della prima struttura dovrebbe puntare a null. Il terzo membro dei dati dell'ultima struttura dovrebbe anche indicare nulla.

Nel caso dell'elenco singolarmente collegato, ometti il ​​primo membro dei dati.

Conclusione

La complessità temporale per la ricerca di un elenco collegato è:
SU)

Per semplicità, la complessità del tempo per l'inserimento di un elemento in un elenco collegato è:
SU)
e non O (1).

Per semplicità, la complessità temporale per la cancellazione di un elemento, fuori da un elenco collegato, è:
SU)
e non O (1).