ROZWINIĘTA LISTA POŁĄCZONA | ZESTAW 1 (WPROWADZENIE)

Podobnie jak tablica i lista połączona, rozwinięta lista połączona jest również liniową strukturą danych i jest wariantem listy połączonej.

Dlaczego potrzebujemy rozwiniętej listy połączonej?

Jedną z największych zalet list połączonych w porównaniu z tablicami jest to, że wstawienie elementu w dowolnym miejscu zajmuje tylko O(1). Jednak haczyk polega na tym, że przeszukanie elementu na połączonej liście wymaga O(n). Aby więc rozwiązać problem wyszukiwania, czyli skrócić czas wyszukiwania elementu, zaproponowano koncepcję rozwijanych list połączonych. Rozwinięta lista połączona obejmuje zalety zarówno tablicy, jak i listy połączonej, ponieważ zmniejsza obciążenie pamięci w porównaniu z prostymi listami połączonymi, przechowując wiele elementów w każdym węźle, a także ma tę zaletę, że umożliwia szybkie wstawianie i usuwanie, jak w przypadku listy połączonej.

Rozwinięta lista połączona | Zestaw 1 (Wprowadzenie) rozwinięta lista linków

Zalety:

Ze względu na zachowanie pamięci podręcznej wyszukiwanie liniowe jest znacznie szybsze na rozwijanych listach połączonych.
W porównaniu do zwykłej listy połączonej wymaga mniej miejsca na wskaźniki/odniesienia.
Wykonuje operacje takie jak wstawianie, usuwanie i przeglądanie szybciej niż zwykłe listy połączone (ponieważ wyszukiwanie jest szybsze).

Wady:

Narzut na węzeł jest stosunkowo wysoki niż w przypadku list pojedynczo połączonych. Zapoznaj się z przykładowym węzłem w poniższym kodzie

Przykład: Powiedzmy, że mamy 8 elementów, więc sqrt(8)=2,82, co zaokrągla do 3. Zatem każdy blok będzie przechowywać 3 elementy. Zatem do przechowywania 8 elementów zostaną utworzone 3 bloki, z których pierwsze dwa bloki będą przechowywać 3 elementy, a ostatni blok będzie przechowywać 2 elementy.

W jaki sposób wyszukiwanie staje się lepsze na rozwijanych listach połączonych?

Biorąc więc powyższy przykład, jeśli chcemy wyszukać 7. element na liście, przechodzimy przez listę bloków do tego, który zawiera 7. element. Zajmuje tylko O(sqrt(n)), ponieważ znaleźliśmy to, przechodząc nie więcej niż sqrt(n) bloków.

Prosta implementacja:

Poniższy program tworzy prostą, rozwiniętą listę połączoną z 3 węzłami zawierającymi zmienną liczbę elementów w każdym. Przechodzi także przez utworzoną listę.

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>

Wyjście

1 2 3 4 5 6 7 8 9

Analiza złożoności:

Złożoność czasowa: O(n). Złożoność przestrzeni: O(n).

W tym artykule przedstawiliśmy listę rozwijaną i jej zalety. Pokazaliśmy także, jak poruszać się po liście. W następnym artykule szczegółowo omówimy usuwanie wstawiania i wartości maxElements/numElements.

Wstawienie na rozwiniętą listę połączoną

Utwórz quiz