• Regolamento Macrocategoria DEV
    Prima di aprire un topic nella Macrocategoria DEV, è bene leggerne il suo regolamento. Sei un'azienda o un hosting/provider? Qui sono anche contenute informazioni per collaborare con Sciax2 ed ottenere l'accredito nella nostra community!

Guida Lista concatenata

Mi.ke

Utente Master
Autore del topic
16 Giugno 2011
2.857
60
Miglior risposta
0
Salve, :emoji_relieved:

Quest'oggi vi annoierò con un po di teoria sulle Strutture di dati e file.

Che cos'è la lista concatenata?
La lista concatenata (linked list) è una struttura di dati in cui gli elementi sono ordinati linearmente. Ogni elemento conosce qual è il suo successore e in questo modo, a partire dal primo elemento (nodo) è possibile ricostruire tutti gli elementi presenti nella lista.

Oltre a gestire strutture ordinate, la lista ha il vantaggio di inserire e cancellare i dati in modo più veloce rispetto ad altre soluzioni. Con le liste concatenate, dopo che è stata trovata la posizione, l'inserimento è immediato. La stessa operazione eseguita su un array risulta più "costosa" in quanto per fare spazio al nuovo elemento si devono spostare tutti gli elementi di 1 posto.
Una lista può esssere vista come una successione di nodi, in cui ogni nodo è costituito dai dati relativi all'elemento più un riferimento al nodo successivo.

In altri linguaggi di programmazione, le liste concatenate vengono gestite utilizzando i puntatori. In Java vengono utilizzati i riferimenti agli oggetti (o-obj) che in pratica sono uguali ai puntatori ocn la differenza che la gestione di questi è demandata al modulo run-time di Java.

Grafico di una lista concatenata:


Testa (Primo nodo)
Coda (Ultimo nodo con puntatore null)
Testa

Nodo 0
ContenutoPuntatore al successivo
--->
Nodo 1
ContenutoPuntatore al successivo
--->
Nodo 2
Contenutonull
Coda


Questa struttura può essere realizzata manualmente o attraverso l'uso delle classi già presenti.

Istanziare una lista:
Codice:
Perfavore, Entra oppure Registrati per vedere i codici!

Libreria utilizzata : java.util (LinkedList)

Ovviamente si possono aggiungere gli standardizzatori di <Oggetto> e quindi ad esempio creare una Lista di soli interi:

Codice:
Perfavore, Entra oppure Registrati per vedere i codici!

Quest'ultimi si chiamano Diamond Operator e sono stati implementati nel JDK7.
Sono stati inseriti dopo che sono nate le necessità di avere una lista di oggetti già "consapevole" in modo da agevolare le operazioni da compiere e ridurre il codice.

Ad es: su una lista di Stringhe, con il metodo get(i) posso utilizzare i metodi della Stringa.
lista.get(i).charAt(i), lista.get(i).equals(), etc.

I metodi principali della struttura già data da Java sono:

lista.add(Object obj);
lista.get(int index); // Ritorna il valore all'indice passato.
lista.remove(int index) ;

(... etc )

Documentazione completa:
Perfavore, Entra oppure Registrati per vedere i Link!



Ok, per questa guida è tutto, spero di essere stato abbastanza chiaro, se volete dei chiarimenti non esitate a chiedere.
:bye:
 
Ultima modifica:
Salve, :emoji_relieved:

Quest'oggi vi annoierò con un po di teoria sulle Strutture di dati e file.

Che cos'è la lista concatenata?
La lista concatenata (linked list) è una struttura di dati in cui gli elementi sono ordinati linearmente. Ogni elemento conosce qual è il suo successore e in questo modo, a partire dal primo elemento (nodo) è possibile ricostruire tutti gli elementi presenti nella lista.

Oltre a gestire strutture ordinate, la lista ha il vantaggio di inserire e cancellare i dati in modo più veloce rispetto ad altre soluzioni. Con le liste concatenate, dopo che è stata trovata la posizione, l'inserimento è immediato. La stessa operazione eseguita su un array risulta più "costosa" in quanto per fare spazio al nuovo elemento si devono spostare tutti gli elementi di 1 posto.
Una lista può esssere vista come una successione di nodi, in cui ogni nodo è costituito dai dati relativi all'elemento più un riferimento al nodo successivo.

In altri linguaggi di programmazione, le liste concatenate vengono gestite utilizzando i puntatori. In Java vengono utilizzati i riferimenti agli oggetti (o-obj) che in pratica sono uguali ai puntatori ocn la differenza che la gestione di questi è demandata al modulo run-time di Java.

Grafico di una lista concatenata:


Testa (Primo nodo)
Coda (Ultimo nodo con puntatore null)
Testa

Nodo 0
ContenutoPuntatore al successivo
--->
Nodo 1
ContenutoPuntatore al successivo
--->
Nodo 2
Contenutonull

Coda


Questa struttura può essere realizzata manualmente o attraverso l'uso delle classi già presenti.

Istanziare una lista:
Codice:
Perfavore, Entra oppure Registrati per vedere i codici!

Ovviamente si possono aggiungere gli standardizzatori di <Oggetto> e quindi ad esempio creare una Lista di soli interi:

Codice:
Perfavore, Entra oppure Registrati per vedere i codici!

I metodi principali della struttura già data da Java sono:

lista.add(Object obj);
lista.get(int index); // Ritorna il valore all'indice passato.
lista.remove(int index) ;

(... etc )

Documentazione completa:
Perfavore, Entra oppure Registrati per vedere i Link!



Ok, per questa guida è tutto, spero di essere stato abbastanza chiaro, se volete dei chiarimenti non esitate a chiedere.
:bye:

va specificato anche che appartiene a java.util (LinkedList) , dove ci sono tra l'altro tutte le altre collection.
Dato che ti trovavi potevi parlare anche del diamond operator di SE7 e superiore.

Comunque ottima guida Noyz :soso:
 
va specificato anche che appartiene a java.util (LinkedList) , dove ci sono tra l'altro tutte le altre collection.
Dato che ti trovavi potevi parlare anche del diamond operator di SE7 e superiore.

Comunque ottima guida Noyz :soso:

Ecco cosa stavo dimenticando, la libreria qwe.
Grazie TBH, per quanto riguarda il Diamond Operator, aggiungo due righe ;)