UNROLLED LINKED LIST | SADA 1 (ÚVOD)

Rovnako ako pole a prepojený zoznam je aj rozbalený prepojený zoznam lineárnou dátovou štruktúrou a je variantom prepojeného zoznamu.

Prečo potrebujeme rozbalený prepojený zoznam?

Jednou z najväčších výhod spojených zoznamov oproti poliam je, že vloženie prvku na ľubovoľné miesto trvá iba O(1). Háčik je však v tom, že vyhľadávanie prvku v prepojenom zozname trvá O(n). Aby sa teda vyriešil problém vyhľadávania, t. j. skrátenie času na vyhľadávanie prvku, bol navrhnutý koncept rozbalených prepojených zoznamov. Rozvinutý prepojený zoznam pokrýva výhody poľa aj prepojeného zoznamu, pretože znižuje réžiu pamäte v porovnaní s jednoduchými prepojenými zoznamami ukladaním viacerých prvkov v každom uzle a má tiež výhodu rýchleho vkladania a vymazávania ako prepojený zoznam.

Unrolled Linked List | Sada 1 (úvod) unrolledlinkedlist' title=

Výhody:

Kvôli správaniu vyrovnávacej pamäte je lineárne vyhľadávanie oveľa rýchlejšie v rozbalených prepojených zoznamoch.
V porovnaní s bežným prepojeným zoznamom vyžaduje menej úložného priestoru pre ukazovatele/odkazy.
Vykonáva operácie ako vkladanie vymazanie a prechádzanie rýchlejšie ako bežné prepojené zoznamy (pretože vyhľadávanie je rýchlejšie).

Nevýhody:

Réžia na uzol je porovnateľne vysoká ako pri jednoducho prepojených zoznamoch. Pozrite si príklad uzla v kóde nižšie

Príklad: Povedzme, že máme 8 prvkov, takže sqrt(8)=2,82, čo sa zaokrúhli na 3. Takže každý blok bude obsahovať 3 prvky. Na uloženie 8 prvkov sa teda vytvoria 3 bloky, z ktorých prvé dva bloky uložia 3 prvky a posledný blok uloží 2 prvky.

Ako sa zlepší vyhľadávanie v rozbalených prepojených zoznamoch?

Ak teda chceme vyhľadať 7. prvok v zozname, prejdeme zoznamom blokov k tomu, ktorý obsahuje 7. prvok. Trvá to iba O(sqrt(n)), pretože sme to našli tak, že neprejdeme viac ako sqrt(n) bloky.

Jednoduchá implementácia:

Nižšie uvedený program vytvorí jednoduchý rozbalený prepojený zoznam s 3 uzlami obsahujúcimi premenlivý počet prvkov v každom z nich. Taktiež prechádza vytvorený zoznam.

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>

Výstup

1 2 3 4 5 6 7 8 9

Analýza zložitosti:

Časová zložitosť: O(n). Priestorová zložitosť: O(n).

V tomto článku sme predstavili rozbalený zoznam a jeho výhody. Ukázali sme tiež, ako prechádzať zoznamom. V nasledujúcom článku sa budeme podrobne zaoberať odstránením vloženia a hodnotami maxElements/numElements.

Vloženie do rozbaleného prepojeného zoznamu