Doubly Linked List: TypeError: Converting circular structure to JSON

Viewed 27

I have written a DoublyLinkedList class for use in an algorithm. I am getting errors about circular object references "Example: a = { b: a }". I am confused because it seems that circular object references are inevitable in doubly linked lists because each node has pointers forward and backward. I have included the error and my DoublyLinkedList code below and any help troubleshooting would be appreciated. NOTE: I am not allowed to share the algorithm in which the DoublyLinkedList class is being used.

// A node class for the DoublyLinkedList class

class DoublyLinkedListNode {
  key: string;
  value: number;
  prev: DoublyLinkedListNode | null = null;
  next: DoublyLinkedListNode | null = null;

  constructor(key: string, value: number) {
    this.key = key;
    this.value = value;
  }

  detach(): DoublyLinkedListNode {
    if(this.prev !== null) this.prev.next = this.next;
    if(this.next !== null) this.next.prev = this.prev;

    this.prev = null;
    this.next = null;

    return this;
  }
}

// ------------------------------------------

// A DoublyLinkedList class for use in the main algorithm

class DoublyLinkedList {
  head: DoublyLinkedListNode | null = null;
  tail: DoublyLinkedListNode | null = null;

  setHead(node: DoublyLinkedListNode): DoublyLinkedListNode {
    if(this.head === node) return node;

    // update the head and tail if the list is empty
    
    if(this.head === null) {
      this.head = node;
      this.tail = node;
      return node;
    }

    // otherwise, append the new node to the left of the old head

    this.remove(node);

    this.head.prev = node;
    node.next = this.head;
    this.head = node;

    return node;
  }

  setTail(node: DoublyLinkedListNode): DoublyLinkedListNode {
    if(this.tail === node) return node;
    if(this.tail === null) return this.setHead(node);

    this.remove(node);

    this.tail.next = node;
    node.prev = this.tail;
    this.tail = node;

    return node;
  }

  shift(): DoublyLinkedListNode | null {
    if(this.head === null) return null;

    // if there is only one node, set the head and tail to null
    
    if(this.head === this.tail) {
      const temp = this.head;
      this.head = null;
      this.tail = null;
      return temp;
    }

    // otherwise, this.head.next is the new head

    const oldHead = this.head;
    const newHead = oldHead.next!;

    oldHead.detach();
    newHead.prev = null;
    this.head = newHead;

    return oldHead;
  }

  pop(): DoublyLinkedListNode | null {
    if(this.tail === null) return null;
    if(this.head === this.tail) return this.shift();

    const oldTail = this.tail;
    const newTail = oldTail.prev!;

    oldTail.detach();
    newTail.next = null;
    this.tail = newTail;

    return oldTail;
  }

  remove(node: DoublyLinkedListNode): DoublyLinkedListNode | null {
    if(node === this.head) return this.shift();
    if(node === this.tail) return this.pop();

    node.detach();
    return node;
  }
}

// ------------------------------------------

enter image description here

0 Answers
Related