The stack, queue and linked list in the data structure should be the most basic. It is also very important, such as graph, tree, binary tree, optimal binary tree / solution, etc. I didn't expect the front end to know the data structure. To sum up, use JavaScript to realize the two-way linked list in the stack, queue and linked list in the data structure.

The data structure question asked during the interview was a little confused at that time. I didn't know how to start with paper and pen. It's not difficult to write it later. In particular, the stack and queue can be directly realized by the pop(), push(), shift(), unshift() methods of the native Array. These methods were specially recorded when making JSON data before. It's really that lard was confused and didn't write it.

Stack, queue

The first is the realization of stack and queue. The core idea of stack is "first in first out", and the core idea of queue is "first in first out". In class, teachers keep emphasizing their differences. Queue is like queue, first in first out; The stack is unreasonable, first in and then out. If you are a salesperson, the products produced by your husband are piled up in the warehouse and sell the latest products, you may be approved as PPT by your boss in the end.

First, the implementation of stack. Let's take a look at the main methods to be implemented:

• pop(): the top element of the stack is out of the stack and returned
• push(el): put new elements on the stack
• peek(): return stack top element
• size(): returns the length of the stack
• isEmpty(): Returns whether the stack is empty
• clear(): clear stack
• print(): print stack

class Stack {
  constructor(...val){
    this.values = [...val]
  }
  pop(){
    return this.values.pop()
  }
  push(val){
    this.values.push(val)
  }
  peek(){
    return this.values[this.values.length-1]
  }
  size(){
    return this.values.length
  }
  isEmpty(){
    return this.values.length == 0
  }
  clear(){
    this.values = []
  }
  print(){
    console.log(this.values.toString())
  }
}

Then there is the implementation of queue, which is very similar to the implementation of stack:

• dequeue(): the header element is dequeued
• enqueue(el): new elements are listed
• front(): return queue header
• size(): returns the length of the queue
• isEmpty(): Returns whether the queue is empty
• clear(): clear the queue
• print(): print queue

class Queue {
  constructor(...val){
    this.values = [...val]
  }
  dequeue(){
    return this.values.shift()
  }
  enqueue(val){
    this.values.push(val)
  }
  front(){
    return this.values[0]
  }
  size(){
    return this.values.length
  }
  isEmpty(){
    return this.values.length == 0
  }
  clear(){
    this.values = []
  }
  print(){
    console.log(this.values.toString())
  }
}

Bidirectional linked list

Compared with stack and queue, bidirectional linked list is a little more complex. There is no order in a two-way linked list, but each Node will have a Pointer pointing to the Previous and Next nodes of the Node. There is also a Head Pointer and Tail Pointer pointing to the Head and Tail nodes of the linked list respectively. If not, it will point to Null, that is, Null Pointer. The theory may not be clear, or the diagram is relatively clear

[the external link image transfer fails, and the source station may have an anti-theft chain mechanism. It is recommended to save the image and upload it directly (img-XB8Rqn81-1614410881199)(JavaScript realizes the stack, queue and two-way linked list of data structure. assets/image-20201221191959448.png)]

The second is the implementation. First, we have to have a Node class Node, including the front pointer, rear pointer and data:

class Node {
  constructor(el) {
    this.element = el
    this.previous = null
    this.next = null
  }
  toString(){
    return this.element
  }
}

Then is the implementation of linked list:

• append(el): add node elements
• insert(position, el): inserts a node element at a specified position
• getNode(position): get the node element of the specified position
• get(position): get the node data of the specified location
• indexOf(el): returns the subscript of the specified node
• update(position, el): updates the node at the specified location
• removeAt(position): deletes a node at a specified location
• isEmpty(): Returns whether the linked list is empty
• size(): returns the length of the linked list
• toString(): override toString() method (because the data structure is a custom Node)
• backwardString(): traverses the output node data in reverse order
• forwardString(): traverse the output node data sequentially

All the necessary comments are explained in the code.

class DoubleLinkList {
  head = null
  tail = null
  size = 0
  append(el) {
    if (this.size == 0) {
      // When the length of the linked list is zero
      this.head = this.tail = el
      this.size++
      return
    }
    // When the length of the linked list is not zero: add from the tail
    el.previous = this.tail
    this.tail.next = el
    this.tail = el
    this.size++
  }
  insert(position, el) {
    let current = null
    // The insertion position is added to the tail by default when it is outside the length
    if(position >= this.size)
      return this.append(el)
    // The insertion position is before the head of the linked list. It is inserted into the head by default
    if(position <= 0){
      current = this.head
      current.previous = el
      el.next = current
      this.head = el
      this.size++
      return
    }
    // Insert in the middle
    current = this.getNode(position)
    el.previous = current.previous
    el.next = current
    current.previous.next = el
    current.previous = el
    this.size++
  }
  getNode(position) {
    let index = 0
    let current = null
    // If the linked list is empty
    if (this.isEmpty())
      return
    // If the linked list overflows
    if(position >= this.size || position < 0)
      return
    // If you are in the first half of the linked list, traverse from the beginning
    if((this.size / 2) > position){
      current = this.head
      while (index++ < position) {
        current = current.next
      }
    } else {
    // If in the second half, traverse from the tail
      current = this.tail
      index = this.size - 1
      while (index-- > position) {
        current = current.previous
      }
    }
    return current
  }
  get(position) {
  // It is the same as the previous method, except that it returns the data of the node
    let index = 0
    let current = null
    if (this.size == 0)
      return
    if(position >= this.size || position < 0)
      return
    if((this.size / 2) > position){
      current = this.head
      while (index++ < position) {
        current = current.next
      }
    } else {
      current = this.tail
      index = this.size - 1
      while (index-- > position) {
        current = current.previous
      }
    }
    return current.element
  }
  indexOf(el) {
    let current = this.head
    let index = 0
    while(current){
      // Traversal from the beginning. If it meets the requirements, the node returns the subscript. Otherwise, it returns - 1
      if(el.element == current.element)
        return index
      current = current.next
      index++
    }
    return -1
  }
  update(position, el) {
    if(position >= this.size || position < 0)
    // Cross boundary judgment
      return
    let current = this.getNode(position)
    current.element = el.element
  }
  removeAt(position) {
    // Cross boundary judgment
    if(position >= this.size || position < 0)
      return
    // When there is only one node
    if(this.size == 1){
      this.head = this.tail = null
      this.size--
      return
    }
    // When deleting a header node
    if(position == 0){
      this.head = this.head.next
      this.head.previous = null
      this.size--
      return
    }
    // When deleting the tail node
    if(position == this.size - 1){
      this.tail = this.tail.previous
      this.tail.next = null
      this.size--
      return
    }
    // Delete intermediate node
    let current = this.getNode(position)
    current.previous.next = current.next
    current.next.previous = current.previous
    this.size--
  }
  isEmpty() {
    return this.size == 0
  }
  size(){
    return this.size
  }
  toString() {
    return this.forwardString()
  }
  forwardString() {
    // Traverse from scratch
    let result = []
    let current = this.head
    while(current){
      result.push(current.element)
      current = current.next
    }
    return result.join(',')
  }
  backwardString() {
    // Traverse from tail
    let result = []
    let current = this.tail
    while(current){
      result.push(current.element)
      current = current.previous
    }
    return result.join(',')
  }
}