УНРОЛЛЕД ЛИНКЕД ЛИСТ | СЕТ 1 (УВОД)

Као и низ и повезана листа, и немотана повезана листа је такође линеарна структура података и варијанта је повезане листе.

Зашто нам је потребна одмотана повезана листа?

Једна од највећих предности повезаних листа у односу на низове је да уметање елемента на било коју локацију захтева само О(1). Међутим, квака је у томе што је за претрагу елемента на повезаној листи потребно О(н). Дакле, да би се решио проблем претраживања, односно смањио време за претрагу елемента, представљен је концепт одмотаних повезаних листа. Одмотана повезана листа покрива предности и низа и повезане листе јер смањује оптерећење меморије у поређењу са једноставним повезаним листама тако што чува више елемената на сваком чвору, а такође има предност брзог уметања и брисања као код повезане листе.

Унроллед Линкед Лист | Сет 1 (Увод) унролледлинкедлист

Предности:

Због понашања кеша, линеарна претрага је много бржа у одмотаним повезаним листама.
У поређењу са обичном повезаном листом, она захтева мање простора за складиштење показивача/референци.
Обавља операције попут брисања уметања и преласка брже од обичних повезаних листа (јер је претрага бржа).

Недостаци:

Прекомерни трошкови по чвору су релативно високи у односу на једноструко повезане листе. Погледајте пример чвора у коду испод

Пример: Рецимо да имамо 8 елемената тако да скрт(8)=2,82 што се заокружује на 3. Дакле, сваки блок ће похранити 3 елемента. Дакле, за складиштење 8 елемената биће креирана 3 блока од којих ће прва два блока чувати 3 елемента, а последњи блок 2 елемента.

Како претраживање постаје боље у немотаним повезаним листама?

Дакле, узимајући горњи пример, ако желимо да тражимо 7. елемент на листи, прелазимо преко листе блокова до оног који садржи 7. елемент. Потребно је само О(скрт(н)) пошто смо открили да не иде више од скрт(н) блокова.

Једноставна имплементација:

Програм у наставку креира једноставну одмотану повезану листу са 3 чвора који садрже променљив број елемената у сваком. Такође прелази креирану листу.

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>

Излаз

1 2 3 4 5 6 7 8 9

Анализа сложености:

Временска сложеност: О(н). Сложеност простора: О(н).

У овом чланку представили смо неразмотану листу и њене предности. Такође смо показали како се прелази преко листе. У следећем чланку ћемо детаљно расправљати о брисању уметања и вредностима макЕлементс/нумЕлементс.

Уметање у одмотану повезану листу

Креирај квиз