Intro
Last time, we setup our Singly Linked List.
Today, we learn how to push something to the list. Push
means add something to the end
.
Recap from last time
- we created a class
Node
- we created a class
Singly Linked List
- we learned how to create an instance of the
Node
class - we learned how to create an instance of the
Singly Linked List
class
Current Code
// name of the class
class Node {
// the constructor runs when using the class with `new` (see later)
constructor(value) {
// set this nodes value property to the instantiation value
this.value = value;
// set this nodes next property to `null`
this.next = null;
}
}
// name of the class
class SinglyLinkedList {
// the constructor runs when using the class with `new`
constructor() {
// set this lists length property to `0`
this.length = 0;
// set this lists head property to `null`
this.head = null;
// set this lists tail property to `null`
this.tail = null;
}
}
Thoughts
First, we should think about the constraints and possibilities:
If there is already at least one other node in the Singly Linked List:
- create a new node with an input value
- point the current tails
next
property to the new node (so the new node comes after the current tail) - set the Singly Linked List's
tail
to the new node - increase the Singly Linked List's length by 1
- return the new node (so that we knew what we added)
If there is currently NO other node in the Singly Linked List (so it is currently empty):
- create a new node with an input value
- set the Singly Linked List's
head
to the new node - set the Singly Linked List's
tail
to the new node - increase the Singly Linked List's length by 1
- return the new node (so that we knew what we added)
The differences?
- if the Singly Linked List is empty, we need a head (the new node, because it is the only node)
- if the Singly Linked List already has at least one node, the last node should point to the new node and this new last node is the new tail
Example:
- 0 nodes: before: null (head & tail) => after: A (head & tail)
- 1 node: before: A (head & tail) => after: A (head) -> B (tail)
- 2 nodes: before: A (head) -> B (tail) => after: A (head) -> B -> C (tail)
- n nodes: before: A (head) -> ... -> n (tail) => after: A (head) -> ... -> n -> n+1 (tail)
So A
always stays the head, only if we got 0 nodes, we have to set A
as the new head
.
In every other situation, we have to point the current tail
to the new node and make the new node the new tail
.
Implementation (Long version, no DRY)
- Comments from section
Thoughts
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class SinglyLinkedList {
constructor() {
this.length = 0;
this.head = null;
this.tail = null;
}
push(value) {
/*
* 1. If there is already at least one other node in the Singly Linked List
*/
if (this.length > 0) {
// create a new node with an input value
const newNode = new Node(value);
// point the current tails `next` property to the new node
this.tail.next = newNode;
// set the Singly Linked List's `tail` to the new node
this.tail = newNode;
// increase the Singly Linked List's length by 1
this.length += 1;
// return the new node
return newNode;
} else {
/*
* 2. If there is currently NO other node in the Singly Linked List (so it is currently empty):
*/
// create a new node with an input value
const newNode = new Node(value);
// set the Singly Linked List's `head` to the new node
this.head = newNode;
// set the Singly Linked List's `tail` to the new node
this.tail = newNode;
// increase the Singly Linked List's length by 1
this.length += 1;
// return the new node (so that we knew what we added)
return newNode;
}
}
}
Implementation (Short version, DRY)
- we have a lot of duplicate code, because most of the logic is the same
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;
}
}
Result
Let's have a look how to use the Singly Linked List push
method and its results.
const newSLL = new SinglyLinkedList();
console.log(newSLL);
/*
* SinglyLinkedList {
* length: 0,
* head: null,
* tail: null
* }
*/
newSLL.push("A");
console.log(newSLL);
/*
* SinglyLinkedList {
* length: 1,
* head: Node { value: 'A', next: null },
* tail: Node { value: 'A', next: null }
* }
*/
newSLL.push("B");
console.log(newSLL);
/*
* SinglyLinkedList {
* length: 2,
* head: Node { value: 'A', next: Node { value: 'B', next: null } },
* tail: Node { value: 'B', next: null }
* }
*/
Next Part
We will implement how to remove a node from the end of the Singly Linked List. If you want to be notified, subscribe :)
Top comments (0)