JavaScript implementation linked list

JavaScript implementation linked list

JavaScript implementation of linked lists: using ES6's object-oriented syntax

Linked list: a storage structure of data. A linked list contains several nodes, and each node contains at least one data field and one pointer field

Linked list is a dynamic data structure. Different from array, linked list has the flexibility of allocating memory space. It will not be allocated a continuous memory like array. When you want to insert a new value at any position in the array, you must move the position of each element in the array to achieve the goal. Obviously, the overhead is very large. However, the flexibility of the linked list is that each element node is divided into two parts. One part is the storage element itself, and the other part is the reference to the next node element, which can also be called a pointer. When you want to insert data, point the down pointer of the previous node to the new data node, and the down pointer of the new data node to the original data. However, unlike arrays, linked lists can be located immediately by index, only by traversal.

//Defines the node class of a one-way linked list
class Node {
    constructor(data) {
        this.data = data  //Data field of node
        this.next = null  //Pointer field of node
    }
}

// Define a single Necklace table class
class SingleLinked{
    constructor(){
        this.size = 0  //Used to record the number of nodes in the linked list
        this.head = new Node('head')  //Is the head pointer of the linked list: records the starting address of the linked list
        this.current = ''  //Used to record the current node
    }

    // Get the length of the linked list
    getLength(){
        return this.size;
    }

    // Determine whether the linked list is empty
    isEmpty(){
        return this.size === 0
    }

    // Traverse the linked list: do not repeatedly access each node of the linked list
    displayList() {
        let list = ''
        let current = this.head //Pointer to the head of the linked list
        while(current){  //If the current node is not empty
            list += current.data;
            current = current.next  //Let the pointer point to the next node
            if(current){
                list += '->'
            }
        }
        console.log(list);
    }
    
    // Get the last node of the linked list
    findList() {
        let current = this.head
        while(current.next){
            current = current.next
        }
        return current;
    }

    // Use the tail insertion method to insert elements into the linked list
    appendNode(element){
        let current = this.findList()  //Find the last node of the linked list
        let newNode = new Node(element)  //Create a new node
        current.next = newNode
        newNode.next = null

        this.size++
    }
}

Simple questions of force chain list

83 delete duplicate elements in the sorting linked list

There is a linked list arranged in ascending order. Give you the head node of the linked list. Please delete all duplicate elements so that each element appears only once. Return the result linked list arranged in ascending order.

var deleteDuplicates = function(head) {
    let current = head;
    //Duplicate nodes may exist only when the node pointed to by cur and the subsequent node are not null
    while(current !== null && current.next !== null) {
        if(current.val === current.next.val){ //If the value of the current node is the same as that of the next node
            current.next = current.next.next  //The next node pointer points to the next node of the next node
        }else{
            current = current.next //If not, it is normal
        }
    }
    return head;
};

203 remove linked list elements
Give you a head node of the linked list and an integer val. please delete all nodes in the linked list that meet Node.val == val and return a new head node.

var removeElements = function(head, val) {
    // After deleting a node with the same value, the value may still be the same
    while(head!==null && head.val==val){
        head = head.next
    }
    
    if(head === null){
        return head;
    }
    
    let cur = head;
    // Ensure that there are nodes after the current node
    while(cur.next!==null){
        if(cur.next.val === val){ //If the value of the next node of the current node is the same as the given value
            cur.next = cur.next.next 
        }else{
            cur = cur.next
        }
    }
    return head;
};

Tags: Javascript data structure linked list

Posted by SouThPaw09 on Wed, 22 Sep 2021 21:53:35 +0530