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

How to use CocosCreator to create a shooting game

Analyze the production steps: 1. Prepare resource...

Mysql master-slave synchronization Last_IO_Errno:1236 error solution

What is the reason for the Last_IO_Errno:1236 err...

Based on JavaScript ES new features let and const keywords

Table of contents 1. let keyword 1.1 Basic Usage ...

Example code for implementing 3D text hover effect using CSS3

This article introduces the sample code of CSS3 t...

Nginx operation and maintenance domain name verification method example

When configuring the interface domain name, each ...

Detailed explanation of the basic use of react-navigation6.x routing library

Table of contents react-native project initializa...

Detailed tutorial for installing ffmpeg under Linux

1. Install ffmpeg under centos linux 1. Download ...

How to Easily Remove Source Installed Packages in Linux

Step 1: Install Stow In this example, we are usin...

Detailed explanation of MySQL combined query

Using UNION Most SQL queries consist of a single ...

Install mysql offline using rpm under centos 6.4

Use the rpm installation package to install mysql...

Detailed explanation of how to use JavaScript paging component

The pagination component is a common component in...