JavaScript implements a doubly linked list (code example)

In this article, we will introduce to you how to implement a two-way linked list in JavaScript. We hope it will be helpful to friends in need!

What is a doubly linked list?

In a doubly linked list, each node has a reference to the previous node and the next node. The previous and next start and end nodes should point to null.

Implementation of doubly linked list

We are using the es6 class. In the following code, we create an auxiliary class Node, which contains three attributes data, prev, next.

class Node {

  constructor(data){
    this.data = data; // data
    this.prev = null; // 引用prev节点
    this.next = null; // 引用next节点
  }}

data: The data we need to add to the node.

prev: Reference the previous node.

next: References the next node.

The main algorithm begins

class DoublyLinkedList{

   constructor(){
        this.head = null;
        this.tail = null;
        this.length = null;
  }}

In the above code, we created a DoublyLinkedList class with three properties: head, tail and length.

head: It is the first node in the list.

tail: The last node in the list.

length: How many nodes are there in the list?

Let’s add these functions to our doubly linked list

Push method

Push method helps us add new nodes at the end of the linked list.

push(data){

    const node = new Node(data);

    if(!this.head){
      this.head = node;
      this.tail = node;
    }else{
      node.prev = this.tail;
      this.tail.next = node;
      this.tail = node;

    }

    this.length++;
  }

1. In the above code, we first declare a new variable and call the node constructor.

2. If there is no this.head then this.head and this.tail will become the new nodes we created in step 1.

3. If there is already a node

the new node.prev attribute should be this.tail

this.tail.next should be a new node

Update tail.

4. Increase the length by 1.

pop method

helps us remove the last node from the list.

In a doubly linked list, it is easy to remove the last node from the list because there is a reference to the previous node in the tail attribute.

pop(){

    if(!this.head) return null

    // tail是最后一个节点，因此我们从tail中提取prev属性
    const prevNode = this.tail.prev    
    if(prevNode){
       prevNode.next = null;
       this.tail = prevNode; // 更新tail
    }else{
      // 如果prev属性为null，则表示只有一个节点
      this.head = null;
      this.tail = null;
    }
     this.length--; 
  }

1. In the above code, we first declare a new variable and store the previous attribute of tail.

2. If the previous node is found.

Delete the last node

Update tail.

3. If the previous node is empty, it means there is only one node

this.head and this.tail should be null.

4. Reduce the length by 1.

insertBeginning

insertBeginning method helps us insert a new node at the beginning of the list.

insertBeginning(data){

    // 创建新节点
    const node = new Node(data);

    // 如果没有节点
    if(!this.head) {
      this.head = node;
      this.tail = node;
    }else{
      this.head.prev = node
      node.next = this.head;
      this.head = node;
    }
    // 增加长度
    this.length++;

  }

removeFirst method

The removeFirst method helps us delete the first node from the linked list.

removeFirst(){

    if(!this.head) return null

    // 存储第二个节点
    const node = this.head.next;

    if(node){
     // 删除前一个节点
      node.prev = null
     // 更新head
      this.head = node    
      }else{
      // 只有一个节点，所以我们将head和tail更新为null
      this.head = null
      this.tail = null
    }
     this.length--;

  }

Related recommendations: "javascript tutorial"

The above is the detailed content of JavaScript implements a doubly linked list (code example). For more information, please follow other related articles on the PHP Chinese website!