РАЗГЪНАТ СВЪРЗАН СПИСЪК | КОМПЛЕКТ 1 (ВЪВЕДЕНИЕ)

Подобно на масива и свързания списък, разгънатият свързан списък също е линейна структура от данни и е вариант на свързан списък.

Защо се нуждаем от разгънат свързан списък?

Едно от най-големите предимства на свързаните списъци пред масивите е, че вмъкването на елемент на всяко място отнема само O(1). Но уловката тук е, че търсенето на елемент в свързан списък отнема O(n). И така, за да се реши проблемът с търсенето, т.е. да се намали времето за търсене на елемента, беше представена концепцията за разгънати свързани списъци. Разгънатият свързан списък обхваща предимствата както на масива, така и на свързания списък, тъй като намалява натоварването на паметта в сравнение с обикновените свързани списъци чрез съхраняване на множество елементи във всеки възел и също така има предимството на бързото вмъкване и изтриване като това на свързания списък.

Разгънат свързан списък | Комплект 1 (Въведение) unrolledlinkedlist' title=

Предимства:

Поради поведението на кеша линейното търсене е много по-бързо в разгънати свързани списъци.
В сравнение с обикновения свързан списък, той изисква по-малко място за съхранение на указатели/препратки.
Той извършва операции като вмъкване, изтриване и обхождане по-бързо от обикновените свързани списъци (тъй като търсенето е по-бързо).

Недостатъци:

Разходите за възел са сравнително високи в сравнение с единично свързаните списъци. Обърнете се към примерен възел в кода по-долу

Пример: Да кажем, че имаме 8 елемента, така че sqrt(8)=2,82, което се закръгля до 3. Така че всеки блок ще съхранява 3 елемента. Следователно за съхраняване на 8 елемента ще бъдат създадени 3 блока, от които първите два блока ще съхраняват 3 елемента, а последният блок ще съхранява 2 елемента.

Как търсенето става по-добро в разгънати свързани списъци?

Така че като вземем горния пример, ако искаме да търсим 7-ия елемент в списъка, преминаваме през списъка с блокове до този, който съдържа 7-ия елемент. Отнема само O(sqrt(n)), тъй като го намерихме чрез не преминаване на повече от sqrt(n) блока.

Просто изпълнение:

Програмата по-долу създава прост разгънат свързан списък с 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

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

Времева сложност: O(n). Пространствена сложност: O(n).

В тази статия ви представихме разгънат списък и предимствата му. Ние също така показахме как се преминава през списъка. В следващата статия ще обсъдим подробно изтриването на вмъкване и стойностите на maxElements/numElements.

Вмъкване в разгънат свързан списък