UITGEROLD GELINKTE LIJST | SET 1 (INLEIDING)

Net als array en gekoppelde lijst is ook de uitgerolde gekoppelde lijst een lineaire datastructuur en een variant van een gekoppelde lijst.

Waarom hebben we een uitgerolde gekoppelde lijst nodig?

Een van de grootste voordelen van gekoppelde lijsten ten opzichte van arrays is dat het invoegen van een element op welke locatie dan ook slechts O(1) kost. Het probleem hier is echter dat voor het zoeken naar een element in een gekoppelde lijst O(n) nodig is. Om het zoekprobleem op te lossen, dat wil zeggen de tijd voor het zoeken naar het element te verminderen, werd het concept van uitgerolde gekoppelde lijsten naar voren gebracht. De uitgerolde gekoppelde lijst omvat de voordelen van zowel array als gekoppelde lijst, omdat het de geheugenoverhead vermindert in vergelijking met eenvoudige gekoppelde lijsten door meerdere elementen op elk knooppunt op te slaan, en het heeft ook het voordeel van snel invoegen en verwijderen als dat van een gekoppelde lijst.

Uitgerold gelinkte lijst | Set 1 (inleiding) uitgeroldgekoppeldelijst

Voordelen:

Vanwege het cachegedrag is lineair zoeken veel sneller in uitgerolde gekoppelde lijsten.
In vergelijking met de gewone gekoppelde lijst vereist het minder opslagruimte voor verwijzingen/referenties.
Het voert bewerkingen zoals invoegen, verwijderen en doorlopen sneller uit dan gewone gekoppelde lijsten (omdat zoeken sneller is).

Nadelen:

De overhead per knooppunt is relatief hoog dan bij afzonderlijk gekoppelde lijsten. Raadpleeg een voorbeeldknooppunt in de onderstaande code

Voorbeeld: Laten we zeggen dat we 8 elementen hebben, dus sqrt(8)=2,82, wat wordt afgerond op 3. Elk blok kan dus 3 elementen opslaan. Om 8 elementen op te slaan, worden er dus 3 blokken gemaakt, waarvan de eerste twee blokken 3 elementen opslaan en het laatste blok 2 elementen.

Hoe wordt zoeken beter in uitgerolde gekoppelde lijsten?

Dus als we het bovenstaande voorbeeld nemen en naar het zevende element in de lijst willen zoeken, doorkruisen we de lijst met blokken naar het blok dat het zevende element bevat. Er is slechts O(sqrt(n)) voor nodig, omdat we het hebben gevonden door niet meer dan sqrt(n) blokken te gebruiken.

Eenvoudige implementatie:

Het onderstaande programma maakt een eenvoudige, uitgerolde, gekoppelde lijst met 3 knooppunten die elk een variabel aantal elementen bevatten. Het doorkruist ook de gemaakte lijst.

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>

Uitvoer

1 2 3 4 5 6 7 8 9

Complexiteitsanalyse:

Tijdcomplexiteit: O(n). Ruimtecomplexiteit: O(n).

In dit artikel hebben we een uitgerolde lijst en de voordelen ervan geïntroduceerd. We hebben ook laten zien hoe u door de lijst kunt bladeren. In het volgende artikel zullen we het verwijderen van invoegingen en de waarden van maxElements/numElements in detail bespreken.

Invoeging in uitgerolde gekoppelde lijst

Quiz maken