Lista enlazada desenrollada | Serie 1 (Introducción)

Al igual que la array y la lista enlazada, la lista enlazada desenrollada también es una estructura de datos lineal y es una variante de una lista enlazada. 

¿Por qué necesitamos una lista enlazada desenrollada?

Una de las mayores ventajas de las listas enlazadas sobre los arreglos es que insertar un elemento en cualquier ubicación requiere solo O(1). Sin embargo, el problema aquí es que para buscar un elemento en una lista enlazada se necesita O(n). Entonces, para resolver el problema de la búsqueda, es decir, reducir el tiempo de búsqueda del elemento, se propuso el concepto de listas enlazadas desenrolladas. La lista enlazada desenrollada cubre las ventajas tanto de la array como de la lista enlazada, ya que reduce la sobrecarga de memoria en comparación con las listas enlazadas simples al almacenar múltiples elementos en cada Node y también tiene la ventaja de una inserción y eliminación rápidas como la de una lista enlazada.

ventajas:

• Debido al comportamiento de la memoria caché, la búsqueda lineal es mucho más rápida en las listas enlazadas desenrolladas.
• En comparación con la lista enlazada ordinaria, requiere menos espacio de almacenamiento para punteros/referencias.
• Realiza operaciones como inserción, eliminación y recorrido más rápidamente que las listas enlazadas ordinarias (porque la búsqueda es más rápida).

Desventajas:

• La sobrecarga por Node es comparativamente alta que las listas de enlace simple. Consulte un Node de ejemplo en el siguiente código

Ejemplo: digamos que tenemos 8 elementos, entonces sqrt (8) = 2.82 que se redondea a 3. Entonces, cada bloque almacenará 3 elementos. Por lo tanto, para almacenar 8 elementos, se crearán 3 bloques, de los cuales los primeros dos bloques almacenarán 3 elementos y el último bloque almacenará 2 elementos.

¿Cómo se mejora la búsqueda en listas enlazadas desenrolladas?

Entonces, tomando el ejemplo anterior, si queremos buscar el séptimo elemento en la lista, recorremos la lista de bloques hasta el que contiene el séptimo elemento. Solo se necesita O (sqrt (n)) ya que lo encontramos al no pasar más de sqrt (n) bloques. 

Implementación sencilla:

El siguiente programa crea una lista enlazada desenrollada simple con 3 Nodes que contienen un número variable de elementos en cada uno. También atraviesa la lista creada.

// C++ program to implement unrolled linked list
// and traversing it.
#include <bits/stdc++.h>
using namespace std;
#define maxElements 4
 
// Unrolled Linked List Node
class Node
{
    public:
    int numElements;
    int array[maxElements];
    Node *next;
};
 
/* Function to traverse an unrolled linked list
and print all the elements*/
void printUnrolledList(Node *n)
{
    while (n != NULL)
    {
        // Print elements in current node
        for (int i=0; i<n->numElements; i++)
            cout<<n->array[i]<<" ";
 
        // Move to next node
        n = n->next;
    }
}
 
// Program to create an unrolled linked list
// with 3 Nodes
int main()
{
    Node* head = NULL;
    Node* second = NULL;
    Node* third = NULL;
 
    // allocate 3 Nodes
    head = new Node();
    second = new Node();
    third = new Node();
 
    // Let us put some values in second node (Number
    // of values must be less than or equal to
    // maxElement)
    head->numElements = 3;
    head->array[0] = 1;
    head->array[1] = 2;
    head->array[2] = 3;
 
    // Link first Node with the second Node
    head->next = second;
 
    // Let us put some values in second node (Number
    // of values must be less than or equal to
    // maxElement)
    second->numElements = 3;
    second->array[0] = 4;
    second->array[1] = 5;
    second->array[2] = 6;
 
    // Link second Node with the third Node
    second->next = third;
 
    // Let us put some values in third node (Number
    // of values must be less than or equal to
    // maxElement)
    third->numElements = 3;
    third->array[0] = 7;
    third->array[1] = 8;
    third->array[2] = 9;
    third->next = NULL;
 
    printUnrolledList(head);
 
    return 0;
}
 
// This is code is contributed by rathbhupendra

// C program to implement unrolled linked list
// and traversing it.
#include<stdio.h>
#include<stdlib.h>
#define maxElements 4
 
// Unrolled Linked List Node
struct Node
{
    int numElements;
    int array[maxElements];
    struct Node *next;
};
 
/* Function to traverse an unrolled linked list
   and print all the elements*/
void printUnrolledList(struct Node *n)
{
    while (n != NULL)
    {
        // Print elements in current node
        for (int i=0; i<n->numElements; i++)
            printf("%d ", n->array[i]);
 
        // Move to next node
        n = n->next;
    }
}
 
// Program to create an unrolled linked list
// with 3 Nodes
int main()
{
    struct Node* head = NULL;
    struct Node* second = NULL;
    struct Node* third = NULL;
 
    // allocate 3 Nodes
    head = (struct Node*)malloc(sizeof(struct Node));
    second = (struct Node*)malloc(sizeof(struct Node));
    third = (struct Node*)malloc(sizeof(struct Node));
 
    // Let us put some values in second node (Number
    // of values must be less than or equal to
    // maxElement)
    head->numElements = 3;
    head->array[0] = 1;
    head->array[1] = 2;
    head->array[2] = 3;
 
    // Link first Node with the second Node
    head->next = second;
 
    // Let us put some values in second node (Number
    // of values must be less than or equal to
    // maxElement)
    second->numElements = 3;
    second->array[0] = 4;
    second->array[1] = 5;
    second->array[2] = 6;
 
    // Link second Node with the third Node
    second->next = third;
 
    // Let us put some values in third node (Number
    // of values must be less than or equal to
    // maxElement)
    third->numElements = 3;
    third->array[0] = 7;
    third->array[1] = 8;
    third->array[2] = 9;
    third->next = NULL;
 
    printUnrolledList(head);
 
    return 0;
}

// Java program to implement unrolled
// linked list and traversing it.
import java.util.*;
 
class GFG{
     
static final int maxElements = 4;
 
// Unrolled Linked List Node
static class Node
{
    int numElements;
    int []array = new int[maxElements];
    Node next;
};
 
// Function to traverse an unrolled
// linked list  and print all the elements
static void printUnrolledList(Node n)
{
    while (n != null)
    {
       
        // Print elements in current node
        for(int i = 0; i < n.numElements; i++)
            System.out.print(n.array[i] + " ");
 
        // Move to next node
        n = n.next;
    }
}
 
// Program to create an unrolled linked list
// with 3 Nodes
public static void main(String[] args)
{
    Node head = null;
    Node second = null;
    Node third = null;
 
    // Allocate 3 Nodes
    head = new Node();
    second = new Node();
    third = new Node();
 
    // Let us put some values in second
    // node (Number of values must be
    // less than or equal to maxElement)
    head.numElements = 3;
    head.array[0] = 1;
    head.array[1] = 2;
    head.array[2] = 3;
 
    // Link first Node with the
    // second Node
    head.next = second;
 
    // Let us put some values in
    // second node (Number of values
    // must be less than or equal to
    // maxElement)
    second.numElements = 3;
    second.array[0] = 4;
    second.array[1] = 5;
    second.array[2] = 6;
 
    // Link second Node with the third Node
    second.next = third;
 
    // Let us put some values in third
    // node (Number of values must be
    // less than or equal to maxElement)
    third.numElements = 3;
    third.array[0] = 7;
    third.array[1] = 8;
    third.array[2] = 9;
    third.next = null;
 
    printUnrolledList(head);
}
}
 
// This code is contributed by amal kumar choubey 

# Python3 program to implement unrolled
# linked list and traversing it.
maxElements = 4
 
# Unrolled Linked List Node
class Node:
     
    def __init__(self):
         
        self.numElements = 0
        self.array = [0 for i in range(maxElements)]
        self.next = None
 
# Function to traverse an unrolled linked list
# and print all the elements
def printUnrolledList(n):
 
    while (n != None):
 
        # Print elements in current node
        for i in range(n.numElements):
            print(n.array[i], end = ' ')
 
        # Move to next node
        n = n.next
 
# Driver Code
if __name__=='__main__':
     
    head = None
    second = None
    third = None
 
    # Allocate 3 Nodes
    head = Node()
    second = Node()
    third = Node()
 
    # Let us put some values in second
    # node (Number of values must be
    # less than or equal to
    # maxElement)
    head.numElements = 3
    head.array[0] = 1
    head.array[1] = 2
    head.array[2] = 3
 
    # Link first Node with the second Node
    head.next = second
 
    # Let us put some values in second node
    # (Number of values must be less than
    # or equal to maxElement)
    second.numElements = 3
    second.array[0] = 4
    second.array[1] = 5
    second.array[2] = 6
 
    # Link second Node with the third Node
    second.next = third
 
    # Let us put some values in third node
    # (Number of values must be less than
    # or equal to maxElement)
    third.numElements = 3
    third.array[0] = 7
    third.array[1] = 8
    third.array[2] = 9
    third.next = None
 
    printUnrolledList(head)
     
# This code is contributed by rutvik_56

// C# program to implement unrolled
// linked list and traversing it.
using System;
class GFG{
     
static readonly int maxElements = 4;
 
// Unrolled Linked List Node
class Node
{
  public int numElements;
  public int []array = new int[maxElements];
  public Node next;
};
 
// Function to traverse an unrolled
// linked list  and print all the elements
static void printUnrolledList(Node n)
{
  while (n != null)
  {
    // Print elements in current node
    for(int i = 0; i < n.numElements; i++)
      Console.Write(n.array[i] + " ");
 
    // Move to next node
    n = n.next;
  }
}
 
// Program to create an unrolled linked list
// with 3 Nodes
public static void Main(String[] args)
{
  Node head = null;
  Node second = null;
  Node third = null;
 
  // Allocate 3 Nodes
  head = new Node();
  second = new Node();
  third = new Node();
 
  // Let us put some values in second
  // node (Number of values must be
  // less than or equal to maxElement)
  head.numElements = 3;
  head.array[0] = 1;
  head.array[1] = 2;
  head.array[2] = 3;
 
  // Link first Node with the
  // second Node
  head.next = second;
 
  // Let us put some values in
  // second node (Number of values
  // must be less than or equal to
  // maxElement)
  second.numElements = 3;
  second.array[0] = 4;
  second.array[1] = 5;
  second.array[2] = 6;
 
  // Link second Node with the third Node
  second.next = third;
 
  // Let us put some values in third
  // node (Number of values must be
  // less than or equal to maxElement)
  third.numElements = 3;
  third.array[0] = 7;
  third.array[1] = 8;
  third.array[2] = 9;
  third.next = null;
 
  printUnrolledList(head);
}
}
 
// This code is contributed by Rajput-Ji

<script>
 
      // JavaScript program to implement unrolled
      // linked list and traversing it.
      const maxElements = 4;
 
      // Unrolled Linked List Node
      class Node {
        constructor() {
          this.numElements = 0;
          this.array = new Array(maxElements);
          this.next = null;
        }
      }
 
      // Function to traverse an unrolled
      // linked list and print all the elements
      function printUnrolledList(n) {
        while (n != null) {
          // Print elements in current node
          for (var i = 0; i < n.numElements; i++)
            document.write(n.array[i] + " ");
 
          // Move to next node
          n = n.next;
        }
      }
 
      // Program to create an unrolled linked list
      // with 3 Nodes
 
      var head = null;
      var second = null;
      var third = null;
 
      // Allocate 3 Nodes
      head = new Node();
      second = new Node();
      third = new Node();
 
      // Let us put some values in second
      // node (Number of values must be
      // less than or equal to maxElement)
      head.numElements = 3;
      head.array[0] = 1;
      head.array[1] = 2;
      head.array[2] = 3;
 
      // Link first Node with the
      // second Node
      head.next = second;
 
      // Let us put some values in
      // second node (Number of values
      // must be less than or equal to
      // maxElement)
      second.numElements = 3;
      second.array[0] = 4;
      second.array[1] = 5;
      second.array[2] = 6;
 
      // Link second Node with the third Node
      second.next = third;
 
      // Let us put some values in third
      // node (Number of values must be
      // less than or equal to maxElement)
      third.numElements = 3;
      third.array[0] = 7;
      third.array[1] = 8;
      third.array[2] = 9;
      third.next = null;
 
      printUnrolledList(head);
       
</script>

1 2 3 4 5 6 7 8 9 

Análisis de Complejidad:

• Complejidad temporal: O(n).
• Complejidad espacial: O(n).

En este artículo, presentamos una lista detallada y sus ventajas. También hemos mostrado cómo recorrer la lista. En el próximo artículo, analizaremos en detalle la inserción, la eliminación y los valores de maxElements/numElements.

Inserción en lista enlazada desenrollada

Este artículo es una contribución de Harsh Agarwal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.