Estructura de datos

Estructuras de datos básicas

Array

El tipo más simple de estructura de datos es un array lineal. También se conoce como matriz unidimensional. Un array contiene varios valores del mismo tipo (enteros, flotantes, cadenas, etc.). El acceso a los elementos del array es muy rápido. Un array suele tener un tamaño fijo. Una vez definido el tamaño de la matriz al principio, puede que no sea posible aumentar el tamaño de la matriz sin crear una nueva matriz más grande y copiar todos los valores en la nueva matriz. En informática, una estructura de datos de matriz o simplemente una matriz es una estructura de datos que consiste en una colección de elementos (valores o variables), cada uno identificado por al menos un índice o clave de matriz. Un array se almacena de forma que la posición de cada elemento pueda calcularse a partir de su tupla de índices mediante una fórmula matemática.

Por ejemplo, una matriz de 10 variables enteras, con índices de 0 a 9, puede almacenarse como 10 palabras en las direcciones de memoria 2000, 2004, 2008, 2036, de modo que el elemento con índice i tiene la dirección 2000 + 4 × i.

Como el concepto matemático de matriz puede representarse como una cuadrícula bidimensional, las matrices bidimensionales también se denominan a veces matrices. En algunos casos se utiliza el término "vector" en informática para referirse a una matriz, aunque el equivalente matemático más correcto son las tuplas y no los vectores. Las matrices se utilizan a menudo para implementar tablas, especialmente tablas de búsqueda; la palabra tabla se utiliza a veces como sinónimo de matriz.

Las matrices se encuentran entre las estructuras de datos más antiguas e importantes, y se utilizan en casi todos los programas. También pueden utilizarse para implementar muchas otras estructuras de datos, como listas y cadenas. Aprovechan la lógica de direccionamiento de los ordenadores. En la mayoría de los ordenadores modernos y en muchos dispositivos de almacenamiento externo, la memoria es una matriz unidimensional de palabras, cuyos índices son sus direcciones. Los procesadores, especialmente los vectoriales, suelen estar optimizados para las operaciones de matriz.

Las matrices son útiles porque los índices de los elementos pueden calcularse en tiempo de ejecución. Entre otras cosas, esta característica permite que una sola sentencia iterativa procese un número arbitrario de elementos de un array. Por esta razón, se requiere que los elementos de una estructura de datos de array tengan el mismo tamaño y que utilicen la misma representación de datos. El conjunto de tuplas de índice válidas y las direcciones de los elementos (y, por tanto, la fórmula de direccionamiento de los elementos) suelen ser fijos, aunque no siempre, mientras el array está en uso.

El término array se utiliza a menudo para referirse al tipo de datos array, un tipo de datos proporcionado por la mayoría de los lenguajes de programación de alto nivel que consiste en una colección de valores o variables que pueden ser seleccionados por uno o más índices calculados en tiempo de ejecución. Los tipos de array suelen implementarse mediante estructuras de array; sin embargo, en algunos lenguajes pueden implementarse mediante tablas hash, listas enlazadas, árboles de búsqueda u otras estructuras de datos.

Lista vinculada

Una estructura de datos enlazados es un conjunto de información/datos vinculados entre sí por referencias. Los datos suelen llamarse nodos. Las referencias suelen llamarse enlaces o punteros. A partir de ahora, se utilizarán las palabras nodo y puntero para estos conceptos.

En las estructuras de datos enlazadas, los punteros sólo se desreferencian o se comparan para comprobar la igualdad. Por lo tanto, las estructuras de datos enlazadas son diferentes de las matrices, que requieren sumar y restar punteros.

Las listas enlazadas, los árboles de búsqueda y los árboles de expresión son estructuras de datos enlazadas. También son importantes en algoritmos como la ordenación topológica y la unión de conjuntos.

Pila

Una pila es una estructura de datos básica que puede pensarse lógicamente como una estructura lineal representada por una pila física real, una estructura en la que la inserción y la eliminación de elementos tiene lugar en un extremo llamado parte superior de la pila. El concepto básico se puede ilustrar pensando en el conjunto de datos como una pila de platos o libros en la que sólo se puede sacar el elemento superior de la pila para eliminar cosas de ella. Esta estructura se utiliza en toda la programación.

La implementación básica de una pila también se denomina estructura "Last In First Out"; sin embargo, existen diferentes variaciones de implementaciones de pila.

Hay básicamente tres operaciones que se pueden realizar en las pilas. Son:

• insertar ("empujar") un elemento en una pila
• eliminar ("popping") un elemento de la pila
• mostrar el contenido del elemento superior de la pila ("peeking")

Cola de espera

Una cola es un tipo de datos abstracto o una estructura de datos lineal, en la que el primer elemento se inserta desde un extremo (la "cola"), y la eliminación del elemento existente tiene lugar desde el otro extremo (la "cabeza"). Una cola es una estructura "First In First Out". "Primero en entrar, primero en salir" significa que los elementos puestos en la cola primero saldrán, y los elementos puestos en la cola en último lugar saldrán. Un ejemplo de cola son las filas de personas que esperan. La primera persona de la cola es la primera, y la última, la última.

El proceso de añadir un elemento a una cola se llama "enqueuing" y el proceso de eliminar un elemento de una cola se llama "dequeuing".

Gráfico

Un grafo es un tipo de datos abstracto que pretende implementar los conceptos de grafo e hipergrafo de las matemáticas.

Una estructura de datos de grafos consiste en un conjunto finito (y posiblemente mutable) de pares ordenados, llamados aristas o arcos, de ciertas entidades llamadas nodos o vértices. Como en matemáticas, se dice que una arista (x,y) apunta o va de x a y. Los nodos pueden formar parte de la estructura del grafo, o pueden ser entidades externas representadas por índices o referencias enteras. Una estructura de datos de grafos también puede asociar a cada arista algún valor, como una etiqueta simbólica o un atributo numérico.

Árbol

El árbol es una de las estructuras de datos avanzadas más potentes. Suele aparecer en temas avanzados como la Inteligencia Artificial (IA) y el diseño. Sorprendentemente, el árbol es importante en una aplicación mucho más básica: el mantenimiento de un índice eficiente.

Cuando se utiliza un árbol es muy probable que se utilice un índice. El tipo de índice más sencillo es una lista ordenada de campos clave. Un árbol normalmente tiene una estructura definida. En el caso de un árbol binario, se puede utilizar una búsqueda binaria para localizar cualquier elemento sin tener que mirar todos los elementos.

El tipo de datos árbol es un tipo de grafo, lo que significa que muchos algoritmos hechos para atravesar un grafo también funcionan con un árbol, sin embargo, los algoritmos pueden ser muy similares y deben tener un nodo de inicio dedicado, es decir, el nodo sin otros nodos que lo vinculen.

El problema con una simple lista ordenada se produce cuando se empiezan a añadir nuevos elementos y hay que mantener la lista ordenada; puede hacerse de forma razonablemente eficiente, pero requiere algunas modificaciones. Además, un índice lineal no es fácil de compartir porque hay que "bloquear" todo el índice cuando un usuario lo edita, mientras que se puede bloquear una "rama" de un árbol, dejando las otras ramas editables por otros usuarios (ya que no pueden ser afectadas).

Tabla Hash

Una tabla hash es una matriz en la que cada índice apunta a una lista enlazada basada en un valor hash. Un valor hash es un valor determinado por una función hash. Una función hash determina un valor único basado en los datos que almacena. Esto permite acceder a los datos en tiempo constante porque el ordenador siempre sabe dónde buscar.

Cada nodo apunta a otro nodo.