Linked-List-Based Stack and Queue
| Run Settings | |
|---|---|
| Language | JavaScript |
| Language Version | |
| Run Command |
| Snippet Metadata | |
|---|---|
| Owner | ralletsfix |
| Created | |
| Modified | |
| Visibility | Public |
const { Stack, runStackTests } = require("./Stack.js");
const { Queue, runQueueTests } = require("./Queue.js");
const { SinglyLinkedList, runSLLTests } = require("./SinglyLinkedListWithTail.js");
runQueueTests();
// runSLLTests();
class Node {
constructor(val = 0, next = null) {
this.val = val;
this.next = next;
}
}
class SinglyLinkedList {
constructor() {
this._head = null;
this._size = 0;
}
pushFront(val) {
const newHead = new Node(val);
if (this._head === null) {
this._head = newHead;
}
else {
newHead.next = this._head;
this._head = newHead;
}
this._size += 1;
}
popFront(val) {
if (this._head === null) {
return null;
}
const removedHead = this._head;
this._head = this._head.next;
this._size -= 1;
return removedHead.val;
}
pushBack(val) {
const newHead = new Node(val);
if (this._head === null) {
this._head = newHead;
}
else {
let curr = this._head;
while (curr.next) {
curr = curr.next;
}
curr.next = newHead;
}
this._size += 1;
}
popBack() {
if (this._head === null) {
return null;
}
if (!this._head.next) {
const removedNode = this._head;
this._head = null;
this._size -= 1;
return removedNode.val;
}
let curr = this._head;
while (curr.next && curr.next.next) {
curr.next
}
const removedNode = curr.next;
curr.next = null
this._size -= 1;
return removedNode.val;
}
size() {
return this._size;
}
}
function runTests() {
const sll = new SinglyLinkedList();
// Test size on empty list
console.assert(sll.size() === 0, `\nsize(): got: ${sll.size()}, want: 0\n`);
// Test contains
// Test pop_front on empty list
console.assert(sll.popFront() === null, "\npopFront() on empty list should return null\n");
// Test pop_back on empty list
console.assert(sll.popBack() === null, "\npopBack() on empty list should return null\n");
// Test push_front and size
sll.pushFront(10);
console.assert(sll.size() === 1, `\nsize(): got: ${sll.size()}, want: 1\n`);
// Test push_back and size
sll.pushBack(20);
console.assert(sll.size() === 2, `\nsize(): got: ${sll.size()}, want: 2\n`);
// Test pop_front
console.assert(sll.popFront() === 10, "\npopFront() should return 10\n");
console.assert(sll.size() === 1, `\nsize(): got: ${sll.size()}, want: 1\n`);
// Test pop_back
console.assert(sll.popBack() === 20, "\npopBack() should return 20\n");
console.assert(sll.size() === 0, `\nsize(): got: ${sll.size()}, want: 0\n`);
// Test push_back and pop_back
sll.pushBack(30);
console.assert(sll.popBack() === 30, "\npopBack() should return 30\n");
// Test push_front and pop_front
sll.pushFront(40);
console.assert(sll.popFront() === 40, "\npopFront() should return 40\n");
}
module.exports = {
SinglyLinkedList,
runTests,
};
const { SinglyLinkedList } = require("./SinglyLinkedList.js");
// Linked-list-based Stack Implementation
class Stack {
constructor() {
this._list = new SinglyLinkedList();
}
push(val) {
this._list.pushFront(val);
}
pop() {
if (this._list.size() === 0) return null;
return this._list.popFront();
}
peek() {
if (this._list._head === null) return null
return this._list._head.val;
}
size() {
return this._list.size();
}
empty() {
return this._list.size() === 0;
}
}
function runStackTests() {
const stack = new Stack();
// Test size on empty stack
console.assert(stack.size() === 0, `\nsize(): got: ${stack.size()}, want: 0\n`);
// Test pop on empty stack
console.assert(stack.pop() === null, "\npop() on empty stack should return null\n");
// Test peek on empty stack
console.assert(stack.peek() === null, "\npeek() on empty stack should return null\n");
// Test push and size
stack.push(10);
console.assert(stack.size() === 1, `\nsize(): got: ${stack.size()}, want: 1\n`);
// Test peek
console.assert(stack.peek() === 10, "\npeek() should return 10\n");
// Test push and pop
stack.push(20);
console.assert(stack.pop() === 20, "\npop() should return 20\n");
console.assert(stack.size() === 1, `\nsize(): got: ${stack.size()}, want: 1\n`);
// Test empty
console.assert(!stack.empty(), "\nempty() should return false\n");
stack.pop();
console.assert(stack.empty(), "\nempty() should return true\n");
}
module.exports = {
Stack,
runStackTests,
};
const { SinglyLinkedList } = require("./SinglyLinkedListWithTail.js");
class Queue {
constructor() {
this._list = new SinglyLinkedList();
}
empty() {
return this._list.size() === 0;
}
size() {
return this._list.size();
}
push(val) {
this._list.pushBack(val);
}
pop() {
if (this._list.size() == 0) return null;
return this._list.popFront();
}
}
function runQueueTests() {
const queue = new Queue();
// Test size on empty queue
console.assert(queue.size() === 0, `\nsize(): got: ${queue.size()}, want: 0\n`);
// Test pop on empty queue
const got = queue.pop();
console.assert(got === null, "\npop() on empty queue should should return null\n");
// Test push and size
queue.push(10);
console.assert(queue.size() === 1, `\nsize(): got: ${queue.size()}, want: 1\n`);
// Test push and pop
queue.push(20);
console.assert(queue.pop() === 10, "\npop() should return 10\n");
console.assert(queue.size() === 1, `\nsize(): got: ${queue.size()}, want: 1\n`);
// Test empty
console.assert(!queue.empty(), "\nempty() should return false\n");
queue.pop();
console.assert(queue.empty(), "\nempty() should return true\n");
}
module.exports = {
Queue,
runQueueTests,
};
class Node {
constructor(val = 0, next = null) {
this.val = val;
this.next = next;
}
}
// Singly linked list implementation with tail pointer.
class SinglyLinkedList {
constructor() {
this._head = null;
this._tail = null;
this._size = 0;
}
// TC: O(1)
pushFront(val) {
const newHead = new Node(val);
if (this._head === null) {
this._head = this._tail = newHead;
}
else {
newHead.next = this._head;
this._head = newHead;
}
this._size += 1;
}
// TC: O(1)
popFront(val) {
if (this._head === null) {
return null;
}
const removedHead = this._head;
this._head = this._head.next;
this._size -= 1;
return removedHead.val;
}
// TC: O(1) with a tail pointer
pushBack(val) {
const newTail = new Node(val);
if (this._tail === null) {
this._tail = this._head = newTail;
}
else {
this._tail.next = newTail;
this._tail = newTail;
}
this._size += 1;
}
// TC: O(N)
popBack() {
if (this._head === null) {
return null;
}
if (!this._head.next) {
const removedNode = this._head;
this._head = this._tail = null;
this._size -= 1;
return removedNode.val;
}
let curr = this._head;
while (curr.next && curr.next.next) {
curr.next
}
const removedNode = curr.next;
curr.next = null;
this._tail = curr;
this._size -= 1;
return removedNode.val;
}
// TC: O(1)
size() {
return this._size;
}
}
function runSLLTests() {
const sll = new SinglyLinkedList();
// Test size on empty list
console.assert(sll.size() === 0, `\nsize(): got: ${sll.size()}, want: 0\n`);
// Test contains
// Test pop_front on empty list
console.assert(sll.popFront() === null, "\npopFront() on empty list should return null\n");
// Test pop_back on empty list
console.assert(sll.popBack() === null, "\npopBack() on empty list should return null\n");
// Test push_front and size
sll.pushFront(10);
console.assert(sll.size() === 1, `\nsize(): got: ${sll.size()}, want: 1\n`);
// Test push_back and size
sll.pushBack(20);
console.assert(sll.size() === 2, `\nsize(): got: ${sll.size()}, want: 2\n`);
// Test contains
// console.assert(sll.contains(10) !== null, "\ncontains(10) should find the node\n");
// console.assert(sll.contains(30) === null, "\ncontains(30) should not find the node\n");
// Test pop_front
console.assert(sll.popFront() === 10, "\npopFront() should return 10\n");
console.assert(sll.size() === 1, `\nsize(): got: ${sll.size()}, want: 1\n`);
// Test pop_back
console.assert(sll.popBack() === 20, "\npopBack() should return 20\n");
console.assert(sll.size() === 0, `\nsize(): got: ${sll.size()}, want: 0\n`);
// Test push_back and pop_back
sll.pushBack(30);
console.assert(sll.popBack() === 30, "\npopBack() should return 30\n");
// Test push_front and pop_front
sll.pushFront(40);
console.assert(sll.popFront() === 40, "\npopFront() should return 40\n");
}
module.exports = {
SinglyLinkedList,
runSLLTests,
};
/* Problem 1:
Implement a Stack class using a singly linked list. The Stack class should
support the following methods, all in O(1): push(), peek(), size(), and empty().
class Stack {
}
*/
/*
Since pushFront(),
*/
/* Problem 2:
Implement a Queue class using a singly linked list. The Queue class should
support the following methods, all in O(1): push(), peek(), size(), and empty().
*/
/*
For this one, we can use popFront() for pop() which is O(1). We must update
pushBack() to be O(1) and for this we need to keep a tail pointer.
*/
| Editor Settings | |
|---|---|
| Theme | |
| Key bindings | |
| Full width | |
| Lines |
- More Actions
- Fork Snippet
- Share Snippet