Principales estructuras de datos que todo programador debe conocer

Una estructura de datos organiza y almacena datos en una computadora para que podamos realizar operaciones en los datos de manera más eficiente. Hay muchas aplicaciones diversas de estructuras de datos en Ciencias de la Computación e Ingeniería de Software. El uso de estructuras de datos es más común en todos los programas de computadora y sistemas de software. Además, las estructuras de datos son una parte importante de los fundamentos de la informática y la ingeniería de software. No hay duda de que este tema es un componente clave de la Ingeniería de Software y también muy importante desde la perspectiva de la preparación de entrevistas. Por lo tanto, debemos tener un buen conocimiento sobre la estructura de datos. En esta publicación, discutiremos con usted la estructura de datos superior que todo programador debe conocer. El conocimiento de la estructura de datos superior también se vuelve importante para la implementación de la estructura de datos avanzada.

¿Qué es la estructura de datos?

Una estructura de datos es el modelo matemático o lógico de una organización de datos. En resumen, una estructura de datos es una forma de organizar los datos en una forma accesible para las computadoras. Permite el procesamiento de una gran cantidad de datos en un período de tiempo relativamente corto. El propósito principal de usar estructuras de datos es reducir las complejidades de tiempo y espacio. Una estructura de datos eficiente utiliza un espacio de memoria mínimo y requiere el mínimo tiempo posible para ejecutarse.

Top Estructura de datos que todo programador debe conocer

Ahora, como sabemos sobre la estructura de datos y su importancia, echemos un vistazo a la estructura de datos más común que todo programador debe conocer:

1. array

Una array es una colección de elementos del mismo tipo de variable almacenados que se almacenan en ubicaciones de memoria contiguas. Es una de las estructuras de datos más populares y simples y, a menudo, se usa para implementar otras estructuras de datos. Cada elemento de una array se indexa a partir de 0 .

¿Por qué se necesitan estructuras de datos de array?

Supongamos que hay una clase de cinco estudiantes y si tenemos que mantener registros de sus calificaciones en el examen, podemos hacerlo declarando cinco variables individuales y haciendo un seguimiento de los registros, pero ¿y si el número de estudiantes se vuelve muy grande? difícil manipular y mantener los datos.

Tipos de arreglos: 

Hay principalmente dos tipos de arreglos:

• Array unidimensional (arrays 1-D) : puede imaginar una array 1d como una fila, donde los elementos se almacenan uno tras otro.

• Arreglos bidimensionales: Los arreglos multidimensionales 2-D se pueden considerar como un arreglo de arreglos o como una array que consta de filas y columnas .

• Array tridimensional: una array multidimensional tridimensional contiene tres dimensiones, por lo que puede considerarse una array de arrays bidimensionales.

Tipos de operaciones de array:

• Recorrido : recorrer los elementos de una array.
• Inserción: Insertar un nuevo elemento en una array.
• Deletion: Eliminación de un elemento de la array.
• Buscando:  busca un elemento en la array.
• Clasificación: mantener el orden de los elementos en la array.

Ventajas de usar arreglos:

• Las arrays permiten el acceso aleatorio a los elementos. Esto hace que el acceso a los elementos por posición sea más rápido.
• Las arrays tienen una mejor localidad de caché, lo que hace una gran diferencia en el rendimiento.
• Las arrays representan múltiples elementos de datos del mismo tipo usando un solo nombre.

Aplicación de array:

• Se utilizan en la implementación de otras estructuras de datos, como listas de arrays, montones, tablas hash, vectores y arrays.
• Los registros de la base de datos generalmente se implementan como arrays.
• Se utiliza en tablas de consulta por computadora.
• Se utiliza para diferentes algoritmos de clasificación, como la clasificación por inserción de burbujas, la clasificación por fusión y la clasificación rápida.

Preguntas de entrevista más frecuentes en Array:

Pregunta	Artículo	Práctica	Video
Líderes en una array	Vista	Resolver	Reloj
Punto de equilibrio	Vista	Resolver	Reloj
Ordenar una array de 0s, 1s y 2s	Vista	Resolver	Reloj
Array inversa en grupos	Vista	Resolver	Reloj
Convierta la array en forma de Zig-Zag	Vista	Resolver	Reloj
Reorganizar array alternativamente	Vista	Resolver	Reloj
Número faltante en la array	Vista	Resolver	Reloj
K-ésimo elemento de dos arrays ordenadas	Vista	Resolver	Reloj
Comprobar si dos arrays son iguales o no	Vista	Resolver	Reloj
Algoritmo de Kadane	Vista	Resolver	Reloj
Subarreglo con suma dada	Vista	Resolver	Reloj
Atrapando agua de lluvia	Vista	Resolver	Reloj
Plataformas Mínimas	Vista	Resolver	Reloj
Compra y venta de acciones	Vista	Resolver	Reloj
Número más grande formado a partir de una array	Vista	Resolver	Reloj
El subarreglo más grande con suma 0	Vista	Resolver	Reloj
El intercambio de pares hace que la suma sea igual	Vista	Resolver	Reloj

2. Cuerda

Las strings se definen como una array de caracteres. La diferencia entre una array de caracteres y una string es que la string termina con un carácter especial ‘\0’.

Declarar una string es tan simple como declarar una array unidimensional. A continuación se muestra la sintaxis básica para declarar una string en el lenguaje de programación C.

char str_name[size];

Operaciones con strings:

• Substrings :   una substring es una secuencia contigua de caracteres dentro de una string
• Concatenación: esta operación se usa para agregar una string al final de otra string.
• Longitud: Define el número de caracteres en la string dada. 
• Operaciones de procesamiento de texto: el procesamiento de texto es el proceso de creación y edición de strings.
  • Inserción: esta operación se utiliza para insertar caracteres en la string en la posición especificada.
  • Eliminación: esta operación se utiliza para eliminar caracteres de la string en la posición especificada.
  • Actualizar: esta operación se utiliza para actualizar los caracteres de la string en la posición especificada.

Ventajas de la string:

• String nos proporciona una biblioteca de strings para crear objetos de string que permitirán que las strings se asignen dinámicamente y también los problemas de límites se manejen dentro de la biblioteca de clases.
• String nos proporciona varias funciones incorporadas en la biblioteca de strings, como sort(), substr(i, j), compare(), push_back() y muchas más.
• La string ayuda como base para muchas estructuras de datos, como intentos, árboles de sufijos, arrays de sufijos, árboles de búsqueda ternarios y mucho más.
• Las strings nos proporcionan algoritmos de strings muy útiles para resolver problemas muy complejos con menos complejidad de tiempo.

 Aplicaciones de la string:

• Comprobador de plagio : las strings se pueden usar para encontrar plagio en códigos y contenidos en muy poco tiempo utilizando algoritmos de coincidencia de strings. Usando esto, la computadora puede decirnos fácilmente el porcentaje del código y qué porcentaje coincide con el texto escrito por dos usuarios.
• Codificación/descodificación (generación de texto cifrado): las strings se pueden usar para codificar y decodificar para la transferencia segura de datos del remitente al receptor para asegurarse de que nadie en el camino de la transmisión pueda leer sus datos, ya que podrían realizar acciones tanto activas como pasivas. ataques El texto que transfiere como mensaje se cifra en el extremo del remitente y se decodifica en el extremo del receptor.
• Recuperación de información: las aplicaciones de strings nos ayudan a recuperar información de fuentes de datos desconocidas (grandes conjuntos de datos utilizados como entrada) junto con la ayuda de un módulo de comparación/recuperación de strings que nos ayuda a recuperar información importante.
  Filtros mejorados para el problema de superposición de sufijo-prefijo aproximado: las strings y sus aplicaciones de algoritmos nos ayudan a proporcionar filtros mejorados para el problema de superposición de sufijo-prefijo aproximado.

Preguntas de entrevista más frecuentes en String:

Pregunta	Artículo	Práctica	Video
Encuentra el primer carácter repetido	Vista	Resolver	Reloj
Palabras inversas en una string dada	Vista	Resolver	Reloj
Compruebe si la string se gira dos lugares	Vista	Resolver	Reloj
Número romano a entero	Vista	Resolver	Reloj
Anagrama	Vista	Resolver	Reloj
Eliminar duplicados	Vista	Resolver	Reloj
Caracteres distintos más largos en la string	Vista	Resolver	Reloj
Implementar Atoi	Vista	Resolver	Reloj
Implementar strstr	Vista	Resolver	Reloj
Algoritmo de Rabin Karp	Vista	Resolver	Reloj
Algoritmo KMP	Vista	Resolver	Reloj
Convierta una oración en su secuencia de teclado numérico móvil equivalente.	Vista	Resolver	Reloj
Prefijo común más largo	Vista	Resolver	Reloj
Ventana más pequeña en una string que contiene todos los caracteres de otra string	Vista	Resolver	Reloj
Caracteres poco comunes	Vista	Resolver	Reloj
Carácter indexado mínimo	Vista	Resolver	Reloj

3. Listas enlazadas

Una lista enlazada es una estructura de datos lineal. A diferencia de las arrays, los elementos de la lista enlazada no se almacenan en una ubicación contigua. básicamente son strings de Nodes, cada Node contiene información como datos y un puntero al siguiente Node en la string. En la lista enlazada hay un puntero principal, que apunta al primer elemento de la lista enlazada, y si la lista está vacía, simplemente apunta a nulo o nada.

¿Por qué se necesita una estructura de datos de lista vinculada?

Aquí hay algunas ventajas de una lista vinculada que se enumera a continuación, lo ayudará a comprender por qué es necesario saberlo.

• Estructura de datos dinámica: el tamaño de la memoria se puede asignar o desasignar en tiempo de ejecución en función de la operación de inserción o eliminación.
• Facilidad de inserción/eliminación: la inserción y eliminación de elementos es más simple que las arrays, ya que no es necesario cambiar elementos después de la inserción y eliminación, solo se necesita actualizar la dirección.
• Utilización eficiente de la memoria: como sabemos, Linked List es una estructura de datos dinámica, el tamaño aumenta o disminuye según el requisito, por lo que evita el desperdicio de memoria. 
• Implementación: se pueden implementar varias estructuras de datos avanzadas utilizando una lista vinculada como pila, cola, gráfico, mapas hash, etc.

Tipos de listas enlazadas: 

Existen principalmente tres tipos de listas enlazadas:

• Lista de enlace simple: el recorrido de elementos se puede realizar en la dirección de avance solo debido al enlace de cada Node con su siguiente Node.

• Lista doblemente enlazada: el recorrido de elementos se puede realizar tanto en dirección hacia adelante como hacia atrás, ya que cada Node contiene un puntero anterior adicional que apunta al Node anterior.

• Listas enlazadas circulares: una lista enlazada circular es un tipo de lista enlazada en la que el primer y el último Node también están conectados entre sí para formar un círculo, no hay NULL al final. 

Operaciones en Lista Vinculada:

• Recorrido: podemos recorrer toda la lista enlazada a partir del Node principal. Si hay n Nodes, la complejidad del tiempo para atravesar se convierte en O(n) a medida que saltamos a través de todos y cada uno de los Nodes.
• Inserción: Inserta una clave en la lista enlazada. Una inserción se puede hacer de 3 maneras diferentes; insertar al principio de la lista, insertar al final de la lista e insertar en el medio de la lista.
• Eliminación: Elimina un elemento x de una lista enlazada determinada. No puede eliminar un Node en un solo paso. Una eliminación se puede hacer de 3 maneras diferentes; borrar del principio de la lista, borrar del final de la lista y borrar del medio de la lista.
• Buscar: encuentre el primer elemento con la clave k en la lista vinculada dada mediante una búsqueda lineal simple y devuelva un puntero a este elemento

Ventajas de las listas enlazadas:

• La inserción y eliminación en listas enlazadas son muy eficientes.
• Las listas vinculadas se utilizan para la asignación de memoria dinámica, lo que significa una utilización efectiva de la memoria, por lo tanto, sin desperdicio de memoria.
• Para la implementación de pilas y colas y para la representación de árboles y grafos.
• La lista enlazada se puede expandir en tiempo constante.

Aplicaciones de la lista enlazada: 

Estas son algunas de las aplicaciones de una lista enlazada:

• Las estructuras de datos lineales, como la pila, la cola y las estructuras de datos no lineales, como los mapas hash y los gráficos, se pueden implementar mediante listas vinculadas.
• Asignación dinámica de memoria: Usamos una lista enlazada de bloques libres.
• Implementación de gráficos: la representación de gráficos de listas de adyacencia es la más popular porque utiliza listas enlazadas para almacenar vértices adyacentes.
• En los navegadores y editores web, las listas doblemente enlazadas se pueden usar para crear un botón de navegación hacia adelante y hacia atrás.
• Una lista circular doblemente enlazada también se puede usar para implementar estructuras de datos como montones de Fibonacci.

Preguntas de entrevista más frecuentes en la lista vinculada:

Pregunta	Artículo	Práctica	Video
Encontrar el elemento medio en una lista enlazada	Vista	Resolver	Reloj
Invertir una lista vinculada	Vista	Resolver	Reloj
Rotar una lista vinculada	Vista	Resolver	Reloj
Invertir una lista enlazada en grupos de un tamaño determinado	Vista	Resolver	Reloj
Punto de intersección en listas enlazadas en forma de Y	Vista	Resolver	Reloj
Detectar bucle en la lista vinculada	Vista	Resolver	Reloj
Eliminar bucle en lista enlazada	Vista	Resolver	Reloj
Node n desde el final de la lista Vinculada	Vista	Resolver	Reloj
Aplanar una lista vinculada	Vista	Resolver	Reloj
Combinar dos listas enlazadas ordenadas	Vista	Resolver	Reloj
Intercambio por parejas de una lista enlazada	Vista	Resolver	Reloj
Agregar dos números representados por listas enlazadas	Vista	Resolver	Reloj
Comprobar si la lista enlazada es Palindrome	Vista	Resolver	Reloj
Implementar cola usando lista enlazada	Vista	Resolver	Reloj
Implementar pila usando lista enlazada	Vista	Resolver	Reloj
Dada una lista enlazada de 0s, 1s y 2s, ordenarla	Vista	Resolver	Reloj
Eliminar sin puntero principal	Vista	Resolver	Reloj

4. Apilar

Stack es una estructura de datos lineal en la que la inserción y la eliminación se realizan en un extremo, este extremo generalmente se denomina top . Funciona según el principio de último en entrar, primero en salir (LIFO) o primero en entrar, último en salir (FILO). LIFO significa que el último elemento insertado dentro de la pila se elimina primero. FILO significa que el último elemento insertado está disponible primero y es el primero en ser eliminado. 

Operaciones en una pila:

1. Empujar: agrega un elemento a la parte superior de una pila
2. Pop: elimina un elemento de la parte superior de una pila
3. IsEmpty: comprueba si la pila está vacía
4. IsFull: comprueba si la pila está llena
5. top/Peek: Obtener el valor del elemento superior sin eliminarlo

Ventajas de la pila:

• Stack ayuda en la gestión de datos que siguen la técnica LIFO.
• Las pilas se utilizan para la gestión sistemática de la memoria.
• Las pilas son más seguras y confiables ya que no se corrompen fácilmente.
• Stack permite el control sobre la asignación y desasignación de memoria.
• Stack limpia los objetos automáticamente.

Aplicaciones de la estructura de datos de pila:

• Stack se utiliza para evaluar expresiones con operandos y operaciones.
• Etiquetas coincidentes en HTML y XML
• Función de deshacer en cualquier editor de texto.
• Los compiladores usan la pila para calcular el valor de expresiones como 3 + 4 / 7 * (2 – 1) al convertir la expresión en forma de prefijo o posfijo.
• Las pilas ayudan a invertir cualquier conjunto de datos o strings.

Preguntas de entrevista más frecuentes en Stack:

Pregunta	Artículo	Práctica	Video
Comprobador de paréntesis	Vista	Resolver	Reloj
Fusionar intervalos superpuestos	Vista	Resolver	Reloj
Problema de stock span	Vista	Resolver	Reloj
Siguiente elemento más grande	Vista	Resolver	Reloj
Área rectangular más grande en un histograma	Vista	Resolver	Reloj
Apilar usando dos colas	Vista	Resolver	Reloj
Obtener el elemento mínimo de la pila	Vista	Resolver	Reloj
Caché LRU	Vista	Resolver	Reloj
Recorrido circular	Vista	Resolver	Reloj
Primer carácter que no se repite en una secuencia	Vista	Resolver	Reloj
naranjas podridas	Vista	Resolver	Reloj
Máximo de todos los subarreglos de tamaño k	Vista	Resolver	Reloj

5. Cola

Una cola es una estructura lineal que sigue un orden particular en el que se realizan las operaciones. El orden es Primero en entrar, primero en salir (FIFO). Es similar a la cola de boletos afuera de una sala de cine, donde la primera persona que ingresa a la cola es la primera persona que obtiene el boleto.

Operaciones de cola:

Una cola es un objeto (una estructura de datos abstracta – ADT) que permite las siguientes operaciones:

1. Poner en cola: añadir un elemento al final de la cola
2. Dequeue: elimina un elemento del frente de la cola
3. IsEmpty: comprueba si la cola está vacía
4. IsFull: Comprobar si la cola está llena
5. top/Peek: Obtener el valor del frente de la cola sin eliminarlo

Tipos de colas:

• Cola simple: en una cola simple, la inserción se realiza en la parte trasera y la extracción en la parte delantera. Sigue estrictamente la regla FIFO (primero en entrar, primero en salir).

• Cola circular: en una cola circular, el último elemento apunta al primer elemento haciendo un enlace circular.

• Cola de prioridad: en una cola de prioridad, los Nodes tendrán alguna prioridad predefinida en la cola de prioridad. El Node con la menor prioridad será el primero en ser eliminado de la cola. La inserción se realiza en el orden de llegada de los Nodes.
• Cola de doble extremo: en una cola de doble extremo, la inserción y extracción de elementos se puede realizar desde la parte delantera o trasera. Entonces, podemos decir que no sigue la regla FIFO (First In First Out).

Ventajas de la cola:

• Una gran cantidad de datos se pueden administrar de manera eficiente con facilidad.
• Las operaciones como la inserción y la eliminación se pueden realizar con facilidad ya que sigue la regla de primero en entrar, primero en salir.
• Las colas se pueden utilizar en la implementación de otras estructuras de datos.
• Las colas son útiles cuando varios consumidores utilizan un servicio en particular.
• Las colas son rápidas para la comunicación entre procesos de datos.

Aplicaciones de cola:

• Programación de CPU, Programación de disco
• Cuando los datos se transfieren de forma asíncrona entre dos procesos. La cola se utiliza para la sincronización. Por ejemplo, IO Buffers, pipes, file IO, etc.
• Manejo de interrupciones en sistemas de tiempo real.
• Los sistemas telefónicos de Call Center usan colas para mantener en orden a las personas que los llaman.

Preguntas de entrevista más frecuentes en Queue:

Pregunta	Artículo	Práctica	Video
Comprobador de paréntesis	Vista	Resolver	Reloj
Fusionar intervalos superpuestos	Vista	Resolver	Reloj
Problema de stock span	Vista	Resolver	Reloj
Siguiente elemento más grande	Vista	Resolver	Reloj
Área rectangular más grande en un histograma	Vista	Resolver	Reloj
Cola usando dos pilas	Vista	Resolver	Reloj
Obtener el elemento mínimo de la pila	Vista	Resolver	Reloj
Caché LRU	Vista	Resolver	Reloj
Recorrido circular	Vista	Resolver	Reloj
Primer carácter que no se repite en una secuencia	Vista	Resolver	Reloj
naranjas podridas	Vista	Resolver	Reloj
Máximo de todos los subarreglos de tamaño k	Vista	Resolver	Reloj

6. árbol

Un árbol es una estructura de datos no lineal y jerárquica que consta de una colección de Nodes de modo que cada Node del árbol almacena un valor y una lista de referencias a otros Nodes (los «hijos»).

Tipos de árboles:

• Árbol binario
• Árbol de búsqueda binaria
• Árbol AVL
• Árbol B
• Árbol negro rojo
• Árbol n-ario

Operaciones en la estructura de datos de árbol:

• Insertar: Inserta un elemento en un árbol/crea un árbol.
• Buscar: Busca un elemento en un árbol.
• Tree Traversal: El algoritmo Tree Traversal se utiliza para visitar un Node específico en el árbol para realizar una operación específica en él.

Ventaja de la estructura de datos de árbol:

• Los árboles proporcionan una representación jerárquica de los datos.
• Los árboles son de naturaleza dinámica, por lo que el número de Nodes no está limitado.
• La inserción y eliminación en un árbol se puede realizar en un tiempo moderado.

Aplicaciones de la estructura de datos de árbol:

• Los árboles se pueden utilizar para almacenar datos que están en forma jerárquica.
• Los diferentes tipos de árboles se utilizan en diversos campos, como bases de datos, gráficos por computadora y redes informáticas.
• Los sistemas operativos utilizan estructuras de datos de árbol para administrar los directorios de archivos.

Preguntas de entrevista más frecuentes sobre la estructura de datos del árbol:

Pregunta	Artículo	Práctica	Video
Altura del árbol binario	Vista	Resolver	Reloj
Número de Nodes hoja	Vista	Resolver	Reloj
Compruebe si el árbol binario dado está equilibrado en altura o no	Vista	Resolver	Reloj
Escribir código para determinar si dos árboles son idénticos o no	Vista	Resolver	Reloj
Dado un árbol binario, compruebe si es un espejo de sí mismo.	Vista	Resolver	Reloj
Suma máxima de ruta	Vista	Resolver	Reloj
Imprimir vista izquierda del árbol binario	Vista	Resolver	Reloj
Imprimir vista inferior del árbol binario	Vista	Resolver	Reloj
Imprima un árbol binario en orden vertical	Vista	Resolver	Reloj
Diámetro de un árbol binario	Vista	Resolver	Reloj
Recorrido de orden de nivel en forma de espiral	Vista	Resolver	Reloj
Conectar Nodes al mismo nivel	Vista	Resolver	Reloj
Convierta un árbol binario dado en una lista doblemente enlazada	Vista	Resolver	Reloj
Serializar y deserializar un árbol binario	Vista	Resolver	Reloj

7. montón

Un montón es una estructura de datos especial basada en un árbol en la que el árbol es un árbol binario completo.

Tipos de estructura de datos de montón:

• Max-Heap: en un Max-Heap, la clave presente en el Node raíz debe ser la mayor entre las claves presentes en todos sus hijos. La misma propiedad debe ser verdadera recursivamente para todos los subárboles en ese árbol binario.
• Min-Heap : en un Min-Heap, la clave presente en el Node raíz debe ser mínima entre las claves presentes en todos sus hijos. La misma propiedad debe ser verdadera recursivamente para todos los subárboles en ese árbol binario.

Operación en la estructura de datos del montón:

• Heapify: un proceso de creación de un montón a partir de una array.
  Inserción: proceso para insertar un elemento en la complejidad de tiempo de montón existente O (log N).
• Eliminación: eliminar el elemento superior del montón o el elemento de mayor prioridad, y luego organizar el montón y devolver el elemento con complejidad de tiempo O (log N).
• Peek: para verificar o encontrar el elemento más anterior en el montón (elemento máximo o mínimo para el montón máximo y mínimo).

Ventajas de la estructura de datos del montón:

• Mantiene el elemento según su prioridad.
• La complejidad del tiempo para echar un vistazo al elemento más anterior es constante O (1).
• Se necesita menos complejidad de tiempo, para insertar o eliminar un elemento en el montón, la complejidad de tiempo es solo O (log N).
• Un montón binario es un árbol binario equilibrado y es fácil de implementar.
• La estructura de datos del montón utiliza eficientemente un algoritmo gráfico como Dijkstra.

Aplicación de la estructura de datos del montón:

• Heap se utiliza para construir una cola de prioridad.
• Heap sort es uno de los algoritmos de clasificación más rápidos con una complejidad de tiempo de O(N* log(N), y es fácil de implementar.
• Best First Search (BFS) es una búsqueda informada, donde a diferencia de la cola en Breadth-First Search, esta técnica se implementa utilizando una cola de prioridad.

Preguntas de entrevista más frecuentes sobre la estructura de datos Heap:

Pregunta	Artículo	Práctica	Video
Ordenar montón	Vista	Resolver	Reloj
Encuentra la mediana en una corriente	Vista	Resolver	Reloj
Operaciones en Binary Min Heap	Vista	Resolver	Reloj
Reorganizar personajes	Vista	Resolver	Reloj
Fusionar K ordenadas Listas vinculadas	Vista	Resolver	Reloj
K-ésimo elemento más pequeño en una array ordenada por filas y columnas	Vista	Resolver	Reloj

8. Gráfico

Un gráfico es una estructura de datos no lineal que consta de Nodes y bordes . Los Nodes a veces también se conocen como vértices y los bordes son líneas o arcos que conectan dos Nodes en el gráfico. Más formalmente, un gráfico se puede definir como un gráfico que consta de un conjunto finito de vértices (o Nodes) y un conjunto de aristas que conectan un par de Nodes.

Representación gráfica

En la estructura de datos de gráficos, una representación gráfica es una técnica para almacenar gráficos en la memoria de la computadora. Hay muchas maneras de representar un gráfico:

Las dos siguientes son las representaciones más utilizadas de un gráfico.

1. Array de adyacencia: una array de adyacencia representa un gráfico como una array de valores booleanos (0 y 1). En una computadora, un gráfico finito se puede representar como una array cuadrada, donde el valor booleano indica si dos vértices están conectados directamente.
2. Lista de adyacencia: una lista de adyacencia representa un gráfico como una array de listas vinculadas donde un índice de la array representa un vértice y cada elemento en su lista vinculada representa los otros vértices que están conectados con los bordes, o digamos su vecino.

Tipos de gráficos

Según la dirección de los bordes, hay dos tipos de gráficos:

• Gráfico no dirigido: un gráfico en el que todos los bordes son bidireccionales y los bordes no están dirigidos en ninguna dirección específica a los vértices.

• Gráfico dirigido: un gráfico en el que todos los bordes son unidireccionales y los bordes están dirigidos a algún vértice específico.

Según el peso de los bordes, hay dos tipos de gráficos:

• Gráfico ponderado:  un gráfico en el que cada borde tiene un valor o peso y los valores pueden representar cantidades como el costo, la distancia y el tiempo.  

• Gráfico no ponderado: un gráfico en el que no hay ningún valor o peso asociado con el borde. Se dice que todos los gráficos no están ponderados por defecto a menos que haya un valor asociado.

Operaciones gráficas:

• Agregar/eliminar vértice: agregue o elimine un vértice en un gráfico.
• Agregar/eliminar borde: agregue o elimine un borde entre dos vértices.
• Comprueba si el gráfico contiene un valor dado.
• Encuentra el camino de un vértice a otro vértice.

Ventajas del gráfico:

• Mediante el uso de gráficos, podemos encontrar fácilmente la ruta más corta, los vecinos de los Nodes y muchos más.
• Los gráficos se utilizan para implementar algoritmos como DFS y BFS.
• Ayuda a organizar los datos.
• Se utiliza para encontrar un árbol de expansión mínimo que tiene muchas aplicaciones prácticas.
• Por su estructura no lineal, ayuda en la comprensión de problemas complejos y su visualización.

Aplicaciones de los gráficos:

• Los gráficos se utilizan para representar redes de comunicación.
• La teoría de grafos se utiliza para encontrar el camino más corto en una carretera o en una red.
• Los gráficos se utilizan para representar redes de comunicación.
• En Google Maps, varias ubicaciones se representan como vértices o Nodes y las carreteras se representan como bordes. La teoría de gráficos se utiliza para encontrar el camino más corto entre dos Nodes.
• En Facebook, los usuarios se consideran los vértices y, si son amigos, existe una ventaja entre ellos. El algoritmo de sugerencias de amigos de Facebook utiliza la teoría de grafos. Facebook es un ejemplo de un gráfico no dirigido.

Preguntas de entrevista más frecuentes en Graph:

Pregunta	Artículo	Práctica	Video
Primer recorrido de profundidad	Vista	Resolver	Reloj
Ancho primero recorrido	Vista	Resolver	Reloj
Detectar ciclo en gráfico no dirigido	Vista	Resolver	Reloj
Detectar ciclo en un gráfico dirigido	Vista	Resolver	Reloj
clasificación topológica	Vista	Resolver	Reloj
Encuentra el número de islas	Vista	Resolver	Reloj
Implementando Dijkstra	Vista	Resolver	Reloj
Intercambios mínimos	Vista	Resolver	Reloj
Componentes fuertemente conectados	Vista	Resolver	Reloj
Ruta de origen a destino más corta	Vista	Resolver	Reloj
Averiguar si existe una ruta	Vista	Resolver	Reloj
Ruta de costo mínimo	Vista	Resolver	Reloj
círculo de cuerdas	Vista	Resolver	Reloj
floyd warhall	Vista	Resolver	Reloj
Diccionario alienígena	Vista	Vista	Reloj
Problema de la serpiente y la escalera	Vista	Resolver	Reloj

9. Estructura de datos hash

Una tabla hash es una estructura de datos que asigna claves a valores utilizando una función especial llamada función hash . Hash almacena los datos de manera asociativa en una array donde cada valor de datos tiene su propio índice único.

Las tablas hash generalmente se implementan utilizando arrays y el rendimiento de la estructura de datos hash depende de estos tres factores:

1. Función hash
2. Tamaño de la tabla hash
3. Método de manejo de colisiones

Operación en la estructura de datos Hash:

• Insertar: esta operación se usa para mapear el par clave-valor y almacenar este registro de mapeo en la estructura de datos hash.
• Buscar: esta operación se utiliza para buscar el valor de la clave en la tabla hash.
• Eliminar: esta operación se utiliza para eliminar el par clave-valor almacenado de la tabla hash.

Ventajas de la estructura de datos hash

• Hash proporciona una mejor sincronización que otras estructuras de datos.
• Las tablas hash son más eficientes que los árboles de búsqueda u otras estructuras de datos
• Hash proporciona un tiempo constante para las operaciones de búsqueda, inserción y eliminación en promedio.

Aplicaciones de la estructura de datos hash:

• Hash se utiliza en bases de datos para la indexación.
• Hash se utiliza en estructuras de datos basadas en disco.
• En algunos lenguajes de programación como Python, el hash de JavaScript se usa para implementar objetos.

Preguntas de entrevista más frecuentes sobre la estructura de datos Hash:

Pregunta	Artículo	Práctica	Video
Primer elemento que ocurre k veces	Vista	Resolver	Reloj
Encuentra el elemento que aparece una vez en la array ordenada	Vista	Resolver	Reloj
Número de pares	Vista	Resolver	Reloj
Encuentra todos los pares con una suma dada	Vista	Resolver	Reloj
Elementos comunes	Vista	Resolver	Reloj
Encuentra los cuatro números de suma	Vista	Resolver	Reloj
Contar elementos distintos en cada ventana	Vista	Resolver	Reloj
Problema de divisibilidad de la suma de pares de arreglos	Vista	Resolver	Reloj
Subsecuencia consecutiva más larga	Vista	Resolver	Reloj
Array Subconjunto de otra array	Vista	Resolver	Reloj
Subarreglos de suma cero	Vista	Resolver	Reloj
Clasificación relativa	Vista	Resolver	Reloj

Conclusión

Las estructuras de datos y los algoritmos dependen unos de otros. Utilizamos una estructura de datos adecuada para aplicar algoritmos. Del mismo modo, aplicamos algoritmos a la estructura de datos. Y también queda claro a partir de la definición que la estructura de datos almacena los datos no estructurados de forma organizada, mientras que los algoritmos son el conjunto de instrucciones que sigue una computadora para resolver una tarea en particular.

Las estructuras de datos son los componentes básicos de los algoritmos, y los algoritmos son las plataformas sobre las que se aplican y prueban las estructuras de datos.

Con todos los casos presentados, y después de discutir los méritos y deméritos de las principales estructuras de datos que todo programador debe conocer, es importante que primero comience a aprender Estructuras de datos, pero no profundice en ellas sin el conocimiento de Algoritmos. 

Artículos relacionados:

• ¿Cómo comenzar a aprender datos DSA?
• Programación competitiva: una guía completa
• ¿Cómo puede uno volverse bueno en estructuras de datos y algoritmos fácilmente?
• ¿Por qué es importante aprender las estructuras de datos y los algoritmos?
• Los 15 mejores sitios web para desafíos y competencias de codificación
• HOJA SDE: una guía completa para la preparación de SDE
• Hoja de Amazon SDE: una guía para la preparación de entrevistas de Amazon SDE
• Preparación de entrevistas de Google para ingenieros de software: una guía completa
• 100 días de código: una guía completa para principiantes y experimentados