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:
|
<<: Solution to uninstalling Python and yum in CentOs system
>>: MySQL paging analysis principle and efficiency improvement
Analyze the production steps: 1. Prepare resource...
What is the reason for the Last_IO_Errno:1236 err...
Table of contents 1. let keyword 1.1 Basic Usage ...
1. Add alternative text to your logo This has two...
Shopify Plus is the enterprise version of the e-c...
This article introduces the sample code of CSS3 t...
When configuring the interface domain name, each ...
First look at the code and effect↓ <style> ...
Table of contents react-native project initializa...
1. Install ffmpeg under centos linux 1. Download ...
Step 1: Install Stow In this example, we are usin...
Using UNION Most SQL queries consist of a single ...
Table of contents Introduction to NFS Service Wha...
Use the rpm installation package to install mysql...
The pagination component is a common component in...