عكس قائمة متصلة

عكس قائمة متصلة هو مشكلة مثيرة في هياكل البيانات والخوارزميات. في هذا البرنامج التعليمي، سنناقش الخوارزميات المختلفة لعكس قائمة متصلة ومن ثم تنفيذها باستخدام لغة جافا.

عكس قائمة متصلة

LinkedList هي هيكل بيانات يخزن البيانات بطريقة خطية، على الرغم من عدم اتصالها بشكل متتالٍ. كل عنصر في LinkedList يحتوي على جزء للبيانات وعنوان للعنصر التالي في LinkedList. يُعرف عناصر LinkedList بشكل شائع بأنها عقد.

تخزن Doubly LinkedList عنوانين. العنوان للعنصر السابق والعنصر التالي.

به منظور عكس یک LinkedList در محل، نیاز است که اشاره‌گرها را معکوس کنیم تا عنصر بعدی اکنون به عنصر قبلی اشاره داشته باشد. ورودی و خروجی به شرح زیر است. سر LinkedList اولین گره است. هیچ عنصر دیگری آدرس ذخیره شده برای این موارد ندارد. دم LinkedList آخرین گره است. آدرس بعدی ذخیره شده در این گره null است. ما می‌توانیم یک LinkedList را معکوس کنیم به گونه‌ای که سر و دم نیز تغییر کنند با استفاده از:

• رویه تکراری
• رویه بازگشتی

رویه تکراری برای معکوس کردن یک Linked List

لعكس LinkedList بشكل تكراري ، نحتاج إلى تخزين مراجع العناصر التالية والسابقة ، بحيث لا تضيع عندما نقوم بتبديل مؤشرات عناوين الذاكرة إلى العنصر التالي في LinkedList. يوضح الرسم التوضيحي التالي كيف سنقوم بعكس LinkedList الخاص بنا من خلال تغيير المراجع.

فيما يلي الخطوات التي يجب اتباعها لعكس LinkedList. قم بإنشاء 3 حالات: current ، next ، previous. حلق عبر ما يلي حتى يكون الحالي غير قابل للتحلل:

• قم بحفظ العنصر التالي للعنصر الحالي في مؤشر العنصر التالي.
• قم بتعيين التالي لـ العنصر الحالي إلى السابق. هذا هو الخط الرئيسي.
• انتقل بـ السابق إلى الحالي.
• انتقل بالعنصر الحالي إلى التالي.

في النهاية ، نظرًا لأن الحالي قد ذهب إلى مكان أمام العنصر الأخير ، نحتاج إلى تعيين الرأس إلى العنصر الأخير الذي وصلنا إليه. هذا متاح في السابق. قم بتعيين الرأس إلى السابق. بالتالي لدينا رأس جديد للLinkedList والذي هو العنصر الأخير للLinkedList القديم.

إليك تنفيذ بسيط لـ LinkedList. يرجى ملاحظة أن هذا ليس تنفيذًا جاهزًا للإنتاج ولقد حافظنا على بساطته حتى يظل تركيزنا على خوارزمية عكس قائمة الارتباط.

package com.journaldev.linkedlist.reverse;

public class MyLinkedList {

	public Node head;

	public static class Node {

		Node next;

		Object data;

		Node(Object data) {
			this.data = data;
			next = null;
		}
	}
}

برنامج Java لعكس LinkedList بشكل تكراري وطباعة عناصره معروض أدناه:

package com.journaldev.linkedlist.reverse;

import com.journaldev.linkedlist.reverse.MyLinkedList.Node;

public class ReverseLinkedList {

	public static void main(String[] args) {
		MyLinkedList myLinkedList = new MyLinkedList();
		myLinkedList.head = new Node(1);
		myLinkedList.head.next = new Node(2);
		myLinkedList.head.next.next = new Node(3);

		printLinkedList(myLinkedList);
		reverseLinkedList(myLinkedList);
		printLinkedList(myLinkedList);

	}

	public static void printLinkedList(MyLinkedList linkedList) {
		Node h = linkedList.head;
		while (linkedList.head != null) {
			System.out.print(linkedList.head.data + " ");
			linkedList.head = linkedList.head.next;
		}
		System.out.println();
		linkedList.head = h;
	}

	public static void reverseLinkedList(MyLinkedList linkedList) {
		Node previous = null;
		Node current = linkedList.head;
		Node next;
		while (current != null) {
			next = current.next;
			current.next = previous;
			previous = current;
			current = next;
		}
		linkedList.head = previous;
	}

}

الناتج:

1 2 3 
3 2 1 

عكس قائمة مرتبطة بشكل متكرر

لعكس LinkedList بشكل متكرر، نحتاج إلى تقسيم LinkedList إلى جزئين: الرأس والمتبقي. يشير الرأس إلى العنصر الأول في البداية. المتبقي يشير إلى العنصر التالي من الرأس.

نعبر عن LinkedList بشكل متكرر حتى العنصر قبل الأخير. بمجرد وصولنا إلى العنصر الأخير نضعه كالرأس. من هناك نقوم بما يلي حتى نصل إلى بداية LinkedList. node.next.next = node; node.next = null; لكي لا نفقد متابعة الرأس الأصلي، سنقوم بحفظ نسخة من مثيل الرأس.

فيما يلي توضيح للإجراء أعلاه. البرنامج Java لعكس LinkedList بشكل متكرر هو:

public static Node recursiveReverse(Node head) {
	Node first;

	if (head==null || head.next == null)
		return head;

	first = recursiveReverse(head.next);
	head.next.next = head;
	head.next = null;

	return first;
}

نمرر فقط head.next في الاستدعاء المتكرر للذهاب إلى نهاية LinkedList. بمجرد وصولنا إلى النهاية، نقوم بتعيين العنصر قبل الأخير كالتالي للعنصر الأخير ونقوم بتعيين مؤشر العنصر الثاني قبل الأخير إلى NULL. سيتم تحديد العنصر الأخير كالرأس الجديد. استخدم الكود التالي لعكس قائمة المرتبطة باستخدام النهج التكراري.

myLinkedList.head = recursiveReverse(myLinkedList.head);

سيظل الإخراج كما هو في النهج التكراري السابق.

تعقيد الوقت والمساحة لعكس قائمة متصلة

تعقيد الوقت – O(n) تعقيد المساحة – O(1)

يمكنك مراجعة الشيفرة الكاملة وأمثلة أخرى على هياكل البيانات والخوارزميات من مستودع GitHub الخاص بنا.