Introducción a la lista multienlazada

Una lista de enlaces múltiples es un tipo especial de lista que contiene dos o más secuencias de teclas lógicas. Antes de verificar los detalles sobre la lista de enlaces múltiples, vea qué es una lista enlazada. Una lista enlazada es una estructura de datos que está libre de cualquier restricción de tamaño hasta que la memoria del montón no esté llena. Hemos visto diferentes tipos de listas enlazadas, como Lista enlazada simple , Lista enlazada circular y Lista enlazada doblemente . Aquí veremos acerca de la lista de enlaces múltiples.

En una lista de enlaces múltiples, cada Node puede tener un número N de punteros a otros Nodes. Una lista de enlaces múltiples generalmente se usa para organizar múltiples órdenes de un conjunto de elementos.

Propiedades de la lista de enlaces múltiples:

Las propiedades de una lista de enlaces múltiples se mencionan a continuación.

• Es una lista integrada de estructuras relacionadas.
• Todos los Nodes se integran mediante enlaces de punteros.
• Los Nodes vinculados están conectados con datos relacionados.
• Los Nodes contienen punteros de una estructura a otra.

Estructura de la lista de enlaces múltiples:

La estructura de una lista de enlaces múltiples depende de la estructura de un Node. Un solo Node generalmente contiene dos cosas:

• Una lista de punteros
• Todos los datos relevantes.

 A continuación se muestra la estructura de un Node que contiene solo un dato y una lista de punteros.

typedef struct node {
    int data;
    vector<struct node*> pointers;
} Node;

/*package whatever //do not write package name here */
 
import java.io.*;
 
class GFG {
    public static void main(String[] args) {}
    public static class Node {
        int data;
        Node[] children;
    };
}
 
// This code is contributed by ishankhandelwal

// C# code to create the structure of a node
 
using System;
 
class GFG
{
    public static void Main() { }
    public class Node
    {
        int data;
        Node[] children;
    };
}
 
// This code is contributed by Saurabh jaiswal

Casos de uso de listas multienlazadas:

Algunos casos de uso de una lista de enlaces múltiples son:

• Múltiples órdenes de un conjunto de elementos.
• Representación de una array dispersa
• Lista de lista

Múltiples órdenes de un conjunto de elementos:

• Por ejemplo, supongamos que mis elementos incluyen el nombre de una persona y su edad. p.ej

(ANIMESH, 19), (SUMIT, 17), (HARDIK, 22), (ISHA, 18)

Múltiples órdenes de juego

Insertar en esta estructura es muy parecido a insertar el mismo Node en dos listas separadas. En las listas de enlaces múltiples, es bastante común tener punteros hacia atrás, es decir, inversos de cada uno de los enlaces hacia adelante; en el ejemplo anterior, esto significaría que cada Node tiene 4 punteros.

Representación de array dispersa:

Las listas multienlazadas se utilizan para almacenar arrays dispersas. Una array dispersa es una array que tiene pocos valores distintos de cero. Si usamos una array normal para almacenar dicha array, terminará desperdiciando mucho espacio.

Array de repuesto

La array dispersa se puede representar usando una lista enlazada para cada fila y columna. 

• Un Node en una lista de enlaces múltiples tiene cuatro partes: 
  • La primera parte almacena los datos. 
  • El segundo almacena el puntero a la siguiente fila.
  • Tercero para el puntero a la siguiente columna y 
  • Cuarto para almacenar el número de coordenadas de la celda en la array.

Representación de array dispersa

Lista de lista:

Una lista de enlaces múltiples se puede utilizar para representar una lista de listas. Por ejemplo, podemos crear una lista enlazada donde cada Node sea en sí mismo una lista y tenga punteros a otros Nodes. 
Vea la estructura a continuación:

• Es una estructura de datos bidimensional.
• Aquí cada Node tiene tres campos:
  • El primer campo almacena los datos.
  • El segundo campo almacena un puntero al Node secundario.
  • El tercer campo almacena el puntero al siguiente Node.

Lista de lista (lista enlazada de varios niveles)

Ventajas de la lista de enlaces múltiples:

Las ventajas de una lista multienlazada son:

• Los conjuntos de los mismos datos se pueden procesar en múltiples secuencias.
• Los datos no se duplican en ninguna parte.
• Los datos de un tipo existen solo una vez en la lista.

Comparación de la lista multienlazada con la lista doblemente enlazada:

Veamos primero la estructura de un Node de Lista Doblemente Enlazada:

typedef struct node {
    int data;
    struct node* prev;
    struct node* next;
} Node;

/*package whatever //do not write package name here */
 
import java.io.*;
 
class GFG {
    public static void main(String[] args) {}
    public static class Node {
        int data;
        Node prev;
        Node next;
    };
}
 
// This code is contributed by ishankhandelwal

Comparación de la lista de enlaces dobles y la lista de enlaces múltiples:

• A diferencia de los Nodes dobles en una lista de enlaces múltiples, puede tener o no un inverso para cada puntero.
• Una lista doblemente enlazada tiene exactamente dos punteros, si la lista multienlazada puede tener múltiples punteros
• En una lista doblemente enlazada, los punteros son exactamente opuestos entre sí, pero en una lista multienlazada, no es así.
• La lista doblemente enlazada es un caso especial de lista multienlazada.