linkedlist using javascript issue

Question

I am writing linkedlist datastructure using javascript. I have issue with inserting new node in a particular position. I have following code.

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;
}

I am creating 3 nodes initially and finally a newNode. I want to insert this newNode at position 3 i.e. pos = 3 which means the end of the list. My above code inserts nodes to other places but it does not at the end. Why and how can I solve this?

thgaskell · Accepted Answer · 2013-09-14 14:56:27Z

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.

answered Sep 14, 2013 at 14:56

thgaskell

13.3k5 gold badges34 silver badges39 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Om3ga Over a year ago

Could you add sample example of another condition?

thgaskell Over a year ago

You could try change it to current.next || prev.next instead. The difference it will make is when current.next fails and previous.next is true which would be at an end node.

Om3ga Over a year ago

Where could I add current.next || prev.next?

Arun · Accepted Answer · 2014-08-14 03:54:32Z

You can try dynamic creation of linked list like this.

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;

};

Instantiation of this can be done as shown below.

linkedlist = new Linkedlist();
linkedlist.insert(1);
linkedlist.insert(2);
linkedlist.insert(3);
linkedlist.insert(4);
linkedlist.remove(2);
linkedlist.largest();

Huy Hoang-Nguyen · Accepted Answer · 2016-02-15 18:23:42Z

0

With LinkedList, insert at position is not a common practice as LinkedLists don't maintain position for each node, rather it maintains links between nodes. Usually we want to insert before/after a node. More commonly, we want to insert at the end of the list. Below is code to insertAfter a 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(); 
    }
};

answered Feb 15, 2016 at 18:23

Huy Hoang-Nguyen

11 bronze badge

Comments

Siddhesh Kulkarni · Accepted Answer · 2020-12-06 19:48:45Z

0

With your structure ideally insertAt function would look like:

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);

Let me know if this works.
Also look at this LinkedList class I have created, insertAt function is currently missing, but from this stack question, I am planning to add it in my class as well.
Class- GitHub
NPM package - @dsinjs/linked-list
Complete documentation

answered Dec 6, 2020 at 19:48

Siddhesh Kulkarni

3584 silver badges15 bronze badges

1 Comment

Siddhesh Kulkarni Over a year ago

Ref link- Class - github.com/dsinjs/linked-list NPM package -npmjs.com/package/@dsinjs/linked-list Complete documentation - dsinjs.github.io/linked-list

Collectives™ on Stack Overflow

linkedlist using javascript issue

4 Answers 4

3 Comments

Comments

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

3 Comments

Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related