מערכים מול רשימות מקושרות - מתי להשתמש בכל אחד?
השוואה מקיפה בין שני מבני הנתונים הבסיסיים ביותר, כולל סיבוכיות פעולות וזיכרון.
מערך (Array) ורשימה מקושרת (Linked List) הם שני מבני הנתונים הבסיסיים ביותר במדעי המחשב. שניהם שומרים אוסף סדור של ערכים, אך נבדלים באופן אחסון בזיכרון - והבחירה ביניהם משפיעה דרמטית על הביצועים.
מערך - בלוק רציף בזיכרון
מערך מקצה בלוק זיכרון רציף בגודל קבוע. כל אלמנט נמצא במרחק קבוע מהקודם, ולכן גישה לאלמנט במיקום i היא O(1) - פשוט מחשבים base + i × size.
גישה רציפה לזיכרון מנצלת היטב את מטמון המעבד (CPU cache), מה שהופך מערכים למהירים מאוד בפועל גם כשהתיאוריה אומרת אחרת.
רשימה מקושרת - צמתים מפוזרים בזיכרון
ברשימה מקושרת כל צומת מכיל ערך ומצביע לצומת הבא. הצמתים יכולים להיות מפוזרים בכל הזיכרון, ולכן גישה לאלמנט ה-i דורשת מעבר מהראש דרך i צמתים - O(n).
השוואת סיבוכיות
| פעולה | מערך | רשימה מקושרת |
|---|---|---|
| גישה לפי אינדקס | O(1) | O(n) |
| חיפוש ערך | O(n) | O(n) |
| הוספה בהתחלה | O(n) | O(1) |
| הוספה בסוף | O(1) amortized | O(1) עם זנב |
| מחיקה באמצע | O(n) | O(1) אם יש מצביע |
| זיכרון נוסף לכל אלמנט | 0 | מצביע אחד או שניים |
מתי להשתמש במערך?
- כשצריכים גישה אקראית מהירה לפי אינדקס
- כשגודל הנתונים ידוע מראש או משתנה לאט
- כשחשובה יעילות זיכרון וניצול מטמון
- כברירת מחדל ברוב המקרים בפועל
מתי להשתמש ברשימה מקושרת?
- כשמבצעים הוספות ומחיקות תכופות בהתחלה או באמצע
- כשגודל האוסף משתנה דרמטית בזמן ריצה
- כבסיס למבני נתונים אחרים: מחסניות, תורים, רשימות שכנויות
- במצבים שבהם אין צורך בגישה אקראית
טיפ למבחן: ב-Java, ArrayList זה מערך דינמי ו-LinkedList זו רשימה מקושרת דו-כיוונית. בפייתון, list הוא תמיד מערך דינמי - לא קיימת רשימה מקושרת מובנית.