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

When you iterate over node3, current.next == null, so the loop doesn't execute, so you'll need to come up with another condition for your loop.

Also you should use break instead of return since you're not in a function.

于 2013-09-14T14:56:27.000 回答
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 回答
0

理想情况下，您的结构 insertAt 函数如下所示：

var insertAt = function(head, item, index) {
    var curr = head;
    var count = 0;
    while (curr !== null) {
        if (count === index) {
            var newNode = { data: item, next: curr.next };
            curr.next = newNode;
            break;
        }
        count++;
        curr = curr.next;
    }
};

insertAt(head, 2, 3);

让我知道这个是否奏效。
另请查看我创建的这个 LinkedList 类，insertAt目前缺少函数，但是从这个堆栈问题中，我也计划将它添加到我的类中。
类 - GitHub
NPM 包 - @dsinjs/linked-list
完整文档

于 2020-12-06T19:48:45.347 回答
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 回答