Intro
Last time, we learned how to setup our Doubly Linked List.
Today, we'll learn how to push a new node to the end of our Doubly Linked List.
Starter Code
We start with the setup code from the last post.
class Node {
constructor(value) {
this.value = value;
this.prev = null;
this.next = null;
}
}
class DoublyLinkedList {
constructor() {
this.length = 0;
this.head = null;
this.tail = null;
}
}
Thoughts
First, we should think about the constraints and possibilities:
If the list is empty:
- create a new node
- the new node should become the head and the tail
- increase the List's length by 1
- return new node
All remaining cases:
- create a new node
- the current tail should point forward (= next) to the new node
- the new node should point back (= prev) to the current tail
- the new node should become the new tail
- increase the List's length by 1
- return new node
Example: empty list
- current List: empty (no head & tail)
- desired List: A (head & tail)
Example 2: list with 1 node
- current List: A (head & tail)
- desired List: A (head) <===> B (tail)
Steps:
- current List: A (head & tail)
- desired List: A (head) <===> B (tail)
-
the current tail should point forward (= next) to the new node: A (head & tail) => B -
the new node should point back (= prev) to the current tail: A (head & tail) <===> B -
the new node should become the new tail: A (head) <===> B (tail)
=> list after last step equals the desired list
Implementation
class Node {
constructor(value) {
this.value = value;
this.prev = null;
this.next = null;
}
}
class DoublyLinkedList {
constructor() {
this.length = 0;
this.head = null;
this.tail = null;
}
push(value) {
// create a new node
const newNode = new Node(value);
// if the list is empty,the new node should become the head and the tail
if (!this.length) {
this.head = newNode;
this.tail = newNode;
} else {
// the current tail should point forward (= next) to the new node
this.tail.next = newNode;
// the new node should point back (= prev) to the current tail
newNode.prev = this.tail;
// the new node should become the new tail
this.tail = newNode;
}
// increase length by 1
this.length += 1;
// return new node
return newNode;
}
}
Result
Let's have a look how to use the Doubly Linked List's push method and its results.
// empty list
const newDLL = new DoublyLinkedList();
console.log(newDLL);
// DoublyLinkedList { length: 0, head: null, tail: null }
// push first new node
console.log(newDLL.push("new node 1"));
// Node { value: 'new node 1', prev: null, next: null }
console.log(newDLL);
// DoublyLinkedList {
// length: 1,
// head: Node { value: 'new node 1', prev: null, next: null },
// tail: Node { value: 'new node 1', prev: null, next: null }
// }
// push second new node
console.log(newDLL.push("new node 2"));
// <ref *1> Node {
// value: 'new node 2',
// prev: Node { value: 'new node 1', prev: null, next: [Circular *1] },
// next: null
// }
console.log(newDLL);
// DoublyLinkedList {
// length: 2,
// head: <ref *1> Node {
// value: 'new node 1',
// prev: null,
// next: Node { value: 'new node 2', prev: [Circular *1], next: null }
// },
// tail: <ref *2> Node {
// value: 'new node 2',
// prev: <ref *1> Node {
// value: 'new node 1',
// prev: null,
// next: [Circular *2]
// },
// next: null
// }
// }
Next Part
We will implement our next method for the Doubly Linked List: pop / remove a node from the end.
If you want to get notified, subscribe!
Tasks
- Do you spot some new stuff in the results?
- What do they mean?
Top comments (0)