streamalism.org

1. הקדמה

במדריך זה נבחן את היישום של רשימה מקושרת מעגלית בג'אווה.

2. רשימה מקושרת מעגלית

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

בשינוי פשוט זה אנו מרוויחים כמה יתרונות:

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

הכל מהכל, זה מאוד שימושי ביישום מבנה נתוני התור.

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

3. יישום בג'אווה

נתחיל ביצירת עזר צוֹמֶת כיתה שתאחסן int ערכים ומצביע לצומת הבא:

class Node {int value; צומת nextNode; צומת ציבורי (ערך int) {this.value = value; }}

עכשיו בואו ניצור את הצמתים הראשונים והאחרונים ברשימה המקושרת המעגלית, המכונים בדרך כלל רֹאשׁ ו זָנָב:

מחלקה ציבורית CircularLinkedList {head head head = null; זנב צומת פרטי = null; // ....}

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

3.1. הכנסת אלמנטים

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

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

בשני המקרים לעיל, nextNode ל זָנָב יצביע על רֹאשׁ

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

חלל ציבורי addNode (int ערך) {Node newNode = צומת חדש (ערך); אם (head == null) {head = newNode; } אחר {tail.nextNode = newNode; } זנב = newNode; tail.nextNode = ראש; }

כעת אנו יכולים להוסיף מספר מספרים לרשימה המקושרת המעגלית שלנו:

פרטי CircularLinkedList createCircularLinkedList () {CircularLinkedList cll = new CircularLinkedList (); cll.addNode (13); cll.addNode (7); cll.addNode (24); cll.addNode (1); cll.addNode (8); cll.addNode (37); cll.addNode (46); החזר cll; }

3.2. מציאת אלמנט

הפעולה הבאה שנבדוק היא חיפוש כדי לקבוע אם אלמנט קיים ברשימה.

לזה, נתקן צומת ברשימה (בדרך כלל ה- רֹאשׁ) כמו currentNode ולעבור ברשימה כולה באמצעות nextNode של הצומת הזה, עד שנמצא את האלמנט הנדרש.

בואו נוסיף שיטה חדשה containNode שלוקח את searchValue כפרמטר:

ציבור בוליאני containNode (int searchValue) {Node currentNode = head; אם (head == null) {return false; } אחר {do {if (currentNode.value == searchValue) {return true; } currentNode = currentNode.nextNode; } בעוד (currentNode! = ראש); להחזיר כוזב; }}

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

@Test הציבור בטל givenACircularLinkedList_WhenAddingElements_ThenListContainsThoseElements () {CircularLinkedList cll = createCircularLinkedList (); assertTrue (cll.containsNode (8)); assertTrue (cll.containsNode (37)); } @Test הציבור בטל givenACircularLinkedList_WhenLookingForNonExistingElement_ThenReturnsFalse () {CircularLinkedList cll = createCircularLinkedList (); assertFalse (cll.containsNode (11)); }

3.3. מחיקת אלמנט

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

• אלמנט למחיקה הוא רֹאשׁ את עצמה. במקרה זה, עלינו לעדכן את רֹאשׁ כצומת הבא של הראש הנוכחי, והצומת הבא של ה- זָנָב כראש החדש
• אלמנט למחיקה הוא כל אלמנט שאינו רֹאשׁ. במקרה זה, עלינו רק לעדכן את הצומת הבא של הצומת הקודם כצומת הבא של הצומת שיש למחוק

כעת נוסיף שיטה חדשה deleteNode שלוקח את valueToDelete כפרמטר:

בטל ציבורי deleteNode (int valueToDelete) {Node currentNode = head; if (head! = null) {if (currentNode.value == valueToDelete) {head = head.nextNode; tail.nextNode = ראש; } אחר {do {Node nextNode = currentNode.nextNode; אם (nextNode.value == valueToDelete) {currentNode.nextNode = nextNode.nextNode; לשבור; } currentNode = currentNode.nextNode; } בעוד (currentNode! = ראש); }}}

בואו נוסיף כעת בדיקה פשוטה כדי לוודא שהמחיקה עובדת כמצופה בכל המקרים:

@Test הציבור בטל givenACircularLinkedList_WhenDeletingElements_ThenListDoesNotContainThoseElements () {CircularLinkedList cll = createCircularLinkedList (); assertTrue (cll.containsNode (13)); cll.deleteNode (13); assertFalse (cll.containsNode (13)); assertTrue (cll.containsNode (1)); cll.deleteNode (1); assertFalse (cll.containsNode (1)); assertTrue (cll.containsNode (46)); cll.deleteNode (46); assertFalse (cll.containsNode (46)); }

3.4. חוצה את הרשימה

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

בואו נוסיף שיטה חדשה traverseList המדפיס את האלמנטים שנוספו לרשימה:

חלל ציבורי traverseList () {Node currentNode = head; אם (head! = null) {do {LOGGER.info (currentNode.value + ""); currentNode = currentNode.nextNode; } בעוד (currentNode! = ראש); }} 

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

4. מסקנה

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

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

כרגיל, כל הדוגמאות המשמשות במאמר זה זמינות באתר GitHub.