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

القوائم المرتبطة هي واحدة من أهم هياكل البيانات التي يمكنك تعلمها.

في القائمة المرتبطة ، يحتوي كل عنصر على مرجع للعنصر الذي يليه.

يمكننا أن نبدأ من بداية القائمة ، وhead، وتكرار كل عناصر القائمة ، حتى نصل إلى النهاية (ملفtail).

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

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

ليس لدى JavaScript تطبيق للقوائم المرتبطة ، لذلك سننشئ واحدة الآن.

أولاً نقوم بإنشاء ملفItemالفصل الذي سيكون موجودًا لكل عنصر في القائمة:

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

لدينا مؤشر إلى العنصر التالي في القائمة ، والقيمة.

ثم حددنا ملفLinkedListفئة تستضيف قيمتين خاصتين:headوtail.

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

class LinkedList {
  #head = null
  #tail = null
  append = (value) => {
    const item = new Item(value)
    if (!this.#head) {
      this.#head = item
      this.#tail = item
      return
    }
    this.#tail.next = item
    this.#tail = item
  }
  size = () => {
    let count = 1
    let item = this.#head
    if (!item) return 0
    while ((item = item.next)) {
      count++
    }
    return count
  }
}

هذه هي الطريقة التي يمكننا استخدامها:

const list = new LinkedList()
list.append(1)
list.append(2)
list.append(3)

يمكننا إضافةsize()طريقة إرجاع حجم القائمة:

class LinkedList {
  //...
  size = () => {
    let count = 1
    let item = this.#head
    if (!item) return 0
    while ((item = item.next)) {
      count++
    }
    return count
  }
}
const list = new LinkedList()
list.size() //0
list.append(1)
list.size() //1
list.append(2)
list.append(3)
list.size() //3

كيف يمكننا إيجاد عنصر في القائمة من حيث القيمة؟ دعنا ننفذ طريقة للقيام بذلك:

class LinkedList {
  //...
  find = (value) => {
    let count = 1
    let item = this.#head
    if (!item) return null
    while ((item = item.next)) {
      if (item.value === value) {
        return item
      }
    }
    return null
  }
}

const list = new LinkedList() list.append(1) list.append(2) list.append(3) const item = list.find(2) //item.value === 2

ماذا لو أردنا إدراج عنصر في القائمة المرتبطة؟ لدينا بالفعلappend()لإدراج العنصر في نهاية القائمة. دعنا ننفذ طريقة لإدراج العنصر في موضع محدد:

class LinkedList {
  //...
  insert = (index, value) => {
    //check for out-of-bounds values
    if (index < 0 || index > this.size()) return
<span style="color:#66d9ef">const</span> <span style="color:#a6e22e">node</span> <span style="color:#f92672">=</span> <span style="color:#66d9ef">new</span> <span style="color:#a6e22e">Item</span>(<span style="color:#a6e22e">value</span>)
<span style="color:#66d9ef">let</span> <span style="color:#a6e22e">current</span> <span style="color:#f92672">=</span> <span style="color:#66d9ef">this</span>.<span style="color:#960050;background-color:#1e0010">#</span><span style="color:#a6e22e">head</span>
<span style="color:#66d9ef">let</span> <span style="color:#a6e22e">previous</span>

<span style="color:#66d9ef">if</span> (<span style="color:#a6e22e">index</span> <span style="color:#f92672">===</span> <span style="color:#ae81ff">0</span>) {
  <span style="color:#75715e">//first position

node.next = current this.#head = node } else { let i = 0 while (i++ < index) { previous = current current = current.next } node.next = current previous.next = node } } }

const list = new LinkedList() list.append(1) list.append(2) list.append(3) list.insert(2, ‘a’) list.size() //4

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


المزيد من دروس js: