En java, hay una interfaz de lista y un método de tamaño() para calcular el tamaño de la lista. cuando llamo a List.size(), ¿cómo cuenta? ¿se cuenta linealmente? o el recuento se determina y solo el valor se devuelve cuando size()?¿Cómo funciona Java List size()?
El tamaño se define como el número de elementos en la lista. La implementación no especifica cómo funciona la función miembro de size() (iterar sobre miembros, conteo regresado de almacenamiento, etc.), ya que List es una interfaz y no una implementación.
En general, la mayoría de las implementaciones concretas Lista almacenará su cuenta actual a nivel local, por lo que el tamaño de O (1) y no O (n)
+1 - la última frase es definitivamente cierta para las tres clases de lista de propósito general ArrayList, CopyOnWriteArrayList y LinkedList. –
java.util.List es una interfaz, no una clase. La implementación del método size() puede ser diferente para diferentes implementaciones concretas. Una implementación razonable para un método size() en una implementación java.util.List sería inicializar un miembro de instancia de tipo int a cero e incrementarlo/disminuirlo apropiadamente a medida que se agregan/eliminan elementos del List. El método size() podría simplemente devolver el miembro de instancia mencionado anteriormente. Esto es, por supuesto, simplemente un ejemplo. Para obtener detalles completos, siempre puede consultar las fuentes de las implementaciones integradas List. Todo el código fuente ha estado disponible por años.
Este es un caso en el que realmente favorecer las convenciones de nomenclatura de .NET, utilizando el prefijo de "I" para las interfaces. – dalle
@dalle: encuentro que el prefijo 'I' es un ruido húngaro. Los programadores de Java generalmente saben que 'List' (y' Map' y 'Set' y' Collection', etc.) son interfaces. Por otro lado, muchas interfaces en Java usan el sufijo 'capaz'. p.ej. 'Serializable',' Cloneable', 'Iterable', etc. Así que supongo que java tampoco es internamente coherente ... – Asaph
" Para obtener detalles completos, siempre puedes ver las fuentes de las implementaciones de lista incorporadas. " Este es un buen consejo que te servirá en tu carrera. Y a veces, si el código fuente no está disponible, incluso descompilo para obtener la respuesta. – HairOfTheDog
Pensando en 'strlen()'? –
no es lineal. es O (1). acabo de encontrar aquí http://stackoverflow.com/questions/863469/what-is-the-time-complexity-of-a-size-call-on-a-linkedlist-in-java – coder