جلسه ۶۸: چاپ معکوس یک لیست پیوندی با روش بازگشتی در جاوا

در این جلسه می آموزید که چگونه لیست پیوندی را با استفاده از روش بازگشتی به ترتیب معکوس چاپ کنید. موارد زیر را بیان خواهیم کرد:

• چاپ یک لیست پیوندی معکوس
• تفسیر کد
• متد main
• متد بازگشتی
• حالت پایه
• حالت بازگشتی
• درک از طریق پشته

چاپ یک لیست پیوندی معکوس

برای این کار کافی است به ترتیبی به عناصر لیست دسترسی پیدا کنید که بتوانید عناصر را به ترتیب معکوس لیست چاپ کنید. در این روند نباید عناصر لیست را تغییر دهید. تصویر زیر این مفهوم را توضیح می دهد:

class LinkedList {

    // Linked List Node
    static class Node {
      int value;
      Node next;
    };

    public static void reverse(Node head) {

      // Base case
      if (head == null) {
        return;
      }

      // Recursive case
      else {
        reverse(head.next);
        System.out.print(head.value + " ");
      }
    } 

    static Node insertAtHead(Node temp_head, int new_value) {
      Node new_Node = new Node();
      new_Node.value = new_value;
      new_Node.next = (temp_head);
      (temp_head) = new_Node;

      return temp_head;
    }

    public static void main( String args[] ) {
        // Empty Linked List
        Node head = null;

        // Linked List = 1->2->3->4->5
        head = insertAtHead(head, 5);        
        head = insertAtHead(head, 4);        
        head = insertAtHead(head, 3);        
        head = insertAtHead(head, 2);        
        head = insertAtHead(head, 1);

        // Print the original Linked List
        System.out.println("Linked List: ");
        for (Node i = head; i != null; i = i.next) {
          System.out.print(i.value + " ");
        }

        // Print the reversed Linked List
        System.out.println(" ");
        System.out.println("Reversed Linked List: ");
        reverse(head);
    }
}

تفسیر کد

کدی که در بالا ارائه شده است را می توان به دو قسمت تقسیم کرد. متد بازگشتی و متد main که متد بازگشتی اولین بار در آن فراخوانی می شود.

متد main

کد داخل main از خط ۳۳ تا خط ۵۳ است.

• در متد main ، بین خطوط ۳۷ و ۴۱ ، با افزودن پنج گره از طریق متد insertAtHead ، یک لیست پیوندی ایجاد می شود.
• متد reverse در خط ۵۲ فراخوانی می شود که فقط ۱ آرگومان دریافت می کند: سر لیست.

متد بازگشتی

هر متد بازگشتی از دو قسمت تشکیل شده است: حالت پایه و حالت بازگشتی.

حالت پایه

حالت پایه در خط ۱۲ تعریف شده است. اگر head (سر) لیست پیوندی null باشد ، نشان دهنده این است که کل لیست پیموده شده است ، و متد خاتمه می یابد. این مورد در صورت خالی بودن لیست نیز اعمال می شود و در این حالت نیز متد باید به سادگی خاتمه یابد.

حالت بازگشتی

حالت بازگشتی در خط ۱۸ تعریف شده است.

• این متد فقط یک آرگومان ، سر لیست ، که اشاره گری به اولین گره لیست است. سر لیست در هر فراخوانی به روز می شود.
• در ابتدا ، سر به گره شروع اشاره می کند. در هر فراخوانی برگشتی متوالی ، سر به گره بعدی اشاره می کند.
• وقتی head (سر لیست) برابر null باشد ، یعنی به انتهای لیست رسیده است، و در حالت پایه هستیم از اینجا به بعد است که فراخوانی بازگشتی جدیدی انجام نمی شود ولی متدها شروع به چاپ مقادیر گره ها به صورت معکوس می کنند.

درک از طریق پشته

تصویر زیر به توضیح کد از طریق پشته کمک می کند:

در جلسه بعدی ، می آموزید که چگونه به روش بازگشتی مجموع داده های یک لیست پیوندی را محاسبه کنید.