Lista enlazada desenrollada | Conjunto 1 (Introducción)
Al igual que la matriz y la lista vinculada, la lista vinculada desenrollada también es una estructura de datos lineal y es una variante de una lista vinculada.
¿Por qué necesitamos una lista enlazada desenrollada?
Una de las mayores ventajas de las listas enlazadas sobre las matrices es que insertar un elemento en cualquier ubicación solo requiere O(1). Sin embargo, el problema aquí es que para buscar un elemento en una lista vinculada 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 matriz 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 nodo y también tiene la ventaja de una inserción y eliminación rápidas como las de una lista enlazada.
Ventajas:
- Debido al comportamiento de la caché, la búsqueda lineal es mucho más rápida en 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 normales (porque la búsqueda es más rápida).
Desventajas:
- La sobrecarga por nodo es comparativamente alta que la de las listas enlazadas individualmente. Consulte un nodo de ejemplo en el siguiente código.
Ejemplo: Digamos que tenemos 8 elementos, por lo que 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 dos primeros bloques almacenarán 3 elementos y el último bloque almacenará 2 elementos.
¿Cómo 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 ir más de bloques sqrt(n).
Implementación sencilla:
El siguiente programa crea una lista enlazada desenrollada simple con 3 nodos que contienen un número variable de elementos en cada uno. También recorre la lista creada.
C++ // C++ program to implement unrolled linked list // and traversing it. #include 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 // C program to implement unrolled linked list // and traversing it. #include #include #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 // 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 # 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# // 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
JavaScript < 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>
Producción
1 2 3 4 5 6 7 8 9
Análisis de complejidad:
En este artículo hemos presentado una lista desplegada y sus ventajas. También hemos mostrado cómo recorrer la lista. En el próximo artículo discutiremos en detalle la eliminación de inserción y los valores de maxElements/numElements.
Inserción en lista enlazada desenrollada
Crear cuestionario
Te Puede Gustar
Artículos Más Populares
