Linked list in javascript

Question

how this.tail.next = newNode is adding the value to next property of head? if it isn't then what part of the code is responsible to add next value to head?

  constructor(value) {
    this.head = {
      value: value,
      next: null
    }
    this.tail = this.head;
    this.lenght = 1;
  }
  append(value) {
    let newNode = {
      value: value,
      next: null 
    }
    this.tail.next = newNode;
    this.tail = newNode;
    this.lenght++;
    return this;
  }


}


let myList = new LinkedList(10);
myList.append(8);
myList.append(8);

Output

  head: { value: 10, next: { value: 8, next: [Object] } },
  tail: { value: 8, next: null },
  lenght: 3
}```

`this.lenght++;` `this.lenght = 1;`spelling error – epascarello Apr 03 '21 at 16:00 — epascarello, Apr 03 '21 at 16:00

score 0 · Answer 1 · answered Apr 03 '21 at 15:55

0

The 'this.tail = this.head' part of your code is making 'this.tail' a reference to 'this.head'. what you want is to make it a copy of 'this.head'.

see here: JavaScript: How to make a copy of a object?.

answered Apr 03 '21 at 15:55

J. Byvelds

19
4

Not actually, it's deliberately making `this.head` and `this.tail` properties refer to the same object. – traktor Apr 03 '21 at 18:04

traktor · Answer 2 · 2021-04-03T18:07:20.747

The posted code has a problem in that it can't create an empty list. Normally a forward linked list maintains both head and tail pointers so that

The head pointer points to the first node in the list,
The tail pointer points to the last entry in the list,
If the list is empty, both head and tail pointers are null,
If the list contains a single element, the head and tail pointers are the same (and point to the only node in the list).
Each node points to the next node in the list.
A two way linked list would maintain both previous and next node values.

In the following example, length still maintains the number of elements in the list to simplify checking if the list is empty.

class ForwardLinkedList {
    constructor(...values) {
        this.head = null;
        this.tail = null;
        this.length = 0;
        values.forEach( value => this.append(value));
    }
    append( value) {
        let newNode = {
            value: value,
            next: null 
        }
        if( this.length) {
            this.tail.next = newNode;
            this.tail = newNode;
        }
        else {
            this.head = this.tail = newNode;
        }
        ++this.length;
    }
}

let myList = new ForwardLinkedList(10);
myList.append(8);
myList.append(6);
console.log(JSON.stringify( myList));

score 0 · Answer 3 · answered Apr 06 '21 at 18:50

 head: { value: 10, next: { value: 8, next: [Object] } },
  tail: { value: 8, next: null },
  lenght: 3
}```

I guess your confusion is, why it is written like this.tail.next = newNode remember previously a reference of this.head was set to this.tail so in that sense, a copy of this.head was inside the this.tail. Now if we simply write this.tail which is tail: { value: 8, next: null } that is the last item in our list because the method doesn't know that we only have one item. So it's going to grab the tail and then grab the next value of tail this.tail.next, so it's going to grab the pointer of the tail and say hey instead of pointing at to null point it to a new node that we just created. Finally we update the this.tail = newNode;

Linked list in javascript

3 Answers3