02 هياكل البيانات: القوائم أحادية الرابط الجزء الثاني

بسم الله الرحمن الرحيم 

السلام عليكم ورحمة الله وبركاته ...،

أولاً اعتذر جداً عن التأخر في طرح الشرح الذي كان من المفترض يكون بعد أسبوع من الموضوع السابق

تطرقنا في شرحنا السابق الى مفهوم القائمة أحادية الرابط وشرحنا استخداماته وطريقة عملها نظريا

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

 

١. إنشاء العقدة Node:

كما نعلم بأن Node هي الوحدة الأساسية لبناء قائمة أحادية الرابط أو القوائم بشكل عام ونستطيع بأن نصفها بأنها الحجر الذي يستخدم لبنائها.

لذلك يجب علينا بنائها ابتداءً.

public class SLLNode {
	public int info;
	public SLLNode next;
	
	public SLLNode(int i){
		this(i, null);
	}
	
	public SLLNode(int i, SLLNode n){
		this.info = i;
		this.next = n;
	}
}

هذا الكلاس والذي سمي بـ SSLNode هو الذي يصف لنا كل عقدة على حدى. 

وكل عقدة تتكون من info وهو المتغير الذي يحتوي على البيانات (المعلومة) وفي حالتنا هذه تكون البيانات من نوع int.

وكذلك next وهو عبارة عن الرابط الذي يصل العقدة الحالية بالعقدة التي تليها ومن الطبيعي أن يكون من نوع  SLLNode.

هذا الكلاس يحتوي على two Constructor وهما عبارة عن وظائف تستخدم لإنشاء العقد Nodes.

الأولى تستخدم لإنشاء عقدة لكنها لا ترتبط بأخرى كما نرى فيها فقد قمنا باستدعاء الميثود الثانية وقمنا بوضع null مكان الرابط.

أما الثانية فتنشأ عقدة ترتبط بأخرى. (قمت بتفصيلها في الموضوع السابق)

 

٢. إنشاء القائمة أحادية الرابط:

الكلاس السابق يمكننا من إنشاء عقدة واحدة لكن في هذا الكلاس سنتمكن من إنشاء قائمة كاملة تتكون من عدد من العقد Nodes.

أ. مؤشر لأول عنصر وآخر عنصر بالقائمة:

لكي نسهل عملية التنقل داخل القائمة سنقوم بإنشاء مؤشرين أحدهما يشير إلى أول عنصر بالقائمة (head: الرأس)،

والآخر يشير إلى آخر عنصر بالقائمة (tail: الذيل). هذين المؤشرين عبارة عن متغيريين من نوع SSNode.

protected SLLNode head, tail;

في بداية إنشاء القائمة (أو في حالة كانت القائمة خالية) فإن هذين العنصريين يكونان خاليين:

	public SLList(){
		head = tail = null;
	}

كما يتبين في هذه الـ Constructor.

 

ب. فحص القائمة إذا كانت خالية أو لا:

هذه الـ Method مهمة جداً ولها أستخدام في جل الـ Methods الأخرى، ومهمتها هي فحص إذا ما كانت القائمة خالية أو لا.

وتقوم بإرجاع قيمة Boolean إما true أو false.

	public boolean isEmpty(){
		return head == null;
		//or return tail == null;
	}

بكل بساطة في حال كان الرأس خالي فإن القائمة خالية كذلك، بالإمكان الإستعانة بالذيل كذلك فمن المستحيل أن يكون أحدهما خالي دون الآخر.

 

ب. إضافة عنصر جديد إلى الرأس (بداية القائمة):

	public void addToHead(int el){
    	head.next = head;
		head = new SLLNode(el);
		if (tail = null){ 
			tail = head;
		}
	}

أولا نجعل الرأس يشير إلى نفسه لكي نربط العنصر الجديد بالعنصر الأول السابق.

عندها نقوم بإنشاء عنصر Node ونجعله الرأس الجديد

في حالة كانت القائمة خالية نجعل الذيل يشير إلى نفس العنصر الذي يشير له الرأس.

ملاحظة: عندما يشير الرأس والذيل إلى نفس العنصر فهذا يعني بأن لدينا عنصر واحد فقط في القائمة.

 

ج. إضافة عنصر جديد إلى الذيل (نهاية القائمة):

	public void addToTail(int el){
		if(!isEmpty()){
			tail.next = new SLLNode(el);
			tail = tail.next;
		}else{
			head = tail = new SLLNode(el);
		}
	}

نفحص القائمة إذا كانت خالية:

- في حالة كانت غير خالية: ننشأ عنصر جديد ونجعل الذيل الحالي يشير إليه، ومن ثم نجعله الذيل الجديد.

- في حال كانت القائمة خالية: ننشأ عنصر جديد ونجعل الرأس والذيل يشيران إليه.

 

د. حذف العنصر الموجود بالرأس (أول عنصر):

	public int deleteHead(){
		int el = head.info;
		if(head == tail){
			head = tail = null;
		}else{
			head = head.next;
		}
		
		return el; 
	}

هذه الـ method تقوم بحذف العنصر الموجود بالرأس ومن ثم ترجع قيمته.

أولا نحفظ القيمة داخل متغير el لكي لا تضيع بعد حذف العنصر.

ومن ثم نفحص إذا كانت القائمة:

- تحتوي على عنصر واحد: فعندها نجعل الرأس والذيل يسيران إلى لا شيء null وتكون القائمة حينها خالية.

- تحتوي على أكثر من عنصر: فعندها نجعل العنصر الذي بعد الرأس هو الرأس الجديد، وفي هذه الحالة سيكون العنصر

لا يوجود ما يشير إليه ويحذف.

ومن ثم ترجع القيمة التي تم حذفها.

 

هـ- حذف العنصر الموجود بالذيل (آخر عنصر):

	public int deleteTail(){
		int el = tail.info;
		if(tail == head){
			head = tail = null;
		}else{
			SLLNode temp;
			for(temp = head; temp.next != tail; temp = temp.next);

			tail = temp; 
			tail.next = null;
		}
		
		return el;
	}

كما في السابق نحتفظ بقيمة العنصر لكي نقوم بإعادته بعد الإنتهاء من عملية الحذف لكن الحذف من الذيل ليس بسهولة الحذف من الرأس.

نفحص التالي:

- في حالة أن القائمة تحتوي على عنصر واحد فقط: فعندها نحذف القائمة كلها بجعل الرأس والذيل null.

- في حالة أن القائمة تحتوي على أكثر من عنصر:

أولا علينا أن نبحث عن العنصر السابق للذيل (العنصر قبل الأخير)، وذلك بأستخدام for loop قبلها علينا أن ننشأ مؤشر مؤقت باسم temp 

وفي بداية الـ loop نجعله يشير إلى الرأس، وننقله من عنصر إلى آخر إلى أن يصل إلى العنصر ما قبل الأخير وذلك بفحص إذا ما كان 

temp.next أي العنصر الذي يليه هو tail فعندها نكون وصلنا إلى العنصر ما قبل الأخير.

بعد أن نجد العنصر ما قبل الأخير نجعل الذيل الجديد ومن ثم نجعل الذيل يشير إلى null لكي يتم حذف العنصر الأخير تماماً.

 

و. طباعة جميع عناصر القائمة:

	public void printAll(){
		System.out.print("[");
		for(SLLNode temp = head; temp != null; temp = temp.next){
			System.out.print(temp.info + " ");
		}
		System.out.println("]");
	}

كما شرحنا سابقا نستخدم for loop للتنقل بين عناصر القائمة وطباعة قيمة كل عنصر على الشاشة.

 

ز. فحص وجود العنصر في القائمة أو لا:

	public boolean isInList(int el){
		if(isEmpty()){
			return false;
		}else{
			SLLNode temp;
			for(temp = head; temp.info != el && temp.next != null; temp = temp.next);
			return temp != null;
		}
	}

للبحث عن وجود قيمة داخل القائمة من عدمه يجب علينا أن نتنقل داخل القائمة عنصر بعنصر، وسنستخدم الأسلوب السابق

وهو باستخدام for loop. ولكن قبلها يجب علينا أن نتأكد من أن القائمة غير خالية.

الـ for loop ستتوقف في إحدى حالتين في حالة وجدة العنصر داخل القائمة وذلك ببطلان الشرط (tmep.info != el)

أو في حالة وصول temp إلى نهاية القائمة. 

عندها سنرجع القية المعاكسة لهذا الشرط (tmep != null) في حالة وصول الـ temp إلى نهاية القائمة بدون أن يجد العنصر

فعندا سيكون temp يساوي null وفي هذه الحالة سيرسل false أما في حالة إجاد العنصر فعندها temp لن يكون  null ويرسل true.

 

ح. حذف عنصر من القائمة:

public void delete(int el){
		if(!isEmpty() && isInList()){
			if(head == tail && head.info == el){
				head = tail = null;
			}else if(el == head.info){
				head = head.next;
			}else{
				SLLNode pre, temp;
				for(temp = head.next, pre = head; temp.info != el;
						pre = temp, temp = temp.next);
				if(temp != null){
					pre.next = temp.next;

					if(temp == tail){
						tail = pre;
					}

				}
			}
		}
	}

في حالة أردنا حذف عنصر من القائمة علينا أن نفكر في جميع الإحتمالات وهي كالتالي:

- هل القائمة غير خالية؟! وهل العنصر في القائمة ولتححق سنستخدم isEmpty و isInList، في حالة لم تكن القائمة خالية وكان العنصر بالقائمة ننتقل للخطوة التالية:

* هل القائمة تحتوي على عنصر واحد؟!: في هذه الحالة نقوم بحذف هذا العنصر ونجعل القائمة خالية.

* هل القائمة تحتوي على أكثر من عنصر والعنصر المراد حذفة بالرأس؟: عنذها نحذف الرأس كما أشرنا في الفقرة (د).

*الخيار الأخير هو أن العنصر موجود داخل القائمة: 

في هذه الحالة نحتاج للبحث عن العنصر بنفس الأسلوب السابق لكننا هنا على خلاف الخطوات السابقة نحتاج إلى متغيرين مؤقتين

أحدهما يشير إلى العنصر المراد حذفه والآخر يشير إلى العنصر الذي يسبقه. ولكي نقوم بذلك فعند إنشاء temp وهو العنصر المؤقت الذي سنبحث

عن طريقه للعنصر المراد حذفه نجعل pre العنصر الذي يسبقه وذلك كما يلي:

pre = head , temp = pre.next 

كما نعلم فنحن لسنا بحاجة لفحص الرأس فقد تأكدنا من أن العنصر ليس بالرأس. تنتهي for loop في حال إجاد العنصر المراد حذف مع العلم بأننا لن نصل إلى نهاية القائمة

لأننا تأكدنا من أن العنصر موجود في القائمة في الخطوة الأولى. وعند نهاية كل دورة من for loop نقوم بتحديث قيمتي pre and temp.

بعد ذلك نجعل الـ pre يشير للعنصر الذي يلي temp أي يشير للعنصر الذي بعد العنصر المراد حذفه عندها لن يكون هناك ما يشير إليه ويحذف.

** تأكد أخير في حال أن العنصر الذي حذفنها هو الأخير فعندها يجب أن نجعل الذيل يشير إلى null.

 

#شرح مفصل للـ for loop المستخدمة مع القوائم بشكل عام:

لأهميتها القصوى سوف أفصلها أكثر، إبتداءً بالشكل العام لها:

for (SLLNode temp = head; temp != null; temp = temp.next);

أولا نقوم بإنشاء متغير مؤقت ونسميه بأي أسم كان هذا المتغير في بداية الـ loop سيشير لأول عنصر بالقائمة

وهو الرأس head بعد ذلك يتأكد من تحقق الشرط وهو أن هذا المتغير لا يساوي null (أي أنه غير خالي)، ومن ثم

يحدث قيمة المتغير وذلك بجعله العنصر التالي له عن طريق (temp = temp.next) ومن ثم يقوم بالتأكد من الشرط مجدداً

هكذا حتى يصل إلى أن temp مساوي لـ tail وعندها يسنتقل للعنصر الذي يليه وهو في الحقيقة null لأنه tail.next دائما يساوي null

وهكذا تنتهي  for loop. 

ملاحظة: قمت بوضع ملفات للـ SLLNode and SLList classes في المرفقات تحتوي على تعليقات توضيحية.

 

أتمنى من الله أن أكون قد وفقت في تفصيل موضوعنا هذا

في حفظ الله إلى لقاء آخر

SLList.java

SLLNode.java

كلمات دليلية: