כיצד ליישם רשימה מקושרת ב- JavaScript

אם אתה לומד מבני נתונים, רשימה מקושרת היא מבנה נתונים אחד שעליך להכיר. אם אתה לא באמת מבין את זה או איך הוא מיושם ב- JavaScript, מאמר זה כאן כדי לעזור לך.

במאמר זה נדון מהי רשימה מקושרת, במה היא שונה ממערך וכיצד ליישם אותה ב- JavaScript. בוא נתחיל.

מהי רשימה מקושרת?

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

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

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

ב- JavaScript, רשימה מקושרת נראית כך:

const list = { head: { value: 6 next: { value: 10 next: { value: 12 next: { value: 3 next: null } } } } } };

יתרון של רשימות מקושרות

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

חסרונות של רשימות מקושרות

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

סוגי רשימות מקושרות

ישנם שלושה סוגים של רשימות מקושרות:

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

הטמעת צומת רשימה ב- JavaScript

כאמור קודם, צומת רשימה מכיל שני פריטים: הנתונים והמצביע לצומת הבא. אנו יכולים ליישם צומת רשימה ב- JavaScript באופן הבא:

class ListNode { constructor(data) { this.data = data this.next = null } }

יישום רשימה מקושרת ב- JavaScript

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

class LinkedList { constructor(head = null) { this.head = head } }

מחברים את הכל ביחד

בואו ליצור רשימה מקושרת עם הכיתה שיצרנו זה עתה. ראשית, אנו יוצרים שני צומת רשימה, node1ו node2ו מצביעים מצומת 1 צומת 2.

let node1 = new ListNode(2) let node2 = new ListNode(5) node1.next = node2

לאחר מכן, ניצור רשימה מקושרת עם ה- node1.

let list = new LinkedList(node1)

בואו ננסה לגשת לצמתים ברשימה שיצרנו זה עתה.

console.log(list.head.next.data) //returns 5

כמה שיטות LinkedList

בהמשך, נבצע ארבע שיטות עוזרות לרשימה המקושרת. הם:

1. גודל()
2. ברור()
3. ללכת לאיבוד()
4. getFirst ()

1. גודל ()

שיטה זו מחזירה את מספר הצמתים הנמצאים ברשימה המקושרת.

size() { let count = 0; let node = this.head; while (node) { count++; node = node.next } return count; } 

2. ברור ()

שיטה זו מרוקנת את הרשימה.

clear() { this.head = null; }

3. getLast ()

שיטה זו מחזירה את הצומת האחרון ברשימה המקושרת.

getLast() { let lastNode = this.head; if (lastNode) { while (lastNode.next) { lastNode = lastNode.next } } return lastNode }

4. getFirst ()

שיטה זו מחזירה את הצומת הראשון ברשימה המקושרת.

getFirst() { return this.head; }

סיכום

במאמר זה דנו מהי רשימה מקושרת וכיצד ניתן ליישם אותה ב- JavaScript. דנו גם בסוגים השונים של רשימות מקושרות, כמו גם היתרונות והחסרונות הכוללים שלהן.

אני מקווה שנהנית לקרוא את זה.

רוצה לקבל הודעה כשאפרסם מאמר חדש? לחץ כאן.