רשימה מקושרת של XOR
מתוך ויקיפדיה, האנציקלופדיה החופשית
רשימה מקושרת של XOR היא רשימה מקושרת דו כיוונית אשר עושה שימוש מעניין בפעולת הXOR במבנה שלה. בזמן שברשימה מקושרת דו כיוונית רגילה נדרשים שני משתנים אשר מחזיקים את הכתובת של האיבר הקודם והאיבר הבא (כפי שמוצג בתרשים הבא):
ברשימה מקושרת של XOR, המידע של שני השדות שמורים במשתנה כתובת בודד, אשר שומר את ערך הXOR המתקבל מהכתובת הקודמת והבאה בתור (כפי שמוצג בתרשים הבא):
לדוגמה, כאשר עוברים על הרשימה משמאל לימין, אם אנו נמצאים בתא B, אנו ניקח את הכתובת של התא הקודם - A - ונבצע עליו פעולת XOR יחד עם הערך שנמצא במשתנה בתא B. כתוצאה מהפעולה, נקבל את כתובת התא C ונוכל להמשיך לעבור על הרשימה. בדומה, אם נלך מהכיוון ההפוך, אנו ניקח את הכתובת של תא C ונפעיל עליו פעולת XOR יחד עם הערך שנמצא במשתנה בתא B, כדי לקבל את כתובת A.
מכך יוצא שבכדי לעבור על הרשימה בכיוון כלשהו מנקודה מסוימת, אנו נזדקק לכתובות של שני תאים סמוכים, ולא רק אחד כמו ברשימה מקושרת רגילה. למרות זאת, זהו חסכון ניכר בזכרון - אנו נזדקק למספר קבוע של משתנים (שניים) כדי להחזיק את הכתובות של התאים הרצויים, ונחסוך בחצי הזכרון שדרוש לרשימה מקושרת דו צדדית רגילה (גודלו של זכרון זה תלוי ברשימה ולכן אינו קבוע ויכול, תיאורטית, להיות בלתי מוגבל).
למרות החסכון בזכרון, השימוש בטריק התכנותי הזה אינו מקובל או מומלץ מהסיבות הבאות:
- כלי ניפוי שגיאות סטנדרטיים אינם מסוגלים לעקוב אחר שרשרת XOR, דבר שהופך את תהליך ניפוי השגיאות לקשה ומסורבל יותר.
- הוזלת הזכרון, והגדלת נפחו באופן מתמיד הופכים את החסכון בזיכרון המתקבל מטריק זה לשולי ולא כדאי.
- מרבית תוכניות איסוף זבל לא עובדות עם מצביעים שאינם ישירים.
