JavaScript implements single linked list process analysis

Preface:

To store multiple elements, arrays are the most commonly used data structure, but arrays also have many disadvantages:

• The creation of an array usually requires a continuous memory space, and the size is fixed, so when the current array cannot meet the capacity requirements, it needs to be expanded (usually by applying for a larger array and then copying the elements in the original array to it)
• Inserting data at the beginning or middle of an array element is very costly and requires shifting a large number of elements.

So to store multiple elements, another option is a linked list. Unlike an array, the elements in a linked list do not have to be continuous space in memory. Each element of a linked list has a node that stores the element itself and a reference to the next element.
Linked lists have some advantages over arrays:

• The memory space does not have to be continuous, which can make full use of the computer's memory and achieve flexible dynamic memory management.
• Linked lists do not have to be sized when they are created, and can extend indefinitely.
• When inserting and deleting data in a linked list, the event complexity can reach O(1), which is much more efficient than an array.

Linked lists have some disadvantages compared to arrays:

• When accessing an element at any position in a linked list, it is necessary to start from the beginning and the element cannot be accessed directly through the subscript.

1. What is a singly linked list

So what exactly is a singly linked list?

It is like a train, the locomotive is connected to a node, there are passengers on the node, and this node is connected to the next node, and so on, as shown below:

Our linked list structure is:

Now that we understand the intuitive linked list, let's encapsulate the code for the singly linked list.

2. Encapsulation of a singly linked list

First, we encapsulate a NodeList class to represent the linked list structure. In this class, we encapsulate an inner class Node to encapsulate the information on each node (data and a reference to the next node). Then, we save two attributes in NodeList class, one is the length of the linked list, and the other is the head node in the linked list.

As shown below:

 function LinkedList(){
            this.length = 0;
            this.head = null;
            //Internal class function Node(data){
                this.data = data;
                this.next = null;
            }
        }

3. Common operations of singly linked lists

Then add the commonly used operations of singly linked lists. The main ones are:

• 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 length property of the array
• toString() : Since the list item uses the Node class, you need to override the default toString method inherited from JavaScript object to output the value of the element

Next, we will implement them one by one.

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

Because there are two possible situations for adding data to the end of a linked list:

• The linked list itself is empty, and the newly added data is the only node
• The linked list is not empty, and nodes need to be added after other nodes

So we need to make a judgment. If the linked list is empty, directly point the pointer of the head node to the new node.
If the linked list is not empty, create a temporary node, make it equal to the head node, and judge it. If the pointer field of the node it points to is empty, it is the tail node. Add the newly added node to the end, that is, let the pointer of the tail node point to the newly added node. If the pointer field of the node it points to is not empty, let the pointer field of this temporary node point to the next node, and keep looping until the pointer field of this node is empty (that is, the tail node). Then each time you add a node, increase the length of the linked list by 1.

LinkedList.prototype.append = function(data){
                var newNode = new Node(data);
                // Determine whether the linked list is empty // 1. If it is empty if (this.length === 0) {
                    this.head = newNode;
                }else{
                    //Not empty var current = this.head;
                    if(current.next){
                        current = current.next;
                    }
                    current.next = newNode;
                }
                this.length += 1;
            }

2. toString method ----- output the value of the element

This is relatively simple. The main thing is to get each element. Because getting any element of the linked list must start from the first node, we can start from the head node, loop through each node, take out element in it, concatenate it into a string, and return the string.

LinkedList.prototype.toString = function(){
                var current = this.head;
                var ListStr = '';
                while(current){
                    ListStr += current.data + ' ';
                    current = current.next;
                }
                return ListStr;
            }

Verification: Create several new nodes and print

 var list = new LinkedList();
        list.append('a');
        list.append('b');
        list.append('c');
        list.append('d');
        list.append('e');
        alert(list);

The print result is:

3. Insert method ----- insert an item into a specific position in the list

To implement the method of inserting data at any position, first determine whether the insertion position is out of bounds, and then divide it into two cases if it is not out of bounds. If it is inserted into the first position, it means that the newly added node is the head, then the original head node needs to be used as the next of the new node, and then let the head point to the new node. If you insert it to other positions, you need to find the node position through a loop first, and save the previous node and the next node during the loop. After finding the correct position, point Next of the new node to the next node, and point next node of the previous node to the new node.

The code is as follows:

 LinkedList.prototype.insert = function(position,data){
                if(position<0 || position >this.length){
                   return false;
               }
                var newNode = new Node(data);
                var index = 0;
              if(position == 0){
                newNode.next = this.head;
                this.head = newNode;

              }else{
                    while(index++ < position){
                        var current = this.head;
                        var previous = null;
                        previous = current;
                        current = current.next;
                    }
                    newNode.next = current;
                    previous.next = newNode;
                }
                this.length += 1;
                return true;
                }

Verification: Insert xl in the first position and wh in the second position

list.insert(1,'xl')
       list.insert(2,'wh')
        alert(list)

4. Get method-----Get the element at the corresponding position

This method is relatively simple. First, it checks whether positon is out of bounds, then traverses the linked list through temporary nodes until it reaches the target position and obtains the element at that position.

LinkedList.prototype.get = function(position,data){

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

Verification: Get the element at the third position:

alert( list.get(3));

5. indexOf() method ----- returns the index of an element in a list

First determine whether the position of the element being searched exists. If not, return -1. If it exists, there are two cases. If the returned element is in the first position, the index of the first position is returned directly. If the returned element is at another position, you need to find the node position through a loop first. During this process, the index needs to be incremented by the number of traversals. After finding the position of the correct element, the printed index is the target position.

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

Verification: Get the index of c:

alert(list.indexOf('c'));

6. Update method-----Modify the element at a certain position

This method is very similar to the get method. It traverses backwards. When the value of index is equal to position , it means that the target position is found and the date is changed to the target value:

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

Verification: Change the element at position 0 to: bear

 list.update(0,'bear')
      alert(list)

7. removeAt method-----Remove an item from the specified position of the list

First, determine whether the position of the deleted item is out of bounds. Then, if it is not out of bounds, give two temporary nodes previous and current . previous is used to save the value of the previous current . Start traversing from the head node until the index position is equal to the target position. Let the temporary node current traverse to the target position, and let the previous next of the temporary node point to the next next.

LinkedList.prototype.removeAt = function(position,data){
                var current = this.head;
                var previous = null;
                var index = 0;
                if(position<0 || position>=this.length){
                    return false;
                }else{
                    while(index++ <position){
                        previous = currrent;
                        current = current.next;
                    }
                    previous.next = current.next;
                    this.length -= 1;
                    return true;
                }
            }
        }

Verification: Remove the element at the third position:

list.removeAt(3)
      alert(list)

8. Remove method - remove an item from the list

First determine whether the element to be deleted is in the linked list. If not, return false . Otherwise, build a temporary node for traversing the linked list. If the data value of the temporary node is equal to the element to be deleted, stop traversing and let the previous next of the temporary node point to the next next. Here you can build a temporary node to store the previous current value.

LinkedList.prototype.remove = function(ele){
                var current = this.head;
                var previous = null;
                var index = 0;
                while(current.data !== ele){
                    previous = current;
                    current = current.next;
                    index++;
                }
                previous.next = current.next;
            }

Verification: Delete the element with value xl:

 list.remove('xl')
      alert(list)

9. isEmpty method-----determine whether the linked list is empty

According to length judgment, if the linked list does not contain any elements, it returns true, and if the length of the linked list is greater than 0, it returns false

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

verify:

 alert(list.isEmpty())

9. Size method ----- returns the number of elements contained in the linked list

length of the element returned directly is its number.

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

verify:

   alert(list.size())

This is the end of this article about JavaScript implementing single linked list process parsing. For more relevant JavaScript implementing single linked list content, please search 123WORDPRESS.COM’s previous articles or continue to browse the following related articles. I hope everyone will support 123WORDPRESS.COM in the future!