Circular linked list in javascript

3
votes

I am trying to implement circular linked list in javascript. I just want to know is it the right way to implement this in javascript? Are there any memory leaks or infinite object creation?

function LinkedList() {
    this.Node = null;
    this.count = 0;
    this.head = null;
};

LinkedList.prototype.append = function (value) {
    // create new node
    var node = this.createNode(value);
    console.log(value);
    if (this.head == null) {
        this.Node = node;
        this.Node.next = null;
        this.head = this.Node;
    } else {
        var ptr = this.Node;
        while (ptr.next != null) {
            ptr = ptr.next;
        }
        ptr.next = node;
    }
    this.count++;
};

LinkedList.prototype.getSize = function () {
    console.log(this);
};

LinkedList.prototype.close = function () {
    var ptr = this.head;
    while (ptr.next != null) {
        ptr = ptr.next;
    }
    ptr.next = this.head;
};

LinkedList.prototype.createNode = function (value) {
    var node = {};
    node.value = value;
    node.next = null;
    return node;
};

var li = new LinkedList();
li.append(1);
li.append(2);
li.append(3);
li.append(4);
li.close();
li.getSize();

When i checked the console, it displayed as head contains one node, and that node contains another node etc. It it the reference or the actual object they are storing?

2
javascriptlinked-listcircular-list
You should ask codereview if you didn't spot any bug yourself. - Denys Séguret
Is the only feature Node addition ? - Denys Séguret
i want to use circular link list. I don't want remove , display etc functions. I just want to know the number of objects and is it the right approach to implement circular linked list in javascript. - sudhir
Is it consistent with the javascript standard to keep the linkedlist data and methods in node it self?I am new to it but in c++ chess programming i usually create a tree creator a tree traverser and a node class.With each node are independent boxes created filled with data and added in place by tree creator.Traversing in managed by traverser class which takes care of forward backward and on branch movement. - amar

2 Answers

1
votes

The way you did your append function seems slightly flawed to me... because exactly after it executes, your list is at an inconsistent state. You need to call close() in order to setup everything correctly. What i would suggest is that you can alter the append() function to dynamically update the head and tail according; thus you wouldn't need to call close().

Below is how I would have implemented the append() method (basically just slightly modifying your code):

LinkedList.prototype.append = function(value) {
  var node = {
        value: value,
        next: this.head
    };//cricular node
  if (this.count === 0) {
    this.head = {};
    this.head.value = value;
    this.head.next = this.head;
    this.tail = this.head;
  } else {
    this.tail.next = node;
    this.tail = node;
  }
  this.count++;
};
0
votes
getCircular(start){
        let i=0,j=0;
        let secondHead = this.head;
        let pointer = this.head;
        let pointer2 = secondHead;
        while(i<start){
            let temp1 = pointer.next;
            pointer = temp1;
            i++;
        }
        this.head = pointer;
        this.tail.next = pointer2;
        while(j<start-1){
            let temp2 = pointer2.next;
            pointer2 = temp2;
            j++;
        }
        this.tail = pointer2;
        this.tail.next = null;
        return this;
    }

Suppose there is already a list as : Kohli -> Dhoni -> Yuvi -> Sharma -> Dhawan , And you pass an index of 2 , then the result will be like : Yuvi -> Sharma -> Dhawan -> Kohli -> Dhoni

Then your call should be like : ll.getCircular(2); // ll is an object for example