RULLAAMATON LINKITETTY LUETTELO | SARJA 1 (JOHDANTO)

Kuten taulukko ja linkitetty lista, myös rullaamaton linkitetty luettelo on lineaarinen tietorakenne ja muunnos linkitetystä luettelosta.

Miksi tarvitsemme rullaamattoman linkitettyjen luettelon?

Yksi linkitettyjen listojen suurimmista eduista taulukoihin verrattuna on, että elementin lisääminen mihin tahansa paikkaan kestää vain O(1). Tässä on kuitenkin ongelma, että linkitetyn luettelon elementin etsiminen kestää O(n). Joten etsimisongelman ratkaisemiseksi eli elementin etsimiseen kuluvan ajan lyhentämiseksi esitettiin rullaamattomien linkitettyjen luetteloiden käsite. Rullattu linkitetty lista kattaa sekä taulukon että linkitetyn listan edut, koska se vähentää muistin ylimääräistä kuormaa verrattuna yksinkertaisiin linkitettyihin listoihin tallentamalla useita elementtejä jokaiseen solmuun, ja sen etuna on myös nopea lisäys ja poistaminen kuin linkitetyllä listalla.

Rullaamaton linkitetty luettelo | Sarja 1 (johdanto) unrolledlinked list' title=

Edut:

Välimuistin käyttäytymisen vuoksi lineaarinen haku on paljon nopeampi rullaamattomissa linkitetyissä luetteloissa.
Tavalliseen linkitettyyn listaan verrattuna se vaatii vähemmän tallennustilaa osoittimille/viitteille.
Se suorittaa toiminnot, kuten lisäyksen poistamisen ja läpikäynnin, nopeammin kuin tavalliset linkitetyt luettelot (koska haku on nopeampi).

Haitat:

Solmukohtaiset yleiskustannukset ovat verrattain korkeat kuin yksittäin linkitetyt luettelot. Katso esimerkkisolmu alla olevassa koodissa

Esimerkki: Oletetaan, että meillä on 8 elementtiä, joten sqrt(8) = 2,82, joka pyöristyy kolmeen. Joten jokainen lohko tallentaa 3 elementtiä. Näin ollen 8 elementin tallentamiseksi luodaan 3 lohkoa, joista kaksi ensimmäistä lohkoa tallentavat 3 elementtiä ja viimeinen lohko tallentavat 2 elementtiä.

Kuinka haku paranee rullaamattomissa linkitetyissä luetteloissa?

Joten yllä oleva esimerkki, jos haluamme etsiä luettelon 7. elementtiä, siirrämme lohkoluettelon siihen, joka sisältää 7. elementin. Se kestää vain O(sqrt(n)), koska löysimme sen läpi enintään sqrt(n) lohkon.

Yksinkertainen toteutus:

Alla oleva ohjelma luo yksinkertaisen puretun linkitetyn luettelon, jossa on 3 solmua, jotka sisältävät vaihtelevan määrän elementtejä kussakin. Se myös kulkee luodun luettelon läpi.

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>

Lähtö

1 2 3 4 5 6 7 8 9

Monimutkaisuusanalyysi:

Aika monimutkaisuus: O(n). Tilan monimutkaisuus: O(n).

Tässä artikkelissa olemme ottaneet käyttöön rullaamattoman luettelon ja sen edut. Olemme myös osoittaneet, kuinka luetteloa voi kiertää. Seuraavassa artikkelissa keskustelemme lisäyspoistosta ja maxElements/numElements-arvoista yksityiskohtaisesti.

Lisäys rullaamattomaan linkitettyyn luetteloon