miku86

Posted on

# JavaScript Data Structures: Singly Linked List: Shift

## Intro

Last time, we learned how to unshift / add something to the beginning of our Singly Linked List.

Today, we learn how to shift something from the list. `Shift` means `remove something from the beginning`.

## Current Code

We start with the code after we added `push()`, because we want to keep the code as simple as possible to understand. We need `push()` to add some nodes to the List.

``````class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}

constructor() {
this.length = 0;
this.tail = null;
}

push(value) {
const newNode = new Node(value);
if (this.length > 0) {
this.tail.next = newNode;
} else {
}
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 anything from the beginning of the Singly Linked list

If there is 1 node in the Singly Linked List:

• set the current `head` as the node we want to remove (`nodeToRemove`)
• set the the 2nd node as the new `head`
• decrease the List's length by 1
• set the `tail` to `null`, because the List is empty now
• return the `nodeToRemove`

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

• set the current `head` as the node we want to remove (`nodeToRemove`)
• set the the 2nd node as the new `head`
• decrease the List's length by 1
• return the `nodeToRemove`

Examples:

• 0 nodes: before: null (head & tail) => after: null (head & tail) (couldn't remove anything)
• 1 node: before: A (head & tail) => after: null (head & tail)
• n nodes: before: A (head) -> B -> ... -> n (tail) => after: B (head) -> ... -> n (tail)

Differences:

• there is only one difference: an additional step if there's only 1 node in the List

## Implementation (Short version, DRY)

``````class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}

constructor() {
this.length = 0;
this.tail = null;
}

push(value) {
const newNode = new Node(value);
if (!this.length) {
} else {
this.tail.next = newNode;
}

this.tail = newNode;
this.length += 1;
return newNode;
}

shift() {
// we can't remove anything from an empty List
if (!this.length) {
return null;
} else {
// set the current `head` as the node we want to remove (`nodeToRemove`)

// set the 2nd node as the new `head`

// decrease the List's length by 1
this.length -= 1;

// if the List is empty now, there isn't a tail anymore
if (!this.length) {
this.tail = null;
}

// return the `nodeToRemove`
return nodeToRemove;
}
}
}
``````

## Result

Let's have a look how to use the Singly Linked List `shift` method and its results.

``````const newSLL = new SinglyLinkedList();

// we can't remove from an empty list
console.log(newSLL.shift());

// add one node and remove it
newSLL.push("1st node");
console.log(newSLL.shift()); // Node { value: '1st node', next: null }

// add two nodes and remove the first
newSLL.push("new 1st node");
newSLL.push("2nd node");
console.log(newSLL);
//   length: 2,
//     value: 'new 1st node',
//     next: Node { value: '2nd node', next: null }
//   },
//   tail: Node { value: '2nd node', next: null }
// }

console.log(newSLL.shift());
// Node {
//  value: 'new 1st node',
//  next: Node { value: '2nd node', next: null }
// }

console.log(newSLL);
//   length: 1,
//   head: Node { value: '2nd node', next: null },
//   tail: Node { value: '2nd node', next: null }
// }
``````

### Next Part

We will implement how to get a specific node by its index. If you want to be notified, subscribe :)

### Questions:

• Any ideas how to improve the post or code?
• Any specific questions?

Raushan Sharma

Thanks for your work, just one thing I see which I find unnecessary is the else block after even though you are already returning above.

`````` //  instead of this
if (!this.length) {
return null;
} else {
// do something
}

// we can simply write
if (!this.length) return null;
// do something
``````

🅖🅡🅔🅖🅞🅡🅨 🅞🅡🅣🅞🅝

Been following along with this as I really needed a refresher on my data structures which I skipped / barely implemented all those years ago at uni!

Implemented a demo her using closures / functions rather than classes, for people to browse a live version of the code: runkit.com/ortonomy/linkedlist-v1