JavaScript data structure and algorithm -- linked list

1. Linked list data structure

A linked list stores an ordered set of elements, but unlike an array, each element in a linked list that is not placed consecutively in memory consists of a node storing the element itself and a reference to the next element. The following figure shows the structure of a linked list:

Advantages of linked list:
Linked list is a very common data structure. It does not need to initialize the capacity and can add or subtract elements at will;
When you add or delete elements, you only need to change the address of the pointer field of the two element nodes before and after, so you can add and delete them quickly;

Disadvantages:
Because it contains a lot of pointer fields, it takes up a lot of space;
It is very time-consuming to search elements by traversing the linked list.

Applicable scenarios:
Scenarios with small amount of data and frequent increase and deletion

2. Create a linked list

function LinkedList() {
    // Create a node class to represent the item to be added element represents the value to be added, and next points to the next node item in the list
    let Node = function(element) {
        this.element = element;
        this.next = null;
    }
    let length = 0;
    let head = null;
    // Here is how to declare the linked list
    // 1. Add a new item to the end of the list
    this.append = function(element) {
        let node = new Node(element);
            current;
        // The list is empty and the first element is added
        if(head === null) {
           head = node; 
        // List is not empty, append to it   
        } else {
           
            current = head;
            // Loop through the list until the last item is found
            while(current.next) {
                current = current.next;
            }
            // Find the last item, assign its next as node, and establish a link
            current.next = node;
        }
        // Update list length
        length++;
    }
    // 2. Remove elements from the list
    this.removeAt = function(position) {
        // Check whether the position is out of the range of linked list
        if(position > -1 && position < length) {
            let current = head,
                previous,
                index = 0;
            // Remove first element
            if(position === 0 ) {
                head = current.next;
            } else {
                // Loop to the specified location to find previous and current
                while(index++ < position) {
                    previous = current;
                    current = current.next;
                }
                // Link previous to the next item in current: skip current
                previous.next = current.next;
            }    
            // Chain length minus one
            length--;
            // Return deleted items
            return current.element;
        } else {
            // Not a valid location, return null
            return null
        }
    }
     // 3. Insert elements anywhere
    this.insert = function(element, position) {
        //Judge whether it is beyond the range of linked list
        if (position >= 0 && position<= length) {
            let node = new Node(element),
                current = head,
                previous,
                index = 0;
            // Insert element first
            if (position === 0 ) {
                node.next = current;
                head = node;
            } else{
                // x loops to the location where the position should be added, taking previous and current
                while(index++ < position) {
                    previous = current;
                    current = current.next;
                }
                // Insert between previous and current
                node.next = current;
                previous.next = node;
            };    
            // Update linked list length
            length++;
            return true;
        } else{
            return false;
        };
    }
    //4. Convert LinkedList object to string
    this.toString = function() {
        let current = head,
            string = '';
        while(current) {
            string += current.element + (current.next ? 'n' : '');
            current = current.next;
        }  
        return string;  
    }
    //5. Whether there is a value in the list
    this.indexOf = function(element) {
        let current = head,
            index = 0;
        while(current) {
            if(element === current.element) {
                return index;
            }
            index++;
            current = current.next;
        }  
        return -1; 
    } 
    //6. Implement remove element through element
    this.remove = function(element) {
        let index = this.indexOf(element);
        return this.removeAt(index);
    }
    //7.isEmpty size getHead method
    this.isEmpty = function() {
        return length === 0; 
    }
    this.size = function() {
        return length;
    }
    this.getHead = function() {
        return head;
    }    
}

Tags: Javascript

Posted on Mon, 02 Dec 2019 04:52:15 -0800 by PnHoPob