¿Cómo funcionan las arrays dinámicas?

Una array dinámica ( vector en C++ , ArrayList en Java) crece automáticamente cuando intentamos hacer una inserción y no queda más espacio para el nuevo elemento. Por lo general, el área se duplica en tamaño. Se puede construir una array dinámica simple asignando una array de tamaño fijo, generalmente mayor que la cantidad de elementos que se requieren de inmediato. Los elementos de la array dinámica se almacenan de forma contigua al comienzo de la array subyacente, y las posiciones restantes hacia el final de la array subyacente se reservan o no se utilizan. Los elementos se pueden agregar al final de una array dinámica en tiempo constante utilizando el espacio reservado hasta que este espacio se consuma por completo. Cuando se consume todo el espacio y se va a agregar un elemento adicional, se debe aumentar el tamaño de la array de tamaño fijo subyacente.Enfoque: cuando ingresamos un elemento en la array pero la array está llena, entonces crea una función, esta función crea una nueva array de tamaño doble o como desee y copia todos los elementos de la array anterior a una nueva array y devuelve esta nueva array. Además, podemos reducir el tamaño de la array. y agregue un elemento en una posición determinada, elimine el elemento al final por defecto y también en la posición.

Características clave de array dinámica

Agregar elemento: agregue un elemento al final si el tamaño de la array no es suficiente, luego extienda el tamaño de la array y agregue un elemento al final de la array original, así como el índice dado. Hacer todo ese copiado toma O(n) tiempo, donde n es el número de elementos en nuestra array. Eso es un costo costoso para un anexo. En una array de longitud fija, los agregados solo toman O(1) tiempo. Pero los anexos toman tiempo O(n) solo cuando los insertamos en una array completa. Y eso es bastante raro, especialmente si duplicamos el tamaño de la array cada vez que nos quedamos sin espacio. Entonces, en la mayoría de los casos, agregar sigue siendo el tiempo O (1) y, a veces, es el tiempo O (n). En una array dinámica, puede crear una array de tamaño fijo cuando sea necesario, agregue más elementos en la array y luego use este enfoque: Eliminar elemento:Elimine un elemento de la array, el método predeterminado remove() elimine un elemento del final, simplemente almacene cero en el último índice y también elimine el elemento en el índice específico llamando al método removeAt (i) donde i es el índice. El método removeAt(i) cambia todo el elemento derecho en el lado izquierdo del índice dado. Cambiar el tamaño del tamaño de la array: cuando la array tiene datos nulos/cero (aparte de un elemento agregado por usted) en el lado derecho de la array, lo que significa que tiene memoria sin usar, el método shrinkSize() puede liberar la memoria adicional. Cuando se consume todo el espacio y se debe agregar un elemento adicional, entonces la array de tamaño fijo subyacente debe aumentar de tamaño. Por lo general, cambiar el tamaño es costoso porque tiene que asignar una array más grande y copiar todos los elementos de la array que ha superado antes de que finalmente podamos agregar nuestro elemento. Código simple para array dinámica. En el siguiente código, la array se llenará de tamaño. Copiamos todos los elementos en una nueva array de tamaño doble (array de tamaño variable). El código de muestra se encuentra a continuación. 

Java

// Java program deals with all operation of a dynamic array
// add, remove, resize memory of array is the main feature
public class DynamicArray {
 
    // create three variable array[] is a array,
    // count will deal with no of element add by you and
    // size will with size of array[]
    private int array[];
    private int count;
    private int size;
    // constructor initialize value to variable
 
    public DynamicArray()
    {
        array = new int[1];
        count = 0;
        size = 1;
    }
    // function add an element at the end of array
 
    public void add(int data)
    {
 
        // check no of element is equql to size of array
        if (count == size) {
            growSize(); // make array size double
        } // insert element at end of array
        array[count] = data;
        count++;
    }
 
    // function makes size double of array
    public void growSize()
    {
 
        int temp[] = null;
        if (count == size) {
 
            // temp is a double size array of array
            // and store array elements
            temp = new int[size * 2];
            {
                for (int i = 0; i < size; i++) {
                    // copy all array value into temp
                    temp[i] = array[i];
                }
            }
        }
 
        // double size array temp initialize
        // into variable array again
        array = temp;
        
        // and make size is double also of array
        size = size * 2;
    }
 
    // function shrink size of array
    // which block unnecessary remove them
    public void shrinkSize()
    {
        int temp[] = null;
        if (count > 0) {
 
            // temp is a count size array
            // and store array elements
            temp = new int[count];
            for (int i = 0; i < count; i++) {
 
                // copy all array value into temp
                temp[i] = array[i];
            }
 
            size = count;
 
            // count size array temp initialize
            // into variable array again
            array = temp;
        }
    }
    // function add an element at given index
 
    public void addAt(int index, int data)
    {
        // if size is not enough make size double
        if (count == size) {
            growSize();
        }
 
        for (int i = count - 1; i >= index; i--) {
 
            // shift all element right
            // from given index
            array[i + 1] = array[i];
        }
 
        // insert data at given index
        array[index] = data;
        count++;
    }
 
    // function remove last element or put
    // zero at last index
    public void remove()
    {
        if (count > 0) {
            array[count - 1] = 0;
            count--;
        }
    }
 
    // function shift all element of right
    // side from given index in left
    public void removeAt(int index)
    {
        if (count > 0) {
            for (int i = index; i < count - 1; i++) {
 
                // shift all element of right
                // side from given index in left
                array[i] = array[i + 1];
            }
            array[count - 1] = 0;
            count--;
        }
    }
 
    public static void main(String[] args)
    {
        DynamicArray da = new DynamicArray();
 
        // add 9 elements in array
        da.add(1);
        da.add(2);
        da.add(3);
        da.add(4);
        da.add(5);
        da.add(6);
        da.add(7);
        da.add(8);
        da.add(9);
 
        // print all array elements after add 9 elements
        System.out.println("Elements of array:");
        for (int i = 0; i < da.size; i++) {
            System.out.print(da.array[i] + " ");
        }
 
        System.out.println();
 
        // print size of array and no of element
        System.out.println("Size of array: " + da.size);
        System.out.println("No of elements in array: " +
                                              da.count);
 
        // shrinkSize of array
        da.shrinkSize();
 
        // print all array elements
        System.out.println("Elements of array "+
                   "after shrinkSize of array:");
        for (int i = 0; i < da.size; i++) {
            System.out.print(da.array[i] + " ");
        }
        System.out.println();
 
        // print size of array and no of element
        System.out.println("Size of array: " + da.size);
        System.out.println("No of elements in array: " +
                                               da.count);
 
        // add an element at index 1
        da.addAt(1, 22);
 
        // print Elements of array after adding an
        // element at index 1
        System.out.println("Elements of array after" +
                      " add an element at index 1:");
        for (int i = 0; i < da.size; i++) {
            System.out.print(da.array[i] + " ");
        }
 
        System.out.println();
 
        // print size of array and no of element
        System.out.println("Size of array: " + da.size);
        System.out.println("No of elements in array: " +
                                               da.count);
 
        // delete last element
        da.remove();
 
        // print Elements of array after delete last
        // element
        System.out.println("Elements of array after" +
                              " delete last element:");
        for (int i = 0; i < da.size; i++) {
            System.out.print(da.array[i] + " ");
        }
 
        System.out.println();
 
        // print size of array and no of element
        System.out.println("Size of array: " + da.size);
        System.out.println("No of elements in array: " +
                                              da.count);
 
        // delete element at index 1
        da.removeAt(1);
 
        // print Elements of array after delete
        // an element index 1
        System.out.println("Elements of array after"+
                      " delete element at index 1:");
        for (int i = 0; i < da.size; i++) {
            System.out.print(da.array[i] + " ");
        }
        System.out.println();
 
        // print size of array and no of element
        System.out.println("Size of array: " + da.size);
        System.out.println("No of elements in array: " +
                                               da.count);
    }
}

C#

// C# program deals with all operation
// of dynamic array add, remove, resize
// memory of array is the main feature
using System;
 
public class DynamicArray
{
 
    // create three variable array[] is
    // a array, count will deal with no
    // of element add by you and
    // size will with size of array[]
    private int []array;
    private int count;
    private int size;
     
    // constructor initialize value to variable
    public DynamicArray()
    {
        array = new int[1];
        count = 0;
        size = 1;
    }
 
    // function add an element at the end of array
    public void add(int data)
    {
 
        // check no of element is equql to size of array
        if (count == size)
        {
            growSize(); // make array size double
        }
         
        // insert element at end of array
        array[count] = data;
        count++;
    }
 
    // function makes size double of array
    public void growSize()
    {
 
        int []temp = null;
        if (count == size)
        {
 
            // temp is a double size array of array
            // and store array elements
            temp = new int[size * 2];
            {
                for (int i = 0; i < size; i++)
                {
                    // copy all array value into temp
                    temp[i] = array[i];
                }
            }
        }
 
        // double size array temp initialize
        // into variable array again
        array = temp;
         
        // and make size is double also of array
        size = size * 2;
    }
 
    // function shrink size of array
    // which block unnecessary remove them
    public void shrinkSize()
    {
        int []temp = null;
        if (count > 0)
        {
 
            // temp is a count size array
            // and store array elements
            temp = new int[count];
            for (int i = 0; i < count; i++)
            {
 
                // copy all array value into temp
                temp[i] = array[i];
            }
 
            size = count;
 
            // count size array temp initialize
            // into variable array again
            array = temp;
        }
    }
     
    // function add an element at given index
    public void addAt(int index, int data)
    {
        // if size is not enough make size double
        if (count == size)
        {
            growSize();
        }
 
        for (int i = count - 1; i >= index; i--)
        {
 
            // shift all element right
            // from given index
            array[i + 1] = array[i];
        }
 
        // insert data at given index
        array[index] = data;
        count++;
    }
 
    // function remove last element or put
    // zero at last index
    public void remove()
    {
        if (count > 0)
        {
            array[count - 1] = 0;
            count--;
        }
    }
 
    // function shift all element of right
    // side from given index in left
    public void removeAt(int index)
    {
        if (count > 0)
        {
            for (int i = index; i < count - 1; i++)
            {
 
                // shift all element of right
                // side from given index in left
                array[i] = array[i + 1];
            }
            array[count - 1] = 0;
            count--;
        }
    }
 
    // Driver code
    public static void Main()
    {
        DynamicArray da = new DynamicArray();
 
        // add 9 elements in array
        da.add(1);
        da.add(2);
        da.add(3);
        da.add(4);
        da.add(5);
        da.add(6);
        da.add(7);
        da.add(8);
        da.add(9);
 
        // print all array elements after add 9 elements
        Console.WriteLine("Elements of array:");
        for (int i = 0; i < da.size; i++)
        {
            Console.Write(da.array[i] + " ");
        }
 
        Console.WriteLine();
 
        // print size of array and no of element
        Console.WriteLine("Size of array: " + da.size);
        Console.WriteLine("No of elements in array: " +
                                            da.count);
 
        // shrinkSize of array
        da.shrinkSize();
 
        // print all array elements
        Console.WriteLine("Elements of array "+
                "after shrinkSize of array:");
        for (int i = 0; i < da.size; i++)
        {
            Console.Write(da.array[i] + " ");
        }
        Console.WriteLine();
 
        // print size of array and no of element
        Console.WriteLine("Size of array: " + da.size);
        Console.WriteLine("No of elements in array: " +
                                            da.count);
 
        // add an element at index 1
        da.addAt(1, 22);
 
        // print Elements of array after adding an
        // element at index 1
        Console.WriteLine("Elements of array after" +
                    " add an element at index 1:");
        for (int i = 0; i < da.size; i++)
        {
            Console.Write(da.array[i] + " ");
        }
 
        Console.WriteLine();
 
        // print size of array and no of element
        Console.WriteLine("Size of array: " + da.size);
        Console.WriteLine("No of elements in array: " +
                                            da.count);
 
        // delete last element
        da.remove();
 
        // print Elements of array after delete last
        // element
        Console.WriteLine("Elements of array after" +
                            " delete last element:");
        for (int i = 0; i < da.size; i++)
        {
            Console.Write(da.array[i] + " ");
        }
 
        Console.WriteLine();
 
        // print size of array and no of element
        Console.WriteLine("Size of array: " + da.size);
        Console.WriteLine("No of elements in array: " +
                                            da.count);
 
        // delete element at index 1
        da.removeAt(1);
 
        // print Elements of array after delete
        // an element index 1
        Console.WriteLine("Elements of array after"+
                    " delete element at index 1:");
        for (int i = 0; i < da.size; i++)
        {
            Console.Write(da.array[i] + " ");
        }
        Console.WriteLine();
 
        // print size of array and no of element
        Console.WriteLine("Size of array: " + da.size);
        Console.WriteLine("No of elements in array: " +
                                            da.count);
    }
}
 
/* This code contributed by PrinciRaj1992 */
Producción:

Elements of array:
1 2 3 4 5 6 7 8 9 0 0 0 0 0 0 0 
Size of array: 16
No of elements in array: 9
Elements of array after shrinkSize of array:
1 2 3 4 5 6 7 8 9 
Size of array: 9
No of elements in array: 9
Elements of array after add an element at index 1:
1 22 2 3 4 5 6 7 8 9 0 0 0 0 0 0 0 0 
Size of array: 18
No of elements in array: 10
Elements of array after delete last element:
1 22 2 3 4 5 6 7 8 0 0 0 0 0 0 0 0 0 
Size of array: 18
No of elements in array: 9
Elements of array after delete element at index 1:
1 2 3 4 5 6 7 8 0 0 0 0 0 0 0 0 0 0 
Size of array: 18
No of elements in array: 8

Publicación traducida automáticamente

Artículo escrito por Rajput-Ji y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *