Intro
Last time, we learned how to shift / remove a node from the beginning of our Singly Linked List.
Today, we learn how to get any specific node by its index.
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;
}
}
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 the index is negative or equal to or greater than the length of the List:
- return null
Else:
- start at the beginning of the List
- go to the next node [index]-times
- return this node
Examples:
- index < 0: return null
- index = 0: return
head - index >= List.length: return null
- remaining cases: go to head, go index-times to the next node & return this node
Differences:
- return null if the List doesn't have the desired node or go index-times to the next node
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 > 0) {
this.tail.next = newNode;
} else {
this.head = newNode;
}
this.tail = newNode;
this.length += 1;
return newNode;
}
get(index) {
// return null if index is negative or equal to or greater than the length of the List
if (index < 0 || index >= this.length) {
return null;
} else {
// start at the beginning of the List
let currentNode = this.head;
// keep track how many times we went to the next node
let count = 0;
// as long as the current count is smaller than the desired node's index
while (count < index) {
// set the next node as the currentNode
currentNode = currentNode.next;
// increase the count by 1
count += 1;
}
// return this node
return currentNode;
}
}
}
Result
Let's have a look how to use the Singly Linked List's get method and its results.
const newSLL = new SinglyLinkedList();
// show List, should be empty
console.log(newSLL);
// SinglyLinkedList { length: 0, head: null, tail: null }
// add three nodes
newSLL.push("0");
newSLL.push("1");
newSLL.push("2");
// there is no node with a negative index
console.log(newSLL.get(-1));
// null
// there is no node with that high of an index
console.log(newSLL.get(3));
// null
// show me the first node
console.log(newSLL.get(0));
// Node {
// value: '0',
// next: Node { value: '1', next: Node { value: '2', next: null } }
// }
// show me the second node
console.log(newSLL.get(1));
// Node { value: '1', next: Node { value: '2', next: null } }
// show me the third node
console.log(newSLL.get(2));
// Node { value: '2', next: null }
Next Part
We will implement how to give a specific node a new value. If you want to be notified, subscribe :)
Questions:
- Any ideas how to improve the post or code?
- Any specific questions?
Top comments (0)