Doubly LinkedList nodes [Circular] in Javascript

Question

class LinkedList{
  constructor(value){
    this.head = {
      data: value,
      next: null,
      prev: null
    }
    this.tail = this.head
    this.length = 1

  }
  append(val){
    const node = {
      data: val,
      next: null,
      prev: this.tail
    }
    this.tail.next = node
    this.tail = node
    this.length++ 
    return this
  }
  prepend(val){
    const node = {
      data: val,
      next: null,
      prev: null
    }
    node.next = this.head
    this.head.prev = node
    this.head = node
    this.length++
    return this
  }
  insert(value, pos){
    let i = 1
    let target = this.head
    while (i!=pos){
      target = target.next
      i++
    }
    const node = {
      data: value,
      next: null,
      prev: null
    }
    node.next = target.next
    let nextNode = target.next
    nextNode.prev = node
    node.prev = target
    target.next = node 
    this.length++
  }
  remove(i){
    let counter = 1
    let currentNode = this.head
    while (counter!= i){
      currentNode = currentNode.next
      counter++
    }

    let temp = currentNode.next 
    currentNode.next = temp.next
    let nextNode = temp.next 
    nextNode.prev = currentNode
    temp.next = null 
    temp.prev = null
    this.length--
  }
  printNodes(){
    const nodeArray = []
    let currentNode = this.head;
    while (currentNode){
      nodeArray.push(currentNode.data.toString())
      currentNode = currentNode.next
    }
    console.log(nodeArray.join("-->"))
  }
}
const lili = new LinkedList(5)
lili.append(12)
lili.append(18)
lili.append(15)
lili.insert(14,2)
lili.printNodes()
lili.remove(2)
console.log(lili)

I made this incomplete implementation of a doubly LinkedList in Javascript. The 2nd node's prev property and the 2nd to last node's next property are both showing [Circular] instead of [Object]. Could someone explain what Circular is and why this is happening? Thanks.

Your code seems fine. `console` may give indications on whether an object has occurred before in the same structure. It is of course characteristic for doubly linked lists that you have multiple references to the same node (e.g. `head.next.prev === head`, `tail.prev.next === tail`). — trincot, Mar 02 '21 at 18:31

Mr. Polywhirl · Answer 1 · 2021-03-02T19:20:31.610

You should never print the underlying data structure since all other nodes point to their neighbors. I also flipped the arguments for your insert method, because position is usually the first argument in many standard libraries.

Instead, you need to devise an iterator that allows you to traverse your list from head to tail once. In the example below, I adapted the folowing class iterator within your LinkedList class. You can find out more about iterators here: MDN: Iterators and generators.

You can quickly traverse the list by simply spreading.

printNodes() {
  console.log(`List nodes: ${[...this].join("-->")}`);
}

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
    this.prev = null;
  }
}

class LinkedList {
  constructor(value) {
    this.head = this.tail = null;
    this.length = 1
  }
  append(data) {
    const node = new Node(data);  
    if (this.head == null) {
      this.head = this.tail = node;  
      this.head.prev = null;  
      this.tail.next = null;  
    } else {
      this.tail.next = node;  
      node.prev = this.tail;  
      this.tail = node;  
      this.tail.next = null;  
    }
    this.length++;
    return this;
  }
  prepend(data) {
    const node = new Node(data);  
    if (this.head == null) {
      this.head = this.tail = node;  
      this.head.prev = null;  
      this.tail.next = null;  
    } else {
      this.tail.prev = node;  
      node.next = this.head;  
      this.head = node;  
      this.tail.prev = null;  
    }
    this.length++;
    return this;
  }
  get(pos) {
    let i = 0, currentNode = this.head;
    while (currentNode) {
      if (i === pos) return currentNode;
      currentNode = currentNode.next;
      i++;
    }
    return null;
  }
  insert(pos, value) {
    const target = this.get(pos), node = new Node(value);
    node.next = target.next;
    const nextNode = target.next;
    nextNode.prev = node;
    node.prev = target;
    target.next = node;
    this.length++;
    return this;
  }
  remove(pos) {
    let counter = 1, currentNode = this.head;
    while (counter != pos) {
      currentNode = currentNode.next;
      counter++;
    }
    const temp = currentNode.next;
    currentNode.next = temp.next;
    const nextNode = temp.next;
    nextNode.prev = currentNode;
    temp.next = null;
    temp.prev = null;
    this.length--;
  }
  // See: https://stackoverflow.com/a/45849918/1762224
  *iterator() {
    let currentNode = this.head;
    while (currentNode) {
      const { data } = currentNode;
      currentNode = currentNode.next;
      yield data;
    }
  }
  [Symbol.iterator]() {
    return this.iterator();
  }
  printNodes() {
    if (this.head == null) {
      console.log('List is empty');
      return;
    }
    console.log(`List nodes: ${[...this].join("-->")}`);
  }
}

const list = new LinkedList()
  .append(5)
  .prepend(12)
  .append(18)
  .append(15)
  .insert(2, 14);
list.printNodes();

list.remove(2);
list.printNodes();

.as-console-wrapper { top: 0; max-height: 100% !important; }

Doubly LinkedList nodes [Circular] in Javascript

1 Answers1