# JavaScript Data Structures: Singly Linked List: Pop

17 November 2019

## Intro

Last time, we learned how to push a new node to the end of our Singly Linked List.

Today, we learn how to pop something from the list. `Pop`

means `remove something from the end`

.

## Current Code

```
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class SinglyLinkedList {
constructor() {
this.length = 0;
this.head = null;
this.tail = null;
}
push(value) {
const newNode = new Node(value);
if (this.length > 0) {
this.tail.next = newNode;
} else {
this.head = newNode;
}
this.tail = newNode;
this.length += 1;
return newNode;
}
}
```

## Thoughts

First, we should think about the constraints and possibilities:

If there is currently NO other node in the Singly Linked List (so it is currently empty):

- return
`null`

, because we can't remove a node

If there is 1 node in the Singly Linked List:

- find the second to last node (it should become the new tail)
- set its
`next`

to`null`

- set it as
`tail`

- decrease the Singly Linked List's
`length`

by 1 - set the Singly Linked List's
`head`

and`tail`

to`null`

, because it is empty now - return the popped node

If there is more than 1 node in the Singly Linked List:

- find the second to last node (it should become the new tail)
- set its
`next`

to`null`

- set it as
`tail`

- decrease the Singly Linked List's
`length`

by 1 - return the popped node

Examples:

- 0 nodes: before: null (head & tail) => after: null (head & tail)
- 1 node: before: A (head & tail) => after: null (head & tail)
- 2 nodes: before: A (head) -> B (tail) => after: A (head & tail)
- n nodes: before: A (head) -> ... -> n-1 -> n (tail) => after: A (head) -> ... -> n-1 (tail)

## Implementation (Short version, DRY)

```
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class SinglyLinkedList {
constructor() {
this.length = 0;
this.head = null;
this.tail = null;
}
push(value) {
const newNode = new Node(value);
if (!this.length) {
this.head = newNode;
} else {
this.tail.next = newNode;
}
this.tail = newNode;
this.length += 1;
return newNode;
}
pop() {
// no node in the list, therefore return null
if (!this.length) {
return null;
} else {
/*
* find the second to last node (it should become the new tail):
* - set the current head as currentNode (we always have to start from the List's head node)
* - set the current head as secondToLastNode (we can't go back a node, therefore we have to save the second to last)
* - as long as the current node has a next node (so it is not the last node)
* - then set the current node to the second to last
* - then set the current node's `next` as the current node
*/
let currentNode = this.head;
let secondToLastNode = this.head;
while (currentNode.next) {
secondToLastNode = currentNode;
currentNode = currentNode.next;
}
// set the second to last node's `next` to `null` (the second to last should "cut" its connection to the next node)
secondToLastNode.next = null;
// set it as `tail`
this.tail = secondToLastNode;
// decrease the Singly Linked List's `length` by 1
this.length -= 1;
// if the Singly Linked List now is empty, set its `head` and `tail` to `null`
if (!this.length) {
this.head = null;
this.tail = null;
}
// return the popped node (found some lines above)
return currentNode;
}
}
}
```

## Result

Let's have a look how to use the Singly Linked List `pop`

method and its results.

```
const newSLL = new SinglyLinkedList();
newSLL.push("1");
newSLL.push("2");
console.log(newSLL);
/* SinglyLinkedList {
* length: 2,
* head: Node { value: '1', next: Node { value: '2', next: null } },
* tail: Node { value: '2', next: null }
* }
*/
console.log(newSLL.pop()); // Node { value: '2', next: null }
console.log(newSLL.pop()); // Node { value: '1', next: null }
console.log(newSLL.pop()); // null
console.log(newSLL); // SinglyLinkedList { length: 0, head: null, tail: null }
```

### Next Part

We will implement how to add a node to the beginning of the Singly Linked List. If you want to be notified, subscribe :)