I'm looking for feedback on my singly linked list implementation in JavaScript. Please let me know if you have any suggestions on coding style, documentation, bug fixes, etc.
UML / code overview
LinkedList _head - The first element in the list _size - The number of elements in the list getSize() Returns the number of elements in the list get(index) Returns the node at index Throws a ReferenceError if index is not specified Throws a RangeError if index is out of range getFirst() Returns the first element in the list Calls and returns this.get(0) getLast() Returns the last element in the list Calls and returns this.get(this._size - 1) add(node, index) Inserts the given node at the specified index Throws a ReferenceError if node is not passed Throws a TypeError if node is not an instance of ListNode addFirst(node) Inserts the given node at the front of the list Calls and returns add(node, 0) addLast(node) Appends the given node at the end of the list Calls and returns add(node, this._size - 1) remove(index) Removes and returns the node at the specified index Throws a ReferenceError if index is undefined Throws a RangeError if index is not between 0 and this._size removeFirst() Removes and returns the first node in the list Calls and returns remove(0) removeLast() Removes and returns the last node in the list Calls and returns remove(0) clear() Removes all elements in the list set(index, node) Replaces the node at index with the given node Calls this.remove(index) then calls and returns this.add(node, index) indexOf(value) Returns -1 or the first index value is found at Throws a ReferenceError if value is undefined lastIndexOf(value) Returns -1 or the last index value is found at Throws a ReferenceError if value is undefined contains(value) Returns true/false if the value is/not in the list ListNode _value - The value this node holds _next - The next node in the list getValue() setValue(value) getNext() setNext(node)
Code
I've left out the ListNode class because there's nothing more to it than the UML above.
class LinkedList {
// Initializes the list by setting the head to null,
// and the size to 0
constructor() {
this._head = null;
this._size = 0;
}
// Returns the number of nodes in the list
getSize() {
return this._size;
}
// Returns the head of the list
getFirst() {
return this._head;
}
// Returns the tail of the list
getLast() {
return this.get(this._size - 1);
}
// Returns the node at the specified index
get(index) {
// If the index parameter was not specified
if (index === undefined) {
throw new ReferenceError('no index was specified', 'LinkedList.js');
}
// Make sure the index is in range
if (index < 0 || index >= this._size) {
const msg = `Index (${index}) out of range; List size (${this._size})`;
throw new RangeError(msg, 'LinkedList.js');
}
let current = this._head;
for (let i = 0; i < index; i++) {
current = current.getNext();
}
return current;
}
// Inserts the given node at the specified index
add(node, index) {
// If the node parameter was not specified
if (node === undefined) {
throw new ReferenceError('no node was specified', 'LinkedList.js');
}
// Make sure node is a ListNode
if (!(node instanceof ListNode)) {
const msg = "add(node, index): node must be of type ListNode";
throw new TypeError(msg, 'LinkedList.js');
}
// The index parameter is optional. If not defined, add node to the end
if (index === undefined) {
index = this._size;
}
// Make sure the index is in range
if (index < 0 || index > this._size) {
const msg = `Index (${index}) out of range; List size (${this._size})`;
throw new RangeError(msg, 'LinkedList.js');
}
// If inserting the node at the beginning of the list
if (index === 0) {
// Set the node's next to point to the current head
node.setNext(this._head);
// Replace the current head with the new node
this._head = node;
this._size++;
return node;
} else {
// The node just before the insertion index
let previous = this.get(index - 1);
// The node at the insertion index
let next = previous.getNext();
// Set the node at the insertion index
previous.setNext(node);
node.setNext(next);
this._size++;
return node;
}
}
// Inserts the given node at the beginning of the list
addFirst(node) {
return this.add(node, 0);
}
// Appends the given node at the beginning of the list
addLast(node) {
return this.add(node, this._size);
}
// Removes and returns the node at the specified index
remove(index) {
// If the index parameter was not specified
if (index === undefined) {
throw new ReferenceError('no index was specified', 'LinkedList.js');
}
// Make sure the index is in range
if (index < 0 || index > this._size) {
const msg = `Index (${index}) out of range; List size (${this._size})`;
throw new RangeError(msg, 'LinkedList.js');
}
// If removing the head of the list
if (index === 0) {
const removed = this._head;
this._head = this._head.getNext();
this._size--;
return removed;
} else {
// The node at the index before the one to be removed
let previous = this.get(index - 1);
// The node to be removed
let removed = previous.getNext();
// Removes the node at index by setting the next pointer of the node at
// index-1 to the node at index+1, skipping the node at index
previous.setNext(removed.getNext());
this._size--;
return removed;
}
}
// Removes and returns the head of the list
removeFirst() {
return this.remove(0);
}
// Removes and returns the last node in the list
removeLast() {
return this.remove(this._size - 1);
}
// Empties the list by setting the head to null and sets the size to 0
clear() {
this._head = null;
this._size = 0;
}
// Replaces the node at the specified index with the given node
set(index, node) {
// Remove the node currently at index
this.remove(index);
// Inserts the new node at the specified index
return this.add(node, index);
}
// Returns the index that the value is found at, -1 if the value is not found
indexOf(value) {
// If the index parameter was not specified
if (value === undefined) {
throw new ReferenceError('no value was specified', 'LinkedList.js');
}
// If the list is empty, return -1 indicating the value wasn't found
if (this._head == null) {
return -1;
}
let current = this._head;
let index = 0;
while (current.getNext() != null) {
if (current.getValue() === value) {
return index;
}
current = current.getNext();
index++;
}
return -1;
}
// Returns the last index the value is found at, -1 if it is not found
lastIndexOf(value) {
// If the index parameter was not specified
if (value === undefined) {
throw new ReferenceError('no value was specified', 'LinkedList.js');
}
// If the list is empty, return -1 indicating the value wasn't found
if (this._head == null) {
return -1;
}
let current = this._head;
let lastMatch = -1;
let index = 0;
while (current != null) {
// If a match is found, update the lastMatch to the current index
if (current.getValue() === value) {
lastMatch = index;
}
current = current.getNext();
index++;
}
return lastMatch;
}
// Returns true if the value is in the list, false otherwise
contains(value) {
// Returns true if indexOf() finds the value, false if it does not
return (this.indexOf(value) !== -1);
}
}
