Estructuras de datos estáticas y dinámicas en Java con ejemplos

Posted on by Rudeus Greyrat

La estructura de datos es una forma de almacenar y organizar datos de manera eficiente, de modo que las operaciones requeridas en ellos se puedan realizar de manera eficiente con respecto al tiempo y la memoria. Simplemente, la estructura de datos se usa para reducir la complejidad (principalmente la complejidad del tiempo) del código.

Las estructuras de datos pueden ser de dos tipos:

Estructura de datos estáticos

En la estructura de datos estática, el tamaño de la estructura es fijo. El contenido de la estructura de datos se puede modificar pero sin cambiar el espacio de memoria que se le asigna.

Ejemplos de estructuras de datos estáticos:

  1. Formación

    Una array es un objeto contenedor que contiene un número fijo de valores de un solo tipo. La longitud de una array se establece cuando se crea la array. Una array es un grupo de variables del mismo tipo a las que se hace referencia con un nombre común. Las arrays en Java funcionan de manera diferente a como lo hacen en C/C++.

    Sintaxis:

    // Declaration
type var-name[];
OR
type[] var-name;

// Initialization
var-name = new type [size];

    Implementación:

    // Java program to illustrate creating an array
    // of integers, puts some values in the array,
    // and prints each value to standard output.
      
    class GFG {
        public static void main(String[] args)
        {
            // declares an Array of integers.
            int[] arr;
      
            // allocating memory for 5 integers.
            arr = new int[5];
      
            // initialize the first
            // element of the array
            arr[0] = 10;
      
            // initialize the second
            // element of the array
            arr[1] = 20;
      
            // so on...
            arr[2] = 30;
            arr[3] = 40;
            arr[4] = 50;
      
            // accessing the elements
            // of the specified array
            for (int i = 0; i < arr.length; i++)
                System.out.println(
                    "Element at index "
                    + i + " : " + arr[i]);
        }
    }
    Producción:

    Element at index 0 : 10
Element at index 1 : 20
Element at index 2 : 30
Element at index 3 : 40
Element at index 4 : 50

    Problema con la implementación de la array anterior:
    una vez que creamos la array, no podemos modificar el tamaño de la array. Entonces, el tamaño de la array es inalterable.

Estructura de datos dinámica

En la estructura de datos dinámica, el tamaño de la estructura no es fijo y puede modificarse durante las operaciones realizadas en él. Las estructuras de datos dinámicas están diseñadas para facilitar el cambio de estructuras de datos en el tiempo de ejecución.

Ejemplos de estructuras de datos dinámicas:

  1. Lista de enlaces individuales

    Las listas enlazadas son estructuras de datos lineales donde los elementos no se almacenan en ubicaciones contiguas y cada elemento es un objeto separado con una parte de datos y una parte de dirección. Los elementos se vinculan mediante punteros y direcciones. Cada elemento se conoce como un Node. Debido a la dinámica y la facilidad de las inserciones y eliminaciones, son preferibles a las arrays.

    // Java code for Linked List implementation
      
    import java.util.*;
      
    public class Test {
        public static void main(String args[])
        {
            // Creating object of class linked list
            LinkedList<String> object
                = new LinkedList<String>();
      
            // Adding elements to the linked list
            object.add("A");
            object.add("B");
            object.addLast("C");
            object.addFirst("D");
            object.add(2, "E");
            object.add("F");
            object.add("G");
            System.out.println("Linked list : "
                               + object);
      
            // Removing elements from the linked list
            object.remove("B");
            object.remove(3);
            object.removeFirst();
            object.removeLast();
            System.out.println(
                "Linked list after deletion: "
                + object);
      
            // Finding elements in the linked list
            boolean status = object.contains("E");
      
            if (status)
                System.out.println(
                    "List contains the element 'E' ");
            else
                System.out.println(
                    "List doesn't contain the element 'E'");
      
            // Number of elements in the linked list
            int size = object.size();
            System.out.println(
                "Size of linked list = " + size);
      
            // Get and set elements from linked list
            Object element = object.get(2);
            System.out.println(
                "Element returned by get() : "
                + element);
            object.set(2, "Y");
            System.out.println(
                "Linked list after change : "
                + object);
        }
    }
    Producción:

    Linked list : [D, A, E, B, C, F, G]
Linked list after deletion: [A, E, F]
List contains the element 'E' 
Size of linked list = 3
Element returned by get() : F
Linked list after change : [A, E, Y]

  2. Lista doblemente enlazada

    Una lista doblemente enlazada (DLL) contiene un puntero adicional, normalmente llamado puntero anterior , junto con el siguiente puntero y los datos que están allí en una lista enlazada individualmente.

    // Java program to demonstrate DLL
      
    // Class for Doubly Linked List
    public class DLL {
        Node head; // head of list
      
        /* Doubly Linked list Node*/
        class Node {
            int data;
            Node prev;
            Node next;
      
            // Constructor to create a new node
            // next and prev is by default
            // initialized as null
            Node(int d) { data = d; }
        }
      
        // Adding a node at the front of the list
        public void push(int new_data)
        {
            /* 1. allocate node 
            * 2. put in the data */
            Node new_Node = new Node(new_data);
      
            /* 3. Make next of new node as head
            and previous as NULL */
            new_Node.next = head;
            new_Node.prev = null;
      
            /* 4. change prev of head node to new node */
            if (head != null)
                head.prev = new_Node;
      
            /* 5. move the head to point to the new node */
            head = new_Node;
        }
      
        /* Given a node as prev_node, 
        insert a new node after the given node */
        public void InsertAfter(
            Node prev_Node, int new_data)
        {
      
            /*1. check if the given
            prev_node is NULL */
            if (prev_Node == null) {
                System.out.println(
                    "The given previous node"
                    + " cannot be NULL ");
                return;
            }
      
            /* 2. allocate node 
            * 3. put in the data */
            Node new_node = new Node(new_data);
      
            /* 4. Make next of new node 
            as next of prev_node */
            new_node.next = prev_Node.next;
      
            /* 5. Make the next of
            prev_node as new_node */
            prev_Node.next = new_node;
      
            /* 6. Make prev_node as
            previous of new_node */
            new_node.prev = prev_Node;
      
            /* 7. Change previous of 
            new_node's next node */
            if (new_node.next != null)
                new_node.next.prev = new_node;
        }
      
        // Add a node at the end of the list
        void append(int new_data)
        {
            /* 1. allocate node 
            * 2. put in the data */
            Node new_node = new Node(new_data);
      
            Node last = head; /* used in step 5*/
      
            /* 3. This new node is going
            to be the last node, so 
            * make next of it as NULL*/
            new_node.next = null;
      
            /* 4. If the Linked List is empty,
            * then make the new 
            * node as head */
            if (head == null) {
                new_node.prev = null;
                head = new_node;
                return;
            }
      
            /* 5. Else traverse till
            the last node */
            while (last.next != null)
                last = last.next;
      
            /* 6. Change the next of last node */
            last.next = new_node;
      
            /* 7. Make last node as
            previous of new node */
            new_node.prev = last;
        }
      
        // This function prints contents
        // of linked list starting
        // from the given node
        public void printlist(Node node)
        {
            Node last = null;
            System.out.println(
                "Traversal in forward Direction");
            while (node != null) {
                System.out.print(node.data + " ");
                last = node;
                node = node.next;
            }
            System.out.println();
            System.out.println(
                "Traversal in reverse direction");
            while (last != null) {
                System.out.print(last.data + " ");
                last = last.prev;
            }
        }
      
        /* Driver program to test above functions*/
        public static void main(String[] args)
        {
            /* Start with the empty list */
            DLL dll = new DLL();
      
            // Insert 6. So linked list becomes 6->NULL
            dll.append(6);
      
            // Insert 7 at the beginning.
            // So linked list becomes 7->6->NULL
            dll.push(7);
      
            // Insert 1 at the beginning.
            // So linked list becomes 1->7->6->NULL
            dll.push(1);
      
            // Insert 4 at the end.
            // So linked list becomes
            // 1->7->6->4->NULL
            dll.append(4);
      
            // Insert 8, after 7.
            // So linked list becomes
            // 1->7->8->6->4->NULL
            dll.InsertAfter(dll.head.next, 8);
      
            System.out.println("Created DLL is: ");
            dll.printlist(dll.head);
        }
    }
    Producción:

    Created DLL is: 
Traversal in forward Direction
1 7 8 6 4 
Traversal in reverse direction
4 6 8 7 1

  3. Vector

    La clase Vector implementa una array creciente de objetos. Los vectores básicamente pertenecen a las clases heredadas, pero ahora son totalmente compatibles con las colecciones. Vector implementa una array dinámica que significa que puede crecer o reducirse según sea necesario. Al igual que una array, contiene componentes a los que se puede acceder mediante un índice entero.

    // Java code illustrating Vector data structure
      
    import java.util.*;
      
    class Vector_demo {
        public static void main(String[] arg)
        {
      
            // Create default vector
            Vector v = new Vector();
      
            v.add(1);
            v.add(2);
            v.add("geeks");
            v.add("forGeeks");
            v.add(3);
      
            System.out.println("Vector is " + v);
        }
    }

    Producción:

    Vector is [1, 2, geeks, forGeeks, 3]

  4. Pila

    El marco de Java Collection proporciona una clase Stack que modela e implementa una estructura de datos Stack. La clase se basa en el principio básico de último en entrar, primero en salir. Además de las operaciones básicas de inserción y extracción, la clase proporciona tres funciones más de vaciar, buscar y mirar. También se puede decir que la clase extiende Vector y trata a la clase como una pila con las cinco funciones mencionadas. La clase también puede denominarse subclase de Vector.

    // Java code for stack implementation
      
    import java.io.*;
    import java.util.*;
      
    public class stack_implementation {
        public static void main(String a[])
        {
            Stack<Integer> stack = new Stack<>();
            stack.push(1);
            stack.push(2);
            stack.push(3);
            stack.push(4);
      
            int n = stack.size();
      
            for (int i = 0; i < n; i++) {
                System.out.println(stack.pop());
            }
        }
    }
    Producción:

    4
3
2
1

    Artículos relacionados:

  5. Cola

    La interfaz Queue está disponible en el paquete java.util y amplía la interfaz Collection. La colección de colas se usa para contener los elementos a punto de ser procesados ​​y proporciona varias operaciones como la inserción, eliminación, etc. Es una lista ordenada de objetos con su uso limitado para insertar elementos al final de la lista y eliminar elementos desde el principio. de lista, es decir, sigue el FIFO o el principio First-In-First-Out.

    // Java program to demonstrate working
    // of Queue interface in Java
      
    import java.util.LinkedList;
    import java.util.Queue;
      
    public class QueueExample {
        public static void main(String[] args)
        {
            Queue<Integer> q = new LinkedList<>();
      
            // Adds elements {0, 1, 2, 3, 4} to queue
            for (int i = 0; i < 5; i++)
                q.add(i);
      
            // Display contents of the queue.
            System.out.println("Elements of queue-" + q);
      
            // To remove the head of queue.
            int removedele = q.remove();
            System.out.println("removed element-"
                               + removedele);
      
            System.out.println(q);
      
            // To view the head of queue
            int head = q.peek();
            System.out.println("head of queue-"
                               + head);
      
            // Rest all methods of collection interface,
            // Like size and contains can be
            // used with this implementation.
            int size = q.size();
            System.out.println("Size of queue-"
                               + size);
        }
    }
    Producción:

    Elements of queue-[0, 1, 2, 3, 4]
removed element-0
[1, 2, 3, 4]
head of queue-1
Size of queue-4

    Artículos relacionados:

  6. Árbol

    Un árbol es una estructura de datos que almacena valores dentro de entidades llamadas Nodes . Los Nodes están conectados a través de líneas denominadas bordes . Cada Node almacena un valor dentro de él.
    Terminología:

    • La raíz es el Node superior del árbol.
    • Padre es un Node que tiene uno o más Nodes adjuntos.
    • Edge es el enlace que une los dos Nodes.
    • Hijo es un Node que tiene un Node padre
    • Leaf es un Node que no tiene ningún Node secundario adjunto, es el Node inferior de un árbol.

    // Java program for different tree traversals
      
    /* Class containing left and right child of current 
    node and key value*/
    class Node {
        int key;
        Node left, right;
      
        public Node(int item)
        {
            key = item;
            left = right = null;
        }
    }
      
    class BinaryTree {
        // Root of Binary Tree
        Node root;
      
        BinaryTree()
        {
            root = null;
        }
      
        /* Given a binary tree, print
        its nodes according to the 
        "bottom-up" postorder traversal. */
        void printPostorder(Node node)
        {
            if (node == null)
                return;
      
            // first recur on left subtree
            printPostorder(node.left);
      
            // then recur on right subtree
            printPostorder(node.right);
      
            // now deal with the node
            System.out.print(node.key + " ");
        }
      
        /* Given a binary tree, 
        print its nodes in inorder*/
        void printInorder(Node node)
        {
            if (node == null)
                return;
      
            /* first recur on left child */
            printInorder(node.left);
      
            /* then print the data of node */
            System.out.print(node.key + " ");
      
            /* now recur on right child */
            printInorder(node.right);
        }
      
        /* Given a binary tree,
        print its nodes in preorder*/
        void printPreorder(Node node)
        {
            if (node == null)
                return;
      
            /* first print data of node */
            System.out.print(node.key + " ");
      
            /* then recur on left sutree */
            printPreorder(node.left);
      
            /* now recur on right subtree */
            printPreorder(node.right);
        }
      
        // Wrappers over above recursive functions
        void printPostorder() { printPostorder(root); }
        void printInorder() { printInorder(root); }
        void printPreorder() { printPreorder(root); }
      
        // Driver method
        public static void main(String[] args)
        {
            BinaryTree tree = new BinaryTree();
            tree.root = new Node(1);
            tree.root.left = new Node(2);
            tree.root.right = new Node(3);
            tree.root.left.left = new Node(4);
            tree.root.left.right = new Node(5);
      
            System.out.println(
                "Preorder traversal of binary tree is ");
            tree.printPreorder();
      
            System.out.println(
                "\nInorder traversal of binary tree is ");
            tree.printInorder();
      
            System.out.println(
                "\nPostorder traversal of binary tree is ");
            tree.printPostorder();
        }
    }
    Producción:

    Preorder traversal of binary tree is
1 2 4 5 3 
Inorder traversal of binary tree is
4 2 5 1 3 
Postorder traversal of binary tree is
4 5 2 3 1

Publicación traducida automáticamente

Artículo escrito por meghsat 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 *