IŠVYNIOTAS SUSIETŲ SĄRAŠAS | 1 RINKINYS (ĮVADAS)

Kaip ir masyvas ir susietasis sąrašas, išvyniotas susietasis sąrašas taip pat yra linijinė duomenų struktūra ir susieto sąrašo variantas.

Kodėl mums reikia išvynioto susieto sąrašo?

Vienas didžiausių susietų sąrašų pranašumų, palyginti su masyvais, yra tas, kad elemento įterpimas į bet kurią vietą užtrunka tik O(1). Tačiau svarbiausia yra tai, kad norint ieškoti elemento susietame sąraše, reikia O(n). Taigi, siekiant išspręsti paieškos problemą, ty sutrumpinti elemento paieškos laiką, buvo pasiūlyta išvyniotų susietų sąrašų koncepcija. Išvyniotas susietas sąrašas apima ir masyvo, ir susieto sąrašo pranašumus, nes sumažina atminties sąnaudas, palyginti su paprastais susietais sąrašais, nes kiekviename mazge saugo kelis elementus, taip pat turi greito įterpimo ir ištrynimo pranašumą, kaip ir susieto sąrašo.

Išvyniotas susietų sąrašas | 1 rinkinys (įvadas) išvyniotas nuorodų sąrašas

Privalumai:

Dėl talpyklos veikimo linijinė paieška yra daug greitesnė išvyniotuose susietuose sąrašuose.
Palyginti su įprastu susietu sąrašu, jam reikia mažiau vietos nuorodoms / nuorodoms laikyti.
Jis atlieka tokias operacijas kaip įterpimo ištrynimas ir perėjimas greičiau nei įprasti susieti sąrašai (nes paieška yra greitesnė).

Trūkumai:

Vieno mazgo pridėtinės išlaidos yra palyginti didesnės nei atskirai susietų sąrašų. Žr. pavyzdinį mazgą toliau pateiktame kode

Pavyzdys: Tarkime, kad turime 8 elementus, taigi sqrt(8)=2.82, kuris suapvalinamas iki 3. Taigi kiekviename bloke bus saugomi 3 elementai. Taigi 8 elementams saugoti bus sukurti 3 blokai, iš kurių pirmuose dviejuose blokuose bus saugomi 3 elementai, o paskutiniame bloke – 2 elementai.

Kaip paieška tampa geresnė išvyniotuose susietuose sąrašuose?

Taigi, atsižvelgiant į aukščiau pateiktą pavyzdį, jei norime ieškoti 7-ojo sąrašo elemento, perkeliame blokų sąrašą į tą, kuriame yra 7-asis elementas. Tai užtrunka tik O(sqrt(n)), nes radome ne daugiau nei sqrt(n) blokus.

Paprastas įgyvendinimas:

Toliau pateikta programa sukuria paprastą išvyniotą susietą sąrašą su 3 mazgais, kurių kiekviename yra kintamas elementų skaičius. Jis taip pat kerta sukurtą sąrašą.

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>

Išvestis

1 2 3 4 5 6 7 8 9

Sudėtingumo analizė:

Laiko sudėtingumas: O(n). Erdvės sudėtingumas: O(n).

Šiame straipsnyje mes pristatėme išvyniotą sąrašą ir jo pranašumus. Taip pat parodėme, kaip pereiti sąrašą. Kitame straipsnyje mes išsamiai aptarsime įterpimo ištrynimą ir maxElements / numElements reikšmes.

Įterpimas į išvyniotą susietų sąrašą

Sukurti viktoriną