معکوس کردن لیست پیوندی دو طرفه

تاریخ نگارش مطلب: 2019/08/09 نویسنده: حامد آهنگری

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

برای درک معکوس شدن یک لیست پیوندی به به تصویر زیر و ترتیب موجود در عکس دقت کنید.

مثالی از معکوس کردن لیست پیوندی دو طرفه

شیوه کار:

می دانیم که هر گره در لیست پیوندی دو طرفه یک اشاره گر به گره قبلی و اشاره گر دیگری به بعدی دارد. ما برای معکوس کردن لیست، یه پیمایش خطی روی آن صورت می دهیم و به هر گره ای که می رسیم، جای گره های قبل و بعد آن را عوض می کنیم.

در نهایت آخرین گره را به عنوان اشاره گر جدید سر لیست در نظر می گیریم.

کد کامل روش توضیح داده شده

کد زیر که به زبان جاوا است، شیوه کار توضیح داده شده را پیاده سازی کرده است:

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;
    }
}

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;

}

خروجی اجرای کد بالا:

->4->3->2->1
->1->2->3->4

1 2	->4->3->2->1 ->1->2->3->4

الگوریتم ها و هوش مصنوعی, جاوا, لیست پیوندی - linked list

معکوس کردن لیست پیوندی دو طرفه

شیوه کار:

کد کامل روش توضیح داده شده

مطالب آموزنده مشابه:

نظرتان را برای ما بنویسید لغو پاسخ