JavaScript data structure bidirectional linked list

JavaScript data structure bidirectional linked list

A singly linked list can only be traversed from the beginning to the end or from the end to the beginning; so a singly linked list can easily reach the next node, but it is difficult to return to the previous node.

A bidirectional linked list can be traversed from the beginning to the end, and from the end to the beginning. The connection of the linked list is bidirectional. A node has both forward-connected references and backward-connected references.

But because of this, when inserting or deleting a node, the doubly linked list needs to process the references of four nodes, and the memory space occupied is also larger.

Doubly linked list implementation

JavaScript code to implement a doubly linked list

// Create a doubly linked list constructor function DoublyLinkedList() {
 // Create a node constructor function Node(element) {
  this.element = element
  this.next = null
  this.prev = null // Newly added}

 // Define the property this.length = 0
 this.head = null
 this.tail = null // Newly added // Define related operation methods // Append data at the tail DoublyLinkedList.prototype.append = function (element) {
  // 1. Create a node based on the element var newNode = new Node(element)

  // 2. Determine whether the list is an empty list if (this.head == null) {
   this.head = newNode
   this.tail = newNode
  } else {
   this.tail.next = newNode
   newNode.prev = this.tail
   this.tail = newNode
  }

  // 3.length+1
  this.length++
 }

 //Insert data at any position DoublyLinkedList.prototype.insert = function (position, element) {
  // 1. Determine the problem of out-of-bounds if (position < 0 || position > this.length) return false

  // 2. Create a new node var newNode = new Node(element)

  // 3. Determine the insertion position if (position === 0) { // Insert data at the first position // Determine whether the linked list is empty if (this.head == null) {
    this.head = newNode
    this.tail = newNode
   } else {
    this.head.prev = newNode
    newNode.next = this.head
    this.head = newNode
   }
  } else if (position === this.length) { // Insert to the end // Think: In this case, do we need to check if the linked list is empty? The answer is no, why?
   this.tail.next = newNode
   newNode.prev = this.tail
   this.tail = newNode
  } else { // Insert data in the middle // Define attribute var index = 0
   var current = this.head
   var previous = null

   // Find the correct position while (index++ < position) {
    previous = current
    current = current.next
   }

   //Exchange the pointing order of nodes newNode.next = current
   newNode.prev = previous
   current.prev = newNode
   previous.next = newNode
  }

  // 4.length+1
  this.length++

  return true
 }

 // Delete the corresponding element according to the position DoublyLinkedList.prototype.removeAt = function (position) {
  // 1. Determine the problem of out-of-bounds if (position < 0 || position >= this.length) return null

  // 2. Determine the location to be removed var current = this.head
  if (position === 0) {
   if (this.length == 1) {
    this.head = null
    this.tail = null
   } else {
    this.head = this.head.next
    this.head.prev = null
   }
  } else if (position === this.length -1) {
   current = this.tail
   this.tail = this.tail.prev
   this.tail.next = null
  } else {
   var index = 0
   var previous = null

   while (index++ < position) {
    previous = current
    current = current.next
   }

   previous.next = current.next
   current.next.prev = previous
  }

  // 3.length-1
  this.length--

  return current.element
 }

 // Get the position of the element in the linked list DoublyLinkedList.prototype.indexOf = function (element) {
  // 1. Define variables to save information var current = this.head
  var index = 0

  // 2. Find the correct information while (current) {
   if (current.element === element) {
    return index
   }
   index++
   current = current.next
  }

  // 3. If it is not found at this position, return -1
  return -1
 }

 // Delete according to the element DoublyLinkedList.prototype.remove = function (element) {
  var index = this.indexOf(element)
  return this.removeAt(index)
 }

 // Check if it is empty DoublyLinkedList.prototype.isEmpty = function () {
  return this.length === 0
 }

 // Get the length of the linked list DoublyLinkedList.prototype.size = function () {
  return this.length
 }

 // Get the first element DoublyLinkedList.prototype.getHead = function () {
  return this.head.element
 }

 // Get the last element DoublyLinkedList.prototype.getTail = function () {
  return this.tail.element
 }

 // Implementation of traversal method // Forward traversal method DoublyLinkedList.prototype.forwardString = function () {
  var current = this.head
  var forwardStr = ""

  while (current) {
   forwardStr += "," + current.element
   current = current.next
  }

  return forwardStr.slice(1)
 }

 // Reverse traversal method DoublyLinkedList.prototype.reverseString = function () {
  var current = this.tail
  var reverseStr = ""

  while (current) {
   reverseStr += "," + current.element
   current = current.prev
  }

  return reverseStr.slice(1)
 }

 // Implement the toString method DoublyLinkedList.prototype.toString = function () {
  return this.forwardString()
 }
}

The above is the full content of this article. I hope it will be helpful for everyone’s study. I also hope that everyone will support 123WORDPRESS.COM.

You may also be interested in:
  • Four methods of using JS to determine data types
  • Examples of correct judgment methods for data types in JS
  • Detailed explanation of JavaScript primitive data type Symbol
  • Detailed explanation of JavaScript data types
  • This article takes you into the world of js data types and data structures

<<:  Solution to uninstalling Python and yum in CentOs system

>>:  MySQL paging analysis principle and efficiency improvement

Recommend

Vue achieves the top effect through v-show

html <div class="totop" v-show="...

Teach you how to use vscode to build a react-native development environment

question The code has no prompt: Many non-front-e...

jQuery implements breathing carousel

This article shares the specific code of jQuery t...

Summary of MySQL logical backup and recovery testing

Table of contents 1. What kind of backup is a dat...

Interpretation of the module for load balancing using nginx

Table of contents Two modules for using nginx for...

Solve the black screen problem after VMware installs Linux system and starts

1. Installation environment 1. HUAWEI mate x cpu ...

Design Reference Beautiful and Original Blog Design

All blogs listed below are original and uniquely ...

CentOS 8 installation diagram (super detailed tutorial)

CentOS 8 is officially released! CentOS fully com...

Detailed tutorial on installing Protobuf 3 on Ubuntu

When to install If you use the protoc command and...

6 Uncommon HTML Tags

First: <abbr> or <acronym> These two s...

How to configure Nginx domain name rewriting and wildcard domain name resolution

This article introduces how to configure Nginx to...

MySQL 5.7.20 free installation version configuration method graphic tutorial

I have seen many relevant tutorials on the Intern...

A simple way to restart QT application in embedded Linux (based on QT4.8 qws)

Application software generally has such business ...