const LinkedList = (function () {
// const head = Symbol('head') //To keep head as private in linked list
// const size = Symbol('size')
class ListNode {
constructor(val, next = null) {
this.val = val
this.next = next
}
}
class LinkedList {
// Private instance fields
#head
#size
constructor() {
// The head and size property shouldn't be modifiable outside the class. So there should only be a getter. Class fields aren't supported by a lot of browsers. Use symbol instead to create private class variables if you're not using babel.
this.#head = null
this.#size = 0
// this[head] = null
// this[size] = 0
}
//getters
get head() {
return this.#head
}
get size() {
return this.#size
}
get tail() {
let curr = this.#head
if (!curr) return null
while (curr.next) {
curr = curr.next
}
return curr
}
fromArray(array) {
for (const val of array) {
this.appendToTail(val)
}
}
toArray() {
const result = []
let curr = this.#head
while (curr) {
result.push(curr.val)
curr = curr.next
}
return result
}
// T — O(1)
prependToHead(val) {
const node = new ListNode(val)
if (this.#head == null) this.#head = node
else {
const prevHead = this.#head
this.#head = node
this.#head.next = prevHead
}
this.#size++
}
// T — O(n)
appendToTail(val) {
const node = new ListNode(val)
if (this.#head == null) this.#head = node
else {
let curr = this.#head
while (curr.next) {
curr = curr.next
}
curr.next = node
}
this.#size++
}
// T — O(1)
deleteFromHead() {
const currHead = this.#head
if (!currHead) return null
this.#head = currHead.next
this.#size--
return currHead.val
}
// T — O(n)
deleteFromTail() {
let curr = this.#head
if (!curr) return null
//Handle case of single node in linked list
if (!curr.next) {
this.#head = null
this.#size--
return curr.val
}
let prev = null
while (curr.next) {
prev = curr
curr = curr.next
}
prev.next = null
this.#size--
return curr.val
}
// T — O(n). Non recursive version of deleteNodeRecursive
deleteNode(val, deleteMultiple = false) {
let deleteCount = 0
let curr = this.#head,
prev = null
while (curr) {
if (curr.val === val) {
if (!prev) {
//Don't need to garbage collect. This is Javascript, not C++
// const temp = curr
curr = curr.next
// temp.next = null
this.#head = curr
} else {
prev.next = curr.next
// curr.next = null
curr = prev.next
}
this.#size--
deleteCount++
if (!deleteMultiple) return true
} else {
prev = curr
curr = curr.next
}
}
return !!deleteCount
}
search(val) {
let curr = this.#head
while (curr) {
if (curr.val === val) return true
curr = curr.next
}
return false
}
printList() {
const result = this.toArray()
console.log(result)
return result
}
}
return LinkedList
})()
module.exports = LinkedList
const ll = new LinkedList(),
testList = [1, 2, 1, 3]
ll.fromArray(testList)
console.log(ll.deleteNode(1, true))
console.log(ll.deleteNode(2, false))
console.log(ll.size)Tests (jest):
const { LinkedList } = require('../src')
describe('head, tail, size, print, search', () => {
const ll = new LinkedList(),
testList = [5, 3]
ll.fromArray(testList)
test('gets head of linked list', () => {
expect(ll.head).toEqual({ val: 5, next: { val: 3, next: null } })
})
test('gets tail of linked list', () => {
expect(ll.tail).toEqual({ val: 3, next: null })
})
test('does not mutate head of linked list', () => {
ll.head = null
expect(ll.head).toEqual({ val: 5, next: { val: 3, next: null } })
})
test('gets size of linked list', () => {
expect(ll.size).toBe(2)
})
test('prints all node vals as an array', () => {
expect(ll.printList()).toEqual(testList)
})
test('searches linked list and returns true if given val exists', () => {
expect(ll.search(5)).toBe(true)
})
test('searches linked list and returns false if given val does not exist', () => {
expect(ll.search(1)).toBe(false)
})
})
describe('add', () => {
test('appends nodes to end of linked list from vals of array', () => {
const ll = new LinkedList(),
testList = [5, 3]
ll.fromArray(testList)
expect(ll.head).toEqual({ val: 5, next: { val: 3, next: null } })
})
test('prepends node of given val to head of linked list ', () => {
const ll = new LinkedList()
ll.fromArray([2])
ll.prependToHead(1)
expect(ll.printList()).toEqual([1, 2])
})
test('appends node of given val to tail of linked list ', () => {
const ll = new LinkedList()
ll.fromArray([1])
ll.appendToTail(2)
expect(ll.printList()).toEqual([1, 2])
})
})
describe('delete from head', () => {
test('deletes head node of linked list if node does not equal null and returns deleted node val', () => {
const ll = new LinkedList(),
testList = [5, 3]
ll.fromArray(testList)
expect(ll.deleteFromHead()).toBe(5)
})
test('returns null if head is null', () => {
const ll = new LinkedList()
expect(ll.deleteFromHead()).toBe(null)
})
})
describe('delete from tail', () => {
test('deletes tail node of linked list if node does not equal null and returns deleted node val', () => {
const ll = new LinkedList(),
testList = [5, 3]
ll.fromArray(testList)
expect(ll.deleteFromTail()).toBe(3)
expect(ll.size).toBe(1)
expect(ll.deleteFromTail()).toBe(5)
expect(ll.size).toBe(0)
})
test('returns null if head is null', () => {
const ll = new LinkedList()
expect(ll.deleteFromTail()).toBe(null)
})
})
describe('delete node of given val', () => {
test('deletes first node that matches the given val', () => {
const ll = new LinkedList(),
testList = [1, 2, 1, 3]
ll.fromArray(testList)
expect(ll.deleteNode(1, true)).toBe(true)
expect(ll.deleteNode(2, false)).toBe(true)
expect(ll.size).toBe(1)
})
test('deletes only the first node that matches the given val', () => {
const ll = new LinkedList(),
testList = [1, 2, 1, 3]
ll.fromArray(testList)
ll.deleteNode(1, false)
expect(ll.printList()).toEqual([2, 1, 3])
})
test('deletes all nodes that matches the given val', () => {
const ll = new LinkedList(),
testList = [1, 2, 1, 3]
ll.fromArray(testList)
ll.deleteNode(1, true)
expect(ll.printList()).toEqual([2, 3])
expect(ll.size).toBe(2)
})
test('returns false if node of given val is not found', () => {
const ll = new LinkedList(),
testList = [1, 2, 1, 3]
ll.fromArray(testList)
expect(ll.deleteNode(9, false)).toBe(false)
})
test('returns null if head is null', () => {
const ll = new LinkedList()
expect(ll.deleteFromTail()).toBe(null)
})
})