/ javascript

How To Create A Singly Linked List In JavaScript

Linked Lists are relatively common and simple data structures that allow us to 'link'/chain data together. Linked Lists are useful for insertion/deletion (time complexity of O(1)), but are unfortunately not incredibly efficient when it comes to access and search (time complexity of O(n)).

The core idea behind a linked list is that you have nodes that contain two pieces of information:

  • The data itself
  • A pointer towards the next piece of data

The pointer is what chains the pieces of data together and creates the linked list.

There are two main types of Linked Lists, singly linked lists, and doubly linked lists. We will go over the singly linked list below and will tackle the doubly linked list in a later article.

function LinkedList() {
    let Node = function(element) {
        this.element = element
        this.next = null
    }
    let head = null
    let length = 0
    this.append = function(element) {
        let node = new Node(element)
        let current
        if (!head) {
            head = node
        } else {
            current = head
            while (current.next) {
                current = current.next
            }
            current.next = node
        }
        length++
    }
    this.removeAt = function(position) {
        if (position > -1 && position < length) {
            let current = head,
                previous,
                index = 0
            if (position === 0) {
                head = current.next
            } else {
                while (index++ < position) {
                    previous = current
                    current = current.next
                }
                previous.next = current.next
            }
            length--
            return current.element
        } else {
            return null
        }
    }
    this.insert = function(position, element) {
        let node = new Node(element)
        if (position >= 0 && position <= length) {
            let current = head,
                previous,
                index = 0
            if (position === 0) {
                node.next = current
                head = node
            } else {
                while (index++ < position) {
                    previous = current
                    current = current.next
                }
                previous.next = node
                node.next = current
            }
            length++
            return true
        } else {
            return false
        }
    }
    this.toString = function() {
        let current = head
        let string = ''
        while (current) {
            string += current.element + (current.next ? 'n' : '')
            current = current.next
        }
        return string
    }
    this.indexOf = function(element) {
        let current = head
        let index = 0
        while (current) {
            if (current.element === element) return index
            index++
            current = current.next
        }
        return -1
    }
    this.remove = function(element) {
        let index = this.indexOf(element)
        return this.removeAt(index)
    }
    this.size = function() {
        return length
    }
    this.head = function() {
        return head
    }
    this.isEmpty = function() {
        return length === 0
    }
}
How To Create A Singly Linked List In JavaScript
Share this

Subscribe to Elliot Sachs