Linked List Implementation in JavaScript

As a continuation of my foray into the Colt Steele Data Structures and Algorithms Master Class on Udemy, the first data structure we will be reviewing is the Linked List. I will be covering the implementation of a linked list and how to implement a reversed linked list in JavaScript.

Image from Colt Steele’s JS Data Structures and Algo course on Udemy.

In some programming languages, there are native data structures provided but in JavaScript, we will have to create a class with specific attributes to be able to use these data structures. You should know by now that classes can be considered blueprints and that whenever we want to use a data structure we can create instances of these blueprints that have inherited the attributes of those aforementioned classes.

First, what is a linked list? A linked list is a collection of nodes and each list has a head, length, and tail property. Each node will have a value and a pointer that is directed to the next node or null if the current node is the tail. Some special characteristics of linked lists are that they are not indexed (unlike arrays which are indexed from 0 to n-1, n being the length of the array), random access is not allowed, and nodes are connected by the next pointer noted earlier. By random access I mean that we can access any element in the list by index, in a linked list we can only traverse from the head toward the tail via that next pointer.

Example of a linked list from Visualgo

If you would like to play around with the above example, please visit Visualgo.net they have great visualizations for various algorithms and data structures.

JavaScript Implementation of Linked Lists

First, we create a Node class and only has 2 properties a value, and a next pointer.

Using this Node class along with some logic we can implement a singly linked list class with the following methods:

The initial properties of a SLL are a head, a tail, and list length.

1. push: adds to the tail of the list

.push() method

2. pop: remove from the tail of the list

.pop() method

3. shift: remove from the head of the list

.shift() method

4. unshift: insert a node to the beginning of the list

.shift(value) method

5. get: retrieves a value at a given index

.get(index) method

6. set: given an index and value, will update the value of that node

.set(index, value) method

7. insert: accepts an index and value and inserts a new node

.insert( index, value) method

8. remove, accepts an index removes the node at that index

.remove(index) method

Depending on the functionality that you may need some of the above methods may not be necessary for your singly-linked list class. Once you have these basic methods you can create, read, update, and delete nodes on your linked list. Take note of how we use the basic functionality of the next pointer in the logic of each method. This was probably one of my favorite parts of this course using some logic and just a single pointer we can create a data structure for our needs. I could go off on a tangent about how mindblowing this was to me when I first came across it but I’ll save it for another time.

BigO of Linked Lists

• Insertion: O(1)
• Removal: O(1) or O(n) // removal vs. within the list
• Searching: O(n)
• Access: O(n)

Linked Lists vs Arrays

One thing we have to discuss is the similarity of arrays and linked lists. When would you use a linked list over an array? They are excellent alternatives when insertion and deletion at the beginning of a collection are frequently required. To use insert or delete elements at the beginning of an array the entire array of length n must be resequenced due to the index of elements that arrays naturally keep. When inserting or deleting from the end of a collection array and linked lists act similarly. Linked lists are also the foundation of other data structures like stacks and queues which should be covered in a future post.

Reverse Linked List

Now, one of the most common coding problems given on linked lists is reversing a linked list. It’s a nice check of a person’s capability to think logically as well as identify their comfort of using data structures as a linked list is one of the more simple ones we will be coming across. Here’s some pseudocode if you’d like to attempt the problem yourself:

• Swap the head and the tail of the current list
• Create 2 new variables, previous and next
• Create a 3rd variable node and set it to the initial head property

Looping through the list:

• Set the variable next to be .next property of whatever the node is
• Set the .next property on the node to be what the previous variable is
• Set the variable previous to be the value of the node variable
• Set the node variable to be the value of the next variable

Your code should look something like the following:

.reverse() method of a singly linked list

More content at plainenglish.io