Hello! This is the third installment in a series of posts that will introduce you to the Data structures and algorithms you can expect to be asked about at a technical interview. If you want a more thorough introduction, check out parts 1 and 2 where I discuss arrays in the menu above. Let's get right into it.
Linked Lists
Linked Lists are a sorted collection of vertices or nodes that contain data and refs that link to each other or in one direction, aptly called pointers. The nodes in a linked list must contain a head, or a first value, a tail, which is the last value in a node, and a pointer, which connects a node's tail to the next node in the linked list. The last node in a linked list, however, will point to null to indicate the end of the linked list.
Creating a linked list
It's safe to say that it is unlikely that you'll be asked to create a linked list from scratch at an interview, but I found creating one to be an excellent learning tool. We can create a linked list class that we can instantiate as needed. Since linked lists are sorted, nodes are inserted front to back; the first value inserted in an empty linked list becomes the head and will also be the tail. We can define a linked list's values in a class constructor:
class LinkedList {
constructor(value) {
this.head = {
value: value,
next: null
};
this.tail = this.head;
this.length = 1;
}
}
// we can now instantiate this linked list as needed
const myLinkedList = new LinkedList(10)
Prepend
Prepending, or inserting a value at the beginning of a linked list, is more optimal in a linked list than it would be in an array, given that adding to a linked list does not require traversal of any kind. There is also no shifting involved as it would be in an array. Prepending a value in a linked list is done in constant time, O(1), as opposed to linear time in an array, O(n). The same goes for appending, or adding a value at the end of a linked list. For an array, both cases require traversing to either end of an array.
To prepend a new node to a linked list we simply need to assign a new node as the head of the given linked list.
class MyArray {
constructor(value) {
this.head = null,
this.value = value
}
//initialize a method to prepend a node
//our method will receive the node's value
prepend(value) {
//we can either initialize an object or instantiate a node class,
//like we created in the last example
const newNode = new Node(value)
//if there is no head, we can simply I sort the new node as the head of the linked list
if(this.head === null) {
this.head = newNode;
return this;
//have the new node point to the head of the linked list
newNode.next = this.head;
//reassign the head property to equate to the new node
this.head = newNode;
//increase the size of the linked list
this.length++;
//return the linked list
return this;
}
}
Append
Appending nodes to a linked list is very similar to prepending. Like appending it is done in 0(1) time, since no traversing or shifting of elements is required. We simply reassign the inserted node as the new tail in the linked list and have the former tail point to the inserted node.
...
append(value) {
const newNode = new Node(value);
//make the old tail point to the new tail
this.tail.next = newNode;
//make the inserted node the new tail
this.tail = newNode;
//since we need to allocate memory in a linked list, increase the length of it
this.length++;
return this;
}
Insert
Prepending and appending may be simple, but things get a little complicated when we need to insert a node at any other position in a linked list. We can identify the head or the tail of a linked list in O(1) time, but accessing values between the head and the tail requires traversal, an operation that runs in O(n) time. As a reminder, this means that it's time complexity grows relative to the size of the data structure. The bigger the list, the more nodes we need to traverse. After traversal we need to insert our new node and shift the pointers of the adjacent nodes.
...
insert(index, value){
//check our parameters
if(index >= this.length) {
return this.append(value);
}
const newNode = new Node(value);
//define the index before our insertion point
const leader = this.traverseToIndex(index-1);
//define the index after the insertion point
const holdingPointer = leader.next;
//make the leader point to the inserted node
leader.next = newNode;
//make the inserted node point to the holding node
newNode.next = holdingPointer;
this.length++;
return this;
}
...
Deletion
The last operation I'll go over is deleting a node in a linked list. Unlike deletion in an array, we don't need to traverse through every node to delete a head or tail node, so long as we have a defined value for the node. This makes deletion of a head or tail node in Singly-Linked Lists run in O(1) time. Here's an example of deletion methods, where I've included a third method that deletes any node in a linked list that isn't the head or the tail:
//remove the head node of a linked list
removeHead(index) {
if(!this.head) {
return }
this.head =this.head.next
return this
}
//removing the tail node of a linked list
removeTail(index) {
//verify parameters
if(!this.head) {
this.head = null;
return;
}
//define node before target node
let prevNode = this.head;
//define node after the target node
let tail = this.head.next;
while(tail.next != null) {
let targetNode = this.prevNode.next;
prevNode= tail;
tail = tail.next
return this;
}
}
//removing a node from the linked list that isn't the head or tail
remove(index) {
// Check Parameters
const leader = this.traverseToIndex(index-1);
const unwantedNode = leader.next;
leader.next = unwantedNode.next;
this.length--;
return this.printList();
}
The example above shows us three cases for deleting from a linked list. Deleting a head or tail node is our best case here, having a time complexity of O(1). At worst case, which is deleting any other node, has a time complexity of O(n), where n is the number of nodes that must be traversed in the linked list.
With that said I will wrap this post up here. Next time I will discuss the tradeoffs for linked lists, and identifying situations best solved with a linked list. Thanks for reading. See you soon.
sources
Shubhangi Raj Arwal. "Linked Lists in Javascript (ES6 Code)". https://link.medium.com/Tlg73imsFfb. April 2018. Medium.
Top comments (0)