La tarea dada es implementar una clase en Java que se comporte como la array dinámica usando ArrayList .
ArrayList es igual que los arreglos dinámicos con la capacidad de cambiar su tamaño automáticamente cuando se inserta o elimina un elemento, y el contenedor maneja automáticamente su almacenamiento.
- Los elementos de ArrayList se colocan en almacenamiento contiguo para que se pueda acceder a ellos y recorrerlos mediante iteradores .
- En ArrayList, los datos se insertan al final.
- Insertar al final toma un tiempo diferencial, ya que a veces puede ser necesario extender la array.
- Eliminar el último elemento lleva solo un tiempo constante porque no se cambia el tamaño.
- Insertar y borrar al principio o en el medio es lineal en el tiempo.
Funciones a implementar en la clase de array dinámica:
Ciertas funciones asociadas al ArrayList que implementaremos son:
- void push(int data) : Esta función toma un elemento y lo inserta en el último. La complejidad del tiempo amortizado es O(1) .
- void push(int data, int index): Inserta datos en el índice especificado. La complejidad del tiempo es O(1) .
- int get(int index): Se utiliza para obtener el elemento en el índice especificado. La complejidad del tiempo es O(1) .
- void pop(): Elimina el último elemento. La complejidad del tiempo es O(1) .
- int size(): Devuelve el tamaño de ArrayList, es decir, el número de elementos en ArrayList. La complejidad del tiempo es O(1) .
- int getcapacity(): Devuelve la capacidad del ArrayList. La complejidad del tiempo es O(1) .
- void print(): se utiliza para imprimir elementos de array. La complejidad del tiempo es O(N) , donde N es el tamaño de ArrayList.
Implementación de la clase de array dinámica:
A continuación se muestra la implementación de nuestra propia clase ArrayList.
// Java program to implement // our own Dynamic Array class import java.util.*; // Self implementation of // the ArrayList Class in Java class ArrayListClass { // arr is the array which stores // our ArrayList elements private int arr[]; // capacity is the total storage // capacity of the ArrayList private int capacity; // current is the number of elements // currently present in the ArrayList private int current; // Default constructor to initialise // an initial capacity of 1 element and // allocating storage using dynamic allocation public ArrayListClass() { arr = new int[1]; capacity = 1; current = 0; } // Function to add an element at the last public void push(int data) { // if the number of elements // is equal to the capacity, // that means we don't have space // to accommodate more elements. // We need to double the capacity if (current == capacity) { int temp[] = new int[2 * capacity]; // copying old array elements // to new array for (int i = 0; i < capacity; i++) temp[i] = arr[i]; capacity *= 2; arr = temp; } // Inserting data arr[current] = data; current++; } // function to add element at any index void push(int data, int index) { // if index is equal to capacity // then this function is same // as push defined above if (index == capacity) push(data); else arr[index] = data; } // Function to extract // element at any index int get(int index) { // if index is within the range if (index < current) return arr[index]; // if index is outside the range return -1; } // function to delete last element void pop() { current--; } // function to get size // of the ArrayList int size() { return current; } // function to get capacity // of the ArrayList int getcapacity() { return capacity; } // function to print ArrayList elements void print() { for (int i = 0; i < current; i++) { System.out.print(arr[i] + " "); } System.out.println(); } // Driver program to check ArrayListClass public static void main(String args[]) { ArrayListClass v = new ArrayListClass(); v.push(10); v.push(20); v.push(30); v.push(40); v.push(50); System.out.println("ArrayList size: " + v.size()); System.out.println( "ArrayList capacity: " + v.getcapacity()); System.out.println( "ArrayList elements: "); v.print(); v.push(100, 1); System.out.println( "\nAfter updating 1st index"); System.out.println( "ArrayList elements: "); v.print(); System.out.println( "Element at 1st index: " + v.get(1)); v.pop(); System.out.println( "\nAfter deleting the" + " last element"); System.out.println( "ArrayList size: " + v.size()); System.out.println( "ArrayList capacity: " + v.getcapacity()); System.out.println( "ArrayList elements: "); v.print(); } }
Producción:
ArrayList size: 5 ArrayList capacity: 8 ArrayList elements: 10 20 30 40 50 After updating 1st index ArrayList elements: 10 100 30 40 50 Element at 1st index: 100 After deleting the last element ArrayList size: 4 ArrayList capacity: 8 ArrayList elements: 10 100 30 40