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
Scenario 1. Maintain a citizen system with a fiel...
Table of contents Select Structure Loop Structure...
Table of contents 1. What is JSON 1.1 Array liter...
console.log( [] == ![] ) // true console.log( {} ...
The project needs to use MySQL. Since I had alway...
A website uses a lot of HTML5 and CSS3, hoping th...
Error screenshot Can't find where the excepti...
Cascading and Cascading Levels HTML elements are ...
Table of contents 1. Prototype Relationship 2. Pr...
When Mysql occupies too much CPU, where should we...
1. According to the online tutorial, the installa...
This article uses examples to explain the princip...
Try installing via pip in a virtual environment: ...
1. View the types of fields in the table describe...
Preface The essence of deadlock is resource compe...