JavaScript implements bidirectional linked list process analysis

1. What is a doubly linked list

We know that a singly linked list can only be traversed from the beginning to the end or from the end to the beginning (generally from the beginning to the end), that is, the process of connecting the linked lists is one-way, and the implementation principle is that there is a reference in the previous linked list pointing to the next one. It has a more obvious disadvantage:

We can easily reach the next node, but it is difficult to return to the previous node. However, in actual development, we often encounter situations where we need to return to the previous node, so a bidirectional linked list is needed here.

The so-called doubly linked list is a linked list that can be traversed from the beginning to the end and from the end to the beginning. However, the doubly linked list also has disadvantages. For example, each time a node is inserted or deleted, four node references need to be processed instead of two. Compared with a single linked list, it takes up more memory. However, these disadvantages are negligible compared to the convenience of our use.
Let's take a look at the structure diagram of a doubly linked list. As shown below:

Features of a doubly linked list:

• You can use a head and a tail to point to the head and tail nodes respectively.
• Each node consists of three parts: the pointer to the previous node (prev), the saved element (data), and the pointer to the next node (next)
• The prev of the first node of a doubly linked list is null
• The next of the last node of a doubly linked list is null

We can abstract it as:

Knowing the structure of a doubly linked list, let's take a look at the encapsulation of a doubly linked list.

2. Encapsulation of a doubly linked list

First, we encapsulate a DoublyLinkedList class to represent the linked list structure. In this class, we encapsulate an inner class Node to encapsulate the information on each node (reference to the previous node, data and reference to the next node). Then we save three attributes in Node class, one is the length of the linked list, one is the head node in the linked list, and one is the tail node of the linked list. As shown below:

function DoublyLinkedList(){
	 this.head = null;
	 this.tail = null;
	 this.length = 0;
	 function Node(data){
		 this.data = data;
		 this.prev = null;
		 this.next = null;
	}
 

3. Common operations of bidirectional linked lists

Then you can add common operations for bidirectional linked lists:

append（element : add an item to the end of the list

insert(position,element) : insert an item into a specific position in a list

get(position) : Get the element at the corresponding position

indexOf(element) : Returns the index of an element in the list, or -1 if the element does not exist in the list

update(position，ele) : modify the element at a certain position

removeAt(position) : Remove an item from the specified position in the list

remove(element) : remove an item from the list

isEmpty() : Returns true if the linked list does not contain any elements, and returns false if the linked list length is greater than 0

size() : Returns the number of elements in the linked list, which is related to the length property of the array

toString() : Since the list item uses the Node class, you need to override the default toString method inherited from the JavaScript object to output the value of the element

forwardString() : Returns the node string form of the forward traversal

backwardString() : Returns the string form of the node traversed in reverse

Next, we will implement them one by one.

1. append(element) method-----add an item to the end of the list

This method is similar to the singly linked list method. First, create a new list and then determine whether the linked list is empty. If it is empty, directly let the head of the linked list point to the newly created linked list. If it is not empty, let the predecessor pointer of the new node point to the end of the linked list, and the node at the end of the linked list points to the new linked list.

Doubly.prototype.append = function(data){
                var newNode = new Node(data);
                if(this.length == 0){
                    this.head = newNode;
                }else{
                    newNode.prev = this.tail;
                    this.tail.next = newNode;
                    }
                this.tail = newNode;
                this.length += 1;
            }

2. Convert the linked list into a string

1. toString(): output the value of the element in the forward direction

This method is mainly used to obtain each element. By default, any element of the linked list must start from the first node, so we can start from the head node, loop through each node, take out the element, concatenate it into a string, and return the string. The specific method is to create a temporary node current , let this temporary node point to the head of the doubly linked list, and then traverse backwards in sequence through the next pointer, splicing the data obtained from each traversal.

DoublyLinkedList.prototype.tostring = function(){
                var current = this.head;
                var str = '';
                while(current){
                    str += current.data + ' ';
                    current = current.next;
                }
               return str;
            }

2. forwardString(): Returns the node string form of the forward traversal

This method also implements the forward printing and output of a bidirectional linked list, so we can directly call the previous method here:

DoublyLinkedList.prototype.forwardString = function(){
               return this.toString()
            }

3. backwardString(): Returns the node string form of the reverse traversal

This method mainly traverses from back to front to get each element and print it, so we can start from the tail node, loop through each node, take out the element, concatenate it into a string, and return the string. The specific method is to create a temporary node current , let this temporary node point to the tail of the doubly linked list, and then traverse forward in sequence through the prev pointer, splicing the data obtained from each traversal.

 DoublyLinkedList.prototype.backwardString = function(){
                var current = this.tail;
                var str = '';
                //Traverse forward in sequence and get each node while(current){
                    str += current.data +' ';
                    current = current.prev;
                }
                return str;
            }

verify:

For example, we use append() method to create a doubly linked list containing three data, and then concatenate them forward and backward respectively:

var list = new DoublyLinkedList();
         list.append("a");
         list.append("b");
         list.append("c");
         list.append("d");
         console.log('toString() method: ' + list.toString());
         console.log('forwardString() method: '+list.forwardString());
         console.log('backwardString() method: ' + list.backwardString());

The print result is:

Verification successful.

3. insert(position,element): insert an item into a specific position in a list

This method is relatively complicated. First, determine whether the position to be inserted is out of bounds. If it is not out of bounds, judge according to the situation of the linked list. If the linked list is empty, the inserted node is the first element, and the pointers of the head node and the tail node are directly pointed to the newly created node; if the linked list is not empty, there are three situations for the insertion position: insert at the first position, insert at the end, and insert in the middle. The specific operations are as follows:

DoublyLinkedList.prototype.insert = function(position,data){
        var newNode = new Node(data);
         //Out-of-bounds judgment, if not satisfied, return false
         if(position<0 || position>this.length){
             return false;
         }else{
             //Judge again//If the linked list is empty, insert directly if(position==0){
                 this.head = newNode;
                 this.tail = newNode;
             }else {
             //If the linked list is not empty //If the insertion position is at the end if(position == this.length){
                     this.tail.next = newNode;
                     newNode.prev = this.tail;
                     this.tail = newNode;
                 }else if(position == 0){
                     //If the insertion position is the first node this.head.prev = newNode;
                     newNode.next = this.head;
                     this.head = newNode;
                 }else{
                     //If the insertion position is in the middle var index = 0;
                     var current = this.head;
                     while(index++ <position){
                         current = current.next;
                     }
                         newNode.next = current;
                         newNode.prev = current.prev;
                         current.prev.next = newNode;
                         current.prev = newNode;
                 
             }
             this.length += 1;
         }
        
     }
 }

Verification: If you insert xl at position 1, as shown below:

list.insert(1,'xl')
console.log(list.toString());

The running results are:

Verification successful.

4. get(position): Get the element at the corresponding position

This method first determines whether the position is out of bounds. If it is not out of bounds, a temporary node and index are defined, and the pointer of the temporary node is made to point to the head node. The temporary node is traversed, and the index is incremented. If the position of the traversed node is equal to the position of the element to be obtained, the element at the corresponding position of the temporary node is the element to be obtained.

DoublyLinkedList.prototype.get = function(position){
        
        if(position<0 || position>=this.length){
            return false;
        }else{
            var index = 0;
            var current = this.head;
            while(index++ <position){
                current = current.next;
            }
            return current.data;
        }
    }

Verification: Query the element with position = 2

console.log('list.get(2):'+list.get(2));

The result is:

Verification successful.

However, this search method has a disadvantage, that is, it can only search from front to back, which will be very inefficient in some cases, so we can search from both ends. The specific search method is: when the position of the node we want to find is less than or equal to half the length of the linked list, we can search from front to back. If the position of the node to be found is greater than half the length, we search from back to front. The implementation code is:

    DoublyLinkedList.prototype.get = function(position){
        
        if(position<0 || position>=this.length){
            return false;
        }else{
            var len = Math.floor(this.length/2);
            if(position<=len){
                var index = 0;
                var current = this.head;
                while(index++ <position){
                 current = current.next;
                }
            }else{
                var index = this.length-1;
                var current = this.tail;
                while(index->position){
                    current = current.prev;
                }
            }
            return current.data;
        }
    }

5. indexOf(element): returns the index of the element in the list

Create a temporary node and index, let the temporary node point to the head node, traverse backwards in sequence, and let the index increase. If the element obtained by the traversed temporary node is equal to the element we specified, then the position of the temporary node at this time is our target position, and the index of this position is the index of the target value.

DoublyLinkedList.prototype.indexOf = function(data){
        var current = this.head;
        var index = 0;
        while(current){
            if (current.data === data) {
            return index;
         }
         current = current.next;
         index++;
        }
        return -1;
    }

Verification successful.

6. update(position, ele): modify the element at a certain position

First, determine whether the position to be modified is out of bounds. If it is not out of bounds, define a temporary node and index, let the temporary node point to the head node, the index position is 0, traverse the temporary node and determine whether the index of the temporary node at this time is equal to the position of the element to be modified. If they are equal, the position of the temporary node at this time is the position of the element to be modified, and the element can be directly changed in the data domain of the temporary node.

DoublyLinkedList.prototype.update = function(position,newData){
        if(position<0 || position>=this.length){
            return false;
        }else{
            var index = 0;
            var current = this.head;
            while(index++ <position){
                current = curent.next;
            }
            current.data = newData;
            return true;
        }
    }

Verification: Replace the data at position 0 rc

list.update(0,'rc')
       console.log("list.update(0,'rc') is:");
       console.log(list.toString());

Verification successful.

7. removeAt(position): remove an item from the specified position of the list

This method is similar to the insert() method in that it first determines whether it has crossed the bounds. If it has not crossed the bounds, and if there is only one node in the linked list, the item is removed directly, so that both the head node and the tail node of the linked list point to empty. If the linked list has multiple nodes, it can be divided into three cases, and the operations are as follows:

DoublyLinkedList.prototype.removeAt = function(position){
        if(position<0 || position>=this.length){
            return null;
        }else{
            var current = this.head;
            if(this.length === 1){
            //The length of the linked list is 1
                this.head = null;
                this.tail = null
            }else{//The length of the linked list is not 1
                if(position === 0){
                //Delete the first place this.head.next.prev = null;
                    this.head = this.head.next;
                }else if(position === this.length-1){
                    this.tail.prev.next = null;
                    this.tail = this.tail.prev;
                }else{
                    var index = 0;
                    while(index++ <position){
                        current = current.next;
                    }
                    current.prev.next = current.next;
                    current.next.pre = current.prev;
                }
            }
            this.length -=1;
            return current.data;
        }
    }

Verification: Delete the data at position 3:

list.removeAt(3)
       console.log("list.removeAt(3) is:");
       console.log(list.toString());

The result is:

Verification Success

8. remove(element): remove an item from a list

You can directly get the position of an element in the linked list according to indexOf(element) method, and then delete it according to removeAt(position) method.

 DoublyLinkedList.prototype.remove = function(data){
        var index = this.indexOf(data);
        return this.removeAt(index);
    }

Verification: Delete the node whose data is rc :

list.remove('rc');
       console.log("list.remove('rc') is:");
       console.log(list.toString());

9. isEmpty(): Determine whether the linked list is empty

Directly determine whether the number of elements in the linked list is zero. If it is zero, it is empty and returns true. Otherwise, it is not empty and returns false.

DoublyLinkedList.prototype.isEmpty = function(){
        return this.length == 0;
    }
    

verify:

console.log("Is the linked list empty: "+list.isEmpty());     

10. size(): Returns the number of elements contained in the linked list

The length of a linked list is the number of elements.

DoublyLinkedList.prototype.size = function(){
        return this.length;
    }

verify:

 console.log("The number of elements in the linked list is: "+list.size());

The above is the details of JavaScript's implementation of the bidirectional linked list process analysis. For more information about JavaScript's bidirectional linked list, please pay attention to other related articles on 123WORDPRESS.COM!