LeetCode: Designing Linked Lists II — JavaScript implements bidirectional linked lists

Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.

Last time we used JavaScript to design a single linked list, this time we’re going to design a double linked list, why do we design a double linked list? Since I met The “Quick Hand second Interview” in an interview, I thought I’d post it on my blog as well so that I could have another tidbit of knowledge. In general, it’s one more prev pointer than a single linked list

707. Design linked lists

Design the implementation of linked lists. You can choose to use single or double linked lists. Nodes in a singly linked list should have two attributes: val and next. Val is the value of the current node and next is a pointer/reference to the next node. If you are using a bidirectional linked list, you also need an attribute prev to indicate the last node in the list. Assume that all nodes in the list are 0-index.

Implement these functions in the linked list class:

• get(index): Gets the value of the index node in the list. If the index is invalid, -1 is returned.
• addAtHead(val): Adds a node with the value val before the first element of the list. After insertion, the new node becomes the first node in the linked list.
• addAtTail(val): appends a node with the value val to the last element of the list.
• addAtIndex(index,val): Adds a node with the value val before the index node in the list. If index is equal to the length of the list, the node is appended to the end of the list. If index is greater than the list length, no node will be inserted. If index is less than 0, insert the node in the header.
• deleteAtIndex(index): If index is valid, the index node in the linked list is deleted.

Source: LeetCode link: leetcode-cn.com/problems/de…

1. Define node constructors in a double-linked list

There is an extra pointer prev to the previous node

/** * Node constructor * in the list@param {*} val* /
function ListNode(val) {
  this.val = val;
  this.next = null;
  this.prev = null;
};
Copy the code

2. Initialize data structure MyLinkedList

Different from the idea of designing a single linked list last time, this time we add a pseudo-header and a pseudo-tail to the list, so that we can easily operate. (The previous single-linked list design could do the same thing.)

/** * Initialize your data structure here
var MyLinkedList = function () {
  // Initializes the list length
  this.length = 0;
  // Define a virtual header and a virtual dummy to facilitate subsequent operations
  this.head = new ListNode(0);
  this.tail = new ListNode(0);
  // Establish the initial connection
  this.head.next = this.tail;
  this.tail.prev = this.head;
};
Copy the code

 3. get

Since we have designed a pseudo-header and a pseudo-tail, when we get an element, we can first make a judgment to see whether the index is near the head or the tail, which can improve the efficiency of searching

/** * Get the value of the index-th node in the linked list. If the index is invalid, return -1. * Get the value of the index node in the linked list. If the index is invalid, -1 * is returned@param {number} index
 * @return {number}* /
MyLinkedList.prototype.get = function (index) {
  if (index < 0 || index >= this.length) {
    return -1;
  }


  let current = this.head;
  // If you are close to the head node, start traversing the head node
  if(index + 1 < this.length - index){
    for (let i = 0; i < index + 1; i++) { current = current.next; }}else{
    // If it is close to the tail, start traversal from the tail
    current = this.tail;
    for(let i = 0; i < this.length - index; i++) { current = current.prev; }}return current ? current.val : -1;
};
Copy the code

With pseudo headers and pseudo tails, we can unify our three methods of inserting data

• Find the precursor node to insert the node intoprevNodeAnd successor nodesnextNode. If a node is inserted in a header, its precursor is a dummy header. If a node is inserted at the tail, its successor is a pseudo-tail.
• Add elements by changing the link relationship between the precursor node and its successor.

A uniform procedure for adding an element to a double-linked list

addNode.prev = prevNode;
addNode.next = nextNode;
prevNode.next = addNode;
nextNode.prev = addNode;
Copy the code

4. addAtHead

/** * Add a node of value val before the first element of the linked list. After the insertion, The new node will be the first node of the linked list. * Add a node with the value val before the first element of the linked list. After insertion, the new node will become the first node in the linked list *@param {number} val
 * @return {void}* /
MyLinkedList.prototype.addAtHead = function (val) {
  // Create a new node and pass in the value val
  let addNode = new ListNode(val);
  
  // Find the precursor and the successor
  let prevNode = this.head;
  let nextNode = this.head.next;
  
  // Add a node
  addNode.prev = prevNode;
  addNode.next = nextNode;
  prevNode.next = addNode;
  nextNode.prev = addNode;
  
  // The list length increases
  this.length++;
};

Copy the code

5. addAtTail

/** * Append a node of value val to the last element of the linked list@param {number} val
 * @return {void}* /
MyLinkedList.prototype.addAtTail = function (val) {
  // Create a new tail
  let addNode = new ListNode(val);

  // Find the precursor and the successor
  let prevNode = this.tail.prev;
  let nextNode = this.tail;
  
  // Add a node
  addNode.prev = prevNode;
  addNode.next = nextNode;
  prevNode.next = addNode;
  nextNode.prev = addNode;

  this.length++;
};

Copy the code

6. addAtIndex

/** * Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list,  the node will be appended to the end of linked list. If index is greater than the length, The node will not be inserted. * Add a node with the value val before the index node in the list. * If index is equal to the length of the list, the node is appended to the end of the list. * Nodes will not be inserted if index is greater than the list length. * If index is less than 0, insert the node in the header. *@param {number} index
 * @param {number} val
 * @return {void}* /
MyLinkedList.prototype.addAtIndex = function (index, val) {
  if (index <= 0) return this.addAtHead(val);
  if (index === this.length) return this.addAtTail(val);
  if (index > this.length) return;

  let addNode = new ListNode(val);


  // Find the precursor and the successor
  let prevNode = null;
  let nextNode = null;
  
  if(index < this.length - index){
    prevNode = this.head;
    for(let i = 0; i < index; i++){
      prevNode = prevNode.next;
    }
    nextNode = prevNode.next;
  }else{
    nextNode = this.tail;
    for(let i = 0; i < this.length - index; i++){
      nextNode = nextNode.prev
    }
    prevNode = nextNode.prev
  }

  // Add a node
  addNode.prev = prevNode;
  addNode.next = nextNode;
  prevNode.next = addNode;
  nextNode.prev = addNode;

  this.length++;
};
Copy the code

7. deleteAtIndex

• Find the precursor of the node to deleteprevNodeAnd successor nodesnextNode.
• Remove elements by changing the link relationship between the precursor node and its successor.

Key steps

prevNode.next = nextNode;
nextNode.prev = prevNode;
Copy the code

/**
 * Delete the index-th node in the linked list, if the index is valid.
 * @param {number} index
 * @return {void}* /
MyLinkedList.prototype.deleteAtIndex = function (index) {
  if (index < 0 || index >= this.length) return;
  
  // Find the precursor and the successor
  let prevNode = null;
  let nextNode = null;
  
  if(index < this.length - index) {
    prevNode = this.head;
    for(let i = 0; i < index; i++){
      prevNode = prevNode.next;
    }
    nextNode = prevNode.next.next;
  }else{
    nextNode = this.tail;
    for(let i = 0; i < this.length - index - 1; i++){
      nextNode = nextNode.prev;
    }
    prevNode = nextNode.prev.prev;
  }
  
  // Delete operation
  prevNode.next = nextNode;
  nextNode.prev = prevNode;

  this.length--;
};
Copy the code

The results

Class version

class ListNode {
  constructor(val) {
    this.val = val;
    this.next = null;
    this.prev = null; }}class MyLinkedList {
  constructor() {
    this.length = 0;

    this.head = new ListNode(0);
    this.tail = new ListNode(0);

    this.head.next = this.tail;
    this.tail.prev = this.head;
  }
  get(index) {
    if (index < 0 || index >= this.length) {
      return -1;
    }

    let current = this.head;
    // If you are close to the head node, start traversing the head node
    if (index + 1 < this.length - index) {
      for (let i = 0; i < index + 1; i++) { current = current.next; }}else {
      // If it is close to the tail, start traversal from the tail
      current = this.tail;
      for (let i = 0; i < this.length - index; i++) { current = current.prev; }}return current ? current.val : -1;
  }
  addAtHead(val) {
    // Create a new node and pass in the value val
    let addNode = new ListNode(val);

    // Find the precursor and the successor
    let prevNode = this.head;
    let nextNode = this.head.next;

    // Add a node
    addNode.prev = prevNode;
    addNode.next = nextNode;
    prevNode.next = addNode;
    nextNode.prev = addNode;

    // The list length increases
    this.length++;
  }
  addAtTail(val) {
    // Create a new tail
    let addNode = new ListNode(val);

    // Find the precursor and the successor
    let prevNode = this.tail.prev;
    let nextNode = this.tail;

    // Add a node
    addNode.prev = prevNode;
    addNode.next = nextNode;
    prevNode.next = addNode;
    nextNode.prev = addNode;

    this.length++;
  }
  addAtIndex(index, val) {
    if (index <= 0) return this.addAtHead(val);
    if (index === this.length) return this.addAtTail(val);
    if (index > this.length) return;

    let addNode = new ListNode(val);

    // Find the precursor and the successor
    let prevNode = null;
    let nextNode = null;

    if (index < this.length - index) {
      prevNode = this.head;
      for (let i = 0; i < index; i++) {
        prevNode = prevNode.next;
      }
      nextNode = prevNode.next;
    } else {
      nextNode = this.tail;
      for (let i = 0; i < this.length - index; i++) {
        nextNode = nextNode.prev;
      }
      prevNode = nextNode.prev;
    }

    // Add a node
    addNode.prev = prevNode;
    addNode.next = nextNode;
    prevNode.next = addNode;
    nextNode.prev = addNode;

    this.length++;
  }
  deleteAtIndex(index) {
    if (index < 0 || index >= this.length) return;

    // Find the precursor and the successor
    let prevNode = null;
    let nextNode = null;

    if (index < this.length - index) {
      prevNode = this.head;
      for (let i = 0; i < index; i++) {
        prevNode = prevNode.next;
      }
      nextNode = prevNode.next.next;
    } else {
      nextNode = this.tail;
      for (let i = 0; i < this.length - index - 1; i++) {
        nextNode = nextNode.prev;
      }
      prevNode = nextNode.prev.prev;
    }

    // Delete operation
    prevNode.next = nextNode;
    nextNode.prev = prevNode;

    this.length--; }}Copy the code