معکوس کردن لیست پیوندی دو طرفه
در این مطلب آموزشی از وبسایت اوپن مایند هدف آن است که نشان دهیم چطور می توان یک لیست پیوندی دو طرفه را معکوس کرد.
برای درک معکوس شدن یک لیست پیوندی به به تصویر زیر و ترتیب موجود در عکس دقت کنید.
مثالی از معکوس کردن لیست پیوندی دو طرفه
شیوه کار:
می دانیم که هر گره در لیست پیوندی دو طرفه یک اشاره گر به گره قبلی و اشاره گر دیگری به بعدی دارد. ما برای معکوس کردن لیست، یه پیمایش خطی روی آن صورت می دهیم و به هر گره ای که می رسیم، جای گره های قبل و بعد آن را عوض می کنیم.
در نهایت آخرین گره را به عنوان اشاره گر جدید سر لیست در نظر می گیریم.
کد کامل روش توضیح داده شده
کد زیر که به زبان جاوا است، شیوه کار توضیح داده شده را پیاده سازی کرده است:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 | public class reverseDoublyLinkedList { public static Node head = null; public static Node tail = null; public static int size = 0; public Node reverseDLL() { Node current = head; Node temp = null; while (current != null) { temp = current.prev; //swap the next and prev pointer current.prev = current.next; current.next = temp; current = current.prev; } return temp.prev; } public void print(Node head) { Node current = head; while (current != null) { System.out.print(" " + current.data); current = current.next; } } public void add(int data) { Node n = new Node(data); if (head == null) { head = n; tail = n; } else { head.prev = n; n.next = head; head = n; } size++; } public static void main(String args[]) { reverseDoublyLinkedList r = new reverseDoublyLinkedList(); r.add(1); r.add(2); r.add(3); r.add(4); r.print(head); Node x = r.reverseDLL(); System.out.println(""); r.print(x); } } class Node { int data; Node next; Node prev; public Node(int data) { this.data = data; this.next = null; this.prev = null; } } |
خروجی اجرای کد بالا:
1 2 | ->4->3->2->1 ->1->2->3->4 |