Una lista enlazada desenrollada es una lista enlazada de arrays pequeñas, todas del mismo tamaño donde cada una es tan pequeña que la inserción o eliminación es rápida y rápida, pero lo suficientemente grande como para llenar la línea de caché. Un iterador que apunta a la lista consiste en un puntero a un Node y un índice en ese Node que contiene una array. También es una estructura de datos y es otra variante de Lista enlazada. Está relacionado con B-Tree. Puede almacenar una array de elementos en un Node a diferencia de una lista enlazada normal que almacena un solo elemento en un Node. Es una combinación de arrays y listas enlazadas fusionadas en una sola. Aumenta el rendimiento de la memoria caché y reduce la sobrecarga de memoria asociada con el almacenamiento de referencias para metadatos. Otras ventajas y desventajas importantes ya se mencionan en el artículo anterior.
Requisito previo : Introducción a la lista enlazada desenrollada
A continuación se muestra la operación de inserción y visualización de la lista enlazada desenrollada.
Input : 72 76 80 94 90 70 capacity = 3 Output : Unrolled Linked List : 72 76 80 94 90 70 Explanation : The working is well shown in the algorithm below. The nodes get broken at the mentioned capacity i.e., 3 here, when 3rd element is entered, the flow moves to another newly created node. Every node contains an array of size (int)[(capacity / 2) + 1]. Here it is 2. Input : 49 47 62 51 77 17 71 71 35 76 36 54 capacity = 5 Output : Unrolled Linked List : 49 47 62 51 77 17 71 71 35 76 36 54 Explanation : The working is well shown in the algorithm below. The nodes get broken at the mentioned capacity i.e., 5 here, when 5th element is entered, the flow moves to another newly created node. Every node contains an array of size (int)[(capacity / 2) + 1]. Here it is 3.
Algoritmo:
Insert (ElementToBeInserted) if start_pos == NULL Insert the first element into the first node start_pos.numElement ++ end_pos = start_pos If end_pos.numElements + 1 < node_size end_pos.numElements.push(newElement) end_pos.numElements ++ else create a new Node new_node move final half of end_pos.data into new_node.data new_node.data.push(newElement) end_pos.numElements = end_pos.data.size / 2 + 1 end_pos.next = new_node end_pos = new_node
A continuación se muestra la implementación Java de la operación de inserción y visualización. En el siguiente código, la capacidad es 5 y se ingresan números aleatorios.
Java
/* Java program to show the insertion operation * of Unrolled Linked List */ import java.util.Scanner; import java.util.Random; // class for each node class UnrollNode { UnrollNode next; int num_elements; int array[]; // Constructor public UnrollNode(int n) { next = null; num_elements = 0; array = new int[n]; } } // Operation of Unrolled Function class UnrollLinkList { private UnrollNode start_pos; private UnrollNode end_pos; int size_node; int nNode; // Parameterized Constructor UnrollLinkList(int capacity) { start_pos = null; end_pos = null; nNode = 0; size_node = capacity + 1; } // Insertion operation void Insert(int num) { nNode++; // Check if the list starts from NULL if (start_pos == null) { start_pos = new UnrollNode(size_node); start_pos.array[0] = num; start_pos.num_elements++; end_pos = start_pos; return; } // Attaching the elements into nodes if (end_pos.num_elements + 1 < size_node) { end_pos.array[end_pos.num_elements] = num; end_pos.num_elements++; } // Creation of new Node else { UnrollNode node_pointer = new UnrollNode(size_node); int j = 0; for (int i = end_pos.num_elements / 2 + 1; i < end_pos.num_elements; i++) node_pointer.array[j++] = end_pos.array[i]; node_pointer.array[j++] = num; node_pointer.num_elements = j; end_pos.num_elements = end_pos.num_elements / 2 + 1; end_pos.next = node_pointer; end_pos = node_pointer; } } // Display the Linked List void display() { System.out.print("\nUnrolled Linked List = "); System.out.println(); UnrollNode pointer = start_pos; while (pointer != null) { for (int i = 0; i < pointer.num_elements; i++) System.out.print(pointer.array[i] + " "); System.out.println(); pointer = pointer.next; } System.out.println(); } } /* Main Class */ class UnrolledLinkedList_Check { // Driver code public static void main(String args[]) { Scanner sc = new Scanner(System.in); // create instance of Random class Random rand = new Random(); UnrollLinkList ull = new UnrollLinkList(5); // Perform Insertion Operation for (int i = 0; i < 12; i++) { // Generate random integers in range 0 to 99 int rand_int1 = rand.nextInt(100); System.out.println("Entered Element is " + rand_int1); ull.Insert(rand_int1); ull.display(); } } }
C#
/* C# program to show the insertion operation * of Unrolled Linked List */ using System; // class for each node public class UnrollNode { public UnrollNode next; public int num_elements; public int[] array; // Constructor public UnrollNode(int n) { next = null; num_elements = 0; array = new int[n]; } } // Operation of Unrolled Function public class UnrollLinkList { private UnrollNode start_pos; private UnrollNode end_pos; int size_node; int nNode; // Parameterized Constructor public UnrollLinkList(int capacity) { start_pos = null; end_pos = null; nNode = 0; size_node = capacity + 1; } // Insertion operation public void Insert(int num) { nNode++; // Check if the list starts from NULL if (start_pos == null) { start_pos = new UnrollNode(size_node); start_pos.array[0] = num; start_pos.num_elements++; end_pos = start_pos; return; } // Attaching the elements into nodes if (end_pos.num_elements + 1 < size_node) { end_pos.array[end_pos.num_elements] = num; end_pos.num_elements++; } // Creation of new Node else { UnrollNode node_pointer = new UnrollNode(size_node); int j = 0; for (int i = end_pos.num_elements / 2 + 1; i < end_pos.num_elements; i++) node_pointer.array[j++] = end_pos.array[i]; node_pointer.array[j++] = num; node_pointer.num_elements = j; end_pos.num_elements = end_pos.num_elements / 2 + 1; end_pos.next = node_pointer; end_pos = node_pointer; } } // Display the Linked List public void display() { Console.Write("\nUnrolled Linked List = "); Console.WriteLine(); UnrollNode pointer = start_pos; while (pointer != null) { for (int i = 0; i < pointer.num_elements; i++) Console.Write(pointer.array[i] + " "); Console.WriteLine(); pointer = pointer.next; } Console.WriteLine(); } } /* Main Class */ public class UnrolledLinkedList_Check { // Driver code public static void Main(String[] args) { // create instance of Random class Random rand = new Random(); UnrollLinkList ull = new UnrollLinkList(5); // Perform Insertion Operation for (int i = 0; i < 12; i++) { // Generate random integers in range 0 to 99 int rand_int1 = rand.Next(100); Console.WriteLine("Entered Element is " + rand_int1); ull.Insert(rand_int1); ull.display(); } } } // This code has been contributed by 29AjayKumar
Javascript
<script> /* Javascript program to show the insertion operation * of Unrolled Linked List */ // class for each node class UnrollNode { // Constructor constructor(n) { this.next = null; this.num_elements = 0; this.array = new Array(n); for(let i = 0; i < n; i++) { this.array[i] = 0; } } } // Operation of Unrolled Function class UnrollLinkList { // Parameterized Constructor constructor(capacity) { this.start_pos = null; this.end_pos = null; this.nNode = 0; this.size_node = capacity + 1; } // Insertion operation Insert(num) { this.nNode++; // Check if the list starts from NULL if (this.start_pos == null) { this.start_pos = new UnrollNode(this.size_node); this.start_pos.array[0] = num; this.start_pos.num_elements++; this.end_pos = this.start_pos; return; } // Attaching the elements into nodes if (this.end_pos.num_elements + 1 < this.size_node) { this.end_pos.array[this.end_pos.num_elements] = num; this.end_pos.num_elements++; } // Creation of new Node else { let node_pointer = new UnrollNode(this.size_node); let j = 0; for (let i = Math.floor(this.end_pos.num_elements / 2 )+ 1; i < this.end_pos.num_elements; i++) node_pointer.array[j++] = this.end_pos.array[i]; node_pointer.array[j++] = num; node_pointer.num_elements = j; this.end_pos.num_elements = Math.floor(this.end_pos.num_elements / 2) + 1; this.end_pos.next = node_pointer; this.end_pos = node_pointer; } } // Display the Linked List display() { document.write("<br>Unrolled Linked List = "); document.write("<br>"); let pointer = this.start_pos; while (pointer != null) { for (let i = 0; i < pointer.num_elements; i++) document.write(pointer.array[i] + " "); document.write("<br>"); pointer = pointer.next; } document.write("<br>"); } } // Driver code let ull = new UnrollLinkList(5); // Perform Insertion Operation for (let i = 0; i < 12; i++) { // Generate random integers in range 0 to 99 let rand_int1 = Math.floor(Math.random()*(100)); document.write("Entered Element is " + rand_int1+"<br>"); ull.Insert(rand_int1); ull.display(); } // This code is contributed by rag2127 </script>
Entered Element is 90 Unrolled Linked List = 90 Entered Element is 3 Unrolled Linked List = 90 3 Entered Element is 12 Unrolled Linked List = 90 3 12 Entered Element is 43 Unrolled Linked List = 90 3 12 43 Entered Element is 88 Unrolled Linked List = 90 3 12 43 88 Entered Element is 94 Unrolled Linked List = 90 3 12 43 88 94 Entered Element is 15 Unrolled Linked List = 90 3 12 43 88 94 15 Entered Element is 7 Unrolled Linked List = 90 3 12 43 88 94 15 7 Entered Element is 67 Unrolled Linked List = 90 3 12 43 88 94 15 7 67 Entered Element is 74 Unrolled Linked List = 90 3 12 43 88 94 15 7 67 74 Entered Element is 85 Unrolled Linked List = 90 3 12 43 88 94 15 7 67 74 85 Entered Element is 48 Unrolled Linked List = 90 3 12 43 88 94 15 7 67 74 85 48
Complejidad del tiempo: O(n)
Además, pocas aplicaciones del mundo real:
- Se utiliza en B-Tree y T-Tree
- Utilizado en árbol de array hash
- Utilizado en la lista de saltos
- Utilizado en la codificación CDR
Publicación traducida automáticamente
Artículo escrito por Chinmoy Lenka y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA