شرح الSingly linked list

صورة توضيحية للsingly linked list

 Singly linked list

المقدمة:

تعد الsingly linked list في أغلب الأحيان أول هيكل بيانات يتعرف إليها أى مهتم بعلوم البرمجيات، كهيكل بيانات وليس كنوع من أنواع البيانات وذلك بخلاف الِArray، بل إنها تساهم بمفاهيمها في بناء العديد من هياكل البيانات الأكثر تعقيدا.

الSingly Linked List:

هى واحدة من هياكل البيانات، والتي تخزن البيانات بشكل غير متسلسل في الذاكرة، ويشير كل بيان أو عنصر فيها إلى البيان\العنصر الذي يليه.

من التعريف السابق يمكنك إستنتاج بعض الأسئلة:

أولا: ما هى هياكل البيانات؟

هى طرق لترتيب البيانات في الجهاز، بشكل يكون أكثر فاعلية.

ثانيا: ما المقصود بشكل غير متسلسل؟

المتسلس عادة هو ما يلي بعضه بعضا، أى لو قلت أن البيانات تحزن بشكل متسلسل  في الذاكرة: أى أنها تخزن بجانب بعضها البعض. إلا أن الsingly linked list لا يشترط تخزين بياناته بجانب بعضها البعض في الذاكرة، بل يمكن أن تخزن البيانات في أى مكان بالذاكرة.

ثالثا: ما المقصود بأن كل بيان\عنصر يشير إلى ما يليه؟

ستعرف إجابة هذا السؤال بشكل مفصل في فقرة الsingly node، لكن يمكن أن أقول باختصار: أن أى عنصر في الsingly linked list يحتوي على جزئين، جزء يحمل البيان (أو يمكن القول بالإنجليزية Data) والجزئ الآخر يشير إلى العنصر التالي ويمكن أن تسميه (pointer).

الSingly node:

تعد الsingly node هى وحدة بناء الsingly linked list، حيث تحوي الsingle linked list مجموعة من الsingly nodes المترابطة فكل singly node يشير إلى الsingly node الذي يليه.

لتتعرف بالsingly node دعنى نطرح بعض الاسئلة:

 

1 - مما تتكون الsingly node:

صورة توضيحية للsingly node

قد تتصور من الصورة أعلاه أن الsingly node تتكون من 3 أجزاء، إلا أنه في الحقيقة: يتكون من جزئين فقط. وذلك سيتضح فيما هو آت:

الجزء (1): جزء تخزين البيانات:

في هذا الجزء من الsingly node يخزن البيان، ولا يهم نوع البيان، فقد يكون رقمًا أو نصًا أو  غيره.

الجزء (2): جزء تخزين الsingly node التالية:

في هذا الجزء إذا كنت تستخدم لغات تتعامل مع الذاكرة بشكل  مباشر، فإنك في الغالب تخزن موقع الsingly node الذي يليك. أما لو كنت تستخدم لغة من اللغات الحديثة، ففي الغالب أن تخزن الsingly node نفسها في هذا الجزء.

الجزء (3): مؤشر وهمي للفهم:

ذلك الجزء في الصورة: ما هو إلا جزء وهمي؛ نريد ان نوصل من خلاله مفهوم المؤشر: حيث أريدك ان تعلم أن كل singly node لديها مؤشر واحد يشير إلى العنصر الذي يليه، أو قد لا يشير إلى أى شىء، إذا كان الsingly node الأخير في السلسلة.

2 - ما الذي أحتاجه من معرفة لأستطيع بناء الsingly node؟

في حقيقة الامر إن الكثير من هياكل البيانات تشترك فيما سأقوله لك من متطلبات الآن:

1 - أن تكون لديك معرفة في استخدام لغة برمجة ما: كل ما تحتاجه من هذه اللغة ما هو إلا الأساسيات ك:

• تعريف المتغيرات.
• أنواع البيانات.
• الدوال الشرطية (if,switch) .
• دوال التكرار (for,while).
• الfunction.

2 - أن تكون لديك معرفة بسيطة بكيفية تطبيق الOOP في لغتك التي تعلمتها.

3 - كيفية تنفيذ الsingly node برمجيًا:

في بداية الأمر قبل تنفيذ الsingly node برمجيًا، عليك أن تعلم أنه ما دمت تعرف اللغة التي تستعملها بشكل جيد، فلن يشكل لك فارقا كبيرا أى لغة سأستخدمها.

 سأستخدم لتنفيذ الcode في هذه المقالة لغة الJavaScript.

سنقوم بتنفيذ الsingly node في عدد من الخطوات، اتبعها واحدة تلو الأخرى:

الخطوة الأولى: اعلن عن class يحمل مسمى الsinglyNode مثل ما في الصورة أدناه:

class معلن عنه باسم singlyNode باستخدام الJavaScript

تقوم بهذه الخطوة طبقا للsyntax (طريقة الكتابة) الخاص باللغة التي تستعملها، وذلك ليس في هذه الخطوة فقط، بل يتضمن ذلك أى خطوة لاحقة أخرى.

الخطوة الثانية: أعلن عن  function الconstructor داخل الsinglyNode class الذي أعلنا عنه في الخطوة السابقة كما في الصورة أدناه:

تنويه: function الconstructor هو function يعمل تلقائيا كلما تم تخليق كائن من نفس الclass.

الخطوة الثالثة: نضع argument بداخل القوسين النصف دائرين "()" يعبر عن قيمة الnode ونسميه val، أنظر للصورة أدناه:

الخطوة الرابعة: نعلن عن أول مكون من مكونات الsinglyNode وهو الجزء المتخصص بحمل البيانات وسنميه هنا مثلا "val" وسنعطيه قيمة الargument الذي أعلنا عنه سابقا "val"، كما ترى أدناه:

 

الخطوة الخامسة: نعلن عن المكون الثاني للsingly node وهو الجزء الخاص بحمل أو التأشير إلى الnode الذي يليه، وسنميه هنا "next" ونعطيه القيمة "null" في الوقت الحالي، أنظر للصورة أدناه:

هنيئا لك، الآن قد أنشأت singly node، لكن لا تتعجل للبدئ بإنشاء الsingly linked list، سنقوم أولا بكتابة بعض الcode التجريبي لفهم الclass الذي أنشأناه.

تعالى لننشئ كائن من الclass الذي أنشأناه ونضع له القيمة "7" مثلا:

في الصورة أعلاه أعلنت عن كائن جديد وسميته newNode، نستخدم كلمة new للإعلن عن كائن جديد يستمد صفاته من الclass الذي ذكرنا اسمه بعده، وهو الsinglyNode كما ترى في الصورة أعلاه.

 تلاحظ أن بعد ذكر اسم الclass فتحنا قوسين "()" ووضعنا بداخلهما القيمة 7.

عندما وضعنا القيمة 7 في الصورة أعلاه، فإن الconstructor function يستدعى تلقائيا، ويأخذ القيمة التي أدخلناها ("7")، ويعطيها للparameter الذي يحمل القيم، والذي سميناه val.

للتأكد مما قلته في الفقرة السابقة، سأقوم بطباعة قيمة parameter الval للكائن الذي أنشأناه "newNode":

في الصورة أعلاه، استخدمت أمر الطباعة (console.log) وهو أمر طباعة بلغة الJavaSript  ووضعت بداخله أمران ليطبعهما:

 الأول: سهم طويل (ليس السهم مهما فهو مجرد زينة).

الثاني: أمرته بأن يطبع بجوار السهم قيمة parameter الval للكائن الذي أنشأناه "newNode".

ترى أسفل الكود في الصورة أعلاه، أنه بالفعل قد طبع البرنامج سهما طويلا، ثم الرقم 7 بلون اصفر.

 في حال إن لم يكن ذلك واضحا في الصورة أعلاه، انظر للصورة أدناه:

الآن دعنا نرى ماذا يحدث إذا أردنا طباعة الجزء الثاني من مكونات الnode وهو الnext:

تلاحظ: في الصورة أعلاه أن ناتج أمر الطباعه للnext parameter هو null، وذلك لأننا لم نربطه بشىء بعد.

يمككننا بكل بساطة أن نربط الnext parameter بأى ما تريد، ولكن لنتمكن من خلق singly linked list فأنت بحاجه إلى ربط العديد من الnodes مع بعضها البع؛، لذا ستكون قيمة الnext هو singly node أخرى.

لاحظ الثلاث أسطر في الصورة أدناه:

في السطر الأول: تلاحظ أنني أنشأت singly ndoe جديدة، وسميتها newNode2 وأعطيناها القيمة 9.

في السطر الثاني: ترى أنني جعلت قيمة الnext parameter للnewNode (أول singly node قمنا بإنشائها) تساوي الnewNode2 (الsingly node الجديدة التي أنشأناها في السطر الأول).

في السطر الثالث: طلبنا مرة أخرى طباعة قيمة الnext parameter للnewNode، وتلاحظ أن النتيجة هذه المرة ليست null، بل هى singly node، وتلاحظ أن قيمة الval في الnode تساوي 9، وبذلك فأنت متأكد أن تلك الsingly node هى الnewNode2.

 الصورة أدناه للنتيجة فقط حال أنك لم تستوضحها من الصورة أعلاه:

الpointer:

لا أقصد بشرح الpointer هنا، الpointer الذي لربما سمعت عنه في أحد الدروس التعليمية للغة ال++C، لكن هو مفهوم مقارب له نوعا ما.

إذا كنت قد درست الarray مسبقا، فإنك تعلم على الأغلب أننا يمكننا الوصول لأى عنصر من عناصر الarray من خلال الindex الخاص بها، وذلك لأن كل index يشير إلى عنصر ما.

إلا أننا لا نستخدم الIndex للوصول إلى عناصر الsingly linked list؛ وذلك لأن عناصر الsingly linked list لا تجاور بعضها البعض في ذاكرة الجهاز، فإن كنت لا تعرف ما علاقة ذاكرة الجهاز بالindex راجع جزء الindex من مقالة الarray.

بما أننا لا نستخدم الindex فإننا نستخدم مفهوم الpointer؛ لنشير إلى عناصر الsingly linked list، وهو في الحقيقة: عبارة عن متغير يخزن أولsingly node في سلسلة الnodes ونسميه الhead.

 في بعض الأحيان ولكن ليس شرطا، أفضل أن أضيف مؤشر آخر يشير أو يحفظ آخر عنصر في سلسلة الnodes، ونسميه عادة الtail.

من الممكن أن تصاب بالهلع، أو عدم الفهم، لما أقوله، ولكن كل شىء سيتضح خطوة خطوة، في باقي المقال، استمر بعزم...

مزيد عن الsingly linked list:

 أعلم أن المقال يبدأ بتعريف للsingly linked list ومن ثم تفصيل له، لكن من هنا ستعلم ما يحويه باقي المقال، لتعلم كيف سيسير بناؤنا للsingly linked list:

سنقوم بشرح الآتي على الترتيب:

أولا: شرح مكونات function الconstructor للsingly linked list: الغرض من هذه الخطوة أن أعرفك على أهم ثلاث معلومات تقوم عليها معظم العمليات التي سنبنيها في class الsingly linked list الخاص بنا.

ثانيا: شرح function الreSize: الغرض من هذه الfunction أن نغير ايمة حجم الsingly linked list الخاصة بنا، فكلما أضفنا عنصرا، يزيد واحد، وكلما حذفنا عنصرا، ننقص واحد.

ثالثا: شرح function الunshift: الغرض من هذه الfunction أن نتعلم كيف نضيف عنصر إلى بداية الsingly linked list.

رابعا: شرح function الpush: الغرض من هذه الfunction أن نتعلم كيف نضيف عنصر في نهاية الsingly linked list.

خامسا: شرح function الsearch: الغرض من هذه الfunction أن نتعلم كيف نبحث عن عنصر حسب ترتيبه في الsingly linked list.

سادسا: شرح function الinsert: الغرض من هذه الfunction أن نتعلم كيف نضيف عنصر في أى مكان في الsingly linked list.

سابعا: شرح function الshift: الغرض من هذه الfunction أن نتعلم كيف نحذف عنصر من بداية الsingly linked list.

ثامنا: شرح function الpop: الغرض من هذه الfunction أن نتعلم كيف نحذف عنصر من نهاية الsingly linked list.

تاسعا: شرح function الdelete: الغرض من هذه الfunction أن نتعلم كيف نحذف عنصر من أى مكان من الsingly linked list.

بتمام دراستك للتسع موضوعات السابقة، سيكون فهمك أعمق للsingly linked list، وإذا أردت أن يكون فهمك متقنا فمن الأفضل أن تطبق كل ما شرح منذ فقرة الsingly node حتى نهاية هذه المقالة بإذن الله.

function الconstructor للsingly linked list:

function الconstructor كما تعلمنا مسبقا: هى function تتفعل تلقائيا، بمجرد أن نعلن عن object نريد انشاءه، من الclass الذي أعلنا بداخله الfunction.

أريدك أن تدرك في حال أنك تستخدم لغة غير الjavaScript، أنه قد يكون مسمى الfunction التي تقوم بتلك المهمة مختلفا عندك، كل ما عليك فعله، هو أن تستغل فهمك لوظيفة هذه  الfunction  للبحث عن مسماها في لغتك.

في الconstructor function سنعلن عن ثلاث متغيرات هن كالآتي:

• متغير الhead: ووظيفته أن يظل مشيرا إلى رأس الsingly linked list، والمقصود بالرأس: هو أول node في الsingly linked list.

• متغير الtail: ووظيفته أن يظل مشيرا إلى ذيل الsingly linked list، والمقصود بالذيل: هو آخر عنصر في الsingly linked list.

• متغير الlength: ووظيفته أن يظل حاملا لعدد الsingly nodes التي تحملها الsingly linked list.

أنشأت كل مما سبق في class سميته singlyLinkedList كما ترى أدناه:

تلاحظ أن كلا من قيمتى الhead والtail يساويا null، وذلك لأنه لا يوجد أى عنصر بالsingly linked list حتى الآن.
كما تالاحظ أن قيمة الlingth تساوي الصفر لنفس السبب.

function الreSize:

نستهدف من بنائنا لهذة الfunction: أن نكون قادرين على أن نضيف لparameter الlength أى قيمة نريدها، لذا سنبني function الreSize بحيث تستقبل مني رقما، ثم تضيفه تلقائيا لparameter الlength. أنظل للصورة أدناه:

هكذا نحدث طول الsingly linked list من خلال هذه الfunction.

function الunshift:

من خلال هذه الfunction: أريد أن أضيف عنصر(singly node) تكون في بداية الsingly linked list.

 بالطبع تعلم مسبقا أن أول عناصر الsingly linked list يشير إليه المؤشر head.

هذه الfunction لديها حالتان:

الأولى: أن تكون الsingly linked list فارغة:

في هذه الحالة سيكون العنصر الذي نريد أن نضيفه في بداية الsingly linked list الخاصة بنا: هو أول عنصر، وذلك منطقى؛ لأن هذه هى وظيفة الFunction أساسا. إلا أنه سيكون في نفس الوقت هو آخر عنصر في الsingly linked list، وذلك لأنه الوحيد الموجود.

 في الصورة أدناه: الcode الذي كتبته بلغة الjavaScript لرصد هذه الحالة وحلها، وفيما يلي الصورة، الشرح المفصل لخطوات كتابة الكود:

تلاحظ في نهاية كل سطر برمجى أنني أنهيه ب (//) ومن ثم رقم، وهذه هى الطريقة التي يكتب بها الcomment في لغة الJS، وسأستخدم هذا الترقيم، الذي قمت به لشرح أسطر الcode.

السطر (1): 

في هذا السطر قمنا بالإعلان عن Method (تسمى الfunctions في الclasses والobjects بالmethods) الunshift، كما أعلنا عن argument الnum وهى تمثل قيمة الData ل-الsingly node الذي سننشؤه.

السطر (2): 

في هذا السطر قمنا بإنشاء singly node جديد من الsingly node class الذي أنشأناه سابقا، وأدخلنا له قيمة الnum؛ لتكون قيمة parameter الval في الsingly node الجديد (إذا شعرت ببعض اللبس، تفقد فقرة الsingly node مرة أخرى بتمعن)، ثم حفظنا الsingly node الذي أنشأناه في المتغير newNode.

السطر (3): 

في هذا السطر بدأنا بحل الحالة الأولى، حيث أن كلا من الاسطر 1 ، 2 ، 6 هي خطوات مشتركة مع كلتا الحالتين، إلا أن الأسطر 4 ، 5 فهما مخصصان لحل الحالة الأولى فقط. ويعمل السطر 3 على رصد الحالة. ففي هذا السطر تجد أني وضعت شرطا: بأن ينفذ ما يوجد بداخل الif statement في حال كان طول الsingly linked list يساوي صفرا.

السطر (4): 

في هذا السطر تجد أنني جعلت مؤشر الhead يشير إلى الnewNode : وهو المتغير الذي يشير إلى الsingly node التي أنشأناها سابقا في السطر (2).

 بالطبع ما قمنا به منطقي؛ وذلك لأن الsingly node الجديدة: هى بالفعل أول عنصر في سلسلة الsingly linked list.

السطر (5): 

في هذا السطر تجد أنني جعلت مؤشر الtail شير إلى الnewNode، وهذا منطقى أيضا؛ فبما أن الnewNode هو العنصر الوحيد الذي لدينا في الsingly linked list الآن؛ فبتالي هو يمثل العنصر الأول والأخير. 

الصورة توضح لك  الفارق الذي حدث للsingly linked list الفارغة قبل إضافة عنصر في بدايتها وبعده.

الثانية: أن تكون الsingly linked list بها  عنصر واحد فما يزيد:

في هذه الحالة تكون الsingly linked list غير فارغة بالفعل، فبالتالي يوجد عنصر أو عناصر اخرى، والعنصر الجديد الذي أريد إضافته أريده أن يكون أول هذه المجموعة، وأن يشير إلى العنصر الأول (سابقا: بما أن عنصرنا الجديد سيكون أول العناصر).

 ثم أغير مؤشر الhead ليشير إلى عنصرنا الجديد؛ لأنه أول العناصر الآن؛ بينما تلاحظ اننا لا نحتاج لنتعامل مع مؤشر الtail ؛ لأنه بإضافة عنصر لبداية السلسلة لن يؤدي إلى تغيير العنصر الذي يقع في نهايتها.

 إليك الcode:

تلاحظ الأسطر أعلاه قد رقمتها من 1 إلى 4، وسأشرح كل وظيفة سطر على حده:

السطر (1): 

في هذا السطرقمنا برصد جميع الحالات، باستثناء الحالة الاولى: وهى أن تكون الsingly linked list فارغة. 

أما فما تبقى من الحالات هى جميع الحالات التي لا تكون فيها الsingly linked list فارغة.

السطر (2): 

في هذا السطر تلاحظ أننا جعلنا الnewNode يشير إلى العنصر الذي يشير إليه الhead، ويعد العنصر المشار إليه هو أول عنصر بالsingly linked list. ولكن بما أن عنصرنا الجديد أصبح يشير إليه الآن، فقد أصبح عنصرنا الجديد هو الاول بدلا عنه.

السطر (3): 

في هذا السطر جعلت مؤشر الhead يشير إلى عنصرنا الجديد (newNode)؛ وذلك لأنه الآن أصبح أول node في الsingly linked list.

السطر (4): 

هذا السطر هو نفسه السطر (6) من صورة code الحالة الأولى: والذي لم أشرح ما يفعله آن ذاك؛ وذلك لبساطة ما يفعلة. 

إذ تتذكر أننا بنينا تلك الmethod التي تغير الحجم (reSize) عن طريق أخذ قيمة وإضافته لparameter الlength، فهنا ستأخذ الreSize method القيمة 1 لتزيد من حجم الsingly linked list بمقدار واحد، وذلك لأننا أضفنا عنصرا واحدا.

Method الunshift للsingly linked list كاملة

صورة توضيحية للفرق بين singly linked list ذات عنصر واحد وأخرى متعددة العناصر.

بعد أن بنينا دالة الunshift بشكل كامل، تلاحظ أن كلا من حالتى الدالة لا تتضمن المرور عبر عناصر المجموعة كلها، أو حتى عدد منها.

 بل الخطوات محدودة بالعدد، وستتكرر مرة واحدة كلما اردت أن أضيف عنصرا لبداية السلسة.

هذا ما نعبر عنه بأن الخوارزمية تستهلك وقتا قدره O(1) (ننطق هذا التعبير الأخير هكذا: Big O of one(1)) ، وهو يعني أن الوقت الذي ستستهلكة هذه الخوارزمية سيظل ثابتا،  مهما كان طول الsingly linked list. 

إذا كنت قد مررت بمقالة الArray سابقا فلعلك تعلم ذلك. إلا لو أنه ما زال الأمر مربكا لديك، يمكنك أن تبحث عن "تحليل الخوارزميات".

لربما تتذكر أو تعلم مسبقا: أنه كانت خاورزمية الunshift في الArray تستهلك وقتا قدره O(n) (وذلك يعني أن الوقت الذي تأخذه الخوارزمية لإجراء عملياتها، يساوي: الوقت الذي تستغرقه جميع العمليات أو جزء منها في المرة الواحدة X في عدد عناصر الArray). أظن أنه الآن يمكنك إدراك أن الSingly linked list لديها  القدره على إضافة عنصر في بداية السلسلة أسرع مما تقوم به الArray.

function الpush:

ما نريده من خوارزمية الpush التي سنبنيها بإذن القدير، أن نضيف عنصر لنهاية الsingly linked list.

ولهذه فللخوارزمية حالتان: تكاد تطابق حالتا خوارزمية الunshift، ندرسهما فيما هو آت:

الأولى: أن تكون الsingly linked list فارغة:

في هذه الحالة لا جديد فيما سنكتبه من code، هو نفسه؛ وذلك ﻷن أول عنصر في الsingly linked list لا تختلف طريقة إضافته مهما كانت الخوارزمية التي تريد أن تستخدمها.

إليك الcode  مكتوبا بداخل خوارزميتنا الجديدة:

كل ما فعلته هو أنني أعلنت عن الخوارزمية الجديدة ، ولكن كل ما يتضمنها إلى الآن هو مطابق لما تتضمنه خوارزمية الunshift في الحالة الأولى، حتى أني لم أكتبها، بل أخذتها نسخا ولصقا.

الثانية:  أن تكون الsingly linked list بها  عنصر واحد فما يزيد:

هذه الحالة ليست متطابقة مع الحالة الثانية في الخوارزمية unshift، لكن يوجد بينهما بعض التشابه. دعك من كل  هذا دعنا نبدأ باسم العلى.

في هذه الخوارزمية أريد بكل بساطة: أن أضيف العنصر الجديد إلى نهاية السلسلة.

 ولأقوم بذالك سأتبع الخطوات التالية:

1 - بما أن لدى parameter يسمى tail يشير دائما إلى آخر عنصر في السلسلة، فسأجعله يشير بالعنصر الذي يحمله إلى العنصر الجديد، وبهذا سيصبح العنصر الجديد  مشارا إليه من قبل آخر عنصر (سابقا؛ وذلك لأن عنصرنا الجديد هو الآن يعد آخر عنصر).

2 - بعد أن أصبح عنصرنا الجديد هو العنصر الاخير الآن، سأجعل parameter الtail يحمل العنصر الجديد.

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

في الحقيقة لو اتطلعت على خوارزمية الpush، لوجدتها لا تحتوي على أي عملية مرور عبر عناصر، او وجود أى جمل برمجية مهمتها تكرار العمليات البرمجية ك(for, while)، لذا يمكنك إستنتاج أن التعقيد الزمني لخوارزمية الpush هو O(1).

إن كنت تتذكر أن خوارزمية الpush في الarray هى أيضا تعقيدها الزمني هو O(1)، وهذا يعني أن كلتا الخوارزميتين لهما نفس التعقيد الزمني.

ملاحظة: في بعض الاحيان قد يستغني المبرمجون الآخرون عن parameter الtail، وذلك يؤدي إلى خوارزمية push مختلفة، كما أنها ستستغرق وقتا أطول؛ حيث سيكون التعقيد الزمني لخوارزمية الpush وقتها هو O(n).

خوارزمية الPush كاملة.

لو راجعت الcode أعلاه: ستلاحظ السطر الأخير الذي لم نشرحه، وذلك ﻷنك على الأغلب قد تذكرته الآن، وهو استدعاؤنا لخوارزمية الreSize لتزيد من حجم السلسلة بمقدار 1.

function الsearch:

أرجو أنه بوصولك لهذه الخوارزمية، أن تكون مفاهيم وأدوات الsingly linked list قد بدت مألوفة لديك.

لربما تظن أن من المفترض: أن تتبع خوارزميتا الshift والpush خوارزمية الinsert مباشرة، إلا أني قد أجلتها، لما بعد شرح هذه الخوارزمية؛ وذلك لأنها ستوفر علينا أمرين:

أولهما: التسهيل من تعقيد خوارزمية الinsert لتصبح أكثر بساطة.

ثانيهما: تقصير حجم خوارزمية الinsert عند كتابتها.

الهدف من هذه الخوارزمية: كل ما استهدفه من هذه الخوارزمية: هو أن أستطيع أن أعطيها رقما (يعد رقم ترتيب أحد العناصر في سلسلة الsingly linked list)، ثم تأخذ ذلك الرقم وتعود  لي بالعنصر.

لهذه الخوارزمية أربعة حالات:

الأولى: أن تكون السلسلة فارغة.

الثانية: أن تكون السلسلة ليست فارغة، والقيمة الرقمية المدخلة أقل من أو تساوي 1(الواحد).

الثالثة: أن تكون السلسلة ليست فارغة والقيمة الرقمية المدخلة أكبر من أو تساوي طول السلسلة.

الرابعة: أن تكون السلسلة ليست فارغة والقيمة االرقمية المدخلة أكبر من 1(الواحد) وأقل من طول السلسلة.

نشرح حل كل حالة من هذه الحالات، ونتضمنها في خوارزمية الsearch فيما هو آت:

الحالة الأولى: أن تكون السلسلة فارغة:

عندما تكون السلسلة فارغة، فاريد أن تخرج الخوارزمية بالقيمة -1.

في حال إن كنت تتسائل عن سبب إختياري للقيمة (-1)؛ فلذلك سببان:

الأول: أنه يجب أن تكون القيمة المعبرة عن عدم إيجاد العنصر المدخول رقمه: هى قيمة يستحيل أن تكون ناتج لعنصر موجود.

وفي حالتنا هذه إذا كان العنصر موجودا سيكونا المخرج هو singly node، وذلك يعني أني لو جعلت قيمة المخرج أى نوع بيان آخر، سيكون مناسبا لهذه الخوارزمية. فلما اخترت بالذات (-1) وليس رقما آخر؟!.

الثاني: الرقم (-1) هو مخرج معظم دوال البحث التي لا تجد ناتجا في معظم لغات البرمجة. لكن لاحظ أنه يجب أن يتحقق السبب الأول حتى يكون الآخر مقبولا.

إليك الcode لحل هذه المشكلة وبعض الإسهاب فيما يلي:

كالعادة سنتبع الترقيم الأخضر لشرح الأسطر:

السطر (1): في هذا السطر أعلنا عن خوارزمية الsearch.

السطر (2): في هذا السطر رصدنا الحالة لنتعامل معها، وبالطبع إذا كانت السلسلة فارغة فسيكون طولها يساوي 0. وفي حال تحقق ذلك سيبدأ بتنفيذ السطر (3).

السطر (3): تتوقف الخوارزمية في هذا السطر معيدة القيمة (-1).

الحالة الثانية: أن تكون السلسلة ليست فارغة، والقيمة الرقمية المدخلة أقل من أو تساوي 1(الواحد):

في هذه الحالة أريد من الخوارزمية: أن تخرج الsingly node الأولى في السلسلة، وذلك لأنه الاقرب من القيمة 1 فما أقل.

دعنا نشرح كيف سنقوم بذلك من خلال الcode:

السطر (1): في هذا السطر نرصد الحالة، فنتأكد أن الرقم المطلوب يساوي 1 أو أقل.

السطر (2): بما أنه لدينا بالفعل parameter يسمى الhead ويظل حاملا لأول عنصر في السلسلة: وهو العنصر الذي نريد من الخوارزمية أن تخرجه في حال تحقق الحالة الثانية؛ لذا فجعلت الhead مخرجا في هذه الحالة.

الحالة الثالثة: أن تكون السلسلة ليست فارغة، والقيمة الرقمية المدخلة أكبر من أو تساوي طول السلسلة.

في هذه الحالة أريد من الخوارزمية أن تخرج الsingly node الأخيرة في السلسلة؛ وذلك لأنه الأقرب من القيمة التي تساوي طول السلسلة أو يتجاوزها.

دعنا نشرح كيف سنقوم بذلك من خلال الcode:

السطر (1): في هذا السطر نرصد الحالة، فنتأكد أن الرقم المطلوب يساوي طول السلسلة أو أكثر.

السطر (2): بما أنه لدينا بالفعل parameter يسمى الtail ويظل حاملا لآخر عنصر في السلسلة: وهو العنصر الذي نريد من الخوارزمية أن تخرجه في حال تحقق الحالة الثالثة: لذا فجعلت الtail مخرجا في هذه الحالة.

الحالة الرابعة: أن تكون السلسلة ليست فارغة، والقيمة الرقمية المدخلة أكبر من 1(الواحد) وأقل من طول السلسلة.

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

دعنى نرى الأمر بشكل من التفصيل:

الcode المكتوب بالصورة أعلاه، هو حل للحالة الأخيرة، نشرحه بالتفصيل:

السطر (1): هنا نرصد الحالة الرابعه، فنتأكد أن ترتيب العنصر المطلوب أكبر من 1 وأقل من طول السلسلة؛ لنضمن أن هنالك ناتجا بالفعل.

السطر (2): قمنا بالإعلان عن العداد الذي سيقوم بالعد كلما مررنا على عنصر، حتى نصل إلى العنصر الذي يساوي رقمه في العد الرقم المدخل.

 ووضعنا للعداد قيمه مبدئية قيمتها 1 وذلك يفسره السطر التالي.

السطر (3): قمنا بالإعلان عن مؤشر جديد سميناه temp، وجعلناه يشير إلا نفس ما يشير إليه المؤشر head: أى أنه يشير إلى أول عنص في السلسلة.

سيقوم هذا المؤشر بالتحرك عبر عناصر السلسلة مشيرا إليها واحدا تلو الآخر، وفي كل مره يشير الtemp إلى عنصر سيزداد العداد بمقدار 1.

 ولأنه مبدئيا يشير إلى أول عنصر في السلسلة، فإن العداد cntr قيمته المبدئية 1.

السطر (4): هنا أعلنا عن بداية عمليات تكرارية، ستظل تتكرر طالما الشرط بين القوسين أعلاه متحقق، والذي ينص على: أن يدوم التكرار طلما لم يتساويا كلا من قيمة العداد وقيمة الترتيب المدخلة.

 السطر (5): هنا يزداد العداد cntr ما مقداره 1 مع كل دورة، معلنا عن تحرك المؤشر temp خطوة للأمام.

 السطر (6): هنا ترى أن المؤشر temp ينتقل من العنصر الحالي إلى العنصر الذي يليه.

السطر (7): عندما تنتهي العمليات التكراريه، سينفذ هذا السطر والذي يخرج في نهاية الأمر آخر singly node أشار إليها المؤشر temp وهو الsingly node المراد.

يمكن أن تلاحظ: من خلال الحالة الرابعة لخوارزمية الsearch، أنك تقوم بمجموعه من العمليات، طبقا لعدد العناصر التي ستضطر أن تمر عليها؛ لتصل إلى ترتيب العنصر المطلوب.

 فتلاحظ أنك تقوم بعدد من العمليات، يختلف حسب قرب العنصر المطلوب من بداية السلسلة، فلو طلب منك أن تبحث عن العنصر الذي ترتيبه يكون ال 1000 بين العناصر، فذلك سيستغرق عدد من العمليات يساوي: 1000 X عدد العمليات.

ولأن عدد العمليات يتغير تكرارها  بشكل خطي حسب المدخل، فإننا نرمز للتعقيد الزمني لهذه الخوارزمية ب O(n).

إن لم تستوعب ما أقصده بالتغير الخطي، فكل ما عليك أن تعوض هذه القيم (1، 2، 3، 4) في هذه المعادلة: num X 2، ومثل النتائج على المحورين (X, Y)، لتجد أنه قد تشكل لك خط مستقيم، يدل على معدل التغير.

function الinsert:

إن مهمة هذه الخوارزمية هو إضافة عنصر جديد في أى مكان في السلسلة.

قد تعلمنا مسبقا خوارزمية لإضافة عنصر في بداية السلسلة (unshift) ،وأخرى تضيف العنصر في نهاية السلسلة (push)، أما الآن نريد أن نضيف العنصر في أى مكان.

ستأخذ هذه الخوارزمية مدخلين، أولهما رقم: وهو يدل على القيمة التي ستعطى للعنصر الجديد، وسنسمي ذلك المدخل val. أما الآخر: فأيضا قمة رقمية، إلا أنه يدل على الترتيب الذي نريد أن نضع العنصر الجديد عنده، وسنسمي ذلك المدخل num.

لهذه الخوارزمية ثلاث حالات هى كالتالي:

الأولى: أن تكون السلسلة فارغة، أو أن تكون السلسلة ليست فارغة، وقيمة الnum تساوي ال1 أو أقل منه.

الثانية: أن تكون السلسلة ليست فارغة، وقيمة الnum  المدخلة أكبر من طول السلسلة.

الثالثة: أن تكون السلسلة ليست فارغة، وقيمة الnum  المدخلة أكبر من 1(الواحد)، وأقل من طول السلسلة، أو تساويها.

دعنا نناقش كل حالة على حده:

الحالة الأولى: أن تكون السلسلة فارغة، أو أن تكون السلسلة ليست فارغة، وقيمة الnum تساوي ال1 أو أقل منه.

في هذه الحالة من المفترض: أن تضيف الخوارزمية العنصر في أول السلسلة.

دعنا نرى بالتفصيل ماذا يحدث:

فلنأخذ الcode أعلاه سطرا سطرا كما اعتدنا:

السطر (1): هنا أعلنا عن خوارزمية الinsert واستقبالها لمدخلين هما (num, val).

السطر (2): هنا نرصد الحالة الأولى، وهي تتكون من جزئين:

 الأول: أن تكون السلسلة فارغة.

الثاني: أن تكون قيمة الnum أقل من 1 أو تساويه.

تلاحظ أنه بين الشرطين علامة (||) ، وتستعمل تلك العلامة في لغة الJS بمعنى (أو) في الدوال الشرطية، وهذا يعني: أنه لا يلزم تحقق الشرطين لينفذ الكود، بل يكفي تحقق شرط واحد.

السطر (3): بما أن ما أريد تنفيذه من خلال هذه الحاله هو أن أضيف عنصر جديد إلى أول السلسلة، فلدى بالفعل خوارزمية قد بنيناها سابقا، يمكنها أن تقوم بتلك المهمة، وهى خوارزمية: الunshift، لذا استدعيتها وأدخلت لها قيمة الval  الخاصة بالsingly node الجديد.

الحالة الثانية: أن تكون السلسلة ليست فارغة، وقيمة الnum  المدخلة أكبر من طول السلسلة.

في هذه الحال بما أن قيمة الnum أكبر من طول السلسلة، فهذا يعني أننا سنضيف العنصر في نهاية السلسلة، وبما أنني لدى خوارزمية تقوم بهذه المهمة بالفعل، فكل ما على القيام به هو: رصد الحالة، ومن ثم استعمال الخوارزمية push.

الحالة الثالثة: أن تكون السلسلة ليست فارغة، وقيمة الnum  المدخلة أكبر من 1(الواحد)، وأقل من طول السلسلة، أو تساويها.

في هذه الحالة قد يبدو الأمر أكثر تعقيدا؛ لذا صفي ذهنك وتأمل الصورة أدناه:

  

 

تلاحظ من الصورة أعلاه، أننا قمنا بالخطوات التالية، لنضيف عنصر قيمته 11 إلى السلسله، ويكون ترتيبه هو 2 .

الخطوة الأولى: أنشأنا عنصرا جديد أعطيناه القيمه 11، إلا أنك تلاحظ أنه ما زال وحيدا، لم يضف إلى السلسلة بعد.

الخطوة الثانية: تلاحظ أنني حرفت فيمة ال next  parameter للعنصر (1)، (وهو: العنصر الذي يقع قبل الترتيب الذي نريد ان نضيف عنده العنصر الجديد بواحد)؛ لأجعله يشير إلى العنصر الجديد. وبهاذا أصبح لدينا سلسلتين منفصلتين.

الخطوة الثالثة: قمت بتعيين قيمة للnext parameter للعنصر الجديد، يجعله يشير إلى العنصر الثاني سابقا.

وهكذا اصبحت سلسلتنا متصله، وترتيب العنصر الجديد هو 2.

انظر الى الخطوات بالcode ادناه، مع الشرح:

السطر (1): في هذا السطر كالعاده رصدنا الحالة الثالثة، فنتأكد ما إذا كان المدخل num قيمته فوق 1، وأقل من طول السلسلة، أو يساويها.

السطر (2): تلاحظ اننا في هذا السطر، كل ما قمنا به هو انشاء العنصر الجديد، وسميناه newNode.

السطر (3): في هذا السطر أردت ان أحدد العنصر الذي يقع ترتيبه قبل الترتيب الذي اريد أن أضيف فيه العنصر الجديد، واستغليت للبحث عن ذلك العنصر خوارزمية الsearch التي أنشأناها سابقا. وسميت العنصر الذي يقع قبل ترتيب العنصر الجديد بpreNumTh.

السطر (4): هنا قمت بتحديد العنصر: الذي يقع في نفس الترتيب، الذي تريد أن أضيف العنصر الجديد عنده.

السطر (5): هنا جعلنا العنصر الذي يقع قبل الترتيب بواحد، يشير إلى العنصر الجديد newNode، إلا أن ذلك يعني أننا انفصلنا عن السلسلة؛ لأن الnewNode لا تشير الى شىء بعدها.

السطر (6): هنا جعلنا العنصر الجديد يشير للعنصر: الذي كان يقع في نفس ترتيبه سابقا. وبهذا اتصلت السلسلة بعضها ببعض، وأصبح عنصرنا الجديد في الترتيب المراد، وتراجعت كل العناصر بعده بمقدار واحد.

السطر (7): هنا قمنا باستخدام خوارزمية الreSize؛ لنزيد من طول السلسلة بمقدار 1؛ فقد أضفنا عنصرا جديدا.

خوارزمية الinsert كاملة بجميع حالاتها

لاحظ: قمت بتعديل كلا من الحالة الأولى والحالة الثانية، بوضع الأمر return قبل الأمر الذي سيتم تنفيذه، وذلك لأني استنتجت ثغرة في الcode الذي كتبناه، إذا ما كانت قيمة الnum تساوي 1، وكانت السلسلة فارغة، حينها ستتوافق المدخلات مع الحالتين الأولى والثانين، وذلك سيؤدي إلى إضافة نفس الnode مرتين في السلسلة.

لاحظ أيضا: أن أسطر خوارزمية الInsert، لا يوجد بها جمل من الجمل التكرارية (for / while). وذلك يعني: أن كل سطر في خوارزميتنا ينفذ مرة واحده، مع كل عنصر نريد اضافته. مما يعني أن التعقيد الزمني لخوارزمية الinsert هو O(1). وبالطبع استنتاجك ذلك يعد "خطأ كبيرا".

ستلاحظ أن خوارزميتنا، بالرغم من أنها لا تحوي جملا تكرارية، إلا أنها تستدعي خوارزمية الsearch في إحدى حالتها، وهذه الخوارزمية كما علمنا مسبقا تعقيدها الزمني هو O(n).

ستخبرني أن دالة الsearch لا يتم استدعاؤها في جميع حالات الإضافة، إلا أنني أخبرك كالعاده: عندما تقرر ما التعقيد الزمني لخوارزميتك، فاختار التعبير الذي يدل على أسوء احتمال ممكن، وبذلك يمكن أن نقول أن التعقيد الزمني لخوارزمية الinsert هو O(n).

بهذا يمكنك أن تلاحظ أن خوارزمية الinsert في كل من الArrays والsingly linked list لها نفس التعقيد الزمني.

Function الshift:

صورة توضيحية لما تقوم به خوارزمية الshift

ما ستقوم به هذه الخوارزمية هو: حذف العنصر الأول في السلسلة كلما تم استدعاؤها.

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

الأولى: تدمير العنصر الأول (بمعنى حذفه).
الثانية: تحريك مؤشر الhead خطوة للأمام، أى للعنصر الثاني سابقا، والذي يعد العنصر الأول حاليا.

انظر للcode ادناه:

السطر (1): في هذا السطر، أعلنت عن خوارزمية الshift. وتلاحظ أنها لا تستقبل مدخلا؛ لأن مهمتها لا تعتمد على مدخل.

السطر (2): هنا نرصد الحالة الوحيدة لتعمل هذه الخوارزمية، ولأن الخوارزمية مهمتها هو حذف العنصر الاول من السلسلة، لذا رصدنا الحالة التي لا تكون فيه السلسلة فارغة.

السطر (3): تلاحظ أنني أعلن عن مؤشر (متغير) آخر، يحمل نفس العنصر الذي يحمله الhead، وذلك العنصر بالطبع هو أول عنصر في السلسلة، والذي نريد حذفه.

السطر (4): في هذا السطر غيرنا القيمة التي يحملها الhead، لتساوي العنصر الذي يلي العنصر الأول (العنصر الثاني: الذي سيكون العنصر الأول فيما بعد).

السطر (5) & (6): في هذان السطران، قمنا بحذف جميع القيم التي يحملها العنصر الذي يحمله المتغير/المؤشر first؛ وهذا لأنه في لغة الjavaScript يلزم: أن تحذف كل ما يدل عليه العنصر، ليعد العنصر محذوفا تلقائيا في اللغة؛ لأنه لم يعد يدل على أى شىء. لكن في لغات أخري يوجد أمر مباشر يسمح بتدمير العناصر، أو يمكن أن نقول بشكل أدق: يسمح بحذف الكائنات (objects).

السطر (7): في هذا السطر بعد أن دمرنا العنصر الأول، وجعلنا مؤشر الhead يشير إلى العنصر الأول الجديد في السلسلة، فقد اصبحت السلسة اصغر بمقدار 1، وهذا ما قمنا به باستخدام خوارزمية الreSize، وهو أن أنقصنا من طول السلسلة ما مقداره 1.

تلاحظ: أن خوارزمية الshift ينفذ فيها كل سطر لمرة واحده، كلما أردنا أن نحذف عنصر، ولا يوجد في الأسطر ما يدل على الجمل التكرارية (for/while)، أو استدعاء خوارزميات تحوي جمل تكرارية (for/while)، مما يعني أن التعقيد الزمني للخوارزمية هو O(1).

function الpop:

صورة توضيحية لما تقوم به خوارزمية الpop

يكمن الغرض من هذه الخوارزمية، هو حذف آخر عنصر في السلسلة، وللقيام بذلك لا أحتاج عدى خطوتين:

الخطوة الأولى: تحريك مؤشر/متغير الtail خطوة للوراء، حيث أصبح المؤشر tail يشير إلى العنصر قبل الأخير.

الخطوة الثانية: حذف العنصر الأخير (سابقا)، ليصبح العنصر الذي يشير إليه المؤشر tail حاليا، هو العنصر الأخير.

دعنا نرى خوارزمية الpop ببعض من التفصيل:

فلنفصل الأسطر كالآتي:

السطر (1): بالطبع في هذا السطر، تجد أني قد أعلنت عن خوارزمية الpop.

السطر (2): هنا نرصد الحالة الوحيدة، التي يمكن أن أحذف فيها عنصر: وهو أن لا تكون السلسلة فارغة.

السطر (3): في هذا السطر أعلنا عن متغير/مؤشر جديد سميناه lastNode؛ ليشير إلى نفس العنصر الذي يشير له المؤشر tail (والذي يشير بالطبع إلى آخر عنصر في السلسلة). أى: يمكن أن نقول: أن المؤشر lastNode يشير إلى آخر عنصر في السلسلة.

السطر (4): في هذا السطر أعلنت عن المتغير previousLastNodePosition، والذي يحوي قيمة ترتيب العنصر الذي يقع قبل العنصر الاخير، والذي يساوي: طول السلسلة - 1.

السطر (5): في هذا السطر أعلنت عن المتغير previousLastNode، والذي يحوي العنصر قبل الأخير، والذي حصلنا عليه من خلال استخدام خوارزمية الsearch، والتي ناقشناها فيما سبق.

السطر (6): في هذا السطر نغير قيمة الtail parameter، ليشير إلى العنصر الذي وجدناه في السطر(5)، وهو العنصر القبل الأخير.

السطر (7): في هذا السطر يغير مؤشر الtail قيمة خاصية الnext للعنصر القبل الاخير، ليجعلها تساوي null؛ فلم تعد تشير إلى العنصر الأخير بعد الآن.

السطر (8) و (9): لا تنسى أننا احتفظنا بالعنصر الاخير في المتغير/المؤشر lastNode، ونقوم الآن بحذف جميع القيم التي كان يشير إليها العنصر سابقا. وهكذا تقوم الJS تلقائيا بحذف العنصر من الذاكرة.

السطر (10): في هذا السطر نقلل من طول السلسلة ما مقداره واحد؛ لأننا حذفنا عنصرا للتو.

تلاحظ: أن خوارزمية الpop ينفذ فيها كل سطر لمرة واحده، إلا أنها استدعت خوارزمية الsearch، في أحد خطواتها، والتي يبلغ تعقيدها الزمني O(n)، لذا يمكن أن نقول: أن التعقيد الزمني لخوارزمية الpop أيضا هو O(n). في حال إن لم تفهم لما توصلنا لهذا التعقيد الزمني، راجع المقاطع الأخيرة من شرح خوارزمية الinsert في هذه المقالة.

 function الdelete:

أهدف من خلال هذه الخوارزمية: أن أقوم من خلالها، بحذف أي عنصر من العناصر باستخدام ترتيبه، فلو ادخلت القيمة 5 إلى الخوارزمية، فهذا يعني أنه: سيتوجب على الخوارزمية حذف العنصر الخامس في الترتيب في السلسلة.

لهذه الخوارزمية أربعة حالات، هى كالتالي في إيجاز:

• الحالة الأولى: أن تكون السلسلة فارغة.
• الحالة الثانية: أن تكون قيمة الترتيب المدخله تساوي 0، أو أقل.
• الحالة الثالثة: أن تكون قيمة الترتيب المدخلة تساوي طول السلسلة، أو ما يزيد.
• الحالة الرابعة: أن تكون قيمة الترتيب المدخلة أكبر من الصفر، وأقل من طول السلسلة.

أما الآن فلنناقش كل حالة، بشىء من التفصيل:

الحالة الأولى: أن تكون السلسلة فارغة.

في هذه الحالة أريد من الخوارزمية أن تعيد هذه الرسالة : "empty  singly linked list".

انظر إلى  الcode أدناه:

بالمختصر المفيد، تلاحظ أنه في السطر الأول رصدنا الحالة التي تكون عندها السلسلة فارغ، وفي الثاني أعدنا الرسالة.

الحالة الثانية: أن تكون قيمة الترتيب المدخله تساوي 0، أو أقل.

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

أنظر للcode أدناه:

الحالة الثالثة: أن تكون قيمة الترتيب المدخلة تساوي طول السلسلة، أو ما يزيد.

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

أنظر للcode أدناه:

الحالة الرابعة: أن تكون قيمة الترتيب المدخلة أكبر من الصفر، وأقل من طول السلسلة.

صورة توضيحية لما يفعله code الحالة الرابعه من خوارزمية الdelete

قد تبدو الصورة أعلاه معقدة بعض الشىء، إلا أن قراءتها مليا، ثم إتباعها بقراءة code الحالة الرابعة، ثم أخذت توائم بينهما، ستستوعب كلا منهما بشكل جيد.

كل ما أريد أن اقوم به في هذه الحالة، هو: أن أقوم بحذف العنصر الذي ستعطيني الخوارزمية قيمة ترتيبه، ولأقوم بذالك سأحتاج إلى اتباع الخطوات التالية:

1. تحديد العنصر المراد حذفه.
2. تحديد العنصر الذي يسبق العنصر المراد حذفه.
3. تحديد العنصر الذي يلي العنصر المراد حذفه.
4. جعل parameter الnext للعنصر المراد حذفه، يشير إلى العنصر الذي يلي العنصر المراد حذفه.
5. حذف العنصر المراد حذفه من السلسلة.
6. تقصير طول السلسلة بمقدار واحد.

أثبت مدى مثابرتك: استنتج عدد المرات التي ذكرت فيها كلمت "حذف أو حذفه" خلال ال6 نقاط السابقة، وشاركها في التعليقات".

انظر الcode أدناه، وحاول أن تحدد ما هى الخطوة التي ينفذها كل سطر، قبل أن تتطرق إلى الشرح أدنا الcode.

أرجو أنه كان من السهل عليك فهم الcode أعلاه، ليأكد فهمك الأسطر التالية:

السطر (1): هنا حددت العنصر الذي يسبق العنصر المراد حذفه، عن طريق إدخال قيمة ترتيب العنصر المراد حذفه منقوصا منه 1، كمدخل في خوارزمية الsearch التي أنشأناها من قبل. وسميته: previousNodeOfTargetNode

السطر (2): هنا حددت العنصر المراد حذفه، عن طريق إدخال قيمة ترتيب العنصر المراد حذفه، كمدخل في خوارزمية الsearch. وسميته: targetNode

السطر (3): هنا حددت العنصر الذي يلي(يتبع) العنصر المراد حذفه، عن طريق: إدخال قيمة ترتيب العنصر المراد حذفه مضافا إليه(+) 1، كمدخل في خوارزمية الsearch. وسميته: nextNodeOfTargetNode

السطر (4): في هذا السطر جعلت العنصر الذي يسبق العنصر المراد حذفه(previousNodeOfTargetNode) يشير إلى العنصر الذي يلي العنصر المراد حذفه(nextNodeOfTargetNode).

السطر (5) و (6): في هذان السطران حذفت كل الparamaters التي كان يحملها العنصر المراد حذفه(targetNode)، وبهذا يحذف العنصر تلقائيا (طبقا لكيفية عمل لغة الJS).

السطر (7): قمنا هنا كما هو متوقع، بتصغير حجم السلسلة بما مقداره واحد، باستخدام خوارزمية الreSize التي بنيناها سابقا.

صورة توضيحية لخوارزمية الdelete بجميع حالاتها.

تلاحظ: الحالة الرابعه، تسخدم خوارزمية الsearch، والتي يبلغ تعقيدها الزمني O(n)، وباقي أكوادها المكتوبة تعقيدها الزمني هو O(1)، وباقي الحالات أيضا تعقيدها الزمني هو O(1). فمن خلال ما سبق يمكن أن نقول: أن التعقيد الزمني لخوارزمية الdelete هو O(n)؛ وذلك لأن التعقيد الزمني يعبر عن أسوأ وقت قد تستنزفه الخوارزمية لتنفيذ مطلوب.

الخاتمة:

أين يمكن أن تجد الكود الذي كتبته بلغة الJavaScript:

تستطيع أن تصل إلى كل code كتبته في هذه المقالةK وأى مقالة لاحقة بإذن الله، في هذا الrepository الخاص بي على GitHub.

اللغة الإنجليزية:

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

الآن لديك فهم جيد حول ما هية الsingly linked list، جرب ان تقرأ شرحا أجنبيا موجزا.

الصعوبة الحقيقية:

لا يكمن التعقيدي الحقيقي للDataStructure في كيفية بنائها، إن التحدي الحقيقي هو أن تعرف كيف تستخدمها، وتتعامل معها، لذا هذه بعض الاسئلة التي يصنفها موقع leetCode على أنها سهله، لكن لا أنصحك بالإكتفاء بالمستوى السهل:

• Remove Linked List Elements
• Palindrome Linked List
• Reverse Linked List

انصحني:

أخبرني هل الفهم كان يسيرا، أم شعرت بالتعقيد؟

ما الذي أضافته لك المقالة؟

إن كنت خبيرا بكتابة المقالات التقنية واطلعت على مقالتي، ما التحسينات التي تقترحها على؟

أحب أن أستفيد من آرائكم.