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.

Java voegt tekenreeksen samen

Uitgerold gelinkte lijst | Set 1 (inleiding) uitgeroldgekoppeldelijst' title=

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:

java booleaans

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

Java voor pauze