רשימה מקושרת של XOR

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

ברשימה מקושרת של XOR, המידע של שני השדות שמורים במשתנה כתובת בודד, אשר שומר את ערך ה - XOR המתקבל מהכתובת הקודמת והכתובת הבאה בתור (כפי שמוצג בתרשים הבא):

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

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

למרות החיסכון בזיכרון, השימוש בטריק התכנותי הזה אינו מקובל או מומלץ מהסיבות הבאות:

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

ראו גם

• אלגוריתם ההחלפה של XOR