Data Structure: Implement Linked List Using JavaScript

Jan 23, 2020

I have decided to brush up on my data structures and algorithms. So I thought it would be a great opportunity to share it with you! Who doesn't love some Maps and linked list! Kidding, I hate it but can't deny they are essential basics for anyone trying to be successful Software Engineer. Lets get started!

I am not going to talk too much about the theory of the linked list. We need two classes for implementing Linked lists. First is the Node class and second is the Linked List class itself.

Singly Linked List

The Mighty 'Node' class

Let's get started by writing our Node class.

class Node {
    constructor(element, next = null) {
        this.element = element;
        this.next = next;
    }
}

The two property of a Node is the 'element' and 'next' property.

Linked List class

class LinkedList {
	constructor() {
    	this.head = null;
        this.size = 0;
    }
}

Now our LinkedList class has a head (of course) and we will also keep track of the size of the linked list.

At this point you can print your list and see it in the console. So, outside of your LinkedList class put the following piece of code.

const linkedList = new LinkedList();
console.log(linkedList);

You should see something like this:

LinkedList { head: null, size: 0  }

Next we will go ahead and implement some methods within the LinkedList class.

insertFirst()

insertFirst(element) {
	this.head = new Node(element, this.head);
    	this.size+;
}

insertLast()

insertLast(element) {
    let node = new Node(element, null);
    let current;
	if (!this.head) {
    	this.head = node; 
	} else {
    	current = this.head;
        while (current.next) {
          current = current.next;
    	}
        current.next = node;
    }
    this.size++;
}

insertAt()

insertAt(element, index) {
   let node = new Node(element);
   let current;
   let previous;
    
    if (index === 0) {
    	this.head = node;
    }
    if (index < 0 || index > this.size-1) {
    	return;
    } else {
    	current = this.head;
        let count = 0;
        while (count < index) {
        	previous = current;
            count++;
            current = current.next
        }
        node.next = current;
        previous.next = node;
    }
    this.size++;
 }

getAt()

getAt(index) {
   let current = this.head;
   let count = 0;
   while(current) {
       if(count === index) {
           console.log(current.element);
       }
       count++;
       current = current.next;
   }
   return null;
}

removeAt()

removeAt(index) {
    if(index < 0 || index > this.size - 1) {
    	return;
    }
    let current = this.head;
    let previous;
    let count = 0;
    if(index === 0) {
    	this.head = current.next;
    } else {
    	while(count < index) {
        	count++;
            previous = current;
            current = current.next;
        }
        previous.next = current.next;
    }
    this.size--;
}

clearList()

clearList() {
    this.head = null;
    this.size = 0;
}

size()

size() {
    return this.size;
}

printList()

let current = this.head;
while(current) {
	let result = current.element;
    current = current.next;
    console.log(result);
    }
}

Testing

Now you can go ahead and test it. Or you can test it after writing individual functions (recommended). To test it (like I mentioned in the beginning) put these lines after your class and run the code:

const linkedList = new LinkedList();

linkedList.insertFirst(4);
linkedList.insertLast(40);
linkedList.insertAt(15, 1);
linkedList.insertAt(7, 2);
linkedList.insertLast(50);
linkedList.removeAt(4);
linkedList.size();
linkedList.printList();
linkedList.clearList();
linkedList.printList();

Time and Space Complexity:

Time:
Access: O(n)
Search: O(n)
Insertion: O(1)
Deletion: O(1)
Space: O(n)