TechCodeview

• ניתן להגדיר רשימה מקושרת כאוסף אובייקטים שנקרא צמתים שמאוחסנים באופן אקראי בזיכרון.
• צומת מכיל שני שדות כלומר נתונים המאוחסנים בכתובת המסוימת הזו והמצביע שמכיל את הכתובת של הצומת הבא בזיכרון.
• הצומת האחרון ברשימה מכיל מצביע ל-null.

שימושים ברשימה מקושרת

• הרשימה אינה נדרשת להיות נוכחת ברציפות בזיכרון. הצומת יכול לשהות בכל מקום בזיכרון ולקושר יחדיו כדי ליצור רשימה. זה משיג ניצול מיטבי של החלל.
• גודל הרשימה מוגבל לגודל הזיכרון ואין צורך להצהיר עליו מראש.
• לא יכול להיות צומת ריק ברשימה המקושרת.
• אנו יכולים לאחסן ערכים של טיפוסים או אובייקטים פרימיטיביים ברשימה המקושרת בודדת.

למה להשתמש ברשימה מקושרת מעל מערך?

עד כה, השתמשנו במבנה הנתונים של מערך כדי לארגן את קבוצת האלמנטים שאמורים להיות מאוחסנים בנפרד בזיכרון. עם זאת, ל-Array יש כמה יתרונות וחסרונות שחייבים להיות ידועים על מנת להחליט על מבנה הנתונים שישמש לאורך התוכנית.

המערך מכיל את ההגבלות הבאות:

1. יש לדעת את גודל המערך מראש לפני השימוש בו בתוכנית.
2. הגדלת גודל המערך היא תהליך שלוקח זמן. כמעט בלתי אפשרי להרחיב את גודל המערך בזמן ריצה.
3. כל האלמנטים במערך צריכים להיות מאוחסנים ברציפות בזיכרון. הכנסת אלמנט כלשהו במערך דורשת הסטה של ​​כל קודמיו.

רשימה מקושרת היא מבנה הנתונים שיכול להתגבר על כל המגבלות של מערך. שימוש ברשימה מקושרת הוא שימושי מכיוון,

מקשי שינוי

1. הוא מקצה את הזיכרון באופן דינמי. כל הצמתים של רשימה מקושרת מאוחסנים באופן לא רציף בזיכרון ומקושרים יחד בעזרת מצביעים.
2. גודל זה כבר לא מהווה בעיה מכיוון שאיננו צריכים להגדיר את הגודל שלו בזמן ההצהרה. הרשימה גדלה בהתאם לדרישת התוכנית ומוגבלת לשטח הזיכרון הפנוי.

רשימה מקושרת יחידה או שרשרת חד כיוונית

רשימה מקושרת בודדת יכולה להיות מוגדרת כאוסף של קבוצה מסודרת של אלמנטים. מספר האלמנטים עשוי להשתנות בהתאם לצורך של התוכנית. צומת ברשימה המקושרת בודדת מורכבת משני חלקים: חלק נתונים וחלק קישור. חלק הנתונים של הצומת מאחסן מידע ממשי שאמור להיות מיוצג על ידי הצומת בעוד שחלק הקישור של הצומת מאחסן את הכתובת של היורש המיידי שלו.

חיפוש bfs

ניתן לעבור בשרשרת חד כיוונית או רשימה מקושרת בודדת רק בכיוון אחד. במילים אחרות, אנו יכולים לומר שכל צומת מכיל רק את המצביע הבא, ולכן איננו יכולים לעבור את הרשימה בכיוון ההפוך.

שקול דוגמה שבה הציונים שהשיג התלמיד בשלושה מקצועות מאוחסנים ברשימה מקושרת כפי שמוצג באיור.

באיור שלמעלה, החץ מייצג את הקישורים. חלק הנתונים של כל צומת מכיל את הציונים שקיבל התלמיד במקצוע השונה. הצומת האחרון ברשימה מזוהה על ידי מצביע ה-null שנמצא בחלק הכתובת של הצומת האחרון. אנחנו יכולים לקבל כמה אלמנטים שאנחנו צריכים, בחלק הנתונים של הרשימה.

מוּרכָּבוּת

פעולות ברשימה מקושרת יחידה

ישנן פעולות שונות שניתן לבצע ברשימה מקושרת בודדת. רשימה של כל הפעולות הללו מובאת להלן.

Java לנתח מחרוזת ל-int

יצירת צומת

 struct node { int data; struct node *next; }; struct node *head, *ptr; ptr = (struct node *)malloc(sizeof(struct node *)); 

הַכנָסָה

ניתן לבצע את ההוספה לרשימה מקושרת בודדת במיקומים שונים. בהתבסס על המיקום של הצומת החדש המוכנס, ההכנסה מסווגת לקטגוריות הבאות.

מחיקה ומעבר

מחיקת צומת מרשימה מקושרת בודדת יכולה להתבצע במיקומים שונים. בהתבסס על מיקום הצומת הנמחק, הפעולה מסווגת לקטגוריות הבאות.

רשימה מקושרת ב-C: תוכנית מונחית תפריטים

 #include #include struct node { int data; struct node *next; }; struct node *head; void beginsert (); void lastinsert (); void randominsert(); void begin_delete(); void last_delete(); void random_delete(); void display(); void search(); void main () { int choice =0; while(choice != 9) { printf('

*********Main Menu*********
'); printf('
Choose one option from the following list ...
'); printf('
===============================================
'); printf('
1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
 5.Delete from last
6.Delete node after specified location
7.Search for an element
8.Show
9.Exit
'); printf('
Enter your choice?
'); scanf('
%d',&choice); switch(choice) { case 1: beginsert(); break; case 2: lastinsert(); break; case 3: randominsert(); break; case 4: begin_delete(); break; case 5: last_delete(); break; case 6: random_delete(); break; case 7: search(); break; case 8: display(); break; case 9: exit(0); break; default: printf('Please enter valid choice..'); } } } void beginsert() { struct node *ptr; int item; ptr = (struct node *) malloc(sizeof(struct node *)); if(ptr == NULL) { printf('
OVERFLOW'); } else { printf('
Enter value
'); scanf('%d',&item); ptr->data = item; ptr->next = head; head = ptr; printf('
Node inserted'); } } void lastinsert() { struct node *ptr,*temp; int item; ptr = (struct node*)malloc(sizeof(struct node)); if(ptr == NULL) { printf('
OVERFLOW'); } else { printf('
Enter value?
'); scanf('%d',&item); ptr->data = item; if(head == NULL) { ptr -> next = NULL; head = ptr; printf('
Node inserted'); } else { temp = head; while (temp -> next != NULL) { temp = temp -> next; } temp->next = ptr; ptr->next = NULL; printf('
Node inserted'); } } } void randominsert() { int i,loc,item; struct node *ptr, *temp; ptr = (struct node *) malloc (sizeof(struct node)); if(ptr == NULL) { printf('
OVERFLOW'); } else { printf('
Enter element value'); scanf('%d',&item); ptr->data = item; printf('
Enter the location after which you want to insert '); scanf('
%d',&loc); temp=head; for(i=0;inext; if(temp == NULL) { printf('
can't insert
'); return; } } ptr ->next = temp ->next; temp ->next = ptr; printf('
Node inserted'); } } void begin_delete() { struct node *ptr; if(head == NULL) { printf('
List is empty
'); } else { ptr = head; head = ptr->next; free(ptr); printf('
Node deleted from the begining ...
'); } } void last_delete() { struct node *ptr,*ptr1; if(head == NULL) { printf('
list is empty'); } else if(head -> next == NULL) { head = NULL; free(head); printf('
Only node of the list deleted ...
'); } else { ptr = head; while(ptr->next != NULL) { ptr1 = ptr; ptr = ptr ->next; } ptr1->next = NULL; free(ptr); printf('
Deleted Node from the last ...
'); } } void random_delete() { struct node *ptr,*ptr1; int loc,i; printf('
 Enter the location of the node after which you want to perform deletion 
'); scanf('%d',&loc); ptr=head; for(i=0;inext; if(ptr == NULL) { printf('
Can't delete'); return; } } ptr1 ->next = ptr ->next; free(ptr); printf('
Deleted node %d ',loc+1); } void search() { struct node *ptr; int item,i=0,flag; ptr = head; if(ptr == NULL) { printf('
Empty List
'); } else { printf('
Enter item which you want to search?
'); scanf('%d',&item); while (ptr!=NULL) { if(ptr->data == item) { printf('item found at location %d ',i+1); flag=0; } else { flag=1; } i++; ptr = ptr -> next; } if(flag==1) { printf('Item not found
'); } } } void display() { struct node *ptr; ptr = head; if(ptr == NULL) { printf('Nothing to print'); } else { printf('
printing values . . . . .
'); while (ptr!=NULL) { printf('
%d',ptr->data); ptr = ptr -> next; } } } 

תְפוּקָה:

 *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 1 Enter value 1 Node inserted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 2 Enter value? 2 Node inserted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 3 Enter element value1 Enter the location after which you want to insert 1 Node inserted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 8 printing values . . . . . 1 2 1 *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 2 Enter value? 123 Node inserted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 1 Enter value 1234 Node inserted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 4 Node deleted from the begining ... *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 5 Deleted Node from the last ... *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 6 Enter the location of the node after which you want to perform deletion 1 Deleted node 2 *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 8 printing values . . . . . 1 1 *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 7 Enter item which you want to search? 1 item found at location 1 item found at location 2 *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 9