preface

Above briefly introduced the data structure – using JS to achieve linked list – single linked list; This installment appears as a sequel. Through the implementation of bidirectional linked list to further deepen the list of some concepts and implementation.

Included in the “Advanced Incomplete Guide” coding section is implemented in javascript. The full code is linked at the end

The list

A bidirectional linked list, also known as a doubly linked list, is a type of linked list in which each data node has two Pointers pointing to the direct successor and direct precursor respectively. So, starting from any node in a bidirectional linked list, you can easily access its predecessors and successors. In general, we construct bidirectional circular lists. [Baidu Baike]

List characteristics

  • Use an arbitrary set of memory Spaces to store data elements (either contiguous or discontiguous)
  • Each node is composed of data itself, a pointer to the previous node and a pointer to subsequent nodes
  • Access to the entire list must start with a ab initio pointer, with a head pointer pointing to the first node. The tail pointer ends and points to the last node.

There is no pointer in JS, the pointer of the above node is just a concept borrowed from C language.

List complexity

Time complexity

Access Search Insertion Deletion
O(n) O(n) O(1) O(1)

Spatial complexity

O(n)

Basic operation implementation

The node structure

Class DoublyLinkedListNode {constructor(value, next = null) previous = null) { this.value = value; this.next = next; this.previous = previous; }}Copy the code

List initialization

class DoublyLinkedList { constructor() { this.head = null; this.tail = null; }}Copy the code

Add insert (head and tail)

// Prepend (value) {const newNode = new DoublyLinkedListNode(value, this.head); // Prepend (value) {const newNode = new DoublyLinkedListNode(value, this.head); If (this.head) {this.head. Previous = newNode; if (this.head) {this.head. } this.head = newNode; // If there is no tail node, set the new node to the tail node. this.tail) { this.tail = newNode; } return this; } // add to end appEnd (value) {const newNode = new DoublyLinkedListNode(value); // If there is no head node, set the new node as the head node. // Also the tail node if (! this.head) { this.head = newNode; this.tail = newNode; return this; } // If there are head nodes (and of course there are tail nodes) // Add the head nodes to the end of the list this.tail.next = newNode; Newnode.previous = this.tail; newNode.previous = this.tail; newNode.previous = this.tail; // set the newNode to the end of the list this.tail = newNode; return this; }Copy the code

delete

For the sake of reading experience, some non-critical code is omitted here, you can go to the warehouse to check. A link will follow.

delete(value) { if (! this.head) { return null; } let deletedNode = null; let currentNode = this.head; While (currentNode) {if (currentNode.value === value) {// The repository introduces a comparison JS. The logic is simple: deletedNode = currentNode; //1. What do I need to do if I delete a header node? If (deletedNode === this.head) {// If (deletedNode === this.head) {// If (deletedNode === this.head) {// If (deletedNode === this.head) {// If (deletedNode === this.head) {// If (deletedNode === this.head) {// If (deletedNode === this.head) {// If (deletedNode === this.head) { // Set previous to null this.head = deletedNode.next; // Set previous to null this.head = deletedNode.next; if (this.head) { this.head.previous = null; } if (deletedNode === this.tail) { this.tail = null; }} else if (deletedNode === this.tail) {// If the deletedNode is a tail node, set tail to the penultimate node, which will become the new tail this.tail = deletedNode.previous; this.tail.next = null; } else {// Delete intermediate node const previousNode = deletedNode.previous; const nextNode = deletedNode.next; previousNode.next = nextNode; nextNode.previous = previousNode; } } currentNode = currentNode.next; } return deletedNode; }Copy the code

Traversing the list

The coding implementation part is reflected in the deletion, which can be extracted by itself.

While (){// if the current is not next to the end // if the current is not previous to the head // if the current is not previous to the head. }Copy the code

conclusion

To summarize, a bidirectional linked list is a node that contains the current value, the previous one, and the next one. And then the initialization is head, head,tail. Then add, delete, change and check the infrastructure. When you get to it, it’ll feel easy.

Finally, don’t forget to make connections in the real world.

Other links

The sample code repository above