Data Structures Decoded: Singly Linked Lists III

Photo by Arisa Chattasa on Unsplash

Data structures: the other cornerstone of a competent software engineer. This is why I’m compiling all my research and work on the topic in a series of articles titled Data Structures Decoded.

Previously on Data Structures Decoded…

In the second part of our look at Singly Linked Lists, we created a .pop() instance method, a method common in other structures like Arrays.

In today’s article, we’ll be exploring how to add a .shift() function to our Singly Linked List class.

Let’s Shift Gears

In arrays, .shift() removes the first element of the array. While the goal is the same, its implementation with our Singly Linked List is slightly different. The benefit, though, is implementing .shift() here allows us to enjoy constant time always. With arrays, for instance, every index would have to be reassigned and for a large dataset, that’s a big no-no/

Psuedo My Code

Before we dive into the code, let’s check out the pseudocode that will structure our approach:

1. If there aren’t any nodes, return undefined. This is our main edge case.
2. Store the current head property in a variable.
3. Set the head property to be the current head’s next property.
4. Decrement the length by 1.
5. Finally, return the value of the node removed.

Implementing .shift()

shift() { 
    if (!this.head) return undefined; 
    var currentHead = this.head; 
    this.head = currentHead.next; 
    this.length--; 
    if (this.length === 0) { 
        this.tail = null; 
    }
    return currentHead; 
}

What do you think? If you liked what you read, consider connecting or dropping me a line at nick.echev AT gmail.com!