Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

What is a linked list?

The data stored in a linked list is ordered, but unlike an array, the elements in a linked list are not placed consecutively. Each element consists of a node that stores the element itself and a reference (also known as a pointer or link) to the next element

The nice thing about a linked list is that you don’t need to move other elements when you add or remove them, but when you want to access an element in the middle of the list, you need to start at the beginning (the header) until you find the element you want

Create a list

function LinkedList() {
    function Node(data) {
        this.data = data
        this.next = null
    }

    / / property
    this.head = null
    this.length = 0
}
Copy the code

Create add method

// Append methods
    LinkedList.prototype.append = function (data) {
        //1 Create a new node
        var newNode = new Node(data)

        //2. Check whether it is the first node
        if (this.length == 0) {
            this.head = newNode
        } else {
            // Find the last node
            var current = this.head
            while (current.next) {
                current = current.next
            }

            // Next of the last node points to the new node
            current.next = newNode
        }

        // The length of the list increases by one
        this.length += 1
    }
Copy the code

Override the toString method

/ / 2. Tostring method
    LinkedList.prototype.toString = function () {
        var current = this.head

        var listString = ""

        while (current) {
            listString += current.data + ""
            current = current.next
        }

        return listString
    }
Copy the code

Inserts elements at specific locations

/ / insert method
    LinkedList.prototype.insert = function (position, data) {
        // Determine if the boundary is crossed
        if (position < 0 || position > this.length) return false

        var newNode = new Node(data)

        if (position == 0) {
            newNode.next = this.head
            this.head = newNode
        } else {
            var index = 0
            var current = this.head
            var previous = null

            while (index++ < position) {
                previous = current
                current = current.next
            }
            newNode.next = current
            previous.next = newNode
        }
    }
Copy the code

Remove elementsRemoveAt method

    LinkedList.prototype.removeAt = function (position) {
        if (position < 0 || position >= this.length) return null

        // Define variables
        var index = 0
        var current = this.head
        var previous = null

        if (position == 0) {
            this.head = current.next
        } else {
            while (index++ < position) {
                previous = current
                current = current.next
            }
            previous.next = current.next
        }
        this.length -= 1
        return current.data
    }
Copy the code

View the list lengthMethod indexOf

    LinkedList.prototype.indexOf = function (position) {
        var index = 0
        var current = this.head

        while (current) {
            if (current.data == position) {
                return index
            }
            index++
            current = current.next
        }

        return -1
    }
Copy the code

Deletes linked lists by element

    LinkedList.prototype.remove = function (position) {
        var index = this.indexOf(position)
        return this.removeAt(index)
    }
Copy the code