Data Structures: Singly Linked List Part Three

Shifting and Unshifting

In this blog post I will continue breaking down the Singly Linked List Data Structure, specifically the shift and unshift methods. The shift method will allow us to remove the node at the beginning of the list, replacing the Head with the second item in our linked list, if there is one. The unshift method will allow us to do the opposite, by adding an item to the list and replacing the current head as the new head of the list. It’s also the exact opposite of pop, where instead of adding to the end of the list, we are adding to the start. As I mentioned in my previous post, if you are not familiar with Pop or Push, or unfamiliar with what a linked list is, check out my previous posts, where I go over them in depth.
Part One: Singly Linked Lists and the Push Method
Part Two: Singly Linked Lists and the Pop Method

How does the shift method work?

The shift method removes the first item on our Singly Linked List. Inside the function we need to test if there is a second item in our list, and if there is, using the .next of our current Head, we assign the Head property to the next element of our Singly Linked List. Think that we are shifting our head node from the current head to the the next item in the linked list. And if there is no next item simply return the node we are removing and set the tail to null. If there is nothing in our list to begin with we return undefined. Lastly we decrement the length minus one and return the value of the removed node.

shift(){
    if(!this.head) return undefined
    let removedHead = this.head
    this.head = removedHead.next 
    this.length --
    if(this.head === this.tail){
      this.tail = null
    }
    return removedHead
    }

Example:

Let’s use some sample data and say we have a shopping list for groceries. In it we have Oatmeal as the head, Blueberries, Beans, and Honey as the tail.

shoppingList.shift()
//=> oatmeal 
shoppingList
//=> blueberries, beans, honey. 

How does unshift work?

As mentioned above, unshift works similarly to shift in that we work with the current head. It is opposite to the push method in that we are adding to the start instead of the end and it’s also easier to implement than the push method, since we don’t have to go through the entire linked list in order to unshift or add an item into the list. It works by creating a new head and pointing it to the old head. Inside the method, we pass in a value that we want to add then we create a new node and pass in the value. If there’s no head in the list, we’ll set the head and tail to be our newly created node. If there is a head or anything in the list, we set the new node’s next property to be the current head on the list and the new node to be the head and then increment the length of the list by 1. Finally we return the linked list.

unshift(value){
    let newNode = new Node(val)
    if(!this.head) {
      this.head = newNode;
      this.tail = this.head
      } else {
       newNode.next = this.head
       this.head = newNode
      }
     this.length ++
     return this
   }

Example:

Using our previous shopping list example, let’s add oat milk to the start of our list.

shoppingList.unshift("Oat milk")
//=> Oat milk => blueberries => beans => honey 

Here’s the full code with all methods we have gone over so far.