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

هل سبق لك أن قمت ببناء آلة روب غولدبرغ؟ إذا لم يكن الأمر كذلك ، فربما تكون قد قمت ببناء خط متطور من الدومينو؟

حسنًا ، ربما لم تكن طفلاً كما كنت. ليكن. بالنسبة لأولئك منكم الذين سعدوا بتنفيذ أي مما سبق ، فقد أدركت بالفعل جوهر بنية البيانات الحالية: القوائم المرتبطة!

كيف تعمل القوائم المرتبطة

أبسط شكل من أشكال القوائم المرتبطة - قائمة مرتبطة بشكل فردي - هو سلسلة من العقد حيث تحتوي كل عقدة فردية على قيمة ومؤشر للعقدة التالية في القائمة.

الإضافات ( إضافة ) تزيد القائمة عن طريق إضافة عناصر إلى نهاية القائمة.

ستتم إزالة عمليات الإزالة ( إزالة) دائمًا من موضع معين في القائمة.

البحث ( يحتوي على ) سيبحث في القائمة عن قيمة.

أمثلة على حالات الاستخدام:

  • تخزين القيم في جدول التجزئة لمنع الاصطدامات (المزيد حول هذا في عدد قليل من المشاركات)
  • إعادة صنع السباق المذهل!

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

أثناء استعراضك لهذا الأمر ، أريدك أن تسأل نفسك: "كيف تختلف القوائم المرتبطة عن المصفوفات؟ كيف يتشابهون؟"

هيا بنا نبدأ.

أولاً ، تحتاج إلى إنشاء تمثيل لقائمتنا المرتبطة:

class LinkedList{ constructor(){ this._head = null; this._tail = null; this._length = 0; }
 size(){ return this._length; }}

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

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

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

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

نظرًا لأنك ستنشئ عقدة جديدة في كل مرة تضيف فيها إلى القائمة ، فإنك تقرر إنشاء مُنشئ يسهل إنشاء عقدة جديدة لكل قيمة تُضاف إلى قائمتك.

class Node{ constructor(value){ this.value = value; this.next = null; }}

يتيح لك توفر هذا المُنشئ إنشاء طريقة الإضافة الخاصة بك.

class Node { constructor(value) { this.value = value; this.next = null; }}
class LinkedList { constructor() { this._head = null; this._tail = null; this._length = 0; } add(value) { let node = new Node(value); //we create our node if(!this._head && !this._tail){ //If it's the first node this._head = node; //1st node is head & tail this._tail = node; }else{ this._tail.next = node; //add node to the back this._tail = this._tail.next; //reset tail to last node } this._length++; } size() { return this._length; }}
const AmazingRace = new LinkedList();AmazingRace.add("Colombo, Sri Lanka");AmazingRace.add("Lagos, Nigeria");AmazingRace.add("Surat, India");AmazingRace.add("Suzhou, China");

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

{ _head: { value: 'Colombo, Sri Lanka', next: { value: 'Lagos, Nigeria', next: { value: 'Surat, India', next: { value: 'Suzhou, China', next: null } } } }, _tail: { value: 'Suzhou, China', next: null }, _length: 4 }

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

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

بالطبع يمكنه فقط تشغيل console.log (AmazingRace) وقراءة ما تنتجه وحدة التحكم. لكن كينت هو مبرمج كسول ويحتاج إلى طريقة للتحقق من وجود شيء ما حتى يتمكن من منع التكرارات. مع وضع ذلك في الاعتبار ، يمكنك إنشاء طريقة تحتوي على للتحقق من القيم الموجودة.

class Node { constructor(value) { this.value = value; this.next = null; }}class LinkedList { constructor() { this._head = null; this._tail = null; this._length = 0; } add(value) { let node = new Node(value); if(!this._head && !this._tail){ this._head = node; this._tail = this._head; }else{ this._tail.next = node; this._tail = this._tail.next; } this._length++; } contains(value){ let node = this._head; while(node){ if(node.value === value){ return true; } node = node.next; } return false; } size() { return this._length; } }
const AmazingRace = new LinkedList();AmazingRace.add("Colombo, Sri Lanka");AmazingRace.add("Lagos, Nigeria");AmazingRace.add("Surat, India");AmazingRace.add("Suzhou, China");
//Kent's check
AmazingRace.contains('Suzhou, China'); //trueAmazingRace.contains('Hanoi, Vietnam'); //falseAmazingRace.add('Hanoi, Vietnam');AmazingRace.contains('Seattle, Washington'); //falseAmazingRace.add('Seattle, Washington');AmazingRace.contains('North Pole'); // falseAmazingRace.add('North Pole');

رائع ، لدى كينت الآن طريقة للتحقق من القيم قبل إضافتها لتجنب التكرارات.

جانبا ، قد تتساءل لماذا لم تستخدم فقط التابع يحتوي على طريقة الإضافة لمنع الإضافات المكررة؟ عندما تقوم بتنفيذ قائمة مرتبطة - أو أي بنية بيانات ، لهذا الأمر - يمكنك نظريًا إضافة أي وظيفة إضافية تريدها.

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

Array.prototype.push = () => { return 'cat';}
let arr = [];arr.push('eggs'); // returns 'cat';

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

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

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

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

class Node { constructor(value) { this.value = value; this.next = null; }}class LinkedList { constructor() { this._head = null; this._tail = null; this._length = 0; } add(value) { let node = new Node(value); if(!this._head && !this._tail){ this._head = node; this._tail = this._head; }else{ this._tail.next = node; this._tail = this._tail.next; } this._length++; } remove(value) { if(this.contains(value)){ // see if our value exists let current = this._head; // begin at start of list let previous = this._head; while(current){ // check each node if(current.value === value){ if(this._head === current){ // if it's the head this._head = this._head.next; // reset the head this._length--; // update the length return; // break out of the loop } if(this._tail === current){ // if it's the tail node this._tail = previous; // make sure to reset it } previous.next = current.next; // unlink (see img below) this._length--; // update the length return; // break out of } previous = current; // look at the next node current = current.next; // ^^ } } } contains(value){ let node = this._head; while(node){ if(node.value === value){ return true; } node = node.next; } return false; } size() { return this._length; } }
const AmazingRace = new LinkedList();AmazingRace.add("Colombo, Sri Lanka");AmazingRace.add("Lagos, Nigeria");AmazingRace.add("Surat, India");AmazingRace.add("Suzhou, China");AmazingRace.add('Hanoi, Vietnam');AmazingRace.add('Seattle, Washington');AmazingRace.add('North Pole');
//Kent's check
AmazingRace.remove('North Pole');

There’s a lot of code in that remove function up there. Essentially it boils down to the following:

  1. if the value exists in the list…
  2. iterate over the linked list, keeping track of the previous and current node
  3. then, if there’s a match →

4A . if it’s the head

  • reset the head to the next node in the list
  • update the length
  • break out of the loop

4B. if it’s the tail

  • reset the tail to the previous node in the list
  • unlink the node by resetting the pointers as seen below

4C. If it’s not a match → continue iterating

  • make the next node current
  • make the current node previous

One last thing to note: you may have realized that you didn’t actually delete the node. You just removed the references to it. Well, that’s OK because once all references to an object are removed, the garbage collector helps us remove it from memory. You can read up on the garbage collection here.

With the remove method now implemented, you can run this little piece of code below to make sure contestants don’t freeze to death, or accidentally bother Santa as he’s prepping for this year’s festivities.

AmazingRace.remove('North Pole');

You’ve done it! You’ve created a simple implementation of a linked list. And you can grow the list by adding items, and shrink it by removing items — all based on the item’s value.

See if you can add you can expand the linked list to allow you to insert values at the beginning, end, or any point in between.

You have all you need to implement those methods. The names and arguments for these methods should look a little like this:

addHead(value) {
}
insertAfter(target, value){
}

Feel free to share your implementations in the comments below ?

A time complexity analysis on the queue methods

Here’s the code again:

class LinkedList { constructor() { this._head = null; this._tail = null; this._length = 0; } add(value) { let node = new Node(value); if(!this._head && !this._tail){ this._head = node; this._tail = this._head; }else{ this._tail.next = node; this._tail = this._tail.next; } this._length++; } remove(value) { if(this.contains(value)){ let current = this._head; let previous = this._head; while(current){ if(current.value === value){ if(this._head === current){ this._head = this._head.next; this._length--; return; } if(this._tail === current){ this._tail = previous; } previous.next = current.next; this._length--; return; } previous = current; current = current.next; } } } contains(value){ let node = this._head; while(node){ if(node.value === value){ return true; } node = node.next; } return false; } size() { return this._length; }
// To Be Implemented
addHead(value) {
}
insertAfter(target, value){
}

Add is O(1): Since you always know the last item in the list thanks to tail property, you don’t have to iterate over the list.

Remove is O(n): In the worst case scenario you’re going to have to iterate over the entire list to find the value to be removed. Great part though is the actual removal of the node is O(1) because you’re just resetting pointers.

Contains is O(n): You have to iterate over the entire list to check if the value exists in your list.

addHead is O(1): Similar to our add method above, we always know the position of the head, so no iteration necessary.

insertAfter is O(n): Similar to our Remove method above, you’ll have to iterate over the entire list to find the target node that your value should be inserted after. Likewise, the actual insertion is O(1) because you’re just resetting pointers.

Linked List vs Array?

Why would you use a linked list instead of an arrays? Arrays technically allow you to do all of the things linked lists do, such as additions, insertions, and removals. Also, all these methods are already readily available to us in JavaScript.

Well, the biggest difference comes in the insertions and removals. Since arrays are indexed, when you perform an insertion or removal in the middle of the array, you have to reset the position of all following values to their new indices.

Imagine inserting into the start or middle of an array 100,000 values long! Insertions and removals like this are extremely expensive. Because of this, linked lists are often preferred for large data sets that are often shifted around.

On the other hand, arrays are great when it comes to finding items (random access) since they are indexed. If you know the position of an item, you can access it in O(1) time via array[position].

Linked lists always require you to iterate over the linked lists sequentially. Given this, arrays are usually preferred for either smaller data sets, or data sets that aren’t shifted around as often.

Time for a quick recap

Linked Lists:

  1. have a tail and head property to track the ends of the list
  2. have an add, addHead, insertAfter, and remove method to manage the contents of your list
  3. have a length property to track how long your linked list is

Further Reading

There are also the doubly-linked list and circular-linked list data structures. You can read about them on Wikipedia.

Also, here’s a solid, quick overview by Vivek Kumar.

أخيرًا ، كتب إيان إليوت إرشادًا يساعدك في تنفيذ جميع الأساليب. لكن هل يمكنك معرفة ما إذا كان يمكنك تنفيذ addHead () و insertAfter () لقائمتك المرتبطة قبل النظر إلى هذا؟