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(',') } }