JavaScript Data Structures: Linked Lists (pt. 2)
Last week, I introduced another JavaScript data structure — the linked list. To briefly summarize a linked list, it’s essentially an array-type structure where each element, or node, points to the next node in the list but does not keep track of location in the list. Unlike arrays, nodes do not have an index. The first node in a list is the head, while the last node in the list points to a null value.
This week, I’ll be discussing how to implement a singly-linked list along with some helper methods.
Implementing a List Node
First, we’ll have to create a node in order to create a new list.
As stated in the previous blog and mentioned briefly above, a node consists of two values: its specific data value and the pointer to the next node.
class LinkedListNode {
constructor(data) {
this.data = data;
this.next = null;
}
}We always want to initialize a new node with the next value as null because we don’t know what the last node will be in the list.
You can later update a node to set the next value to another node, creating the list.
let node1 = new LinkedListNode(1);
console.log(node1); //=> {data: 1, next: null}let node2 = new LinkedListNode(2);
console.log(node2); //=> {data: 2, next: null}node1.next = node2;
console.log(node1); //=> {data: 1, next: {data: 2, next: null}}
Pretty simple! Creating a new list is even simpler.
Implementing a List
class LinkedList {
constructor(head = null) {
this.head = head;
}
}Here, we’re defaulting the head to equal to null incase a list is initialized without a head value. If the head is null, that means the list is empty because we know that the last node in a list always points to null.
let newList = new LinkedList(node1);
console.log(newList); //=> {head: {data: 1, next: {data: 2, next: null}}}This sets our node1 from prior as the head of the new list.
console.log(newList.head.next.data) //=> returns 2 Helper Methods
Next, I’ll discuss a few helper methods for linked lists.
First, we’ll create a size() method, which will return the size of the list.
class LinkedList {
... size() {
let length = 0;
let node = this.head;
while (node) { // while node is not null
length++; // increment the length by 1
node = node.next // set node to next node value
}
return length // after loop is done, return length
}
}
Two other methods are the getFirst() and getLast() methods, which will get the first node and the last node, respectively.
class LinkedList {
...
getFirst() {
return this.head; // return the head node
} getLast() {
let last = this.head; // start with the head node
if (last) { // if last doesn't equal null
while (last.next) { // loop while last.next =/= null
last = last.next; // set last to next node
}
}
return last; // return last
}
}
You could also a clear() method to clear out a linked list.
class LinkedList {
...
clear() {
this.head = null;
}
}And there you have it! It’s fairly simple to implement a node and a linked list. You could also write more custom methods as helper methods for your linked lists.
Next week, I’ll go over doubly-linked lists and a common algorithm problem.
Again, here are some LeetCode challenges to try regarding linked lists (from easy → medium → hard):
