What is a bidirectional list
A DoublyLinkedList: Also known as a double-linked list, is a type of linked list in which each data node has two Pointers to the next node and the previous node.
Unidirectional and bidirectional lists:
One-way linked list:
- You can only go from the beginning to the end or from the end to the end.
- The connection of nodes is one-way, the principle is that the previous node has a reference to the next node.
- It is easy to get to the next node, but difficult to return to the last node.
Bidirectional linked list:
- You can go from the beginning to the end or you can go from the end to the end.
- The process of node connection is bidirectional. The principle is that this node has a reference to the next node and a reference to the previous node.
Disadvantages of double-linked lists:
- It is cumbersome to operate on four references each time a node is added or removed.
- It takes up more memory than a one-way list
Double linked list structure:
- A bidirectional list has not only a head node to hold references to the first node, but also a tail node to hold references to the last node.
- Each node consists of three parts: data: stores data, next: stores references to the next node, and previous: stores references to the previous node.
- The previous node of the bidirectional list points to NULL, and the next node at the end points to NULL.
The bidirectional linked list is shown below:
The common method of bidirectional linked lists
- Append (data) adds a node to the tail
- Insert (position, data) Specifies the position to insert data
- GetData (position) Gets the list node at the specified position
- IndexOf (data) Finds the index of the data
- RemoveAt (position) Deletes the node at the specified position
- Update (position, data) Modifies the node at the specified position
- Remove (data) Removes the node where the specified data resides (inheriting one-way linked lists)
- IsEmpty () checks whether the list isEmpty
- Size () gets the length of the list
- ForwardToString () list data is returned as a string from front to back
- BackwardString () list data is returned as a string from back to front
ES6 implements a bidirectional linked list structure
- Bidirectional linked list internal node class encapsulation
/ * ** node class* data Indicates the data of the node* next stores a reference to the next node* Previous Holds a reference to the previous node * @class Node * /class Node { data; next = null; previous = null; constructor(data) { this.data = data; } } Copy the code- Bidirectional linked list class encapsulation
class DoublyLinkedList {
length = 0;
// Store a reference to the header head = null;
// Store a reference to the end node tail = null; } Copy the code- Append (data) method implementation
// append(data) adds a node to the tail append(data) {
// 1. Create new list nodes const newNode = new Node(data);
// Appends elements if (this.length === 0) { // If the list is empty this.head = newNode; this.tail = newNode; } else { // Append to the end of the list// The neat thing is that instead of looping around to find the end of the list, there is now a reference to the end node in tail this.tail.next = newNode; newNode.previous = this.tail; this.tail = newNode; } // The length increases this.length++; } Copy the code- Insert (position, data) method implementation
// insert(position, data) Specifies the position to insert data insert(position, data) {
// Determine if the boundary is crossed if (position < 0 || position > this.length) return false;
// Create a new list node const newNode = new Node(data); // Append the list node; Here are some common cases:// 1. The empty list is appended to the header// 2. The linked list has data appended to the header// 3. Append to tail// 4. 0---- append this. Length if (position === 0) { // Append to the header if (this.head === null) { // No data is added to the head of the list this.head = newNode; this.tail = newNode; } else { // The linked list has data added to the header newNode.next = this.head; this.head.previous = newNode; this.head = newNode; } } else if (position === this.length) { // Insert nodes at the end of the list this.tail.next = newNode; newNode.previous = this.tail; this.tail = newNode; } else { // 0 -- this.length is inserted in the middle // Prepare variables lettargetIndex = 0; // The index representing the location of the node let currentNode = this.head; letpreviousNode = null; // represents the previous node // loop to find the node while (targetIndex++ < position) { previousNode = currentNode; currentNode = currentNode.next; } / / insert previousNode.next = newNode; newNode.previous = previousNode; newNode.next = currentNode; currentNode.previous = newNode; } // Increase the length this.length++; return true; } Copy the code- GetData (position) method implementation
// getData(position) gets the list node at the specified position getData(position = 0) {
// Judge out of bounds if (position < 0 || position >= this.length) return false;
// loop to find the location lettargetIndex = 0; // The index representing the location of the node let currentNode = this.head; while (targetIndex++ < position) { currentNode = currentNode.next; } / / return return currentNode.data; } Copy the code- IndexOf (data) method implementation
// indexOf(data) Finds the index corresponding to the data indexOf(data) {
// loop to find data
let targetIndex = 0;
let currentNode = this.head; while (currentNode) { if (data === currentNode.data) { return targetIndex; } currentNode = currentNode.next; targetIndex++; } // Otherwise return -1 return- 1; } Copy the code- RemoveAt (Position) method implementation
// removeAt(position) Deletes the node at the specified position removeAt(position) {
// Determine if the boundary is crossed if (position < 0 || position >= this.length) return false;
let currentNode = this.head;
// Delete according to different circumstances if (position === 0) { // 1. Delete the header if (this.length === 1) { // If the list has only one node this.head = null; this.tail = null; } else { // If the list has more than one node this.head = this.head.next; this.head.previous = null; } } else if (position === this.length) { // Delete the last node of the list this.tail.previous.next = null; this.tail = this.tail.previous; } else { // 0-----this.length let targetIndex = 0; let previousNode = null; // Cycle to find positions while (targetIndex++ < position) { previousNode = currentNode; currentNode = currentNode.next; } / / delete previousNode.next = currentNode.next; currentNode.next.previous = previousNode; } // Length decrement this.length--; return currentNode.data; } Copy the code- Update (position, data) method implementation
// Update (position, data) Modifies the node at the specified position update(position, data) {
// Determine the boundary if (position < 0 || position >= this.length) return false;
// loop to find the location let targetIndex = 0; let currentNode = this.head; while (targetIndex++ < position) { currentNode = currentNode.next; } currentNode.data = data; return currentNode.data; } Copy the code- Remove (data) method implementation
//remove(data) remove the node where the specified data resides.
remove(data) {
return this.removeAt(this.indexOf(data));
}
Copy the code- An implementation of isEmpty()
// isEmpty() checks if the list isEmpty isEmpty() {
return this.length === 0;
}
Copy the code- An implementation of the size() method
// size() gets the length of the list size() {
return this.length;
}
Copy the code- Implementation of the forwardToString() method
// forwardToString() list data is returned as a string from front to back forwardToString() {
let currentNode = this.head;
let result = "";
// Iterate over all nodes, concatenating them into strings until the node is null while (currentNode) { result += currentNode.data + "--"; currentNode = currentNode.next; } return result; } Copy the code- Implementation of the backwardString() method
// backwardString() list data is returned as a string from back to front backwardString() {
let currentNode = this.tail;
let result = "";
// Iterate over all nodes, concatenating them into strings until the node is null while (currentNode) { result += currentNode.data + "--"; currentNode = currentNode.previous; } return result; } Copy the codeBidirectional linked list overall code
class Node {
data;
next = null;
previous = null;
constructor(data) {
this.data = data; } } class DoublyLinkedList { length = 0; // Store a reference to the header head = null; // Store a reference to the end node tail = null; // Two-way linked list method// append(data) adds a node to the tail append(data) { // 1. Create new list nodes const newNode = new Node(data); // Appends elements if (this.length === 0) { // If the list is empty this.head = newNode; this.tail = newNode; } else { // Append to the end of the list// The neat thing is that instead of looping around to find the end of the list, there is now a reference to the end node in tail this.tail.next = newNode; newNode.previous = this.tail; this.tail = newNode; } // The length increases this.length++; } // insert(position, data) Specifies the position to insert data insert(position, data) { // Determine if the boundary is crossed if (position < 0 || position > this.length) return false; // Create a new list node const newNode = new Node(data); // Append the list node; Here are some common cases:// 1. The empty list is appended to the header// 2. The linked list has data appended to the header// 3. Append to tail// 4. 0---- append this. Length if (position === 0) { // Append to the header if (this.head === null) { // No data is added to the head of the list this.head = newNode; this.tail = newNode; } else { // The linked list has data added to the header newNode.next = this.head; this.head.previous = newNode; this.head = newNode; } } else if (position === this.length) { // Insert nodes at the end of the list this.tail.next = newNode; newNode.previous = this.tail; this.tail = newNode; } else { // 0 -- this.length is inserted in the middle // Prepare variables lettargetIndex = 0; // The index representing the location of the node let currentNode = this.head; letpreviousNode = null; // represents the previous node // loop to find the node while (targetIndex++ < position) { previousNode = currentNode; currentNode = currentNode.next; } / / insert previousNode.next = newNode; newNode.previous = previousNode; newNode.next = currentNode; currentNode.previous = newNode; } // Increase the length this.length++; return true; } // getData(position) gets the list node at the specified position getData(position = 0) { // Judge out of bounds if (position < 0 || position >= this.length) return false; // loop to find the location lettargetIndex = 0; // The index representing the location of the node let currentNode = this.head; while (targetIndex++ < position) { currentNode = currentNode.next; } / / return return currentNode.data; } // indexOf(data) Finds the index corresponding to the data indexOf(data) { // loop to find data let targetIndex = 0; let currentNode = this.head; while (currentNode) { if (data === currentNode.data) { return targetIndex; } currentNode = currentNode.next; targetIndex++; } // Otherwise return -1 return- 1; } // removeAt(position) Deletes the node at the specified position removeAt(position) { // Determine if the boundary is crossed if (position < 0 || position >= this.length) return false; let currentNode = this.head; // Delete according to different circumstances if (position === 0) { // 1. Delete the header if (this.length === 1) { // If the list has only one node this.head = null; this.tail = null; } else { // If the list has more than one node this.head = this.head.next; this.head.previous = null; } } else if (position === this.length) { // Delete the last node of the list this.tail.previous.next = null; this.tail = this.tail.previous; } else { // 0-----this.length let targetIndex = 0; let previousNode = null; // Cycle to find positions while (targetIndex++ < position) { previousNode = currentNode; currentNode = currentNode.next; } / / delete previousNode.next = currentNode.next; currentNode.next.previous = previousNode; } // Length decrement this.length--; return currentNode.data; } // Update (position, data) Modifies the node at the specified position update(position, data) { // Determine the boundary if (position < 0 || position >= this.length) return false; // loop to find the location let targetIndex = 0; let currentNode = this.head; while (targetIndex++ < position) { currentNode = currentNode.next; } currentNode.data = data; return currentNode.data; } //remove(data) remove the node where the specified data resides. remove(data) { return this.removeAt(this.indexOf(data)); } // isEmpty() checks if the list isEmpty isEmpty() { return this.length === 0; } // size() gets the length of the list size() { return this.length; } // forwardToString() list data is returned as a string from front to back forwardToString() { let currentNode = this.head; let result = ""; // Iterate over all nodes, concatenating them into strings until the node is null while (currentNode) { result += currentNode.data + "--"; currentNode = currentNode.next; } return result; } // backwardString() list data is returned as a string from back to front backwardString() { let currentNode = this.tail; let result = ""; // Iterate over all nodes, concatenating them into strings until the node is null while (currentNode) { result += currentNode.data + "--"; currentNode = currentNode.previous; } return result; } } Copy the code