Share
A veces desea el tamaño flexible y la facilidad de uso de una lista enlazada pero necesita tener la indexación directa (tiempo constante) de una matriz. En estos casos, un Lista de arreglo puede proporcionar un término medio razonable.
Lista de arreglo Es una colección que implementa el IList interfaz pero está respaldado por una matriz en lugar de una lista vinculada. Al igual que una lista vinculada, se puede agregar un número arbitrario de elementos (limitado solo por la memoria disponible), pero se comportan como una matriz en todos los demás aspectos.
La clase ArrayList implementa la IList interfaz. IList proporciona todos los métodos y propiedades de ICollection Al mismo tiempo que se agrega indexación directa e inserción y eliminación basadas en índices. El siguiente código de ejemplo incluye stubs generados al usar el comando Implement Interface de Visual Studio 2010.
El siguiente ejemplo de código también incluye tres adiciones a los apéndices generados:
Accentsconagua
T (_items). Esta matriz mantendrá los elementos de la colección..Lista de arreglo clase para minimizar el número de veces que la matriz interna necesita ser reasignada.clase pública ArrayList: System.Collections.Generic.IList T [] _items; ArrayList pública (): este (0) ArrayList pública (longitud int) if (longitud < 0) throw new ArgumentException("length"); _items = new T[length]; public int IndexOf(T item) throw new NotImplementedException(); public void Insert(int index, T item) throw new NotImplementedException(); public void RemoveAt(int index) throw new NotImplementedException(); public T this[int index] get throw new NotImplementedException(); set throw new NotImplementedException(); public void Add(T item) throw new NotImplementedException(); public void Clear() throw new NotImplementedException(); public bool Contains(T item) throw new NotImplementedException(); public void CopyTo(T[] array, int arrayIndex) throw new NotImplementedException(); public int Count get throw new NotImplementedException(); public bool IsReadOnly get throw new NotImplementedException(); public bool Remove(T item) throw new NotImplementedException(); public System.Collections.Generic.IEnumerator GetEnumerator() throw new NotImplementedException(); System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() throw new NotImplementedException(); Agregar un artículo a un Lista de arreglo es donde realmente se muestra la diferencia entre la matriz y la lista enlazada. Hay dos razones para esto. La primera es que un Lista de arreglo admite la inserción de valores en el centro de la colección, mientras que una lista vinculada admite agregar elementos al principio o al final de la lista. La segunda es que agregar un elemento a una lista vinculada siempre es una operación O (1), pero agregar elementos a una lista enlazada Lista de arreglo es una operación O (1) o una operación O (n).
A medida que se agregan elementos a la colección, eventualmente la matriz interna puede llenarse. Cuando esto sucede, se debe hacer lo siguiente:
La única pregunta que debemos responder en este momento es en qué tamaño debería convertirse la nueva matriz. La respuesta a esta pregunta está definida por la Lista de arreglo política de crecimiento.
Veremos dos políticas de crecimiento y, para cada una, veremos qué tan rápido crece la matriz y cómo puede afectar el rendimiento..
Hay dos implementaciones de la Lista de arreglo Clase que podemos ver en línea: Mono y Rotor. Ambos utilizan un algoritmo simple que duplica el tamaño de la matriz cada vez que se necesita una asignación. Si la matriz tiene un tamaño de cero, la capacidad predeterminada es 16. El algoritmo es:
tamaño = tamaño == 0? 1: tamaño * 2;
Este algoritmo tiene menos asignaciones y copias de matriz, pero desperdicia más espacio en promedio que el enfoque de Java. En otras palabras, está sesgado hacia tener más inserciones O (1), lo que debería reducir el número de veces que la colección realiza la operación de asignación y copia que consume tiempo. Esto viene a costa de una huella de memoria promedio más grande y, en promedio, más ranuras de matriz vacía.
Java usa un enfoque similar pero hace crecer la matriz un poco más lentamente. El algoritmo que utiliza para hacer crecer la matriz es:
tamaño = (tamaño * 3) / 2 + 1;
Este algoritmo tiene una curva de crecimiento más lenta, lo que significa que está orientado hacia una menor sobrecarga de memoria al costo de más asignaciones. Veamos la curva de crecimiento de estos dos algoritmos para una Lista de arreglo Con más de 200,000 artículos agregados..
La curva de crecimiento para Mono / Rotor versus Java para más de 200,000 artículos En este gráfico se puede ver que se necesitaron 19 asignaciones para que el algoritmo de duplicación cruzara el límite de 200,000, mientras que las asignaciones del algoritmo más lento (Java) 30 llegaron al mismo punto.
Entonces, ¿cuál es la correcta? No hay respuesta correcta o incorrecta. La duplicación realiza menos operaciones O (n), pero tiene una mayor sobrecarga de memoria en promedio. El algoritmo de crecimiento más lento realiza más operaciones O (n) pero tiene menos sobrecarga de memoria. Para una colección de propósito general, cualquiera de los dos enfoques es aceptable. Su dominio de problemas puede tener requisitos específicos que hacen que uno sea más atractivo, o puede requerir que cree otro enfoque por completo. Independientemente del enfoque que adopte, los comportamientos fundamentales de la colección se mantendrán sin cambios..
Nuestro Lista de arreglo clase utilizará el enfoque de duplicación (Mono / Rotor).
private void GrowArray () int newLength = _items.Length == 0? 16: _items.Length << 1; T[] newArray = new T[newLength]; _items.CopyTo(newArray, 0); _items = newArray;
| Comportamiento | Agrega el valor proporcionado en el índice especificado en la colección. Si el índice especificado es igual o mayor que Contar, se lanza una excepción |
| Actuación | En) |
Insertar en un índice específico requiere desplazar todos los elementos después del punto de inserción a la derecha en uno. Si la matriz de respaldo está llena, tendrá que crecer antes de que se pueda realizar el cambio.
En el siguiente ejemplo, hay una matriz con una capacidad de cinco elementos, cuatro de los cuales están en uso. El valor tres se insertará como el tercer elemento en la matriz (índice dos).
La matriz antes de la inserción (una ranura abierta al final) 
La matriz después de desplazarse a la derecha 
La matriz con el nuevo elemento agregado en la ranura abierta Public void Insert (int index, T item) if (index> = Count) lanza una nueva IndexOutOfRangeException (); if (_items.Length == this.Count) this.GrowArray (); // Mueve todos los elementos siguiendo el índice una ranura a la derecha. Array.Copy (_items, index, _items, index + 1, Count - index); _items [index] = item; Cuenta ++;
| Comportamiento | Anexa el valor proporcionado al final de la colección.. |
| Actuación | O (1) cuando la capacidad del array es mayor que Count; O (n) cuando el crecimiento es necesario. |
public void Add (T item) if (_items.Length == Count) GrowArray (); _items [Count ++] = item;
| Comportamiento | Elimina el valor en el índice especificado. |
| Actuación | En) |
La eliminación en un índice es esencialmente lo contrario de la operación de inserción. El elemento se elimina de la matriz y la matriz se desplaza hacia la izquierda.
La matriz antes de que se elimine el valor 3 
La matriz con el valor 3 eliminado 
La matriz se desplazó hacia la izquierda, liberando la última ranura public void RemoveAt (int index) if (index> = Count) arroja una nueva IndexOutOfRangeException (); int shiftStart = index + 1; si (shiftstart < Count) // Shift all the items following index one slot to the left. Array.Copy(_items, shiftStart, _items, index, Count - shiftStart); Count--;
| Comportamiento | Elimina el primer elemento de la colección cuyo valor coincide con el valor proporcionado. Devoluciones cierto si un valor fue eliminado. De lo contrario vuelve falso. |
| Actuación | En) |
public bool Remove (T item) for (int i = 0; i < Count; i++) if (_items[i].Equals(item)) RemoveAt(i); return true; return false;
| Comportamiento | Devuelve el primer índice en la colección cuyo valor es igual al valor proporcionado. Devuelve -1 si no se encuentra un valor coincidente. |
| Actuación | En) |
public int IndexOf (elemento T) para (int i = 0; i < Count; i++) if (_items[i].Equals(item)) return i; return -1;
| Comportamiento | Obtiene o establece el valor en el índice especificado.. |
| Actuación | O (1) |
public T this [int index] get if (index < Count) return _items[index]; throw new IndexOutOfRangeException(); set if (index < Count) _items[index] = value; else throw new IndexOutOfRangeException();
| Comportamiento | Devuelve verdadero si el valor proporcionado existe en la colección. De lo contrario, devuelve falso.. |
| Actuación | En) |
public bool Contiene (elemento T) return IndexOf (item)! = -1;
| Comportamiento | Devuelve un IEnumerador instancia que permite enumerar los valores de la lista de arreglos en orden de primero a último. |
| Actuación | Devolver la instancia del enumerador es una operación O (1). Enumerar cada elemento es una operación O (n). |
Tenga en cuenta que no podemos simplemente diferir a la _artículos array's GetEnumerator porque eso también devolvería los elementos que actualmente no están llenos de datos.
System.Collections.Generic.IEnumerator público GetEnumerator () for (int i = 0; i < Count; i++) yield return _items[i]; System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() return GetEnumerator();
| Comportamiento | Elimina todos los elementos de la lista de matriz. |
| Actuación | O (1) |
Hay dos opciones al implementar Claro. La matriz se puede dejar sola o se puede reasignar como una matriz de longitud 0. Esta implementación reasigna una nueva matriz con una longitud de cero. Se asignará una matriz más grande cuando se agregue un elemento a la matriz usando el Añadir o Insertar metodos.
Public void Clear () _items = new T [0]; Cuenta = 0;
| Comportamiento | Copia el contenido de la matriz interna de principio a fin en la matriz proporcionada comenzando en el índice de matriz especificado. |
| Actuación | En) |
Tenga en cuenta que el método no se limita simplemente a _artículos array's Copiar a método. Esto se debe a que solo queremos copiar el rango desde el índice 0 a Contar, no toda la capacidad del array. Utilizando Array.Copia nos permite especificar el número de elementos a copiar.
public void CopyTo (T [] array, int arrayIndex) Array.Copy (_items, 0, array, arrayIndex, Count);
| Comportamiento | Devuelve un entero que indica la cantidad de elementos que hay actualmente en la colección. Cuando la lista está vacía, el valor es 0. |
| Actuación | O (1) |
Contar es simplemente una propiedad implementada automáticamente con un captador público y un configurador privado. El comportamiento real ocurre en las funciones que manipulan los contenidos de la colección..
public int Count get; conjunto privado
| Comportamiento | Devuelve false porque la colección no es de solo lectura. |
| Actuación | O (1) |
public bool IsReadOnly get return false;
