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

In-depth explanation of MySQL common index and unique index

Scenario 1. Maintain a citizen system with a fiel...

Detailed explanation of JavaScript program loop structure

Table of contents Select Structure Loop Structure...

Json advantages and disadvantages and usage introduction

Table of contents 1. What is JSON 1.1 Array liter...

A little-known JS problem: [] == ![] is true, but {} == !{} is false

console.log( [] == ![] ) // true console.log( {} ...

Detailed tutorial on how to install MySQL 5.7.18 in Linux (CentOS 7) using YUM

The project needs to use MySQL. Since I had alway...

CSS stacking and z-index example code

Cascading and Cascading Levels HTML elements are ...

JavaScript two pictures to understand the prototype chain

Table of contents 1. Prototype Relationship 2. Pr...

Optimization methods when Mysql occupies too high CPU (must read)

When Mysql occupies too much CPU, where should we...

Solve the error of installing VMware Tools on Ubuntu 18.04

1. According to the online tutorial, the installa...

MySql knowledge points: transaction, index, lock principle and usage analysis

This article uses examples to explain the princip...

Mac installation mysqlclient process analysis

Try installing via pip in a virtual environment: ...

Summary of commonly used SQL in MySQL operation tables

1. View the types of fields in the table describe...

MySQL deadlock routine: inconsistent batch insertion order under unique index

Preface The essence of deadlock is resource compe...