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

تاریخ نگارش مطلب: 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

کد سی پلاس پلاس

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

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;

}

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

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

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

شیوه کار

کد جاوا

کد سی پلاس پلاس

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

Pin It on Pinterest

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

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

شیوه کار

کد جاوا

کد سی پلاس پلاس

آموزش های مشابه:

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

Pin It on Pinterest