معکوس کردن لیست پیوندی دو طرفه
در این مطلب آموزشی از وبسایت اوپن مایند هدف آن است که نشان دهیم چطور می توان یک لیست پیوندی دو طرفه را معکوس کرد.
برای درک معکوس شدن یک لیست پیوندی به به تصویر زیر و ترتیب موجود در عکس دقت کنید.
مثالی از معکوس کردن لیست پیوندی دو طرفه
معکوس کردن لیست پیوندی دو طرفه
شیوه کار
می دانیم که هر گره در لیست پیوندی دو طرفه یک اشاره گر به گره قبلی و اشاره گر دیگری به بعدی دارد. ما برای معکوس کردن لیست، یه پیمایش خطی روی آن صورت می دهیم و به هر گره ای که می رسیم، جای گره های قبل و بعد آن را عوض می کنیم.
در نهایت آخرین گره را به عنوان اشاره گر جدید سر لیست در نظر می گیریم.
کد جاوا
کد زیر که به زبان جاوا است، شیوه کار توضیح داده شده را پیاده سازی کرده است:
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 |
کد سی پلاس پلاس
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 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 | #include <iostream> using namespace std; class Node { private: int data; Node *next; Node *prev; public: Node(int data) : data(data) { next = NULL; prev = NULL; } int getData() const { return data; } void setData(int data) { Node::data = data; } Node *getNext() const { return next; } void setNext(Node *next) { Node::next = next; } Node *getPrev() const { return prev; } void setPrev(Node *prev) { Node::prev = prev; } }; class DoublyLinkedList { public: Node *head = NULL; Node *tail = NULL; int size = 0; void add(int data) { Node *n = new Node(data); if (head == NULL) { head = n; tail = n; } else { head->setPrev(n); n->setNext(head); head = n; } size++; } void reverse() { Node *current = head; Node *temp = NULL; while (current != NULL) { temp = current->getPrev(); //swap the next and prev pointer current->setPrev(current->getNext()); current->setNext(temp); current = current->getPrev(); } head = temp->getPrev(); } void print() { Node *current = head; while (current != NULL) { printf(" %d", current->getData()); current = current->getNext(); } printf("\n"); } }; int main() { DoublyLinkedList list; list.add(1); list.add(2); list.add(3); list.add(4); printf("Original list:\n"); list.print(); list.reverse(); printf("Reversed:\n"); list.print(); return 0; } |