ELENCO COLLEGATO SROTOLATO | SET 1 (INTRODUZIONE)

Come l'array e l'elenco collegato, anche l'elenco collegato srotolato è una struttura dati lineare ed è una variante di un elenco collegato.

Perché abbiamo bisogno di un elenco collegato srotolato?

Uno dei maggiori vantaggi delle liste concatenate rispetto agli array è che l'inserimento di un elemento in qualsiasi posizione richiede solo O(1). Tuttavia il problema qui è che per cercare un elemento in un elenco collegato è necessario O(n). Quindi, per risolvere il problema della ricerca, ovvero ridurre il tempo di ricerca dell'elemento, è stato proposto il concetto di elenchi concatenati srotolati. L'elenco concatenato srotolato copre i vantaggi sia dell'array che dell'elenco concatenato poiché riduce il sovraccarico di memoria rispetto ai semplici elenchi concatenati memorizzando più elementi su ciascun nodo e presenta anche il vantaggio di un inserimento ed eliminazione rapidi come quelli di un elenco concatenato.

Elenco collegato srotolato | Set 1 (Introduzione) elencolink non srotolato' title=

Vantaggi:

A causa del comportamento della cache, la ricerca lineare è molto più veloce negli elenchi collegati srotolati.
Rispetto alla normale lista concatenata richiede meno spazio di archiviazione per puntatori/riferimenti.
Esegue operazioni come la cancellazione degli inserimenti e l'attraversamento più rapidamente delle normali liste collegate (perché la ricerca è più veloce).

Svantaggi:

Il sovraccarico per nodo è relativamente elevato rispetto agli elenchi collegati singolarmente. Fare riferimento a un nodo di esempio nel codice seguente

Esempio: Diciamo che abbiamo 8 elementi, quindi sqrt(8)=2,82 che arrotonda a 3. Quindi ogni blocco memorizzerà 3 elementi. Quindi per memorizzare 8 elementi verranno creati 3 blocchi di cui i primi due blocchi memorizzeranno 3 elementi e l'ultimo blocco memorizzerà 2 elementi.

In che modo la ricerca migliora negli elenchi collegati srotolati?

Quindi, prendendo l'esempio sopra, se vogliamo cercare il 7° elemento nell'elenco, attraversiamo l'elenco dei blocchi fino a quello che contiene il 7° elemento. Ci vuole solo O(sqrt(n)) poiché l'abbiamo trovato non superando i blocchi sqrt(n).

Implementazione semplice:

Il programma seguente crea un semplice elenco collegato srotolato con 3 nodi contenenti un numero variabile di elementi in ciascuno. Attraversa anche l'elenco creato.

numpy linspace

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 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# 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>

Produzione

1 2 3 4 5 6 7 8 9

Analisi della complessità:

Complessità temporale: O(n). Complessità spaziale: O(n).

In questo articolo abbiamo introdotto un elenco srotolato e i suoi vantaggi. Abbiamo anche mostrato come attraversare la lista. Nel prossimo articolo discuteremo in dettaglio l'eliminazione dell'inserimento e i valori di maxElements/numElements.

Inserimento in Linked List srotolati