Data Structures Decoded: Singly Linked Lists II

Photo by Kaley Dykstra 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.

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

Previously on Data Structures Decoded…

In the first part of our look at Singly Linked Lists, we examined how we can use the Class syntax to create a Singly Linked List class. In it, we created a .push() instance method, a method common in other structures like Arrays.

.Pop() Goes The Weasel

So, creating .pop() functionality isn’t as straightforward as creating .push() since we cannot go backwards when iterating.

That said, we’re always going to be starting from the beginning of the list and working our way through with our first pointer, current, with the goal of finding the end of the list. Every time current is not the end of the list, we set a separate pointer, newTail, to be equal to current.

When current is equal to the end of the list, we set current to null to sever the connection between the last element and the list, and then we make newTail the second to last element.

Check out how this translates to pseudocode below:

• If there are no nodes in the list, return undefined (mo head, if length === 0)
• Loop through the list until you reach the tail
• Set the next property of the 2nd to lasty node to be null
• Set the tail to be the 2nd to last node
• Decrement the length of the list by 1
• Return the value of the node removed

Code Time

Class SinglyLinkedList{ 
    constructor() { 
        this.length = 0; 
        this.head = null; 
        this.tail = null; 
    }
     pop() {
        //edge case
        if (!this.head) return undefined; 
        //loop through list
        var current = this.head; 
        var newTail = current; 
        //while there is a next, we move forward in this loop
        while (current.next) { 
            newTail = current; 
            current = current.next; 
        }
        //move tail to point to newTail 
        this.tail = newTail; 
        //severs connection of node 
        this.tail.next = null; 
        //change list length 
        this.length--; 
        //edge case: if length === 0 ; able to be refactored into     one line 
        if (this.length === 0) { 
            this.head = null; 
            this.tail = null; 
        }
}

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