-1

ここにいくつかのコードがあり、何が起こっているかについての基本的なロジックがありますが、行ごとに正確に何をしているのかを理解したいと思います。Python tutor に似た Javascript コード チェックが見つからないので、助けてください。LinkedList がどのように機能し、このコードが何をしているのかを段階的に理解したいと思います。これを実際の例でいつ使用しますか？これと配列の違いは何ですか?

4

3 に答える 3

1

基礎：

リンクされたリストは、ノードで構成されるデータ構造です。各ノードは、いくつかの有用なデータと次のノードへの参照を保持します。リストへの参照を保持するには、最初のノードへの参照を保持するだけです。リストは、別のノードではなく null への参照を持つノードで終了します。

JS コード (コメント):

// node structure:
//{ data: value, // useful data
// next: nextNode } // reference to next node. null for last node


var LinkedList = function() { // constructor function
     this.head = null; // reference to the first node
};

LinkedList.prototype.insert = function(value) { // function you use to insert a new node
     if(this.head === null) { // code for when the list has no nodes.
         this.head = {data: value, next: null}; // simply init the reference to the first node to a node
     } else { // if there are nodes, you need to go through the list to get the to the last node
         var temp = this.head; // start from the first node
         while(temp.next !== null) { // until you find the node that has no next
             temp = temp.next; // go from one node to the next
         }
         temp.next = {data: value, next: null}; // the last node should point to a new node you create (which points to nothing, so it becomes the last node)
     } };

より良い解決策:

リスト構造の最後のノードへのポインターも保持します。挿入はO(1)になります。削除はまだ O(n) です。最後のノードが削除された場合は、ポインターを更新する必要があります。

編集：あなたの新しい質問への回答

一般的には配列の方が優れていますが、連結リストの方が望ましい場合もあります。明らかな例の 1 つは、断片化されたメモリが大量にある環境です。配列には連続して割り当てられたメモリが必要であるため、メモリが断片化されている場合、割り当てることができる最大の配列は非常に小さくなります。リンク リストは、もう 1 つのノード用のスペースがある限り、いつでもどこでもより多くのメモリを取得できます。リンクされたリストが JS で役立つ状況に遭遇したことはありません (インタビューの質問でしょうか?)。

于 2013-11-09T20:56:52.937 に答える
1

firebug や chrome dev ツールなどを使用して、ブレークポイントを設定し、コードを段階的に進めることができます。

于 2013-11-09T20:59:38.560 に答える
0

JavaScriptでのテストについて質問していると思います。JasmineまたはQUnitを調べることができます。私はpythonチューターに慣れていないので、これらが似ているかどうかはわかりませんが、それは始まりです.

于 2013-11-09T20:52:59.780 に答える