È possibile perché le "liste" in una rappresentazione di elenchi di adiacenze non sono necessariamente matrici raw.
In particolare, l'aggiunta di un nuovo nodo a un elenco collegato è un'operazione O (1), quindi se si crea l'elenco di adiacenze tra gli elenchi collegati, aggiungere un nuovo nodo o bordo è O (1).
Come il grafico che hai linkato indica, anche le pile e le tabelle hash hanno l'inserimento O (1) così puoi usarle anche tu, ma gli stack probabilmente renderebbero molte altre operazioni molto scomode e le tabelle hash sono solo O ( 1) date alcune forti ipotesi sulla funzione di hashing che sono difficili da giustificare, quindi di solito presumo che gli elenchi di adiacenza siano fatti da liste collegate se vogliono l'inserimento di nodi / edge a tempo costante.
Vale anche la pena notare che anche se si utilizzavano gli array, si avrebbe comunque ammortizzata la complessità a tempo costante per l'inserimento del nodo, perché il caso peggiore di O (| v |) dovrebbe essere un raro occorrenza. Non è chiaro se il grafico che hai collegato includa eventuali complessità ammortizzate.