هياكل البيانات مع JavaScript: قائمة مرتبطة بصورة منفردة وقائمة مرتبطة بمضاعفة

اثنين من الأكثر تدرس عادة هياكل البيانات في علوم الحاسوب هي قائمة مرتبطة بصورة منفردة وقائمة مرتبطة مزدوجة.

عندما علمت هذه هياكل البيانات، طلبت من زملائي للقياس وضع تصور لها. ما سمعت بالعديد من الأمثلة، مثل قائمة البقالة وقطار. هذه المقارنات، كما علمت في نهاية المطاف، لم تكن دقيقة. قائمة بقالة كان أكثر مماثلة قائمة انتظار؛ وكان قطار أكثر مماثلة إلى صفيف.

مع مرور مزيد من الوقت، اكتشفت في نهاية المطاف قياس التي وصفت بدقة قائمة مرتبطة بصورة منفردة وقائمة مرتبطة مزدوجة: مطاردة زبال. إذا كنت غريبة عن العلاقة بين مطاردة زبال وقائمة مرتبطة، ثم قراءة أدناه للإجابة!

قائمة مرتبطة بصورة منفردة

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

العقد قائمة مرتبطة بصورة منفردة مشابهة جداً للخطوات في عملية مطاردة زبال. كل خطوة تحتوي على رسالة (مثل "كنت قد وصلت إلى فرنسا")، والمؤشرات التالية في الخطوة (مثل "زيارة هذه إحداثيات الطول والعرض"). عندما نبدأ في ترتيب تسلسل الخطوات الفردية لتشكيل سلسلة من الخطوات، نقوم بإنشاء عملية مطاردة زبال.

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

عمليات قائمة مرتبطة بصورة منفردة

حيث يحتوي قائمة مرتبطة بصورة منفردة على العقد، والتي يمكن أن تكون دالة إنشائية منفصلة من قائمة مرتبطة بصورة منفردة، أننا مخطط عمليات كلا الصانعين: 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 ينطوي على ثلاث حالات الاستخدام:

1. موقفا غير صحيح يتم تمريرها كوسيطة.
2. موقف واحد (headئمة) يتم تمريرها كوسيطة.
3. وظيفة موجودة (لا الموضع الأول) يتم تمريرها كوسيطة.

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

حالة الاستخدام الثاني يعالج إزالة العقدة الأولى في القائمة، وأيضا head إذا كان هذا هو الحال، ثم يحدث المنطق التالي:

1. يتم إعادة تعيين رئيس ل currentNode.next.
2. ويشير deletedNode إلى currentNode.
3. يتم إعادة تعيين currentNode إلى قيمة null.
4. تنقيص length_ لدينا قائمة من جانب واحد.
5. يتم إرجاع 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 يتعامل مع أربع حالات الاستخدام:

1. الموقف الذي يتم تمريرها كوسيطة (remove(position غير موجودة. وفي هذه الحالة، يمكننا طرح خطأ.
2. ويتمثل موقف يتم تمريرها كوسيطة (remove(position العقدة الأولى (head) من قائمة. إذا كان هذا هو الحال، ونحن سوف تعيين deletedNode إلى head وثم تعيين head للعقدة التالية في القائمة. في هذه اللحظة، يجب أن نرى إذا كان لدينا القائمة على عقده واحدة أو أكثر. إذا كان الجواب لا، سيتم تعيين head ل null وسوف ندخل if كان جزء من بياننا if-else. في الجسم if، أننا يجب أيضا تعيين tail إلى null – وبعبارة أخرى، علينا أن نعود إلى الحالة الأصلية لقائمة مرتبطة مزدوجة فارغة. إذا نحن بإزالة العقدة الأولى في قائمة ولدينا عقده واحدة أو أكثر في قائمة لدينا، نحن ندخل قسم else من بياننا if-else. في هذه الحالة، أننا يجب أن بشكل صحيح تعيين الخاصية previous من head إلى null – هناك لا عقد قبل رأس قائمة.
3. ويتمثل موقف يتم تمريرها كوسيطة (remove(position ذيل قائمة. أولاً، يتم تعيين deletedNode إلى tail. ثانيا، يتم إعادة تعيين tail إلى العقدة السابقة إلى الذيل. ثالثا، لديه أية عقده بعد ذلك ذيل جديد ويحتاج قيمته next لتعيين إلى null.
4. ويحدث الكثير هنا، ولذلك سوف أركز على منطق أكثر من كل سطر من التعليمات البرمجية. علينا كسر لدينا من الوقت 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;
};

الاستنتاج

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