Descripción general de las estructuras de datos | Conjunto 1 (Estructuras de datos lineales)

Una estructura de datos es una forma particular de organizar los datos en una computadora para que pueda usarse de manera efectiva. La idea es reducir las complejidades de espacio y tiempo de las diferentes tareas. A continuación se muestra una descripción general de algunas estructuras de datos lineales populares. 

1. Array  
2. Lista enlazada  
3. Pila  
4. Cola 

Formación 

La array es una estructura de datos utilizada para almacenar elementos homogéneos en ubicaciones contiguas. El tamaño de una array debe proporcionarse antes de almacenar datos. 

Let size of array be n.
Accessing Time: O(1) [This is possible because elements
                      are stored at contiguous locations]   
Search Time:   O(n) for Sequential Search: 
               O(log n) for Binary Search [If Array is sorted]
Insertion Time: O(n) [The worst case occurs when insertion 
                     happens at the Beginning of an array and 
                     requires shifting all of the elements]
Deletion Time: O(n) [The worst case occurs when deletion 
                     happens at the Beginning of an array and 
                     requires shifting all of the elements]

Ejemplo: por ejemplo, digamos que queremos almacenar las calificaciones de todos los estudiantes en una clase, podemos usar una array para almacenarlas. Esto ayuda a reducir el uso de una serie de variables, ya que no necesitamos crear una variable separada para las calificaciones de cada materia. Se puede acceder a todas las marcas simplemente recorriendo la array. 
 

Lista enlazada 

Una lista enlazada es una estructura de datos lineal (como arrays) donde cada elemento es un objeto separado. Una lista enlazada se compone de dos elementos que son datos y una referencia al siguiente Node. Se proporciona una referencia al siguiente Node con la ayuda de punteros y los datos son el valor de un Node. Cada Node contiene datos y enlaces a los otros Nodes. Es una colección ordenada de elementos de datos llamada Node y el orden lineal se mantiene mediante punteros. Tiene una ventaja sobre la array como el número de Nodes, es decir, el tamaño de la lista enlazada no es fijo y puede crecer y reducirse cuando sea necesario, a diferencia de las arrays. 

Tipos de Lista Vinculada: 
1. Lista Vinculada Individualmente: En este tipo de lista vinculada, cada Node almacena la dirección o referencia del siguiente Node en la lista y el último Node tiene la siguiente dirección o referencia como NULL. Por ejemplo 1->2->3->4->NULL 

2. Lista Doblemente Enlazada: En este tipo de lista Enlazada, hay dos referencias asociadas a cada Node, Una de las referencias apunta al siguiente Node y otra al Node anterior. La ventaja de esta estructura de datos es que podemos atravesar en ambas direcciones y para borrar, no necesitamos tener acceso explícito al Node anterior. P.ej. NULO<-1<->2<->3->NULO 

3. Lista enlazada circular: La lista enlazada circular es una lista enlazada donde todos los Nodes están conectados para formar un círculo. No hay NULL al final. Una lista enlazada circular puede ser una lista enlazada circular sencilla o una lista enlazada circular doble. La ventaja de esta estructura de datos es que cualquier Node puede convertirse en un Node inicial. Esto es útil en la implementación de colas circulares en la lista enlazada. P.ej. 1->2->3->1 [El siguiente puntero del último Node apunta al primero] 

4. Lista circular doblemente enlazada: la lista circular doblemente enlazada es una combinación de la lista doblemente enlazada y la lista circular enlazada. Significa que esta lista enlazada es bidireccional y contiene dos punteros y el último puntero apunta al primer puntero.

Accessing time of an element : O(n)
Search time of an element : O(n)
Insertion of an Element : O(1) [If we are at the position 
                                where we have to insert 
                                an element] 
Deletion of an Element : O(1) [If we know address of node
                               previous to the node to be 
                               deleted] 

Ejemplo: Considere el ejemplo anterior donde hicimos una array de calificaciones de los estudiantes. Ahora, si se agrega una nueva materia al curso, sus calificaciones también se agregarán a la array de calificaciones. Pero el tamaño de la array se corrigió y ya está lleno, por lo que no puede agregar ningún elemento nuevo. Si hacemos una array de un tamaño mucho mayor que el número de sujetos, es posible que la mayor parte de la array quede vacía. Reducimos el desperdicio de espacio. Se forma una lista enlazada que agrega un Node solo cuando se introduce un nuevo elemento. Las inserciones y eliminaciones también se vuelven más fáciles con una lista enlazada. 
Un gran inconveniente de una lista enlazada es que no se permite el acceso aleatorio. Con arreglos, podemos acceder al i-ésimo elemento en tiempo O(1). En la lista enlazada, lleva Θ(i) tiempo. 

Pila 

Una pila o LIFO (last in, first out) es un tipo de dato abstracto que sirve como una colección de elementos, con dos operaciones principales: empujar, que agrega un elemento a la colección, y pop, que elimina el último elemento que se agregó. . En la pila, las operaciones de empujar y sacar tienen lugar en el mismo extremo que está en la parte superior de la pila. Se puede implementar utilizando tanto una array como una lista enlazada.  

Insertion : O(1)
Deletion :  O(1)
Access Time : O(n) [Worst Case]
Insertion and Deletion are allowed on one end. 

Ejemplo: las pilas se utilizan para mantener las llamadas a funciones (la última función llamada debe terminar la ejecución primero), siempre podemos eliminar la recursividad con la ayuda de las pilas. Las pilas también se utilizan en los casos en los que tenemos que invertir una palabra, verificar paréntesis equilibrados y en editores donde la última palabra que escribió es la primera que se elimina cuando usa la operación de deshacer. Del mismo modo, para implementar la funcionalidad de retroceso en los navegadores web. 

Operaciones de pila primaria:

• void push(int data): cuando se realiza esta operación, se inserta un elemento en la pila.
• int pop():   cuando se realiza esta operación, se elimina un elemento de la parte superior de la pila y se devuelve.

Operaciones de pila auxiliar:

• int top(): esta operación devolverá el último elemento insertado que está en la parte superior sin eliminarlo.
• int size(): Esta operación devolverá el tamaño de la pila, es decir, el número total de elementos presentes en la pila.
• int isEmpty(): Esta operación indica si la pila está vacía o no.
• int isFull() : esta operación indica si la pila está llena o no.

Tipos de pilas:

• Pila de registros: este tipo de pila también es un elemento de memoria presente en la unidad de memoria y solo puede manejar una pequeña cantidad de datos. La altura de la pila de registros siempre está limitada ya que el tamaño de la pila de registros es muy pequeño en comparación con la memoria.
• Pila de memoria: este tipo de pila puede manejar una gran cantidad de datos de memoria. La altura de la pila de memoria es flexible ya que ocupa una gran cantidad de datos de memoria.

Cola 

Una cola o FIFO (primero en entrar, primero en salir) es un tipo de datos abstracto que sirve como una colección de elementos, con dos operaciones principales: poner en cola, el proceso de agregar un elemento a la colección. (El elemento se agrega desde la parte posterior) y elimine la cola del proceso de eliminación del primer elemento que se agregó. (El elemento se quita del lado frontal). Se puede implementar utilizando tanto una array como una lista enlazada. 

Insertion : O(1)
Deletion  : O(1)
Access Time : O(n) [Worst Case]

Ejemplo: cola como su nombre lo dice es la estructura de datos construida de acuerdo con las colas de una parada de autobús o tren donde la persona que está parada al frente de la cola (de pie durante más tiempo) es la primera en obtener el boleto. Por lo tanto, cualquier situación en la que los recursos se compartan entre varios usuarios y se atiendan por orden de llegada. Los ejemplos incluyen la programación de la CPU, la programación del disco. Otra aplicación de la cola es cuando los datos se transfieren de forma asincrónica (los datos no se reciben necesariamente a la misma velocidad que se envían) entre dos procesos. Los ejemplos incluyen IO Buffers, tuberías, archivo IO, etc. 

Operaciones básicas en cola: 

• void enqueue(int data): Inserta un elemento al final de la cola, es decir, en la parte trasera.
• int dequeue(): esta operación elimina y devuelve un elemento que está al principio de la cola.

Operaciones auxiliares en cola:

• int front(): esta operación devuelve el elemento en el extremo frontal sin eliminarlo.
• int rear(): esta operación devuelve el elemento en la parte trasera sin eliminarlo.
• int isEmpty(): Esta operación indica si la cola está vacía o no.
• int size(): Esta operación devuelve el tamaño de la cola, es decir, el número total de elementos que contiene.

Tipos de colas: 

• Cola simple: la cola simple, también conocida como cola lineal, es la versión más básica de una cola. Aquí, la inserción de un elemento, es decir, la operación de puesta en cola, tiene lugar en el extremo posterior y la eliminación de un elemento, es decir, la operación de eliminación de cola, tiene lugar en el extremo delantero.
• Cola circular:  en una cola circular, el elemento de la cola actúa como un anillo circular. El funcionamiento de una cola circular es similar al de una cola lineal excepto por el hecho de que el último elemento está conectado al primero. Su ventaja es que se aprovecha mejor la memoria. Esto se debe a que si hay un espacio vacío, es decir, si no hay ningún elemento presente en una determinada posición de la cola, se puede agregar fácilmente un elemento en esa posición.
• Cola de prioridad: esta cola es un tipo especial de cola. Su especialidad es que organiza los elementos en una cola en función de alguna prioridad. La prioridad puede ser algo donde el elemento con el valor más alto tiene la prioridad, por lo que crea una cola con un orden decreciente de valores. La prioridad también puede ser tal que el elemento con el valor más bajo obtenga la prioridad más alta, por lo que a su vez crea una cola con un orden creciente de valores.
• Dequeue: Dequeue también se conoce como Double Ended Queue. Como sugiere el nombre, doble extremo significa que un elemento se puede insertar o eliminar de ambos extremos de la cola, a diferencia de las otras colas en las que solo se puede hacer desde un extremo. Debido a esta propiedad, es posible que no obedezca la propiedad Primero en entrar, primero en salir. 

  Descripción general de las estructuras de datos | Conjunto 2 (Árbol binario, BST, Heap y Hash) 

  Este artículo es una contribución de Abhiraj Smit . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.