Hello everyone, this is the first of what I hope to be a series of posts about data structures. I have studied data structures a little bit here and there, but I recently decided to really improve on my computer science fundamentals (data structures, algorithms, etc.) in order to grow my knowledge in the field. And since I didn't study these topics formally in school, I have been using some online resources to aid my endeavor. A few courses that I have been following along with are:
Now, I have done some of the data structure implementations before in plain JavaScript, but for this exercise, I wanted to do them all in TypeScript as well as write tests for them with Jest. You can see the repo to my implementations here, this will be updated along with these posts.
In these posts, I will just talk about the methods implemented and any interesting thoughts I may have had at the time. I will also point out some things I learned or found interesting in TypeScript. For some these may seem to be very rudimentary, but I encourage everyone with corrections, different implementations or ideas to get involved and leave a comment below. The main goal of this is to learn, thank you.
With that being said, let's get started.
Singly Linked List
A singly linked list is basically a list of nodes linked to each other in one direction. Each node in the list has two properties; value: the data we want to have access to, and next: the node that comes after it in the list. The first node in the list is called the head, and the last node is called the tail (the next of tail is null since nothing should come after it). You can read more about linked lists here.
For my singly linked list, I implemented push, pop, shift, unshift, get, set, insert, remove, and reverse.
push
This method is very similar to the push of a JavaScript Array. We will be adding a node to the end of the list. However, there are a few more things that we need to be careful of. Mainly, head and tail management. If this is the first node being added, it will become the head as well as the tail. If there is already a tail, be sure to set the current tail's next to the new node, and set the list's tail to be the new node.
push(value: ValueType): SinglyLinkedList {
const node = new Node(value);
if (this.tail !== null) {
this.tail.next = node;
}
this.tail = node;
if (this.head === null) {
this.head = node;
}
this.length++;
return this;
}
pop
Again, similar to the JavaScript Array method of the same name, pop removes a node from the end of the list and returns the value. One of the main differences here is that we cannot just grab the tail and remove it. We have to also grab the second to last node in order to properly set its next property, and make it the new tail. For this, we have to iterate through nearly the entire list. Also, if the list is empty, we will just return undefined. If there is only one node in the list, we will just return that value and set head and tail to null.
pop(): ValueType | undefined {
if (this.length === 0) {
return undefined;
}
if (this.head === this.tail) {
const { value } = this.head!;
this.head = null;
this.tail = null;
this.length--;
return value;
}
let currentNode = this.head;
while (currentNode) {
const nextNode = currentNode.next;
if (nextNode!.next === null) {
const { value } = nextNode!;
currentNode.next = null;
this.tail = currentNode;
this.length--;
return value;
}
currentNode = currentNode.next;
}
return undefined;
}
shift
With shift, we remove the first node in the list and return its value. Very similar to shifting an array, however, when an element is removed from the beginning of an array, all the other elements have to be moved forward one. When removing a node from the beginning of a linked list, we just need to point to the new head if there are nodes left. If the list is empty, we will just return undefined.
shift(): ValueType | undefined {
if (this.length === 0) {
return undefined;
}
const { value } = this.head!;
if (this.tail === this.head) {
this.head = null;
this.tail = null;
} else {
this.head = this.head!.next;
}
this.length--;
return value;
}
unshift
Unshift adds a node to the beginning of the list, and returns it. If the list is empty, this new node will be the head and the tail.
unshift(value: ValueType): SinglyLinkedList {
const node = new Node(value);
if (this.length === 0) {
this.head = node;
this.tail = node;
} else {
node.next = this.head;
this.head = node;
}
this.length++;
return this;
}
get
Get will retrieve a node by its position in the list and return that node. If the index we pass is less than 0, or greater than or equal to the list length (index starts at 0), we return null. In this method we need to iterate through each node until we get to the index we want. While the shift and unshift methods performed better than an array, an array would perform better in this case (can grab by the index directly meaning constant time).
get(index: number): NodeType {
if (index < 0 || index >= this.length) {
return null;
}
let currentNode = this.head;
let count = 0;
while (count < index) {
currentNode = currentNode!.next;
count++;
}
return currentNode;
}
set
Set will change the value of a node based on its position in the list. For this method we will use our get method to retrieve the node, then we can just set the value of that node if we find it and return true. If the given index is invalid, we will return false.
set(index: number, value: ValueType): boolean {
const node = this.get(index);
if (!node) {
return false;
}
node.value = value;
return true;
}
insert
Insert will add a node to the list at a specific position. Here we need to be sure the index that we give the method is within the bounds of our list. We can also make use of some of our other methods here. If the index is the same as the length of the list, we can use push. If the index is 0, we can use unshift. Otherwise, we can use get to grab the node before our index, grab its next property, set its next property to the new node, and set our new node's next to the previous node's next.
insert(index: number, value: ValueType): boolean {
if (index < 0 || index > this.length) {
return false;
} else if (index === this.length) {
this.push(value);
} else if (index === 0) {
this.unshift(value);
} else {
const prevNode = this.get(index -1);
const insertNode = new Node(value);
insertNode.next = prevNode!.next;
prevNode!.next = insertNode;
this.length++;
}
return true;
}
remove
Remove a node from the list at a specific position. If the given index is out of the bounds of our list we will return undefined. If the index is the same as the list length - 1, then use our pop method. If the index is 0, use shift. Otherwise, get the node at index - 1, set the next property of that node to be the next of the that node's next (index + 1). Return the value of the removed node.
remove(index: number): ValueType | undefined {
if (index < 0 || index >= this.length) {
return undefined;
} else if (index === this.length - 1) {
return this.pop();
} else if (index === 0) {
return this.shift();
} else {
const prevNode = this.get(index - 1);
let removedNode = prevNode!.next;
prevNode!.next = removedNode!.next;
this.length--;
const { value } = removedNode!;
removedNode = null;
return value;
}
}
reverse
This one threw me for a loop a bit. The idea is that we want to reverse the list in place without creating a new list. I will make bullet points so its easier to read. The Missing Computer Science and Coding Interview Bootcamp has the steps, and a video explanation.
Swap the head and the tail
Create a variable called next and a variable called previous
Create a variable called node and set it to the head
Loop through the list
Set next to be current node's next
Set the current node's next to previous (will be null first time)
Set previous to the current node
Set current node to next
Return the list
reverse(): SinglyLinkedList {
let node = this.head;
this.head = this.tail;
this.tail = node;
let prev = null;
let next = null;
for (let i = 0; i < this.length; i++) {
next = node!.next;
node!.next = prev;
prev = node;
node = next;
}
return this;
}
The test cases are included in the repo. In the next entry, I will be implementing a doubly linked list. Thank you for reading and please leave any feedback below.