עבודה עם רשימות מקושרות (Linked Lists) בשפת C

[Tamir]

עבודה עם רשימות מקושרות (Linked Lists) בשפת C


רשימות מקושרות (Linked Lists) הן מבנה נתונים דינמי שמאפשר הוספה, מחיקה ושינוי של אלמנטים בצורה יעילה יותר מאשר במערכים. כל אלמנט ברשימה מקושרת נקרא "צומת" (Node) והוא כולל את המידע ואת המצביע לצומת הבא ברשימה.


הגדרת מבנה לצומת ברשימה מקושרת


בשלב הראשון, יש להגדיר את מבנה הצומת שיכלול את המידע ואת המצביע לצומת הבא:



c
#include <stdio.h>
#include <stdlib.h>


// הגדרת מבנה לצומת
struct Node {
int data;
struct Node *next;
};



יצירת צומת חדש


כדי ליצור צומת חדש ולהוסיף אותו לרשימה, נשתמש בפונקציה שתשתמש ב-`malloc` להקצות זיכרון לצומת חדש:



c
// פונקציה ליצירת צומת חדש
struct Node* createNode(int data) {
struct Node *newNode = (struct Node *)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}



הדפסת רשימה מקושרת


פונקציה זו מדפיסה את כל הצמתים ברשימה:



c
// פונקציה להדפסת רשימה מקושרת
void printList(struct Node *head) {
struct Node *current = head;
while (current != NULL) {
printf("%d -> ", current->data);
current = current->next;
}
printf("NULL\n");
}



הוספה לתחילת הרשימה


כדי להוסיף צומת חדש בתחילת הרשימה, נעדכן את המצביע של הצומת החדש כך שיצביע לצומת הראשון, ולאחר מכן נעדכן את הראש של הרשימה:



c
// פונקציה להוספת צומת בתחילת הרשימה
void insertAtHead(struct Node **head, int data) {
struct Node *newNode = createNode(data);
newNode->next = *head;
*head = newNode;
}



הוספה בסוף הרשימה


כדי להוסיף צומת חדש לסוף הרשימה, נעדכן את המצביע של הצומת האחרון כך שיצביע לצומת החדש:



c
// פונקציה להוספת צומת בסוף הרשימה
void insertAtEnd(struct Node **head, int data) {
struct Node *newNode = createNode(data);
if (*head == NULL) {
*head = newNode;
return;
}


struct Node *current = *head;
while (current->next != NULL) {
current = current->next;
}
current->next = newNode;
}



הסרת צומת מהרשימה


פונקציה זו מסירה צומת עם ערך נתון מהרשימה:



c
// פונקציה להסרת צומת עם ערך נתון
void deleteNode(struct Node **head, int key) {
struct Node *temp = *head, *prev = NULL;


// אם הצומת הראשון הוא הצומת להסרה
if (temp != NULL && temp->data == key) {
*head = temp->next; // עדכון הראש
free(temp); // שחרור זיכרון
return;
}


// חיפוש הצומת להסרה
while (temp != NULL && temp->data != key) {
prev = temp;
temp = temp->next;
}


// אם לא נמצא הצומת
if (temp == NULL) return;


// עדכון המצביע של הצומת הקודם
prev->next = temp->next;
free(temp); // שחרור זיכרון
}



שחרור זיכרון של רשימה מקושרת


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



c
// פונקציה לשחרור זיכרון של רשימה מקושרת
void freeList(struct Node *head) {
struct Node *temp;


while (head != NULL) {
temp = head;
head = head->next;
free(temp);
}
}



דוגמה לשימוש ברשימה מקושרת


להלן דוגמה כיצד להשתמש בפונקציות שהוגדרו:



c
int main() {
struct Node *head = NULL;


// הוספת צמתים לרשימה
insertAtEnd(&head, 10);
insertAtEnd(&head, 20);
insertAtHead(&head, 5);


// הדפסת הרשימה
printList(head);


// הסרת צומת מהרשימה
deleteNode(&head, 20);
printList(head);


// שחרור זיכרון
freeList(head);


return 0;
}



סיכום


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


אם יש לכם שאלות נוספות או אתם זקוקים לעזרה נוספת, אתם מוזמנים לשאול! ?