streamalism.org

1. הקדמה

במדריך זה, אנו מיישמים שני אלגוריתמי היפוך רשימות מקושרים ב- Java.

2. מבנה נתונים מקושר לרשימה

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

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

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

נתחיל קודם עם א ListNode מחלקה לייצוג אלמנט מרשימה מקושרת:

מחלקה ציבורית ListNode {נתוני int פרטי; פרטי ListNode הבא; ListNode (int נתונים) {this.data = נתונים; this.next = null; } // גטרים וקובעים סטנדרטיים}

ה ListNode בכיתה שני תחומים:

• ערך שלם לייצוג נתוני האלמנט
• מצביע / הפניה לאלמנט הבא

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

ListNode constructLinkedList () {ListNode head = null; זנב ListNode = null; עבור (int i = 1; i <= 5; i ++) {ListNode node = ListNode חדש (i); אם (head == null) {head = node; } אחר {tail.setNext (צומת); } זנב = צומת; } להחזיר ראש; }

3. יישום אלגוריתם איטרטיבי

בואו נשתמש באלגוריתם האיטרטיבי ב- Java:

ListNode reverseList (ListNode head) {ListNode הקודם = null; זרם ListNode = ראש; בעוד (current! = null) {ListNode nextElement = current.getNext (); current.setNext (הקודם); הקודם = הנוכחי; הנוכחי = nextElement; } להחזיר הקודם; }

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

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

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

@Test הציבור בטל givenLinkedList_whenIterativeReverse_thenOutputCorrectResult () {ListNode head = constructLinkedList (); צומת ListNode = ראש; עבור (int i = 1; i <= 5; i ++) {assertNotNull (node); assertEquals (i, node.getData ()); node = node.getNext (); } היפוך LinkedListReversal = LinkedListReversal חדש (); node = reversal.reverseList (head); עבור (int i = 5; i> = 1; i--) {assertNotNull (node); assertEquals (i, node.getData ()); node = node.getNext (); }}

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

4. רקורסיבי יישום אלגוריתם

עכשיו, בואו נשתמש באלגוריתם הרקורסיבי ב- Java:

ListNode reverseListRecursive (ראש ListNode) {if (head == null) {return null; } אם (head.getNext () == null) {head return; } צומת ListNode = reverseListRecursive (head.getNext ()); head.getNext (). setNext (head); head.setNext (null); צומת החזרה; }

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

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

@Test ציבורי בטל givenLinkedList_whenRecursiveReverse_thenOutputCorrectResult () {ListNode head = constructLinkedList (); צומת ListNode = ראש; עבור (int i = 1; i <= 5; i ++) {assertNotNull (node); assertEquals (i, node.getData ()); node = node.getNext (); } היפוך LinkedListReversal = LinkedListReversal חדש (); node = reversal.reverseListRecursive (head); עבור (int i = 5; i> = 1; i--) {assertNotNull (node); assertEquals (i, node.getData ()); node = node.getNext (); }}

5. מסקנה

במדריך זה יישמנו שני אלגוריתמים כדי להפוך רשימה מקושרת. כמו תמיד, קוד המקור של המאמר זמין באתר GitHub.