次へ:リンクリストの紹介

このポストでは、アリアナグランデの「ありがとう、次」の言語のリンクリストデータ構造について話します.あなたが歌の音楽ビデオである芸術の部分を見なかったならば、我々が始める前に、休止して、そうしてください.
リンクリストは、データとポインタを持つノードから成るデータの線形コレクションです.私たちは、ノードの値と次のノードへのポインタを格納するノードを含むシンボリックリンクリストに集中するつもりです.リンクされたリストの他のタイプも、二重にリンクされたリストと循環的にリンクされたリストのようです、しかし、我々は現在の間、単独でリンクされたものに集中します.
私たちが同じページにいることを確認するための2つの簡単な定義

ポインタはメモリの値のアドレスを記憶する.これらはまた、何にもポイントすることができます.参照は似ていますが、何も指しません.

データ構造は、どんなプログラミング言語ででも実行されることができるデータのコレクションです.

この投稿では以下のリンクリストを使用します.

上の図では、5つの異なるノードが表示され、それぞれがデータ値を持ちます.最初の4つは、彼女が彼女のEXESを記載する順序です:

Thought I'd end up with Sean
But he wasn't a match
Wrote some songs about Ricky
Now I listen and laugh
Even almost got married
And for Pete, I'm so thankful
Wish I could say, "Thank you" to Malcolm
'Cause he was an angel

最後のものはアリ自身です.

Plus, I met someone else
We havin' better discussions
I know they say I move on too fast
But this one gon' last
'Cause her name is Ari
And I'm so good with that (so good with that)

データに加えて、各々のノードは、次のノードへのポインタを記憶する.彼女はいつも同じ順序で彼女のexesについて歌を歌う.リンクリストを反復処理すると、同じ順序が適用されます.リンクされたリストの最初のノードであるヘッドノードから始め、次のものに移動します.シングルリンクリストの場合は、ノードからノードへランダムに移動したり、ランダムに移動しないでください.
ノードを作成し、次のようにノードをリンクすることで、超簡単なリンクリストを作成できます.

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

let ari = new Node('Ari')
let malcolm = new Node('Malcolm', ari)
let pete = new Node('Pete', malcolm)
let ricky = new Node('Ricky', pete)
let sean = new Node('Sean', ricky)

このポストの最終コードもPythonhere
seanノードがどのように見えるかを出力すると、データ属性としての名前とリッキーである次のノードへのリファレンスを格納することがわかります.を使用してすべてのノードを横断することができますnext 属性!

また、リンクリストの最後にNULLポインタがあります.この場合、アリは女王ですので、彼女は自分で良いし、彼女の次の重要な他に移動する必要はありません.だから、彼女のノードの次の感謝のU、次の.
リンクリストは、線形データ構造の世界での主要な代替手段である配列に比べていくつかの利点があります.配列は伝統的にメモリの連続したブロックに格納されます.そして、それは我々が速いインデックス式を使うのを許しますstart_of_array_in_memory + space_allocated_for_each_array_item * index_of_item_we_want . それは超効率的ですがO(1) ) インデックスで項目を取得するには、配列から項目を挿入または削除するのに効率が悪いです.メモリ内の異なるブロックにすべてを移動する必要があります.その配列の前か後に新しい項目を挿入するスペースがあることは保証されません.あなたが真ん中で挿入または削除するならば、同じロジックは適用されます--あなたは穴を埋めるか、より多くのスペースを割り当てるためにメモリのまわりでアイテムを動かす必要があります.

配列とは異なり、リンクリストは1つの隣接した(または、側から側へ)格納される必要はありません😉) リンクリストの先頭に挿入と削除を行うメモリを簡単にブロックします.ポインタはメモリ内の任意の場所を指しているので、すべてのデータを移動して新しいノードを追加する必要はありません.
これは、リンクされたリストを検索しようとしている場合は、中央に挿入、またはリンクリストの真ん中から削除しようとしている場合は、プロセスははるかに効率的になります.我々は頭から我々がアクセスしようとしているノードまで横断する必要があります.
リンクリストの他の欠点は、配列よりデータを格納し、配列がデータを格納しているのに対して、次のノードへのポインタを格納するので、メモリよりも少しメモリを使用することです.
これらの操作を実装するために使うコードを見てみましょう.リンクリストの先頭に挿入し、インデックスでremoveを実行して、それを実行する必要があることを示します.

class LinkedList {
  constructor() {
    // the head attribute stores a pointer to the first node in our linked list
    this.head = null
    this.length = 0
  }

  insert(data) {
    // inserts to the beginning of the linked list
    // what used to be  the head becomes the second element
    this.head = new Node(data, this.head) 
    this.length++
  }

  remove_value(value) {
    // remove any data value from the linked list

    // we need to store a pointer to a node and it's predecessor
    // so that when we remove the value we can just change the pointer!
    let prevNode = null
    let currentNode = this.head

    while (currentNode) {
      if (currentNode.data === value) {
        if (prevNode) {
          // Set the previous node's next value to the node we're deleting's next attribute
          // effectively removing it from our sequence
          prevNode.next = currentNode.next
        } else {
          this.head = currentNode.next
        }
        currentNode = null
        this.length--
        return true
      }
      // move to the next nodes
      prevNode = currentNode
      currentNode = currentNode.next
    }
  }
}

let thankUNext = new LinkedList()
thankUNext.insert('Ari')
thankUNext.insert('Malcolm')
thankUNext.insert('Pete')
thankUNext.insert('Ricky')
thankUNext.insert('Sean')

thankUNext.remove_value('Ricky')

ここでは、アリが彼のために感謝していなくなったとき、我々のリンクリストからリッキーを取り外すように見えるものの視覚化があります

赤のすべてが削除されます.
他に2つの方法がありますsearch and iterate :

iterate() {
  let node = this.head
  while (node) {
    console.log(node.data)
    node = node.next
  }
}

search(data) {
  let idx = 0
  let node = this.head
  while (node) {
    if (node.data === data) return idx
    node = node.next
    idx += 1
  }
  return -1
}

それで、我々がリンクリストの中で保存しているAriana GrandeのExesがデータ構造のすばらしい使用であるということを知っています、我々が我々が「ありがとうu、次へ」に合わせて歌うとき、我々がいつも同じ順序で彼らをリストしている時から、しかし、他のデータはリンクリストでよく働きますか?一つの使用はタスクキューです.プリンタは、例えば、一度に1つだけのものを印刷することができますが、我々はまだ将来のタスクをロードし、各ページの印刷を押す必要はありません!タスクのリストを作成するときは、常に最新の項目をキューの末尾に追加し、最初の行を出力します.バックボタンの実装は似ています!またはアンドゥホットキー!通常、これらを実装するために、リンクリストの先頭にスタックまたはキューのデータ構造を実装します.私は、彼らが本当に多くのコード挑戦のために本当に役に立つとわかりました.
うまくいけば、このポストはあなたの忍耐や痛みの代わりに愛を教えた.