كيفية تنفيذ قائمة مرتبطة في JavaScript

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

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

ما هي القائمة المرتبطة؟

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

يحتوي كل عنصر (يُسمى عادةً بالعقد) على عنصرين: البيانات المخزنة ورابط إلى العقدة التالية. يمكن أن تكون البيانات أي نوع بيانات صالح. يمكنك رؤية هذا موضح في الرسم البياني أدناه.

صورة قائمة مرتبطة

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

في JavaScript ، تبدو القائمة المرتبطة كما يلي:

const list = { head: { value: 6 next: { value: 10 next: { value: 12 next: { value: 3 next: null } } } } } };

ميزة القوائم المرتبطة

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

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

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

أنواع القوائم المرتبطة

هناك ثلاثة أنواع من القوائم المرتبطة:

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

تنفيذ عقدة القائمة في JavaScript

كما ذكرنا سابقًا ، تحتوي عقدة القائمة على عنصرين: البيانات والمؤشر إلى العقدة التالية. يمكننا تنفيذ عقدة قائمة في JavaScript على النحو التالي:

class ListNode { constructor(data) { this.data = data this.next = null } }

تنفيذ قائمة مرتبطة في JavaScript

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

class LinkedList { constructor(head = null) { this.head = head } }

ضع كل شيء معا

لنقم بإنشاء قائمة مرتبطة بالفصل الذي أنشأناه للتو. أولا، نحن إنشاء عقدتين القائمة، node1و node2ومؤشر من عقدة 1 إلى عقدة 2.

let node1 = new ListNode(2) let node2 = new ListNode(5) node1.next = node2

بعد ذلك ، سننشئ قائمة مرتبطة بامتداد node1.

let list = new LinkedList(node1)

دعنا نحاول الوصول إلى العقد الموجودة في القائمة التي أنشأناها للتو.

console.log(list.head.next.data) //returns 5

بعض طرق LinkedList

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

  1. بحجم()
  2. واضح()
  3. انه شهر مميز لصنع الابطال()
  4. getFirst ()

1. الحجم ()

تقوم هذه الطريقة بإرجاع عدد العقد الموجودة في القائمة المرتبطة.

size() { let count = 0; let node = this.head; while (node) { count++; node = node.next } return count; } 

2. مسح ()

هذه الطريقة تفرغ القائمة.

clear() { this.head = null; }

3. getLast ()

تقوم هذه الطريقة بإرجاع العقدة الأخيرة من القائمة المرتبطة.

getLast() { let lastNode = this.head; if (lastNode) { while (lastNode.next) { lastNode = lastNode.next } } return lastNode }

4. getFirst ()

تقوم هذه الطريقة بإرجاع العقدة الأولى من القائمة المرتبطة.

getFirst() { return this.head; }

ملخص

في هذه المقالة ، ناقشنا ماهية القائمة المرتبطة وكيف يمكن تنفيذها في JavaScript. ناقشنا أيضًا الأنواع المختلفة من القوائم المرتبطة بالإضافة إلى مزاياها وعيوبها الإجمالية.

أتمنى أن تكون قد استمتعت بقراءته.

هل تريد أن يتم إخطاري عند نشر مقال جديد؟ انقر هنا.