This album is based on the video “JavaScript data structures and Algorithms”, the author of this article has the notes, source code, test environment hosted on GitHub, welcome students Star and Fork.

It is recommended that you learn the structure of the directory in order, from the simple to the deep, step by step, easy to figure out the data structure and algorithm.

Unidirectional and bidirectional lists

Singly linked list

  • You can only traverse from beginning to end or from end to end (usually from beginning to end).
  • The process of linking lists is one-way, and the principle is that the previous node has a reference to the next node.
  • One-way lists have an obvious disadvantage: it is easy to get to the next node, but difficult to get back to the previous node. In real development, it is often necessary to go back to the previous node.

Two-way linked list

  • You can traverse from beginning to end, or from end to end.
  • The process of linking lists is two-way. The implementation principle is that a node has both a forward-connected reference and a backward-connected reference.
  • Bidirectional linked list can effectively solve the problems of unidirectional linked list.
  • Disadvantages of bidirectional linked lists:
    • Each time a node is inserted or removed, you need to deal with four references instead of two, which is more difficult to implement.
    • It takes up more memory than a one-way list.
    • However, these disadvantages are minor compared to the convenience of a two-way linked list.

Bidirectional linked list structure

  • Bidirectionally linked lists have a head pointer to the first node and a tail pointer to the last node.
  • Each node consists of three parts: item stores data, prev points to the previous node, and next points to the next node.
  • The prev of the first node of the bidirectional list points to NULL.
  • Next points to NULL on the last node of the bidirectional list.

Common operations for bidirectional linked lists

  • append(element)Appends a new element to the end of the list.
  • insert(position, element)Inserts a new element at the specified position in the linked list.
  • getElement(position)Gets the element at the specified position.
  • indexOf(element)Returns the index of the element in the linked list. Returns -1 if the element is not in the list.
  • update(position, element)Modifies the element at the specified location.
  • removeAt(position)Removes the element at the specified position from the linked list.
  • remove(element)Removes the specified element from the linked list.
  • isEmpty()Returns if the list does not contain any elementstrun, if the list length is greater than 0false.
  • size()Returns the number of elements in the list, and the number of elements in the arraylengthProperties are similar.
  • toString()Because linked list entries use the Node class, we need to override the default inherited from JavaScript objectstoStringMethod to output only the value of the element.
  • forwardString()Returns the forward traversal node as a string.
  • backwordString()Returns the string representation of the node traversed backwards.

Encapsulation of bidirectional linked lists

Create the DoublyLinkedList class

  • The DoublyNode class inherits the Node class of the unidirectional linked listthis.prevProperty that points to the previous node.
  • The DoublyLinkedList class inherits the LinkedList classthis.tailProperty that points to the trailing node.
// The node class of the bidirectional list (inheriting the node class of the unidirectional list)
class DoublyNode extends Node {
  constructor(element) {
    super(element);
    this.prev = null; }}// The bidirectional list class inherits the unidirectional list class
class DoublyLinkedList extends LinkedList {
  constructor() {
    super(a);this.tail = null; }}Copy the code

append(element)

// append(element) Adds a new element to the end of the bidirectional list
/ / rewrite the append ()
append(element) {

// create a bidirectional list node
const newNode = new DoublyNode(element);

// 2
if (this.head === null) {
  this.head = newNode;
  this.tail = newNode;
} else {
  / /!!!!! Unlike a single linked list, there is no loop to find the last node
  // The subtlety
  this.tail.next = newNode;
  newNode.prev = this.tail;
  this.tail = newNode;
}

this.length++;
}
Copy the code

insert(position, element)

// insert(position, data) inserts elements
/ / rewrite the insert ()
insert(position, element) {
    // 1, position is out of bounds
    if (position < 0 || position > this.length) return false;

    // create a new bidirectional list node
    const newNode = new DoublyNode(element);

    // 3. Judge multiple insertions
    if (position === 0) { // Insert at position 0

      if (this.head === null) {
        this.head = newNode;
        this.tail = newNode;
      } else {
        //== // make room for this.head and leave a newNode assignment ==//
        newNode.next = this.head;
        this.head.perv = newNode;
        this.head = newNode; }}else if (position === this.length) { // Insert in the last position

      this.tail.next = newNode;
      newNode.prev = this.tail;
      this.tail = newNode;
    } else { // Insert between 0 and this.length

      let targetIndex = 0;
      let currentNode = this.head;
      let previousNode = null;

      // Find the node to insert
      while (targetIndex++ < position) {
        previousNode = currentNode;
        currentNode = currentNode.next;
      }

      // Switch node information
      previousNode.next = newNode;
      newNode.prev = previousNode;

      newNode.next = currentNode;
      currentNode.prev = newNode;
    }

    this.length++;

    return true;
  }
Copy the code

insert(position, element)

// insert(position, data) inserts elements
/ / rewrite the insert ()
  insert(position, element) {
    // 1, position is out of bounds
    if (position < 0 || position > this.length) return false;

    // create a new bidirectional list node
    const newNode = new DoublyNode(element);

    // 3. Judge multiple insertions
    if (position === 0) { // Insert at position 0

      if (this.head === null) {
        this.head = newNode;
        this.tail = newNode;
      } else {
        //== // make room for this.head and leave a newNode assignment ==//
        newNode.next = this.head;
        this.head.perv = newNode;
        this.head = newNode; }}else if (position === this.length) { // Insert in the last position

      this.tail.next = newNode;
      newNode.prev = this.tail;
      this.tail = newNode;
    } else { // Insert between 0 and this.length

      let targetIndex = 0;
      let currentNode = this.head;
      let previousNode = null;

      // Find the node to insert
      while (targetIndex++ < position) {
        previousNode = currentNode;
        currentNode = currentNode.next;
      }

      // Switch node information
      previousNode.next = newNode;
      newNode.prev = previousNode;

      newNode.next = currentNode;
      currentNode.prev = newNode;
    }

    this.length++;

    return true;
  }
Copy the code

removeAt(position)

  // removeAt() removes the node at the specified location
  / / rewrite the removeAt ()
  removeAt(position) {
    // 1, position is out of bounds
    if (position < 0 || position > this.length - 1) return null;

    // 2, delete elements according to the case
    let currentNode = this.head;
    if (position === 0) { // Delete the first node

      if (this.length === 1) { // There is only one node in the list
        this.head = null;
        this.tail = null;
      } else { // There are multiple nodes in the list
        this.head = this.head.next;
        this.head.prev = null; }}else if (position === this.length - 1) { // Delete the last node

      currentNode = this.tail;
      this.tail.prev.next = null;
      this.tail = this.tail.prev;

    } else { // Delete the number of nodes in 0 ~ this.length -1

      let targetIndex = 0;
      let previousNode = null;
      while (targetIndex++ < position) {
        previousNode = currentNode;
        currentNode = currentNode.next;
      }

      previousNode.next = currentNode.next;
      currentNode.next.perv = previousNode;

    }

    this.length--;
    return currentNode.data;
  }
Copy the code

update(position, data)

  // Update (position, data) Modifies the node at the specified position
  / / rewrite the update ()
  update(position, data) {
    // 1. Delete the node in position
    const result = this.removeAt(position);

    // 2, insert element in position
    this.insert(position, data);
    return result;
  }
Copy the code

forwardToString()

// forwardToString() list data is returned as a string from front to back
  forwardToString() {
    let currentNode = this.head;
    let result = ' ';

    // Iterate over all nodes, concatenating them into strings until the node is null
    while (currentNode) {
      result += currentNode.data + The '-';
      currentNode = currentNode.next;
    }

    return result;
  }
Copy the code

backwardString()

// backwardString() list data is returned as a string from back to front
  backwardString() {
    let currentNode = this.tail;
    let result = ' ';

    // Iterate over all nodes, concatenating them into strings until the node is null
    while (currentNode) {
      result += currentNode.data + The '-';
      currentNode = currentNode.prev;
    }

    return result;
  }
Copy the code

Implementation of other methods

Other approaches to bidirectional lists are implemented by inheriting unidirectional lists.

Complete implementation

class DoublyLinkedList extends LinkedList {
  constructor() {
    super(a);this.tail = null;
  }

  // ------------ common operations on linked lists ------------ //
  // append(element) Adds a new element to the end of the bidirectional list
  / / rewrite the append ()
  append(element) {
    // create a bidirectional list node
    const newNode = new DoublyNode(element);

    // 2
    if (this.head === null) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      / /!!!!! Unlike a single linked list, there is no loop to find the last node
      // The subtlety
      this.tail.next = newNode;
      newNode.prev = this.tail;
      this.tail = newNode;
    }

    this.length++;
  }

  // insert(position, data) inserts elements
  / / rewrite the insert ()
  insert(position, element) {
    // 1, position is out of bounds
    if (position < 0 || position > this.length) return false;

    // create a new bidirectional list node
    const newNode = new DoublyNode(element);

    // 3. Judge multiple insertions
    if (position === 0) {
      // Insert at position 0

      if (this.head === null) {
        this.head = newNode;
        this.tail = newNode;
      } else {
        //== // make room for this.head and leave a newNode assignment ==//
        newNode.next = this.head;
        this.head.perv = newNode;
        this.head = newNode; }}else if (position === this.length) {
      // Insert in the last position

      this.tail.next = newNode;
      newNode.prev = this.tail;
      this.tail = newNode;
    } else {
      // Insert between 0 and this.length

      let targetIndex = 0;
      let currentNode = this.head;
      let previousNode = null;

      // Find the node to insert
      while (targetIndex++ < position) {
        previousNode = currentNode;
        currentNode = currentNode.next;
      }

      // Switch node information
      previousNode.next = newNode;
      newNode.prev = previousNode;

      newNode.next = currentNode;
      currentNode.prev = newNode;
    }

    this.length++;

    return true;
  }

  // getData() inherits a one-way list
  getData(position) {
    return super.getData(position);
  }

  // indexOf() inherits a one-way list
  indexOf(data) {
    return super.indexOf(data);
  }

  // removeAt() removes the node at the specified location
  / / rewrite the removeAt ()
  removeAt(position) {
    // 1, position is out of bounds
    if (position < 0 || position > this.length - 1) return null;

    // 2, delete elements according to the case
    let currentNode = this.head;
    if (position === 0) {
      // Delete the first node

      if (this.length === 1) {
        // There is only one node in the list
        this.head = null;
        this.tail = null;
      } else {
        // There are multiple nodes in the list
        this.head = this.head.next;
        this.head.prev = null; }}else if (position === this.length - 1) {
      // Delete the last node

      currentNode = this.tail;
      this.tail.prev.next = null;
      this.tail = this.tail.prev;
    } else {
      // Delete the number of nodes in 0 ~ this.length -1

      let targetIndex = 0;
      let previousNode = null;
      while (targetIndex++ < position) {
        previousNode = currentNode;
        currentNode = currentNode.next;
      }

      previousNode.next = currentNode.next;
      currentNode.next.perv = previousNode;
    }

    this.length--;
    return currentNode.data;
  }

  // Update (position, data) Modifies the node at the specified position
  / / rewrite the update ()
  update(position, data) {
    // 1. Delete the node in position
    const result = this.removeAt(position);

    // 2, insert element in position
    this.insert(position, data);
    return result;
  }

  // remove(data) remove the node where the specified data resides.
  remove(data) {
    return super.remove(data);
  }

  // isEmpty() checks if the list isEmpty
  isEmpty() {
    return super.isEmpty();
  }

  // size() gets the length of the list
  size() {
    return super.size();
  }

  // forwardToString() list data is returned as a string from front to back
  forwardToString() {
    let currentNode = this.head;
    let result = "";

    // Iterate over all nodes, concatenating them into strings until the node is null
    while (currentNode) {
      result += currentNode.data + "--";
      currentNode = currentNode.next;
    }

    return result;
  }

  // backwardString() list data is returned as a string from back to front
  backwardString() {
    let currentNode = this.tail;
    let result = "";

    // Iterate over all nodes, concatenating them into strings until the node is null
    while (currentNode) {
      result += currentNode.data + "--";
      currentNode = currentNode.prev;
    }

    returnresult; }}Copy the code

The test code

const doublyLinkedList = new DoublyLinkedList();

/ / append () test
doublyLinkedList.append("ZZ");
doublyLinkedList.append("XX");
doublyLinkedList.append("CC");
console.log(doublyLinkedList);

/ / insert () test
doublyLinkedList.insert(0."00");
doublyLinkedList.insert(2."22");
console.log(doublyLinkedList);

/ / getData () test
console.log(doublyLinkedList.getData(1)); //--> ZZ

/ / indexOf () test
console.log(doublyLinkedList.indexOf("XX")); / / -- > 3
console.log(doublyLinkedList);

/ / removeAt () test
doublyLinkedList.removeAt(0);
doublyLinkedList.removeAt(1);
console.log(doublyLinkedList);

/ / update () test
doublyLinkedList.update(0."111111");
console.log(doublyLinkedList);

/ / remove () test
console.log(doublyLinkedList.remove("111111"));
console.log(doublyLinkedList.remove("22222"));
console.log(doublyLinkedList);

/ / forwardToString () test
console.log(doublyLinkedList.forwardToString());

/ / backwardString () test
console.log(doublyLinkedList.backwardString());
Copy the code

If it helps, give the author a thumbs up at ❤️

Album series

  • Learn JavaScript data structures and algorithms from 0
  • Learn JavaScript data structures and algorithms from 0 (2) arrays
  • Learn JavaScript data structures and algorithms from 0 onwards (iii) stack
  • Learn JavaScript data structures and algorithms from 0 (iv) queue
  • Learning JavaScript data structures and algorithms from 0 (5) Priority queue
  • Learning JavaScript data structures and algorithms from 0 (6) one-way linked lists