current position:Home>JavaScript learning data structure (stack, queue, linked list, bidirectional linked list)

JavaScript learning data structure (stack, queue, linked list, bidirectional linked list)

2022-01-27 02:39:05 Ma Luping

Stack

Stack (stack) It is a linear table that only inserts and deletes at the end of the table . We call the end that allows insertion and deletion the top of the stack , The other end is called the bottom of the stack , Stacks without any data elements are called empty stacks . Stack is also known as LIFO linear table   Because the stack has the characteristics of LIFO , So any element that is not at the top of the stack cannot be accessed . To get the elements at the bottom of the stack , You have to remove the elements first .

image.png
image.png
The two main operations on the stack are to push an element into the stack and to eject an element from the stack . Put it on the stack push() Method , Out of stack use pop() Method , The following code is used to realize the data structure of stack

Implementation stack class

  1. dataStore For datasets
  2. top Represents the top coordinate of the stack

    class Stack{
      dataStore=[]
      top=0
      constructor(){
      }
    }

    push(): Into the stack

push(element){
    this.dataStore[this.top++] = element
  }

pop(): Out of the stack

pop(){
    let element = this.dataStore[--this.top]
    this.dataStore.length = this.top
    return element
  }

peek(): Back to the top of the stack

peek(){
    return this.dataStore[this.top-1]
  }

length(): The amount of data

length() {
    return this.top;
  }

clear(): Empty stack

clear() {
    this.top = 0;
    this.dataStore.length=0
  }

Complete code

class Stack {
    dataStore = []
    top = 0
    constructor() {

    }
    push(element) {
        this.dataStore[this.top++] = element
    }
    pop() {
        let element = this.dataStore[--this.top]
        this.dataStore.length = this.top
        return element
    }
    peek() {
        return this.dataStore[this.top - 1]
    }
    length() {
        return this.top;
    }
    clear() {
        this.top = 0;
        this.dataStore.length = 0
    }
}

queue

A queue is a list , An element that can only be inserted at the end of the queue , Delete the list of elements at the head of the team . Queues are used to store data in order , The two main operations of FIFO queue are : Insert new elements into the queue and delete elements from the queue . The insert operation is also called team entry , The delete operation is also called out of the queue . The join operation inserts a new element at the end of the team , Delete the element of the head of the team .

image.png
The following code is used to implement the queue

Realization Queue class

dataStore For datasets

class Queue {
    dataStore = []
    constructor() {
    }
}

enqueue() Method to add an element to the end of the queue

enqueue(element) {
        this.dataStore.push(element)
    }

dequeue() Method to delete the element of the team leader

dequeue() {
        return this.dataStore.shift()
    }

You can use the following method to read the elements at the beginning and end of the team

front() {
    return this.dataStore[0]
}
back() {
    return this.dataStore[this.dataStore.length - 1]
}

toString() Method to display all the elements in the queue

toString() {
        return String(this.dataStore)
    }

Determines if the queue is empty

empty() {

        return this.dataStore.length == 0

    }

Completion code

class Queue {
    dataStore = []
    constructor() {

    }
    enqueue(element) {
        this.dataStore.push(element)
    }
    dequeue() {
        return this.dataStore.shift()
    }
    front() {
        return this.dataStore[0]
    }
    back() {
        return this.dataStore[this.dataStore.length - 1]
    }
    toString() {
        return String(this.dataStore)
    }
    empty() {
        return this.dataStore.length == 0
    }
}

Linked list

A linked list is a set of nodes . Each node uses a reference to an object to point to its successors . A reference to another node is called a chain . Identifying the starting node of the linked list is a little troublesome , Therefore, there is a special node at the front of the linked list , It's called the head node

image.png
The designed linked list contains two classes .Node Class to represent a node ,LinkedList Class provides the insertion node 、 Delete node 、 How to display list elements , And other auxiliary methods .

Node class
Nodes contain data and pointers , As shown in the figure below

image.png

  1. element Representative elements
  2. next For the pointer

    class Node {
       constructor(element){
        this.element=element
        this.next=null
       }
    }

    LinkedList class

Create a linked list by default to a head node

class LinkedList {
  constructor(){
    this.head = new Node('head')
  }
}

find() Find a node

// Search from the beginning 
find(item){
    let node = this.head
    while(node&&node.element != item){
      node = node.next
    }
    return node
  }

findPrevious() Find the node before the target

findPrevious(item){
    let node = this.head
    while(node.next&&node.next.element != item){
      node = node.next
    }
    return node.next?node:null
  }

insert() Insert new node

image.png
Inserting a node is to point the pointer of the new element node to the node pointed to by the target element pointer , Again, the pointer of the target node points to the new node

insert(element,item){
    let node = this.find(item)
    if(node){
      let newNode = new Node(element)
      newNode.next =  node.next
      node.next = newNode
    }
  }

remove() Delete a node

image.png
Deleting a node is to point the previous node of the target node to the next node of the target node

remove(item){
    let node = this.findPrevious(item)
    if(node){
      node.next = node.next.next
    }
  }

display() Print linked list

display(){
    let node = this.head
    while(node){
      console.log(node.element)
      node = node.next
    }
  }

Complete code

class Node {
    constructor(element) {
        this.element = element
        this.next = null
    }
}
class LinkedList {
    constructor() {
        this.head = new Node('head')
    }
    find(item) {
        let node = this.head
        while (node && node.element != item) {
            node = node.next
        }
        return node
    }
    findPrevious(item) {
        let node = this.head
        while (node.next && node.next.element != item) {
            node = node.next
        }
        return node.next ? node : null
    }
    insert(element, item) {
        let node = this.find(item)
        if (node) {
            let newNode = new Node(element)
            newNode.next = node.next
            node.next = newNode
        }
    }
    remove(item) {
        let node = this.findPrevious(item)
        if (node) {
            node.next = node.next.next
        }

    }
    display() {
        let node = this.head
        while (node) {
            console.log(node.element)
            node = node.next
        }
    }
}

Double linked list

Although it's easy to traverse from the head node to the tail node of the list , But, in turn, , Traversing from the back to the front is not that easy . By giving Node Object to add an attribute , This property stores links to the precursor node , It's much easier . At this point, it takes more work to insert a node into the linked list , We need to point out the correct precursor and successor of this node . But when you delete a node from the list , Improve the efficiency , There is no need to find the precursor node of the node to be deleted

Node class

The node of the two-way linked list has one more precursor pointer than the node of the one-way linked list previous

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

}

To realize two-way linked list

class DoubleLink{
  constructor(){
    this.head = new Node('head')
  }
}

Find an element

find(item){
    let node = this.head
    while(node&&node.element != item){
      node = node.next
    }
    return node
  }

Find the previous element

findPrevious(item){
    let node = this.head
    while(node.next&&node.next.element != item){
      node = node.next
    }
    return node.next?node:null
  }

Find the last element

findLast(){
    let node = this.head
    while(node.next){
      node = node.next
    }
    return node
  }

Insert an element

image.png
Insert node , In addition to the same operation as one-way linked list , The precursor pointer of the latter node must point to the node to be inserted , The precursor pointer of the inserted node needs to point to the previous node

insert(element,item){
    let node = this.find(item)
    if(node){
      let newNode = new Node(element)
      newNode.previous = node
      if( node.next){
        node.next.previous = newNode
      }
      newNode.next =  node.next
      node.next = newNode
    }
  }

Delete an element

image.png

remove(item){
    let node = this.findPrevious(item)
    if(node){
      if(node.next.next){
        node.next.next.previous = node
      }
      node.next = node.next.next
    }

  }

Print elements

display(){
    let node = this.head
    while(node){
      console.log(node.element)
      node = node.next
    }
  }

Reverse printing linked list

dispReverse(){
    let node = this.findLast()
    while(node){
      console.log(node.element)
      node = node.previous
    }
  }

Complete code

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

class DoubleLink {
    constructor() {
        this.head = new Node('head')
    }
    find(item) {
        let node = this.head
        while (node && node.element != item) {
            node = node.next
        }
        return node
    }
    findPrevious(item) {
        let node = this.head
        while (node.next && node.next.element != item) {
            node = node.next
        }
        return node.next ? node : null
    }
    findLast() {
        let node = this.head
        while (node.next) {
            node = node.next
        }
        return node
    }
    insert(element, item) {
        let node = this.find(item)
        if (node) {
            let newNode = new Node(element)
            newNode.previous = node
            if (node.next) {
                node.next.previous = newNode
            }
            newNode.next = node.next
            node.next = newNode
        }
    }
    remove(item) {
        let node = this.findPrevious(item)
        if (node) {
            if (node.next.next) {
                node.next.next.previous = node
            }
            node.next = node.next.next
        }
    }
    display() {
        let node = this.head
        while (node) {
            console.log(node.element)
            node = node.next
        }
    }
    dispReverse() {
        let node = this.findLast()
        while (node) {
            console.log(node.element)
            node = node.previous
        }
    }
}

copyright notice
author[Ma Luping],Please bring the original link to reprint, thank you.
https://en.cdmana.com/2022/01/202201270239028026.html

Random recommended