Data structure learning: using JavaScript to implement linked list operations (detailed examples)

This article brings you relevant knowledge about how to use JavaScript to implement linked lists in data structure learning. I hope it will be helpful to you.

The linked list has the following characteristics:

• The space can be dynamically expanded (in js, the same is true for arrays , but the length of the array in some languages ​​is fixed and cannot be added dynamically, such as c language)

• Requires a head node

• Requires Know the address of the next node

Each node in the linked list can be regarded as an object. This object has two attributes, one is the value of the node, and one is the address of the next node of the node (if it is a double linked list, add the attribute of the previous node address)

To implement the operation of adding nodes:

1 Add a node at the tail node

 //在尾节点处添加节点
        function append(element){
        let node = new node(element);
        let current;
        if(head == null){
            current = node
        }else{
            while(current.next){
                current = current.next;
            }
            current.next = node
        }
            length++;
        }

Code analysis:

• Define a node based on the incoming element, This element is used as the value of this node
• Define a variable to represent the current node
• Determine whether it contains a head node. If there is no head node, it means that there is no value in the linked list, and the value passed in will be As the head node; otherwise, traverse the linked list, find the last node, and assign its next attribute to the new node
• The length of the linked list 1

2. At any position Add node

Analysis:

Assign the next attribute of the previous node at this position to this node, save its original next node, and assign it to Now the next attribute of this node

function insert(position,element){
        let node = new Node(element);
        let current = head;
        let previous;//当前节点的前一个节点，在position处添加节点，就是在previos和current之间添加
        if(position = 0){
          node.next = head;
          head = node;
        }else{
          for(let i = 0;i< position;i++){
            pervious = current;
            current = current.next;
          }

          pervious.next = node;
          node.next = current;
        }
        length++;
        return true;
      }

Code analysis:

• Check whether the postion is out of bounds, if not, create a node
• Define a variable to represent the current Node, initialized as the head node, means traversing from the head node; a variable represents the previous node of the current node, which is used to facilitate finding the previous node when inserting the node.
• Determine whether to add it before the head node, and if so, Assign the head node to the next attribute of node, and change the head node to this node; otherwise, traverse the node at this position and insert the node in front of the node at this position
• Length of the linked list 1

Realize the operation of deleting a node

#Analysis: The operation of deleting a node is to delete the node before the target node. The pointer points to the node after the target node

1. Delete the specified node

function removed(element){
    
      let node = new Node(element);
      let pervious;
      let nextNode;
      let current = head;

    if(head != null){
      while (current != node){
        pervious = current;
        current = current.next;
        nextNode = current.next;
      }  

      pervious.next = nextNode;
      length--;
      return true;
    }else{
      return false;
    }    
    }

2. Delete the node at the specified position

function removedAt(position){
        let current = head;
        let pervious;
        let nextNode;
        let i = 0;

        while(i < position){
          pervious = current;
          current = current.next;
          nextNode = current.next;
        }

        pervious.next = nextNode;
        length--;
        return true;
      }

Implement the operation of querying the node

Analysis: Querying nodes is similar to deleting nodes. They both traverse to find the corresponding node or the corresponding location, and then perform the operation

1.Query which node a certain position is

function searchElement(element){
      //输入元素，找到该元素后返回该元素的位置
      if(head != null){
        let node = new Node(element);
        let current;
        let index = 0;
        if(head == node){
          return 0;
        }else{
          current = head;
          while(current != node){
            current = current.next;
            index++;
          }
          return index;
        }
      }else{
        return -1;
      }
    }

2. Query which position a certain node is

function searchPosition(position){
        let i = 0;
        let current = head;
        while(i< position){
          current = current.next;
          i++;
        }
        return current;
    }

Summary of ideas

There are many operations on linked lists, which are a bit more complicated. The linked lists also include double linked lists (adding a previous node when initializing the node) and circular linked lists (the next node of the tail node is the head node). The operations of these linked lists can also be implemented using js, so I won’t go into details here. To sum up, the core of the linked list is that

• The node in the linked list can be regarded as an object with two attribute values, one is the node value and the other is the pointer
• The addition and deletion of the linked list is the change When the pointer points to the
• linked list search, the focus is current = current.next

[Related recommendations: javascript learning tutorial]

The above is the detailed content of Data structure learning: using JavaScript to implement linked list operations (detailed examples). For more information, please follow other related articles on the PHP Chinese website!