Linked List Data Structure Implementation

Use Case:

Linked Lists are dynamic data structures that can grow and shrink as need be without the need for declaring a maximum size on creation. Because of not needing to allocate memory beforehand, linked lists are generally more memory efficient that other data structures such as arrays. Adding and removing values from the front of a list can be done in constant time and operations done at the end or middle of the list can be done easily in linear time.

Disadvantages of linked lists include memory consumption (twice the memory needed because you're storing a pointer in addition to a value) and there isn't constant time, random access to values located inside of the list. Returning a value would require following pointers starting at the head of the list until the value is discovered.

Below is an implementation of a linked list in JavaScript using 2 classes - a Node class and a Linked List class. Please read through the code below and let me know if you're aware of a better, more efficient way to implement linked lists!

1. Node Class

JavaScript

class Node {
	constructor(data) {
		this.data = data // data or value of node is equal to parameter data value
		this.next = null // the node's pointer is null by default
	}
}

Our node class will be pretty simple as each node will contain only a value and a pointer to the next node in the list. The pointer will be null by default and we'll update the pointer later when new nodes are added to the list.

2. Linked List Class

JavaScript

class LinkedList {

	constructor() {
		this.head = null // head node of linked list is null by default
	}

The LinkedList class will only be concerned about holding a head node in the list. This node and all subsequent nodes will contain the meat of the linked list from here on our (values and pointers).

Note: all functions from here on out in this post will belong to this LinkedList class and should be placed inside accordingly.

3. Size of Linked List

JavaScript

size() {
	let temp = this.head // create temp variable and set equal to head node of linked list
	let i = 0 // create counter variable
	while (temp) { // while temp is not null
		temp = temp.next // set temp variable equal to next node in list
		i++ // increment counter
	}
	return i // return counter value
}

The linked list's size function will return the size of our linked list in total number of nodes. We'll create a temp variable to hold the value of the head of our linked list and variable i to be used to hold the actual size of our list. Then, while our temp variable is not equal to null, we'll loop through the linked list and increment our counter variable which we'll return once our loop is finished.

4. Check if Linked List is Empty

JavaScript

empty() {
	return this.head == false // if linked list of empty, this conditional statement will be true, else false
}

Our empty function will allow us to check if the linked list is empty or not, simply by returning the conditional statement that the head of our linked list is equal to false. This function will return true if the list is indeed empty and false if the list is not empty.

5. Front Value of Linked List

JavaScript

front() {
	return this.head // return head node of linked list
}

We'll also create 2 functions that will return to us the first and last values in our linked list without removing them. The front function will simply return the node located at the head of our linked list.

6. Back Value of Linked List

JavaScript

back() {
	let temp = this.head // create temp variable and set equal to head node of linked list
	while (temp.next) { // while node has a pointer value
		temp = temp.next // set temp variable equal to next node in linked list
	}
	return temp // return last node
}

The back function will return the very last node in our list. However, to get there it will loop through our list until the current node's pointer is null. When this is the case then the current node will be returned.

7. Push to Front of Linked List

JavaScript

pushFront(data) {
	let node = new Node(data) // create new node
	let next = this.head // set next variable equal to head node of linked list
	this.head = node // set head of linked list equal to new node
	if (next) { // if next variable is not null
		node.next = next // set pointer for new node equal to node previously at head of list
	}
}

Our LinkedList class will need 2 methods created for adding new values to our list - to the front of the list and the back.

The pushFront function will allow us to add a new node to the front of our linked list. We'll create a new node, then get the node located at the head of the linked list. Then we'll set the head equal to our new node and set the first node's pointer equal to the next node in our list (the node that was formerly at the head).

8. Push to Back of Linked List

JavaScript

pushBack(data) {
	let node = new Node(data) // create new node
	if (this.head == null) { // if head of linked list is null
		this.head = node // set head equal to node
	} else { // if head of linked list is not null
		let temp = this.head // create temp variable and set equal to head node
		while (temp.next) { // while current node has a pointer that's not equal to null
			temp = temp.next // set temp variable equal to next node in list
		}
		temp.next = node // after while loop, set current node's pointer equal to new node
	}
}

We'll create the pushBack function to allow us to add new nodes to the back of our linked list. In order to do this, we'll need to loop through our entire linked list (following the pointers) to find the final node in our list. This operation will need to be done in linear time - O(n) - which is a negative drawback to using linked lists.

After we follow the pointers to the final value, we'll change it's pointers value from null to the new node that we created.

9. Pop from Front of Linked List

JavaScript

popFront() {
	let first = this.head // create first variable and set equal to first node in linked list
	if (first.next) { // if current node has a pointer to another node
		let second = first.next // create second variable and set equal to next node
		this.head = second // set head equal to second node
		this.head.next = second.next // set head node pointer equal to second node's pointer
	} else { // if head node doesn't have a pointer
		this.head = null // set head equal to null
	}
	return
}

We'll now create 2 functions to be used for removing nodes from our list. The first - popFront will allow us to remove the first node in our linked list. We'll just set the head of our list equal to the second node (if it exists) and then if the second node's pointer points to a node, we'll set this as the new head node's pointer.

As opposed to arrays which require linear time - O(n) - for this operation due to having to shift all subsequent items forward, this operation can be done in constant time - O(1) - for linked lists since we're simply updating the first value and it's pointer and don't need to visit the following items.

10. Pop from End of Linked List

JavaScript

popBack() {
	let temp = this.head // create temp variable and set equal to first node in linked list
	let prev = null // create prev variable and set equal to null
	while (temp) { // while temp is not null
		if (temp.next) { // if current node has a pointer to next node in list
			prev = temp // set prev variable equal to current node
			temp = temp.next // set temp variable equal to next node
		} else { // If current node doesn't have a pointer to next node in list
			temp = null // set current node equal to null
			prev.next = null // set previous node's pointer equal to null
			return // return from function
		}
	}
}

To remove a value from the end of our list, we do have to follow our entire list starting at the first, head node. We'll then loop through our list as long as the current node's pointer points to a valid node. Once we've come across a node whose pointer is null, we'll set that node equal to null and set the previous node's pointer equal to null.

11. Get Value at Index in Linked List

JavaScript

valueAt(index) {
	let temp = this.head // create temp variable and set equal to first node in linked list
	let i = 0 // set i = 0 to be used as counter
	if (temp && i == index) { // if temp is not null and i is equal to index value
		return temp.data // return temp node's value
	}
	while (temp) { // while temp is not equal to null
		if (i == index) { // if is is equal to index value
			return temp.data // return temp node's value
		}
		i++ // increment counter
		temp = temp.next // set temp variable equal to next node in list
	}
}

There may be occasion to get the value of a list item at a specific index in our list. Since linked lists aren't index-based lists like arrays, we don't have random access to each value and would need to follow our pointers until we arrived at the nth-node item.

To do this, we'll create a variable - i to hold our counter. Then we'll loop through our list while nodes exist until we've reached the point where our counter equals the index value that we're searching for. At that point we'll return the value (or data in this case) of the node.

12. Remove Nodes from Linked List

JavaScript

remove(data) {
	let temp = this.head // create temp variable and set equal to first node in linked list
	let prev = null // create prev variable and set to null
	if (temp && temp.data == data) { // if temp is not null and temp node's data is equal to value to be removed
		this.head = temp.next // set head of linked list equal to next node
		temp = null // set temp variable equal to null
		return // return from function
	}
	while (temp) { // while temp is not null
		if (temp.data == data) { // if node's data equals data to be removed
			break // break from loop
		}
		prev = temp // set prev variable equal to temp node
		temp = temp.next // set temp equal to next node in linked list
	}
	if (!temp) { // If temp is null
		return // return from function
	}
	prev.next = temp.next // set previous node's pointer equal to current node's next node
	temp = null // set temp variable equal to null
}

We'll need a way to delete specific values from our list, so we'll create a method in our linked list class called remove that will accept a paramater called data that will contain the value to be removed.

We'll loop through our linked list, following the pointers, until we find the value. While we're looping, we'll need to keep track of the current node's previous node so that we can update its pointer to the list item after the item we delete.

13. Reverse a Linked List

JavaScript

reverse() {
	let prev = null // create prev variable and set to null
	let temp = this.head // create temp variable and set equal to first node in linked list
	while (temp) { // while node is not null
		let next = temp.next // set next equal to next node in list
		temp.next = prev // set temp node's pointer equal to prev node
		prev = temp // set prev variable equal to current node
		temp = next // set temp variable equal to next node in list
	}
	this.head = prev // at the end, set the head node equal to node at prev variable
}

If a factor in our program has changed that requires the order of our list to be flipped, we'll need a way to change or reverse our linked list. At first thought, it seems like we may have to loop through our list, put the items into an array, and then recreate a new list working backwards in the array. That's not very efficient, however, and would require a time equivalent to O(n * 2). Since we're only dealing with pointers, we don't need to pluck the values out of our list, we can just update our pointers.

So we'll visit each node in our list, starting with the node located at the linked list's head, and update it's pointer to point to the node previous to it instead of the next node, then, after iterating through our list, we'll set the head node equal to the very last node we come to. This can be done in linear time - O(n) - which is exactly half of the time that the previous way would require.

14. Print the Values of a Linked List

JavaScript

print() {
	let temp = this.head // create current variable and set equal to first node in linked list
	while (temp) { // while node is not null
		console.log(temp.data) // log value
		temp = temp.next // set temp equal to next node in list
	}
}

If we want an easy way to see our values (whether it's logging them or echoing them to the browser window), we'll need to create a print function. This will just loop through our linked list and log each value (data) that it comes across to the console.

15. Implementation

JavaScript

var list = new LinkedList
list.pushBack(5)
list.pushBack(3)
list.pushBack(4)
list.pushBack(6)
list.pushBack(2)
list.pushFront(8)
console.log(list.size()) // 6
list.print() // 8,5,3,4,6,2

Start using the linked list by creating a new LinkedList object, pushing to, checking the size, printing, etc.

Tweet me @tylerewillis

Or send me an email: