רשימה מקושרת לא מגוללת | סט 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.
הוספה ברשימה מקושרת לא מגוללת
צור חידון
מאמרים למעלה
