Principales estructuras de datos y algoritmos en Java que necesita saber

Si tuviera que elegir el tema más importante en el desarrollo de software, serían las estructuras de datos y los algoritmos. Puede pensar en ella como la herramienta fundamental disponible para todo programador de computadoras. Mientras programamos, usamos estructuras de datos para almacenar y organizar datos, y algoritmos para manipular los datos en esas estructuras. Este artículo contiene una revisión detallada de todas las estructuras de datos y algoritmos comunes en para permitir que los lectores estén bien equipados.

A continuación se enumeran los temas que se tratan en este artículo:

• Estructuras de datos en Java
  • Estructuras de datos lineales
  • Estructuras de datos jerárquicas
• Algoritmos en Java
  • Algoritmos de clasificación
  • Algoritmos de búsqueda

Estructuras de datos en Java

Una estructura de datos es una forma de almacenar y organizar datos en una computadora para que se puedan usar de manera eficiente. Proporciona un medio para administrar grandes cantidades de datos de manera eficiente. Y las estructuras de datos eficientes son clave para diseñar algoritmos eficientes.

EnEn este artículo 'Estructuras de datos y algoritmos en Java', vamos a cubrir estructuras de datos básicas como:

• Estructuras de datos lineales
  • Lista enlazada
  • Pilas
  • Colas

• Estructuras de datos jerárquicas
  • Árboles binarios
  • Muchísimo
  • Tablas hash

Echemos un vistazo a cada uno de ellos.

Estructuras de datos lineales en Java

Estructuras de datos lineales en son aquellos cuyos elementos son secuenciales y ordenados de tal manera que: solo hay una primer elemento y tiene solo uno siguiente elemento , sólo hay uno último elemento y tiene solo uno elemento anterior , mientras que todos los demás elementos tienen un Siguiente y un anterior elemento.

Matrices

Un formación es una estructura de datos linealque representa un grupo de elementos similares, a los que se accede por índice. Se debe proporcionar el tamaño de una matriz antes de almacenar datos. A continuación se enumeran las propiedades de una matriz:

• Cada elemento de una matriz es del mismo tipo de datos y tiene el mismo tamaño
• Los elementos de la matriz se almacenan en ubicaciones de memoria contiguas con el primer elemento comenzando en la ubicación de memoria más pequeña
• Se puede acceder de forma aleatoria a los elementos de la matriz
• La estructura de datos de la matriz no es completamente dinámica

Por ejemplo , es posible que deseemos que un videojuego lleve un registro de las diez mejores puntuaciones de ese juego. En lugar de utilizar diez diferentes variables para esta tarea, podríamos usar un solo nombre para todo el grupo y usar números de índice para referirnos a los puntajes más altos en ese grupo.

Lista enlazada

A es una estructura de datos lineal con la colección de múltiples nodos, donde eCada elemento almacena sus propios datos y un puntero a la ubicación del siguiente elemento. El último eslabón de una lista vinculada apunta a nulo, lo que indica el final de la cadena. Un elemento en una lista enlazada se llama nodo . El primer nodo se llama cabeza .El último nodo se llamala cola .

Tipos de lista vinculada

Lista vinculada individualmente (unidireccional)

Lista doblemente enlazada (bidireccional)

Lista enlazada circular

cómo encontrar la longitud de una matriz en javascript

Aquí tienes un ejemplo simple: Imagínese una lista enlazada como una cadena de clips que están enlazados entre sí. Puede agregar fácilmente otro clip en la parte superior o inferior. Incluso es rápido insertar uno en el medio. Todo lo que tiene que hacer es simplemente desconectar la cadena en el medio, agregar el nuevo clip y luego volver a conectar la otra mitad. Una lista vinculada es similar.

Pilas

Apilar, una estructura de datos abstracta, es una colección de objetos que se insertan y quitan de acuerdo con el último en entrar, primero en salir (LIFO) principio. Los objetos se pueden insertar en una pila en cualquier momento, pero solo el objeto insertado más recientemente (es decir, el 'último') objeto se puede eliminar en cualquier momento.A continuación se enumeran las propiedades de una pila:

• Es una lista ordenada en la queLa inserción y la eliminación se pueden realizar solo en un extremo que se llama parte superior
• Estructura de datos recursiva con un puntero a su elemento superior
• Sigue el último en entrar, primero en salir (LIFO) principio
• Admite dos métodos más fundamentales
  • empujar (e): inserta el elemento e, en la parte superior de la pila
  • pop (): elimina y devuelve el elemento superior de la pila

Ejemplos prácticos de la pila incluyen cuando se invierte una palabra,para comprobar la exactitud de paréntesissecuencia,implementar la funcionalidad de retroceso en los navegadores y muchos más.

Colas

son también otro tipo de estructura de datos abstracta. A diferencia de una pila, la cola es una colección de objetos que se insertan y eliminan de acuerdo con primero en entrar, primero en salir (FIFO) principio. Es decir, los elementos se pueden insertar en cualquier momento, pero solo el elemento que ha estado en la cola por más tiempo se puede eliminar en cualquier momento.A continuación se enumeran las propiedades de una cola:

• A menudo conocido como el primero en entrar primero en salir lista
• Admite dos métodos más fundamentales
  • enqueue (e): inserte el elemento e, en el posterior de la cola
  • dequeue (): elimina y devuelve el elemento del frente de la cola

Las colas se utilizan en eltransferencia asincrónica de datos entre dos procesos, programación de CPU, programación de disco y otras situaciones en las que los recursos se comparten entre varios usuarios y se atienden por orden de llegada. A continuación, en este artículo 'Estructuras de datos y algoritmos en Java', tenemos estructuras de datos jerárquicas.

Estructuras de datos jerárquicas en Java

Árbol binario

El árbol binario es unestructuras de datos de árbol jerárquico en las que cada nodo tiene como máximo dos hijos , que se conocen como hijo dejado y el niño correcto . Cada árbol binario tiene los siguientes grupos de nodos:

• Nodo raíz: es el nodo superior y, a menudo, se lo denomina nodo principal.porque se puede acceder a todos los demás nodos desde la raíz
• Subárbol izquierdo, que también es un árbol binario
• Subárbol derecho, que también es un árbol binario

A continuación se enumeran las propiedades de un árbol binario:

• Un árbol binario se puede recorrer de dos formas:
  • Profundidad primer recorrido : En orden (izquierda-raíz-derecha), preorden (raíz-izquierda-derecha) y posorden (izquierda-derecha-raíz)
  • Ancho primer recorrido : Cruce de orden de nivel
• Complejidad temporal del recorrido del árbol: O (n)
• El número máximo de nodos en el nivel 'l' = 2^l-1.

Las aplicaciones de árboles binarios incluyen:

• Se utiliza en muchas aplicaciones de búsqueda donde los datos entran / salen constantemente
• Como flujo de trabajo para la composición de imágenes digitales para efectos visuales
• Se utiliza en casi todos los enrutadores de gran ancho de banda para almacenar tablas de enrutadores
• También se utiliza en redes inalámbricas y asignación de memoria.
• Utilizado en algoritmos de compresión y muchos más

Montón binario

Binary Heap es un completoárbol binario, que responde a la propiedad del montón. En términos simpleses una variación de un árbol binario con las siguientes propiedades:

• Heap es un árbol binario completo: Se dice que un árbol está completo si todos sus niveles, excepto posiblemente el más profundo, están completos. TSu propiedad de Binary Heap lo hace adecuado para ser almacenado en un .
• Sigue la propiedad del montón: Un montón binario es un Min-Heap o un Max-Heap .
  • Montón binario mínimo: Fo cada nodo en un montón, el valor del nodo es menor o igual a valores de los niños
  • Montón binario máximo: Fo cada nodo en un montón, el valor del nodo es Mayor qué o igual a valores de los niños

Las aplicaciones populares del montón binario incluyenimplementar colas de prioridad eficientes, encontrar de manera eficiente los k elementos más pequeños (o más grandes) en una matriz y muchos más.

Tablas hash

Imagina que tienes un objeto y desea asignarle una clave para facilitar la búsqueda. Para almacenar ese par clave / valor, puede usar una matriz simple como una estructura de datos donde las claves (enteros) se pueden usar directamente como un índice para almacenar valores de datos. Sin embargo, en los casos en que las claves son demasiado grandes y no se pueden utilizar directamente como índice, se utiliza una técnica llamada hash.

En hash, las claves grandes se convierten en claves pequeñas utilizando funciones hash . Luego, los valores se almacenan en una estructura de datos llamadaa tabla de picadillo. Una tabla hash es una estructura de datos que implementa un diccionario ADT, una estructura que puede asignar claves únicas a valores.

En general, una tabla hash tiene dos componentes principales:

1. Matriz de cubos: Una matriz de depósito para una tabla hash es una matriz A de tamaño N, donde cada celda de A se considera un 'depósito', es decir, una colección de pares clave-valor. El entero N define la capacidad de la matriz.
2. Función hash: Es cualquier función que mapea cada clave k en nuestro mapa a un número entero en el rango [0, N & menos 1], donde N es la capacidad de la matriz de cubos para esta tabla.

Cuando colocamos objetos en una tabla hash, es posible que diferentes objetos tengan el mismo código hash. Esto se llama colisión . Para hacer frente a la colisión, existen técnicas como el encadenamiento y el direccionamiento abierto.

Por lo tanto, estas son algunas de las estructuras de datos básicas y más utilizadas en Java. Ahora que conoce cada uno de estos, puede comenzar a implementarlos en su . Con esto, hemos completado la primera parte de 'este artículo' Estructuras de datos y algoritmos en Java '. En la siguiente parte, aprenderemos sobrealgoritmos básicos y cómo usarlos en aplicaciones prácticas como ordenar y buscar, dividir y conquistar, algoritmos codiciosos, programación dinámica.

Algoritmos en Java

Utilizados históricamente como herramienta para resolver cálculos matemáticos complejos, los algoritmos están profundamente conectados con la informática y, en particular, con las estructuras de datos. Un algoritmo es una secuencia de instrucciones que describe una forma de resolver un problema específico en un período de tiempo finito. Están representados de dos formas:

• Diagramas de flujo - Es unrepresentación visual del flujo de control de un algoritmo
• Pseudocódigo - Esoes una representación textual de un algoritmo que se aproxima al código fuente final

Nota: El rendimiento del algoritmo se mide en función de la complejidad del tiempo y la complejidad del espacio. En general, la complejidad de cualquier algoritmo depende del problema y del algoritmo en sí.

Exploremos las dos categorías principales de algoritmos en Java, que son:

• Ordenar algoritmos en Java
• Búsqueda de algoritmos en Java

Clasificación de algoritmos en Java

Los algoritmos de clasificación son algoritmos que colocan los elementos de una lista en un orden determinado. Los órdenes más utilizados son el orden numérico y el orden lexicográfico. En este artículo de 'Estructuras de datos y algoritmos', exploremos algunos algoritmos de clasificación.

Clasificación de burbujas en Java

La clasificación de burbujas, a menudo denominada clasificación descendente, es el algoritmo de clasificación más simple. Repetidamente recorre la lista para ordenar, compara cada par de elementos adyacentes y los intercambia si están en el orden incorrecto.La clasificación de burbujas recibe su nombre porque filtra los elementos hacia la parte superior de la matriz, como burbujas que flotan en el agua.

Aquí estápseudocódigo que representa el algoritmo de clasificación de burbujas (contexto de clasificación ascendente).

a [] es una matriz de tamaño N begin BubbleSort (a []) declara el entero i, j para i = 0 a N - 1 para j = 0 a N - i - 1 si a [j]> a [j + 1 ] luego intercambia a [j], a [j + 1] end if end por devolver un fin BubbleSort

Este código ordena una matriz unidimensional de N elementos de datos en orden ascendente. Un bucle exterior realiza N-1 pasadas sobre la matriz. Cada pasada utiliza un bucle interno para intercambiar elementos de datos de manera que el siguiente elemento de datos más pequeño 'burbujee' hacia el comienzo de la matriz. Pero el problema es que el algoritmo necesita una pasada completa sin ningún intercambio para saber que la lista está ordenada.

Peor y peor complejidad del tiempo del caso: O (n * n). El peor de los casos ocurre cuando una matriz se ordena al revés.

Mejor complejidad del tiempo del caso: En). El mejor de los casos ocurre cuando una matriz ya está ordenada.

Orden de selección en Java

La clasificación por selección es una combinación de búsqueda y clasificación. El algoritmo ordena una matriz encontrando repetidamente el elemento mínimo (considerando el orden ascendente) de la parte sin clasificar y colocándolo en una posición adecuada en la matriz.

Aquí hay un pseudocódigo que representa el algoritmo de clasificación de selección (contexto de clasificación ascendente).

a [] es una matriz de tamaño N begin SelectionSort (a []) para i = 0 an - 1 / * establece el elemento actual como mínimo * / min = i / * encuentra el elemento mínimo * / para j = i + 1 an si lista [j]
Como puede comprender por el código, la cantidad de veces que la clasificación pasa a través de la matriz es una menos que la cantidad de elementos de la matriz. El ciclo interno encuentra el siguiente valor más pequeño y el ciclo externo coloca ese valor en su ubicación adecuada. La clasificación por selección nunca hace más de O (n) intercambios y puede ser útil cuando la escritura en memoria es una operación costosa.
 Complejidad del tiempo: En2) ya que hay dos bucles anidados.
convertir decimal a python binario
 Espacio auxiliar: O(1).
 Orden de inserción en Java 
La ordenación por inserción es un algoritmo de ordenación simple que recorre la lista consumiendo un elemento de entrada a la vez y construye la matriz ordenada final. Es muy simple y más eficaz en conjuntos de datos más pequeños. Es una técnica de clasificación estable e in situ.
Aquí hay un pseudocódigo que representa el algoritmo de ordenación por inserción (contexto de ordenación ascendente).
a [] es una matriz de tamaño N begin InsertionSort (a []) para i = 1 a N key = a [i] j = i - 1 while (j> = 0 y a [j]> key0 a [j + 1] = x [j] j = j - 1 final mientras que a [j + 1] = final clave para el final InsertionSort
Como puede comprender en el código, el algoritmo de ordenación por inserciónelimina un elemento de los datos de entrada, encuentra la ubicación a la que pertenece dentro de la lista ordenada y la inserta allí. Se repite hasta que no quedan elementos de entrada sin clasificar.
 Mejor caso: El mejor caso es cuando la entrada es una matriz que ya está ordenada. En este caso, la ordenación por inserción tiene un tiempo de ejecución lineal (es decir, & Theta (n)).
 Peor de los casos:  La entrada más simple en el peor de los casos es una matriz ordenada en orden inverso.
 QuickSort en Java 
El algoritmo de ordenación rápida es un algoritmo de ordenación rápido, recursivo y no estable que funciona según el principio de divide y vencerás. Selecciona un elemento como pivote y divide la matriz dada alrededor de ese pivote elegido.
 Pasos para implementar la ordenación rápida:  
 
Elija un 'punto de pivote' adecuado.
Divida las listas en dos listasbasado en este elemento pivote. Cada elemento que es más pequeño que el elemento pivote se coloca en la lista de la izquierda y cada elemento que es más grande se coloca en la lista de la derecha. Si un elemento es igual al elemento pivote, puede ir en cualquier lista. Esto se llama operación de partición.
Ordene de forma recursiva cada una de las listas más pequeñas. 
Aquí hay un pseudocódigo que representa el algoritmo de ordenación rápida.
QuickSort (A como matriz, bajo como int, alto como int) {if (bajo
En el pseudocódigo anterior, dividir() La función realiza la operación de partición y Ordenación rápida() function llama repetidamente a la función de partición para cada lista más pequeña generada. La complejidad de quicksort en el caso promedio es & Theta (n log (n)) y en el peor de los casos es & Theta (n2).
 Fusionar Ordenar en Java 
Mergesort es un algoritmo de ordenación estable, recursivo y rápido que también funciona según el principio de divide y vencerás. De forma similar a la ordenación rápida, la ordenación combinada divide la lista de elementos en dos listas. Estas listas se ordenan de forma independiente y luego se combinan. Durante la combinación de las listas, los elementos se insertan (o combinan) en el lugar correcto de la lista.
Aquí está el pseudocódigo que representa el algoritmo de clasificación de fusión.
procedimiento MergeSort (a como matriz) if (n == 1) devuelve una var l1 como matriz = a [0] ... a [n / 2] var l2 como matriz = a [n / 2 + 1] ... a [n] l1 = mergesort (l1) l2 = mergesort (l2) return merge (l1, l2) fin del procedimiento procedimiento merge (a como matriz, b como matriz) var c como matriz while (a y b tienen elementos) if ( a [0]> b [0]) agregar b [0] al final de c eliminar b [0] de b de lo contrario agregar a [0] al final de c eliminar a [0] de un final if end while while (a tiene elementos) agrega a [0] al final de c elimina a [0] de un final mientras que (b tiene elementos) agrega b [0] al final de c elimina b [0] de b final mientras regresa c finalizar procedimiento
 mergesort () función divide la lista en dos, llama mergesort () en estas listas por separado y luego las combina enviándolas como parámetros para la función merge ().El algoritmo tiene una complejidad de O (n log (n)) y tiene una amplia gama de aplicaciones.
 Ordenar montón en Java 
Heapsort es un algoritmo de clasificación basado en comparaciónEstructura de datos del montón binario. Puede pensar en ello como una clasificación mejorada de selección de versión f, dondedivide su entrada en una región ordenada y una no ordenada, y reduce iterativamente la región no ordenada extrayendo el elemento más grande y moviéndolo a la región ordenada.
 Pasos para implementar Quicksort (en orden creciente): 
Construye un montón máximo con la matriz de clasificación
En este puntot, el elemento más grande se almacena en la raíz del montón. Reemplácelo con el último elemento del montón y reduzca el tamaño del montón en 1. Finalmente, apile la raíz del árbol
Repita los pasos anteriores hasta que el tamaño del montón sea mayor que 1
Aquí está el pseudocódigo que representa el algoritmo de clasificación de montón.
Heapsort (a como matriz) para (i = n / 2 - 1) to i> = 0 heapify (a, n, i) for i = n-1 to 0 swap (a [0], a [i]) heapify (a, i, 0) end for end for heapify (a como matriz, n como int, i como int) mayor = i // Inicializar mayor como raíz int l eft = 2 * i + 1 // izquierda = 2 * i + 1 int right = 2 * i + 2 // right = 2 * i + 2 if (izquierda a [más grande]) más grande = izquierda si (derecha a [más grande]) más grande = derecha si (más grande! = I) swap ( a [i], A [mayor]) Heapify (a, n, mayor) end heapify
Aparte de estos, hay otros algoritmos de clasificación que no son tan conocidos, como Introsort, Counting Sort, etc. Pasando al siguiente conjunto de algoritmos en este artículo 'Estructuras de datos y algoritmos', exploremos los algoritmos de búsqueda.
 Búsqueda de algoritmos en Java 
La búsqueda es una de las acciones más comunes y que se realizan con más frecuencia en las aplicaciones comerciales habituales. Los algoritmos de búsqueda son algoritmos para encontrar un elemento con propiedades específicas entre una colección de elementos. Exploremos dos de los algoritmos de búsqueda más utilizados.
 Algoritmo de búsqueda lineal en Java 
La búsqueda lineal o secuencial es el algoritmo de búsqueda más simple. Implica la búsqueda secuencial de un elemento en la estructura de datos dada hasta que se encuentra el elemento o se llega al final de la estructura. Si se encuentra el elemento, se devuelve la ubicación del elemento; de lo contrario, el algoritmo devuelve NULL.
Aquí hay un pseudocódigo que representa la búsqueda lineal en Java:
procedimiento linear_search (a [], valor) para i = 0 a n-1 si un [i] = valor entonces imprime 'Encontrado' devuelve i finaliza si imprime 'No encontrado' finaliza para final linear_search
Es unalgoritmo de fuerza bruta.Si bien ciertamente es el más simple, definitivamente no es el más común, debido a su ineficiencia. La complejidad temporal de la búsqueda lineal es EN) .
 Algoritmo de búsqueda binaria en Java 
La búsqueda binaria, también conocida como búsqueda logarítmica, es un algoritmo de búsqueda que encuentra la posición de un valor objetivo dentro de una matriz ya ordenada. Divide la colección de entrada en mitades iguales y el elemento se compara con el elemento central de la lista. Si se encuentra el elemento, la búsqueda termina ahí. De lo contrario, continuamos buscando el elemento dividiendo y seleccionando la partición apropiada de la matriz, en función de si el elemento de destino es más pequeño o más grande que el elemento del medio.
Aquí hay un pseudocódigo que representa la búsqueda binaria en Java:
Procedimiento binary_search una matriz ordenada n tamaño de matriz x valor a buscar lowerBound = 1 upperBound = n mientras que x no se encuentra si upperBound
La búsqueda termina cuando upperBound (nuestro puntero) pasa por lowerBound (último elemento), lo que implica que hemos buscado en toda la matriz y el elemento no está presente.Es el algoritmo de búsqueda más utilizado principalmente debido a su tiempo de búsqueda rápido. La complejidad temporal de la búsqueda binaria es EN) que es una mejora notable en el EN) complejidad temporal de la búsqueda lineal.
Esto nos lleva al final de este artículo 'Estructuras de datos y algoritmos en Java'. He cubierto uno de los temas más fundamentales e importantes de Java.Espero que tengas claro todo lo que se ha compartido contigo en este artículo.
  Asegúrese de practicar tanto como sea posible y revertir su experiencia.   
 Revisar la    por Edureka, una empresa de aprendizaje en línea de confianza con una red de más de 250.000 alumnos satisfechos repartidos por todo el mundo. Estamos aquí para ayudarlo en cada paso de su viaje, para que, además de estas preguntas de la entrevista de Java, se desarrolle un plan de estudios diseñado para estudiantes y profesionales que desean ser Desarrolladores de Java. 
 Tienes una pregunta para nosotros? Menciónelo en la sección de comentarios de este 'Estructuras de datos y algoritmos en Java'  artículo y nos pondremos en contacto con usted lo antes posible.