/**
* Linked list function constructor.
*
* @example const LinkedList = require('dstructures').LinkedList;
* const myLinkedList = new LinkedList();
* @description In computer science, a linked list is a linear collection of data elements,
* in which linear order is not given by their physical placement in memory. Instead, each element
* points to the next. It is a data structure consisting of a group of nodes which together represent
* a sequence. Under the simplest form, each node is composed of data and a reference (in other words, a link)
* to the next node in the sequence. Full wikipedia article at:
* {@link https://en.wikipedia.org/wiki/Linked_list}
* @public
* @constructor
*/
class LinkedList {
constructor(){
const head = new Node('head');
this.getHead = () => head;
}
/**
* Returns the element property of the given node.
*
* @param {any} element Given element.
* @returns Returns element property of the given node.
*/
GetElement (element) {
return this.find(element).element;
}
/**
* Inserts a node in a linked list.
*
* @param {any} newElement The element that will be inserted.
* @param {any} oldElement The old element after whitch the new element will be added.
* At the first insertion this argument have to be ommited.
* @returns {Boolean} Returns false if the element is not present.
* @example LinkedList.insert(1); // [1]
* LinkedList.insert(2, 1); // [1] -> [2]
* LinkedList.insert(3, 2); // [1] -> [2] -> [3]
*/
insert (newElement, oldElement) {
oldElement = oldElement || 'head';
let newNode = new Node(newElement);
let current = this.find(oldElement);
if (current === false) {
return false;
}
newNode.next = current.next;
current.next = newNode;
}
/**
* Returns array representation of the linked list.
*
* @returns {Array} Returns array representation of the linked list.
* @example LinkedList; // ['cat'] -> ['pig'] -> ['dog']
* LinkedList.toArray(); // ['cat', 'pig', 'dog']
*/
toArray () {
let resultArray = [];
let currentNode = this.getHead();
while (currentNode.next !== null) {
resultArray.push(currentNode.next.element);
currentNode = currentNode.next;
}
return resultArray;
}
/**
* Removes element from a linked list.
*
* @param {any} element Given element.
* @returns {Boolean} Returns false if the element is not present.
* @example LinkedList; // [1] -> [2] -> [3]
* LinkedList.remove(2); // [1] -> [3]
*/
remove (element) {
let previousNode = this.findprevious(element)
if (previousNode.next !== null) {
previousNode.next = previousNode.next.next;
}
return false;
}
// Finds given node.
find (element) {
let currentNode = this.getHead();
while (currentNode.element !== element && currentNode.next !== null) {
currentNode = currentNode.next;
}
if (currentNode.element === element) {
return currentNode;
}
return false;
}
// Helper function used by remove function.
findprevious (element) {
let currentNode = this.getHead();
while (!(currentNode.next === null) && (currentNode.next.element !== element)) {
currentNode = currentNode.next;
}
return currentNode;
}
}
module.exports = LinkedList;
// Node function constructor.
// @private
function Node(element) {
this.element = element;
this.next = null;
}