Data Structures: Singly Linked List Part Two

Popping

In this blog post, we will continue discussing Singly Linked Lists, specifically the pop method. Note: for anyone brand new to the topic, or have no idea what a Singly Linked List is, check out my previous blog where I briefly go in depth on some basic fundamentals and how to start using Singly Linked Lists. By the end of this post, my hope is that you walk away with confidence on how to implement some of the other fundamental methods for using this Data Structure. At the very end, I will write out the full code from the previous blog post up until this point, which will include the push method and the SinglyLinkedList class.

The Pop method for linked lists works similarly to the pop method in an array. It removes the last element within the list, however there are a couple more steps in a linked list. The first step is to remove the last element in the list, the next is to reassign and update the tail of the list to be the previous element or whatever was the second to last element (if there was one). In order to update the tail we will need to travel through the list. So let’s get started.

To write out the pop method, we start with an edge case of, if there are no nodes, return undefined. If there is a node, we loop through until we reach the tail. Then we set the next property of the 2nd to last node to be null, and set the tail to be the 2nd to last node. Then decrement the length of the list by 1 and finally return the value of the popped node.

...
pop(){
  if (!this.head) return undefined
  let current = this.head
  let newTail = current
  while(current.next){
    newTail = current
    current = current.next
  }
  this.tail = newTail
  this.tail.next = null
  this.length--
  if(this.head === this.tail){
    this.head = null;
    this.tail = null;
  }
  return current
}
...

In the code above we create the pop method inside of the SinglyLinkedList class. In the line following our catch statement (if there is no head), we create two variables: current set equal to this.head, which we will use to traverse the list, and newTail set to current which will lag behind current. In the while loop following, we first set newTail to whatever current is. As long as there is a current.next, newTail will be assigned to current, but when current hits the tail of the list, there is no current.next and therefor newTail, will never be assigned to the tail of the linkedList. Once the while loop reaches the end, we assign this.tail to newTail, and we assign this.tail.next to null, thereby severing the link to the next node. Then to adjust the length of the list, we decrement this.length by one. Finally before returning current (the popped element), we create a final condition to secure that the head and tail on the last possible pop return null as their value.

Below is the full code with an example of the code.

class Node{
   constructor(value){
     this.value = value;
     this.next = null;
   }
}
class SinglyLinkedList{
  constructor(){
    this.head = null;
    this.tail = null;
    this.length = 0;
  } 
  push(value) {
    let node = new Node(value)
    if(!this.head){
      this.head = node
      this.tail = this.head
    } else {
      this.tail.next = node
      this.tail = node
    }
    this.length++
    return this
  }
  pop(){
    if (!this.head) return undefined
    let current = this.head
    let newTail = current
    while(current.next){
      newTail = current
      current = current.next
    }
    this.tail = newTail
    this.tail.next = null
    this.length--
    if(this.head === this.tail){
      this.head = null;
      this.tail = null;
    }
    return current
  }
}
//Sample
let shoppingList = new SinglyLinkedList()
shoppingList.push("Oat Milk")
shoppingList.push("Tofu")
shoppingList.push("Beans")
shoppingList
   //Oat Milk => Tofu => Beans
shoppingList.pop()
  //=> Beans 
shoppingList
//Oat Milk => Tofu