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

در این جلسه می آموزید که چگونه لیست پیوندی را با استفاده از روش بازگشتی به ترتیب معکوس چاپ کنید. موارد زیر را بیان خواهیم کرد:
- چاپ یک لیست پیوندی معکوس
- تفسیر کد
- متد
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
باشد ، یعنی به انتهای لیست رسیده است، و در حالت پایه هستیم از اینجا به بعد است که فراخوانی بازگشتی جدیدی انجام نمی شود ولی متدها شروع به چاپ مقادیر گره ها به صورت معکوس می کنند.
درک از طریق پشته
تصویر زیر به توضیح کد از طریق پشته کمک می کند:
در جلسه بعدی ، می آموزید که چگونه به روش بازگشتی مجموع داده های یک لیست پیوندی را محاسبه کنید.