Розгорнутий зв'язаний список | Набір 1 (введення)
Подібно до масиву та зв’язаного списку, розгорнутий зв’язаний список також є лінійною структурою даних і є варіантом зв’язаного списку.
Навіщо нам розгорнутий зв'язаний список?
Однією з найбільших переваг пов’язаних списків над масивами є те, що для вставки елемента в будь-яке місце потрібно лише O(1). Однак заковика тут полягає в тому, що для пошуку елемента у зв’язаному списку потрібно O(n). Тому для вирішення проблеми пошуку, тобто скорочення часу на пошук елемента, була висунута концепція розгорнутих зв’язаних списків. Розгорнутий зв’язаний список охоплює переваги як масиву, так і зв’язаного списку, оскільки він зменшує витрати пам’яті порівняно з простими зв’язаними списками, зберігаючи кілька елементів у кожному вузлі, а також має перевагу швидкого вставлення та видалення, ніж у зв’язаного списку.
Переваги:
- Завдяки поведінці кешу лінійний пошук набагато швидший у розгорнутих пов’язаних списках.
- У порівнянні зі звичайним пов’язаним списком, він потребує менше місця для зберігання покажчиків/посилань.
- Він виконує такі операції, як вставка, видалення та обхід швидше, ніж звичайні зв’язані списки (оскільки пошук швидший).
Недоліки:
- Накладні витрати на вузол порівняно високі, ніж однозв’язані списки. Зверніться до прикладу вузла в наведеному нижче коді
приклад: Припустимо, у нас є 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 // 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# // 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
Аналіз складності:
У цій статті ми представили розгорнутий список і його переваги. Ми також показали, як проходити список. У наступній статті ми детально обговоримо видалення вставки та значення maxElements/numElements.
Вставка в розгорнутий пов’язаний список
Створіть вікторину
Вам Може Сподобатися
Кращі Статті
