רשימה מקושרת בnode.js



רשימה מקושרת 

  • רשימה מקושרת(LinkedList) הינה רשימה בסיסית שיכולה לאחסן מידע (כלומר מבנה נתונים). רשימה כזו מורכבת מתאים (או: חוליות), שכל אחד ואחד מהם נקרא node.
  • כל תא ברשימה מכיל שני ערכי מידע: ערך המידע(value/data), כלומר, המידע שהחוליה אמורה להכיל. וערך נוסף, המכיל את כתובת הזיכרון, או את המידע שיעזור לנו לגשת אל החוליה הבאה ברשימה.

החוליה הראשונה ברשימה כזו, נקראת "שורש" או באנגלית root, מכיוון שממש כמו עץ, היא החוליה שממנה "צומחת" כל הרשימה.


האובייקט עצמו אמור להיראות כך :
הקונספט של הרשימה המקושרת אמור להיראות (בצורה ויזואלית):




ועכשיו לחלק של הקוד :

 כמה דגשים:


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


ראשית נבנה את האובייקט node :


האובייקט node מקבל את הvalue שלו בבניה, ובאופן דיפולטיבי מבצע השמה של null בערך המידע next. 
בנוסף, נכתוב getרים וsetרים ל2 ערכי המידע על מנת שנוכל לגשת אליהם בצורה מאובטחת מחוץ לאובייקט.

בjs אנו מצהירים על המשתנים היישר בתהליך הבנייה. this.nameVar = something

דוגמא למהלך הקוד: כאשר ניצור משתנה ;(var node1 = new node(5 המשתנה node1 ייבנה, תא הvalue שלו יהיה שווה ל5, ותא הnext שלו יהיה שווה לnull. אחרי שניצור node נוסף נוכל להשתמש בפונקציית הSetNext של node1 כדי לקשר בין שני הnodes.


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

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

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




כעת, אם ניצור אובייקט מסוג linkedList וניתן לו את הערך 5, תיווצר לנו חוליית השורש (node) ברשימה שערך הdata שלה יהיה 5 וערך הnext שלה שווה לnull.


עכשיו נעבור לחלק המעניין יותר, וניצור פונקצייה להוספת חולייה - AddNewNode.
הפונקציה עצמה, תהיה פונקציה מקומית בתוך האובייקט linkedList והיא תקבל את הערך value, שאותו היא תכניס לnode החדש שהיא תיצור.

באופן טבעי, נרצה ליצור את הפונקציה כללית ככל האפשר ולכתוב קוד אשר רץ על כל החוליות עד שהוא מוצא חולייה שערך הnext שלה שווה לnull, ואז לגרום לו לאחסן את החולייה הבאה. למרות רצוננו,
מכיוון שבהתחלה ערך הvalue של חוליית הROOT שווה לnull, לא נוכל להתחיל לרוץ לאורך השרשרת עם
while this.ROOT.GetNet() != null - מכיוון שלעולם לא ניכנס לתנאי הזה כשערך הnext של החולייה הראשונה שווה לnull.
לכן נחלק את פעילות הפונקציה לשני מקרים, מקרה ובו ערך הnext של החולייה הראשונה (ROOT) שווה לnull, ואז ניצור באופן פרטני את החולייה השנייה (זו שהROOT מצביע עליה), ומקרה שני כללי ובו ערך החולייה הראשונה לא שווה לnull, מקרה המאפשר לנו להיכנס לתנאי הwhile ולכן לרוץ ביעילות על השרשרת עד החוליה האחרונה בה ערך המידע next שווה לnull, ואז להוסיף חולייה חדשה עם ערך הvalue שהפונקציה מקבלת.
כשנרוץ בתוך לולאת הwhile עד החולייה האחרונה, נשתמש בשורת הקוד הבאה :
() this.ROOT = this.ROOT.GetNext, הבעיה בשורת הקוד הזו היא שאנו מאבדים את האחיזה בROOT הראשוני שלנו, מכיוון שבסוף הריצה, הROOT יהיה שווה לחולייה הלפני החוליה שניצור. כדי לפתור את הבעיה הזו, ניצור משתנה זמני this.temp ונשווה אותו אל הROOT. לאחר מכן נרוץ על המשתנה הזמני עד סופו (החוליות יועקו באופן רדוד (shallow copy) כלומר אם נשנה משהו במשתנה הזמני this.temp, נשנה אותו גם במשתנה שהעתקנו this.ROOT). לאחר שנגיע אל החולייה האחרונה בthis.temp נוסיף לה node חדש בעזרת ()node.SetNext, ובכך נוסיף את החולייה גם אל הthis.ROOT.

וכעת, בקוד:



כעת, אם ניצור אובייקט מסוג linkedList ונשתמש בפונקציית AddNewValue פעמיים:

;(5) var V1 = new linkedList
;(3)V1.AddNewValue
;(31)V1.AddNewValue

יהיה לנו רשימה מקושרת בעלת שלוש חוליות.

ROOT -> Value = 5 , Next = { Value = 3 , Next = {    Value = 31, Next = null } }; 

                                                                                      
                                                    
עכשיו, אחרי שכל מה שכתבתנו התרחש "מאחורי הקלעים" נכתוב פונקציית הדפסה, שתמחיש לנו את כל מה שכתבנו עד כה.


כמו בפונקציית ההוספה, נרצה לרוץ על כל חוליה, לאורך כל הרשימה/שרשרת, ולהדפיס את ערך הdata שלהן.
כמו בפונקציית ההוספה, ומאותן סיבות, נחלק את הפונקציה לשני מקרים:

  1. יש רק חולייה אחת בלבד- this.ROOT
  2. יש 2 חוליות לפחות.  
במקרה 1, פשוט נדפיס את ערך הROOT בעזרת (() console.log (this.ROOT.GetValue 

במקרה השני, מאותן סיבות, נעתיק את this.ROOT למשתנה זמני this.temp ונרוץ על כל החוליות שלו, כשבכל חוליה אנו נדפיס את הערך של הdata.
כשנצא מלולאת הwhile, נגיע אל החוליה האחרונה שערך הNext שלה שווה לnull. לפי מבנה הלולאה שנכתוב, הערך של החולייה האחרונה לא יודפס בתוך לולאת while ולכן נדפיס, פעם אחת בלבד - מחוץ ללולאה את הערך של החולייה האחרונה.

וכעת, לקוד :




כעת, אם נפעיל את הפונקציה, נקבל את הפלט :
5
3
31



כעת, נכתוב את כל שורות הקוד בקובץ אחד, נריץ ונהנה 😀
אני הרצתי אותו עם הערכים הנ"ל, כמצורף בקישור לקוד.


 הנה הקישור לצפייה בקובץ: (אפשר גם להוריד).
LinkedList.js

ביינתים אפרסם את הדף עד שאיהיה לי זמן להתפנות כדי לערוך את הכל מחדש.

נכתב בתאריך 7.2.20 בשעה 15:19 ביום שישי.
ⓒ כל הזכויות שמורות, אפשר ורצוי להפיץ למטרות לימודיות בלבד ועם הוספת קרדיט לבלוג. השימוש למטרות מסחריות הינו אסור ועלול לחשוף את המשתמש לתביעות משפטיות.






























   

אין תגובות:

הוסף רשומת תגובה

הירשם ל- רשומות (Atom)