JavaScript Data Structures: Singly Linked List: Insert

#webdev #javascript #beginners #tutorial

Intro

Last time, we learned how to update/set a specific node.

Today, we learn how to insert a new node at any specific index.

Current Code

We start with code that has push, unshift and get, because we can reuse these methods.

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; } unshift(value) { const newHead = new Node(value); if (!this.length) { this.head = newHead; this.tail = newHead; } else { newHead.next = this.head; this.head = newHead; } this.length += 1; return newHead; } get(index) { if (index < 0 || index >= this.length) { return null; } else { let count = 0; let currentNode = this.head; while (count < index) { currentNode = currentNode.next; count += 1; } return currentNode; } } }

Thoughts

First, we should think about the constraints and possibilities:

If we want to add a node "outside" the List (less than 0 or greater than the length of the current List):

return null

If we want to add a node at the beginning of the List (index is 0):

we can use our unshift method

If we want to add a node at the end of the List:

we can use our push method

All remaining cases:

create a new node
put it between the node before the new node's place and the node, that is currently at this place

Example:

current List: A -> B
desired List: A -> N -> B

Steps:

create new node N
point N's next to B
point A's next to N

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; } unshift(value) { const newHead = new Node(value); if (!this.length) { this.head = newHead; this.tail = newHead; } else { newHead.next = this.head; this.head = newHead; } this.length += 1; return newHead; } get(index) { if (index < 0 || index >= this.length) { return null; } else { let count = 0; let currentNode = this.head; while (count < index) { currentNode = currentNode.next; count += 1; } return currentNode; } } insert(index, value) { // add a node "outside" the List (=> invalid) if (index < 0 || index > this.length) { return null; } else if (index === 0) { // add a node to the beginning of the List return this.unshift(value); } else if (index === this.length) { // add a node to the end of the List return this.push(value); } else { // get the node before the new node's desired place (because it has to point to the new node soon) const preDesiredPlace = this.get(index - 1); // create a new node const newNode = new Node(value); // the new node should point to the node, that is currently at the new node's desired place newNode.next = preDesiredPlace.next; // the node before the new node's desired place should point to the new node preDesiredPlace.next = newNode; // increase the List's length by 1 this.length += 1; // return the new node return newNode; } } }

Result

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

const newSLL = new SinglyLinkedList(); console.log(newSLL.insert(0, "A")); // Node { value: 'A', next: null } console.log(newSLL.insert(1, "B")); // Node { value: 'B', next: null } console.log(newSLL); // SinglyLinkedList { // length: 2, // head: Node { value: 'A', next: Node { value: 'B', next: null } }, // tail: Node { value: 'B', next: null } // } console.log(newSLL.insert(1, "N (between A and B)")); // Node { // value: 'N (between A and B)', // next: Node { value: 'B', next: null } // } console.log(newSLL); // SinglyLinkedList { // length: 3, // head: Node { // value: 'A', // next: Node { value: 'N (between A and B)', next: [Node] } // }, // tail: Node { value: 'B', next: null } // }