هياكل البيانات مع JavaScript: قائمة مرتبطة بصورة منفردة وقائمة مرتبطة بمضاعفة
Arabic (العربية/عربي) translation by Muhammad Hakim Almadani (you can also view the original English article)
اثنين من الأكثر تدرس عادة هياكل البيانات في علوم الحاسوب هي قائمة مرتبطة بصورة منفردة وقائمة مرتبطة مزدوجة.
عندما علمت هذه هياكل البيانات، طلبت من زملائي للقياس وضع تصور لها. ما سمعت بالعديد من الأمثلة، مثل قائمة البقالة وقطار. هذه المقارنات، كما علمت في نهاية المطاف، لم تكن دقيقة. قائمة بقالة كان أكثر مماثلة قائمة انتظار؛ وكان قطار أكثر مماثلة إلى صفيف.
مع مرور مزيد من الوقت، اكتشفت في نهاية المطاف قياس التي وصفت بدقة قائمة مرتبطة بصورة منفردة وقائمة مرتبطة مزدوجة: مطاردة زبال. إذا كنت غريبة عن العلاقة بين مطاردة زبال وقائمة مرتبطة، ثم قراءة أدناه للإجابة!
قائمة مرتبطة بصورة منفردة
في علوم الكمبيوتر، وهي قائمة مرتبطة بصورة منفردة بنية بيانات يحتوي على تسلسل العقد المرتبطة. ويتضمن كل عقده، بدوره، البيانات، ومؤشر، التي يمكن أن تشير إلى عقده أخرى.
العقد قائمة مرتبطة بصورة منفردة مشابهة جداً للخطوات في عملية مطاردة زبال. كل خطوة تحتوي على رسالة (مثل "كنت قد وصلت إلى فرنسا")، والمؤشرات التالية في الخطوة (مثل "زيارة هذه إحداثيات الطول والعرض"). عندما نبدأ في ترتيب تسلسل الخطوات الفردية لتشكيل سلسلة من الخطوات، نقوم بإنشاء عملية مطاردة زبال.
الآن أن لدينا نموذج مفاهيمي لقائمة مرتبطة بصورة منفردة، دعنا نستكشف عمليات قائمة مرتبطة بصورة منفردة.
عمليات قائمة مرتبطة بصورة منفردة
حيث يحتوي قائمة مرتبطة بصورة منفردة على العقد، والتي يمكن أن تكون دالة إنشائية منفصلة من قائمة مرتبطة بصورة منفردة، أننا مخطط عمليات كلا الصانعين: Node
و SinglyList
.
Node
-
data
يقوم بتخزين قيمة. -
next
التالية إلى العقدة التالية في القائمة.
SinglyList
-
_length
استرداد عدد العقد في قائمة. -
head
رئيس عقده رئيسا لقائمة. -
(add(value
إضافة عقده إلى قائمة. -
(searchNodeAt(position
للبحث عن عقده في الموضع n في قائمتنا. -
(remove(position
إزالة عقده من قائمة.
تنفيذ قائمة مرتبطة بصورة منفردة
لدينا التنفيذ، سوف نحدد أولاً منشئ Node
المسماة، ومن ثم على منشئ المسمى SinglyList
.
لكل مثيل من Node
تحتاج القدرة على تخزين البيانات، والقدرة على الإشارة إلى عقده أخرى. لإضافة هذه الوظيفة، فإننا سنضع خاصيتين: data
و next
، على التوالي.
function Node(data) { this.data = data; this.next = null; }
وبعد ذلك، نحن بحاجة إلى تعريف SinglyList
:
function SinglyList() { this._length = 0; this.head = null; }
وسيكون لكل مثيل من SinglyList
اثنين من الخصائص: _length
وhead
. السابقة يتم تعيين عدد العقد في قائمة؛ النقاط الأخيرة على الرأس قائمة – العقدة في الجزء الأمامي القائمة. نظرا لان كل مثيل جديد من singlylist
لا يحتوي علي عقده ، القيمة الافتراضية head
و null
والقيمة الافتراضية من _lateris
و 0
.
أساليب قائمة مرتبطة بصورة منفردة
ونحن بحاجة لتحديد الطرق التي يمكن إضافتها، البحث، وإزالة عقده من قائمة. دعنا نبدأ بإضافة عقده.
1 3: (add(value
رهيبة، دعونا الآن تنفيذ وظيفة لإضافة العقد إلى قائمة.
SinglyList.prototype.add = function(value) { var node = new Node(value), currentNode = this.head; // 1st use-case: an empty list if (!currentNode) { this.head = node; this._length++; return node; } // 2nd use-case: a non-empty list while (currentNode.next) { currentNode = currentNode.next; } currentNode.next = node; this._length++; return node; };
إضافة عقده إلى قائمتنا تتضمن العديد من الخطوات. فلنبدأ من بداية طريقة لدينا. نحن نستخدم حجة (add(value
لإنشاء مثيل جديد من Node
، الذي يتم تعيينه إلى متغير اسم Node
. ونحن أيضا تعريف متغير اسمه currentNode
وتهيئته إلى _head
القائمة. إذا كان هناك لا العقد في القائمة، ثم قيمة head
و null
.
وبعد هذه النقطة في التعليمات البرمجية الخاصة بنا، علينا التعامل مع اثنين من حالات الاستخدام.
وتعتبر أول حالة استخدام إضافة عقده إلى قائمة فارغة. إذا لم أشر head
لعقدة، ثم تعيين node
رئيسا لقائمة لدينا وزيادة طول لدينا قائمة بواسطة أحد، وإرجاع node
.
وتعتبر حالة الاستخدام الثاني إضافة عقده إلى قائمة غير فارغة. نحن ندخل أثناء
الحلقة، وخلال كل تكرار، نقوم بتقييم إذا كان currentNode.next
يشير إلى عقده أخرى. (أثناء التكرار الأول، currentNode
دائماً يشير إلى رأس قائمة.)
إذا كان الجواب لا، نحن تعيين node
إلى عقده currentNode.next
وnode
.
إذا كان الجواب نعم، نحن ندخل جسم أثناء
الحلقة. داخل الجسم، وعلينا إعادة تعيين currentNode
إلى currentNode.next
. وتتكرر هذه العملية حتى currentNode.next
لم يعد يشير إلى عقده أخرى. وبعبارة أخرى، currentNode
يشير إلى آخر عقده قائمتنا.
أثناء
حلقة فواصل. أخيرا، نحن تعيين node
إلى currentNode.next
ونحن زيادة _length
بأحد، وثم نعود node
.
2 3: (searchNodeAt(position
ونحن الآن إضافة العقد إلى القائمة، ولكن نحن لا يمكن البحث عن العقد في مواقع محددة في قائمتنا. دعونا إضافة هذه الوظيفة وإنشاء أسلوب يدعى (searchNodeAt(position
، الذي يقبل وسيطة اسم position
. الوسيطة من المتوقع أن يكون عدد صحيح يشير إلى عقده في الموضع n في قائمتنا.
SinglyList.prototype.searchNodeAt = function(position) { var currentNode = this.head, length = this._length, count = 1, message = {failure: 'Failure: non-existent node in this list.'}; // 1st use-case: an invalid position if (length === 0 || position < 1 || position > length) { throw new Error(message.failure); } // 2nd use-case: a valid position while (count < position) { currentNode = currentNode.next; count++; } return currentNode; };
if
كان البيان بالتحقق من حالة الاستخدام الأول: موقفا غير صحيح يتم تمريرها كوسيطة.
إذا كان الفهرس الذي تم تمريره إلى (searchNodeAt(position
صالحاً، ثم نصل إلى حالة الاستخدام الثاني – حلقةwhile
. خلال while
تكرار لبعض الوقت حلقة، cuurentNode
– الأول الذي يشير إلى head
— تتم إعادة تعيين إلى العقدة التالية في القائمة. وتواصل هذا التكرار حتى يساوي عدد من الموقف.
عندما يكسر الحلقة أخيرا، يتم إرجاع currentNode
.
3 3: (remove(position
الأسلوب النهائي سوف ننشئ يدعى(remove(position
.
SinglyList.prototype.remove = function(position) { var currentNode = this.head, length = this._length, count = 0, message = {failure: 'Failure: non-existent node in this list.'}, beforeNodeToDelete = null, nodeToDelete = null, deletedNode = null; // 1st use-case: an invalid position if (position < 0 || position > length) { throw new Error(message.failure); } // 2nd use-case: the first node is removed if (position === 1) { this.head = currentNode.next; deletedNode = currentNode; currentNode = null; this._length--; return deletedNode; } // 3rd use-case: any other node is removed while (count < position) { beforeNodeToDelete = currentNode; nodeToDelete = currentNode.next; count++; } beforeNodeToDelete.next = nodeToDelete.next; deletedNode = nodeToDelete; nodeToDelete = null; this._length--; return deletedNode; };
تنفيذ(remove(position
ينطوي على ثلاث حالات الاستخدام:
- موقفا غير صحيح يتم تمريرها كوسيطة.
- موقف واحد (
head
ئمة) يتم تمريرها كوسيطة. - وظيفة موجودة (لا الموضع الأول) يتم تمريرها كوسيطة.
حالات الاستخدام الأولى والثانية هي أبسط التعامل معها. بالنسبة للسيناريو الأول، إذا كانت القائمة فارغة أو يتم تمرير موقفا غير موجود، يتم طرح خطأ.
حالة الاستخدام الثاني يعالج إزالة العقدة الأولى في القائمة، وأيضا head
إذا كان هذا هو الحال، ثم يحدث المنطق التالي:
- يتم إعادة تعيين
رئيس
لcurrentNode.next
. - ويشير
deletedNode
إلىcurrentNode
. - يتم إعادة تعيين
currentNode
إلى قيمةnull
. - تنقيص
length_
لدينا قائمة من جانب واحد. - يتم إرجاع
deletedNode
.
السيناريو الثالث هو أصعب للفهم. التعقد تنبع من ضرورة تتبع عقدتين خلال while
تكرار لبعض الوقت ومن التكرار الحلقي. خلال كل تكرار لحلقة لدينا، نحن تتبع العقدة قبل العقدة المراد حذفها والعقدة المراد حذفها. عندما يصل لدينا حلقة في نهاية المطاف إلى العقدة في الموقف الذي نريد إزالة، إنهاء الحلقة.
عند هذه النقطة، نحن نحمل الإشارات إلى العقد ثلاثة: beforeNodeToDelete
، nodeToDelete
، وdeleteNode
. قبل حذف nodeToDelete
، ونحن يجب تعيين Next
الخاصة به من جانب قيمة beforeNodeToDelete
المقبل. إذا كان الغرض من هذه الخطوة يبدو غير واضح، تذكير نفسك أن لدينا قائمة عقد المرتبطة؛ مجرد إزالة عقده فواصل الارتباط من العقدة الأولى من القائمة للعقدة الأخيرة من القائمة.
المقبل، ونحن deletedNode
إلى nodeToDelete
. ثم أننا بتعيين قيمة nodeToDelete
إلى null
وإنقاص طول القائمة من واحدة والعودة deletedNode
.
إتمام التنفيذ في قائمة مرتبطة بصورة منفردة
هنا التنفيذ الكامل لقائمتنا:
function Node(data) { this.data = data; this.next = null; } function SinglyList() { this._length = 0; this.head = null; } SinglyList.prototype.add = function(value) { var node = new Node(value), currentNode = this.head; // 1st use-case: an empty list if (!currentNode) { this.head = node; this._length++; return node; } // 2nd use-case: a non-empty list while (currentNode.next) { currentNode = currentNode.next; } currentNode.next = node; this._length++; return node; }; SinglyList.prototype.searchNodeAt = function(position) { var currentNode = this.head, length = this._length, count = 1, message = {failure: 'Failure: non-existent node in this list.'}; // 1st use-case: an invalid position if (length === 0 || position < 1 || position > length) { throw new Error(message.failure); } // 2nd use-case: a valid position while (count < position) { currentNode = currentNode.next; count++; } return currentNode; }; SinglyList.prototype.remove = function(position) { var currentNode = this.head, length = this._length, count = 0, message = {failure: 'Failure: non-existent node in this list.'}, beforeNodeToDelete = null, nodeToDelete = null, deletedNode = null; // 1st use-case: an invalid position if (position < 0 || position > length) { throw new Error(message.failure); } // 2nd use-case: the first node is removed if (position === 1) { this.head = currentNode.next; deletedNode = currentNode; currentNode = null; this._length--; return deletedNode; } // 3rd use-case: any other node is removed while (count < position) { beforeNodeToDelete = currentNode; nodeToDelete = currentNode.next; count++; } beforeNodeToDelete.next = nodeToDelete.next; deletedNode = nodeToDelete; nodeToDelete = null; this._length--; return deletedNode; };
من إحداها إلى مضاعفة
رهيبة، تنفيذنا لقائمة مرتبطة بصورة منفردة يتم إكمال. ونحن الآن استخدام بنية بيانات أن يضيف ويزيل، ويبحث عن العقد في قائمة التي تشغل مساحة غير متجاورة في الذاكرة.
ومع ذلك، في هذه اللحظة، جميع عملياتنا تبدأ من بداية قائمة وتشغيل إلى نهاية قائمة. وبعبارة أخرى، فأحادية الاتجاه.
قد تكون هناك حالات حيث أننا نريد عملياتنا لتكون ثنائية الاتجاه. إذا تعتبر هذه حالة الاستخدام، ثم يمكنك فقط وصف قائمة مرتبطة مزدوجة.
قائمة مرتبطة مزدوجة
قائمة مرتبطة بمضاعفة يأخذ جميع وظائف قائمة مرتبطة بصورة منفردة، ويمتد ذلك لحركة ثنائية الاتجاه في قائمة. ونحن يمكن أن تعبر، وبعبارة أخرى، قائمة مرتبطة من العقدة الأولى في القائمة للعقدة الأخيرة في القائمة؛ ونحن يمكن أن اجتياز من العقدة الأخيرة في القائمة للعقدة الأولى في القائمة.
في هذا القسم، سوف نحافظ على تركيزنا أساسا على الفروق بين قائمة مرتبطة مزدوجة وقائمة مرتبطة بصورة منفردة.
عمليات قائمة مرتبطة مزدوجة
وستشمل قائمتنا منشئات اثنين: Node
وDoublyList
. واسمحوا لنا مخطط عملياتهم.
Node
-
data
يقوم بتخزين قيمة. - النقاط
Next
إلى العقدة التالية في القائمة. - النقاط
previous
إلى العقدة السابقة في القائمة.
DoublyList
-
length_
استرداد عدد العقد في قائمة. - يعين
head
عقده رئيسا لقائمة. - يعين
tail
عقده كذيل قائمة. -
(add(value
إضافة عقده إلى قائمة. -
(searchNodeAt(position
للبحث عن عقده في الموضع n في قائمتنا. -
(remove(position
إزالة عقده من قائمة.
تنفيذ قائمة مرتبطة مزدوجة
السماح بكتابة بعض التعليمات البرمجية!
للتنفيذ، ولدينا نحن سوف إنشاء منشئ Node
المسماة:
function Node(value) { this.data = value; this.previous = null; this.next = null; }
لإنشاء حركة ثنائية قائمة مرتبطة مزدوجة، نحن بحاجة إلى خصائص هذه النقطة في كلا الاتجاهين من قائمة. وقد سميت هذه الخصائص previous
و next
.
وبعد ذلك، نحن بحاجة إلى تنفيذ DoublyList
وإضافة خصائص ثلاثة:length_
، head
و tail
. على عكس قائمة مرتبطة بصفة فردية، قد قائمة مرتبطة بمضاعفة إشارة إلى قائمة كلا بداية ونهاية قائمة. حيث يتم إنشاء مثيل لكل مثيل من DoublyList
دون العقد، يتم تعيين القيم الافتراضية head
وtail
إلى null
.
function DoublyList() { this._length = 0; this.head = null; this.tail = null; }
أساليب قائمة مرتبطة مزدوجة
ونحن الآن سوف تستكشف الطرق التالية: (add(value
، و (remove(position
، و (searchNodeAt(position
. واستخدمت كل هذه الأساليب للحصول على قائمة مرتبطة بصورة منفردة؛ ومع ذلك، يجب إعادة كتابة لحركة ثنائية الاتجاه.
1 3: (add(value
DoublyList.prototype.add = function(value) { var node = new Node(value); if (this._length) { this.tail.next = node; node.previous = this.tail; this.tail = node; } else { this.head = node; this.tail = node; } this._length++; return node; };
في هذا الأسلوب، لدينا اثنين من السيناريوهات. أولاً، إذا كانت قائمة فارغة، ثم تعيين head
و tail
العقدة يتم إضافتها. وثانيا، إذا كانت القائمة تحتوي على العقد، ثم العثور على ذيل القائمة وتعيين tail.next
العقدة التي تضاف؛ وبالمثل، نحن بحاجة إلى تكوين الذيل الجديد لحركة ثنائية الاتجاه. نحن بحاجة إلى تعيين، وبعبارة أخرى، tail.previous
بذيل الأصلي.
2 3: (searchNodeAt(position
تنفيذ (searchNodeAt(position
غير متطابقة إلى قائمة مرتبطة بصورة منفردة. إذا كنت قد نسيت كيفية تنفيذ ذلك، لقد تضمنت ذلك أدناه:
DoublyList.prototype.searchNodeAt = function(position) { var currentNode = this.head, length = this._length, count = 1, message = {failure: 'Failure: non-existent node in this list.'}; // 1st use-case: an invalid position if (length === 0 || position < 1 || position > length) { throw new Error(message.failure); } // 2nd use-case: a valid position while (count < position) { currentNode = currentNode.next; count++; } return currentNode; };
3 3: (remove(position
وسيكون هذا الأسلوب الأكثر تحديا لفهم. سأكون عرض التعليمات البرمجية وثم شرح ذلك.
DoublyList.prototype.remove = function(position) { var currentNode = this.head, length = this._length, count = 1, message = {failure: 'Failure: non-existent node in this list.'}, beforeNodeToDelete = null, nodeToDelete = null, deletedNode = null; // 1st use-case: an invalid position if (length === 0 || position < 1 || position > length) { throw new Error(message.failure); } // 2nd use-case: the first node is removed if (position === 1) { this.head = currentNode.next; // 2nd use-case: there is a second node if (!this.head) { this.head.previous = null; // 2nd use-case: there is no second node } else { this.tail = null; } // 3rd use-case: the last node is removed } else if (position === this._length) { this.tail = this.tail.previous; this.tail.next = null; // 4th use-case: a middle node is removed } else { while (count < position) { currentNode = currentNode.next; count++; } beforeNodeToDelete = currentNode.previous; nodeToDelete = currentNode; afterNodeToDelete = currentNode.next; beforeNodeToDelete.next = afterNodeToDelete; afterNodeToDelete.previous = beforeNodeToDelete; deletedNode = nodeToDelete; nodeToDelete = null; } this._length--; return message.success; };
(remove(position
يتعامل مع أربع حالات الاستخدام:
- الموقف الذي يتم تمريرها كوسيطة
(remove(position
غير موجودة. وفي هذه الحالة، يمكننا طرح خطأ. - ويتمثل موقف يتم تمريرها كوسيطة
(remove(position
العقدة الأولى (head
) من قائمة. إذا كان هذا هو الحال، ونحن سوف تعيينdeletedNode
إلىhead
وثم تعيينhead
للعقدة التالية في القائمة. في هذه اللحظة، يجب أن نرى إذا كان لدينا القائمة على عقده واحدة أو أكثر. إذا كان الجواب لا، سيتم تعيينhead
لnull
وسوف ندخلif
كان جزء من بيانناif-else
. في الجسمif
، أننا يجب أيضا تعيينtail
إلىnull
– وبعبارة أخرى، علينا أن نعود إلى الحالة الأصلية لقائمة مرتبطة مزدوجة فارغة. إذا نحن بإزالة العقدة الأولى في قائمة ولدينا عقده واحدة أو أكثر في قائمة لدينا، نحن ندخل قسمelse
من بيانناif-else
. في هذه الحالة، أننا يجب أن بشكل صحيح تعيين الخاصيةprevious
منhead
إلىnull
– هناك لا عقد قبل رأس قائمة. - ويتمثل موقف يتم تمريرها كوسيطة
(remove(position
ذيل قائمة. أولاً، يتم تعيينdeletedNode
إلىtail
. ثانيا، يتم إعادة تعيينtail
إلى العقدة السابقة إلى الذيل. ثالثا، لديه أية عقده بعد ذلك ذيل جديد ويحتاج قيمتهnext
لتعيين إلىnull
. - ويحدث الكثير هنا، ولذلك سوف أركز على منطق أكثر من كل سطر من التعليمات البرمجية. علينا كسر لدينا من الوقت
while
مرة واحدةcurrentNode
يشير إلى العقدة في الموقف الذي يتم تمريرها كوسيطة إلى(remove(position
. في هذه اللحظة، يمكننا إعادة تعيين قيمةbeforeNodeToDelete.next
إلى العقدة بعدnodeToDelete
، وعلى العكس من ذلك، علينا إعادة تعيين قيمةafterNodeToDelete.previous
إلى العقدة قبلnodeToDelete
. وبعبارة أخرى، نحن إزالة مؤشرات إلى العقدة تمت إزالته وإعادة تعيين لهم إلى العقد الصحيح. المقبل، ونحن تعيينdeletedNode
إلىnodeToDelete
. أخيرا، نحن تعيينnodeToDelete
إلى قيمةnull
.
وأخيراً، نحن إنقاص طول القائمة والعودة deletedNode
.
إتمام التنفيذ في قائمة مرتبطة بمضاعفة
هنا يتم تنفيذ كامل:
function Node(value) { this.data = value; this.previous = null; this.next = null; } function DoublyList() { this._length = 0; this.head = null; this.tail = null; } DoublyList.prototype.add = function(value) { var node = new Node(value); if (this._length) { this.tail.next = node; node.previous = this.tail; this.tail = node; } else { this.head = node; this.tail = node; } this._length++; return node; }; DoublyList.prototype.searchNodeAt = function(position) { var currentNode = this.head, length = this._length, count = 1, message = {failure: 'Failure: non-existent node in this list.'}; // 1st use-case: an invalid position if (length === 0 || position < 1 || position > length) { throw new Error(message.failure); } // 2nd use-case: a valid position while (count < position) { currentNode = currentNode.next; count++; } return currentNode; }; DoublyList.prototype.remove = function(position) { var currentNode = this.head, length = this._length, count = 1, message = {failure: 'Failure: non-existent node in this list.'}, beforeNodeToDelete = null, nodeToDelete = null, deletedNode = null; // 1st use-case: an invalid position if (length === 0 || position < 1 || position > length) { throw new Error(message.failure); } // 2nd use-case: the first node is removed if (position === 1) { this.head = currentNode.next; // 2nd use-case: there is a second node if (!this.head) { this.head.previous = null; // 2nd use-case: there is no second node } else { this.tail = null; } // 3rd use-case: the last node is removed } else if (position === this._length) { this.tail = this.tail.previous; this.tail.next = null; // 4th use-case: a middle node is removed } else { while (count < position) { currentNode = currentNode.next; count++; } beforeNodeToDelete = currentNode.previous; nodeToDelete = currentNode; afterNodeToDelete = currentNode.next; beforeNodeToDelete.next = afterNodeToDelete; afterNodeToDelete.previous = beforeNodeToDelete; deletedNode = nodeToDelete; nodeToDelete = null; } this._length--; return message.success; };
الاستنتاج
لقد غطينا كثير من المعلومات في هذه المقالة. إذا كان أي من ذلك يبدو مربكاً، قراءته مرة أخرى، والتجربة مع التعليمات البرمجية. عند فإنه في نهاية المطاف يجعل الشعور لك، أشعر بالفخر. يمكنك فقط كشفت أسرار قائمة مرتبطة بصورة منفردة وقائمة مرتبطة مزدوجة. يمكنك إضافة هذه هياكل البيانات لحزام الأداة الترميز الخاصة بك!