Created
August 29, 2018 18:05
-
-
Save twhite96/ae43346b75bfb3f092bf74376c661933 to your computer and use it in GitHub Desktop.
LinkedList
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Second import LinkedListNode from './LinkedListNode'; | |
import Comparator from '../../utils/comparator/Comparator'; | |
export default class LinkedList { | |
/** | |
* @param {Function} [comparatorFunction] | |
*/ | |
constructor(comparatorFunction) { | |
/** @var LinkedListNode */ | |
this.head = null; | |
/** @var LinkedListNode */ | |
this.tail = null; | |
this.compare = new Comparator(comparatorFunction); | |
} | |
/** | |
* @param {*} value | |
* @return {LinkedList} | |
*/ | |
prepend(value) { | |
// Make new node to be a head. | |
const newNode = new LinkedListNode(value, this.head); | |
this.head = newNode; | |
// If there is no tail yet let's make new node a tail. | |
if (!this.tail) { | |
this.tail = newNode; | |
} | |
return this; | |
} | |
/** | |
* @param {*} value | |
* @return {LinkedList} | |
*/ | |
append(value) { | |
const newNode = new LinkedListNode(value); | |
// If there is no head yet let's make new node a head. | |
if (!this.head) { | |
this.head = newNode; | |
this.tail = newNode; | |
return this; | |
} | |
// Attach new node to the end of linked list. | |
this.tail.next = newNode; | |
this.tail = newNode; | |
return this; | |
} | |
/** | |
* @param {*} value | |
* @return {LinkedListNode} | |
*/ | |
delete(value) { | |
if (!this.head) { | |
return null; | |
} | |
let deletedNode = null; | |
// If the head must be deleted then make next node that is differ | |
// from the head to be a new head. | |
while (this.head && this.compare.equal(this.head.value, value)) { | |
deletedNode = this.head; | |
this.head = this.head.next; | |
} | |
let currentNode = this.head; | |
if (currentNode !== null) { | |
// If next node must be deleted then make next node to be a next next one. | |
while (currentNode.next) { | |
if (this.compare.equal(currentNode.next.value, value)) { | |
deletedNode = currentNode.next; | |
currentNode.next = currentNode.next.next; | |
} else { | |
currentNode = currentNode.next; | |
} | |
} | |
} | |
// Check if tail must be deleted. | |
if (this.compare.equal(this.tail.value, value)) { | |
this.tail = currentNode; | |
} | |
return deletedNode; | |
} | |
/** | |
* @param {Object} findParams | |
* @param {*} findParams.value | |
* @param {function} [findParams.callback] | |
* @return {LinkedListNode} | |
*/ | |
find({ value = undefined, callback = undefined }) { | |
if (!this.head) { | |
return null; | |
} | |
let currentNode = this.head; | |
while (currentNode) { | |
// If callback is specified then try to find node by callback. | |
if (callback && callback(currentNode.value)) { | |
return currentNode; | |
} | |
// If value is specified then try to compare by value.. | |
if (value !== undefined && this.compare.equal(currentNode.value, value)) { | |
return currentNode; | |
} | |
currentNode = currentNode.next; | |
} | |
return null; | |
} | |
/** | |
* @return {LinkedListNode} | |
*/ | |
deleteTail() { | |
const deletedTail = this.tail; | |
if (this.head === this.tail) { | |
// There is only one node in linked list. | |
this.head = null; | |
this.tail = null; | |
return deletedTail; | |
} | |
// If there are many nodes in linked list... | |
// Rewind to the last node and delete "next" link for the node before the last one. | |
let currentNode = this.head; | |
while (currentNode.next) { | |
if (!currentNode.next.next) { | |
currentNode.next = null; | |
} else { | |
currentNode = currentNode.next; | |
} | |
} | |
this.tail = currentNode; | |
return deletedTail; | |
} | |
/** | |
* @return {LinkedListNode} | |
*/ | |
deleteHead() { | |
if (!this.head) { | |
return null; | |
} | |
const deletedHead = this.head; | |
if (this.head.next) { | |
this.head = this.head.next; | |
} else { | |
this.head = null; | |
this.tail = null; | |
} | |
return deletedHead; | |
} | |
/** | |
* @param {*[]} values - Array of values that need to be converted to linked list. | |
* @return {LinkedList} | |
*/ | |
fromArray(values) { | |
values.forEach(value => this.append(value)); | |
return this; | |
} | |
/** | |
* @return {LinkedListNode[]} | |
*/ | |
toArray() { | |
const nodes = []; | |
let currentNode = this.head; | |
while (currentNode) { | |
nodes.push(currentNode); | |
currentNode = currentNode.next; | |
} | |
return nodes; | |
} | |
/** | |
* @param {function} [callback] | |
* @return {string} | |
*/ | |
toString(callback) { | |
return this.toArray().map(node => node.toString(callback)).toString(); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment