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

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

XorLinked1.png

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

XORlinked2.png

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

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

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

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

ראו גם[עריכת קוד מקור | עריכה]