JavaScriptデータ構造:リンクリスト

リンクリストは、学習できる最も重要なデータ構造の1つです。

リンクリストでは、各アイテムには、それに続くアイテムへの参照が含まれています。

リストの最初から始めることができます。head、そして最後に到達するまで、リストのすべての項目を繰り返します(tail)。

配列と比較すると、アイテムは実際のメモリ(低水準プログラミング言語)で隣り合って配置されていないか、配列のアイテムにランダムにアクセスするために使用できるインデックスがありません。

リストの途中にある項目は、参照方法がわからないため、最初から始めないと参照できません。

JavaScriptにはリンクリストの実装がないため、ここで作成します。

まず、Itemリスト内の各アイテムに含まれるクラス:

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

リスト内の次の項目へのポインタと値があります。

次に、LinkedList2つのプライベート値をホストするクラス: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

別のタイプのリンクリストは二重リンクリストで、各アイテムには前の要素へのリンクも含まれています。

私の無料ダウンロードJavaScriptビギナーズハンドブック


その他のjsチュートリアル: