2

javascriptを使用してリンクリストデータ構造を書いています。特定の位置に新しいノードを挿入する際に問題があります。次のコードがあります。

var node3 = {
    data: 4,
    next: null
},
node2 = {
    data: 3,
    next: node3
},
node1 = {
    data: 1,
    next: node2
},
newNode = {
    data: 2,
    next: null
},
head = node1, current = head, pos = 3, i = 1, prev;

while (current.next) {
    if (pos === i) {
        prev.next = newNode;
        newNode.next = current;
        break;
    }
    prev = current;
    i++;
    current = current.next;
}

最初に 3 つのノードを作成し、最後にnewNode. newNodeこれを位置3に挿入したい、つまりpos = 3リストの最後を意味します。上記のコードはノードを他の場所に挿入しますが、最後には挿入しません。なぜ、どうすればこれを解決できますか?

4

4 に答える 4

1

node3 を反復するとcurrent.next == null、ループが実行されないため、ループの別の条件を考え出す必要があります。

また、関数に含まれていないため、break代わりに使用する必要returnがあります。

于 2013-09-14T14:56:27.000 に答える
0

LinkedList では、LinkedList は各ノードの位置を維持せず、ノード間のリンクを維持するため、位置に挿入することは一般的ではありません。通常、ノードの前後に挿入します。より一般的には、リストの最後に挿入したいと考えています。以下は、sourceNode の後に挿入するコードです。

this.insertAfter = function(sourceNode, node) {
    var curNode = head;
    while (curNode != null) {
        if (curNode === sourceNode) {
            curNode.setNext(node.setNext(curNode.getNext()));
            return;
        }
        else curNode = curNode.getNext(); 
    }
};
于 2016-02-15T18:23:42.553 に答える
0

このような連結リストの動的作成を試すことができます。

var Linkedlist = function() {
this.head = null;
this.tail = null;

};

function createNode( val ) {
var node = {};
node[ "key" ] = val;
node[ "prev" ] = null;
node[ "next" ] = null;
return node;

}

Linkedlist.prototype.insert = function( val ) {
if ( this.head === null ) {
    this.head = createNode( val );
    this.tail = createNode( val );
} else {
    var newNode = createNode( val );
    newNode[ "next" ] = this.head;
    newNode[ "prev" ] = null;
    this.head[ "prev" ] = newNode;
    this.head = newNode;
}
console.log(this);

};

Linkedlist.prototype.search = function( val ) {
var node = this.head;
while ( node[ "key"] != val ) {
    node = node[ "next" ];
    if ( node === null ) {
        break;
    }
}
return node;

};

Linkedlist.prototype.remove =  function( val ) {
var node = this.search(val);
if ( node != null ) {
    if ( node[ "next" ] === null && node[ "prev" ] === null ) {
        this.head = null;
        this.tail = null;
    } else {
        if ( node[ "key"] === this.head[ "key" ] ) {
            this.head = node[ "next" ];
            this.head[ "prev" ] = null;
        } else if ( node[ "key"] === this.tail[ "key" ]) {
            this.tail = node[ "prev" ];
            this.tail[ "next" ] = null;
        } else {
            node[ "prev" ][ "next" ] = node[ "next" ];
            node[ "next" ][ "prev" ] = node[ "prev" ];
        }
    }
    console.log( this );
} else {
    console.log("key doesnt exist");
}

};

Linkedlist.prototype.largest = function() {
var node = this.head;
var largest = this.head;
while ( node[ "next"] !== null ) {
    if ( node[ "key"] > largest[ "key" ] ) {
        largest = node;
    }
    node = node[ "next" ];
}
return largest;

};

これのインスタンス化は、以下に示すように行うことができます。

linkedlist = new Linkedlist();
linkedlist.insert(1);
linkedlist.insert(2);
linkedlist.insert(3);
linkedlist.insert(4);
linkedlist.remove(2);
linkedlist.largest();
于 2014-08-13T06:52:26.177 に答える