In genere, la memoria del computer è sempre lineare. Quindi il termine non lineare è usato per una struttura di dati in senso logico? Se è così, per ottenere logicamente la non linearità in una memoria lineare del computer, usiamo i puntatori. È giusto?
In tal caso, se i puntatori sono implementazioni virtuali per raggiungere la non linearità, perché una struttura di dati come la lista collegata può essere considerata lineare, se in realtà i nodi non sono mai fisicamente adiacenti?
Penso che il loro significato per "lineare" sia molto probabilmente le caratteristiche delle prestazioni della lista collegata . Per accedere all'elemento n -th di un elenco collegato, devi attraversare ciascun elemento prima uno alla volta. Quindi, il tempo necessario per farlo è una funzione lineare di n (il cui limite superiore è la dimensione dell'elenco). Al contrario di ad es. un array, che è accesso casuale , cioè accedere a qualsiasi elemento dell'array per indice richiede praticamente lo stesso, tempo costante.
OTOH inserendo un nuovo elemento in una posizione nota nel mezzo di un elenco collegato richiede un tempo costante, mentre fare lo stesso in un array richiede lo spostamento del resto dell'array in memoria, che è lineare al numero di elementi successivi (limitato dalla dimensione dell'array). Pertanto gli elenchi collegati presentano vantaggi in termini di prestazioni.
Il non lineare tende a implicare una struttura al di là di un semplice schema sequenziale. I puntatori sono un concetto usato per superare una semplice struttura di tipo array. I database relazionali possono anche essere visti come una struttura non lineare se vuoi un altro esempio.
Un elenco collegato può essere considerato lineare se ogni nodo punta a un altro nodo in contrasto con alberi e altre strutture dati in cui potrebbero esserci più puntatori all'interno di un nodo. Ad esempio, un albero binario è molto più difficile da immaginare come una linea. Un altro punto è come alcuni algoritmi come trovare l'elemento massimo in un elenco non ordinato hanno una complessità temporale lineare.
Una possibile ragione - perché dove i nodi appaiono in memoria non è veramente rilevante. È più importante il modo in cui visualizzi concettualmente la lista.
In termini più concreti, considera come normalmente rappresenterai un elenco lineare come un diagramma. Poiché l'arrangiamento in memoria non è importante - è puramente un dettaglio di implementazione - non lo si rappresenta nel diagramma. Normalmente ordinate gli articoli in base all'ordine di lista, in modo che formino una linea, con ogni articolo in ordine di un ulteriore passo lungo la linea.
Un'altra idea è che è puramente "lineare" in contrasto con le liste concatenate.
Anche Péter solleva un buon punto, probabilmente meglio del mio. Ma entrambi stiamo solo inventando razionalizzazioni che sospetto. Alcuni nomi non hanno un significato profondo, ma erano proprio ciò che qualcuno ha pensato senza pensarci troppo e poi il nome è rimasto bloccato.
Leggi altre domande sui tag data-structures