Doubly Linked-List
A JavaScript Doubly Linked-List data structure.
Installation
Install @truck/doubly-linked-list
via npm:
$ npm install --save @truck/doubly-linked-list
Methods
constructor()
Build a new Doubly Linked-List.
delete(value: any): boolean
O(n). Deletes a value from the Doubly Linked-List. The default ===
comparator is used.
delete(comparator: (value: any) => boolean): boolean
O(n). Deletes a value from the Doubly Linked-List. Uses the comparator
to determine whether
the value
should be deleted.
insert(value: any): void
O(1). Inserts a value at the beginning of the Doubly Linked-List.
insertAfter(value: any, after: any): void
O(n). Inserts value
after after
. If after
is not found value
is inserted at the end of
the Doubly Linked-List.
insertAfter(value: any, comparator: (value: any) => boolean): void
O(n). Inserts value
after after
comparator returns true
. If after
does not return true
then value
is inserted at the end of the Doubly Linked-List.
insertBefore(value: any, before: any): void
O(n). Inserts value
before before
. If before
is not found value
is inserted at the end
of the Doubly Linked-List.
insertBefore(value: any, comparator: (value: any) => boolean): void
O(n). Inserts value
before before
comparator returns true
. If before
does not return
true
then value
is inserted at the end of the Doubly Linked-List.
search(value: any): Node|undefined
O(n). Returns the first value
in the Doubly Linked-List that matches value
. The default
===
comparator is used.
search(comparator: (value: any) => boolean): Node|undefined
O(n). Returns the first value
in the Doubly Linked-List that matches. Uses comparator
to
determine whether the value
matches.
toArray(): any[]
O(n). Converts the Doubly Linked-List's values to an array.
toArray(callback: (node: Node) => any): any[]
O(n). Converts the Doubly Linked-List to an array, the callback
receives the Node
with
each iteration.
Properties
.length: number
Returns the current length of the Doubly Linked-List.
Examples
A Doubly Linked-List is a standard class which can be instantiated with the new
keyword:
// Build a new Doubly Linked-List
const doublyLinkedList = new DoublyLinkedList();
// Get the length of the Doubly Linked-List
let length = doublyLinkedList.length; // 0
// Add some values to the Doubly Linked-List
doublyLinkedList.insert(1);
doublyLinkedList.insert('two');
doublyLinkedList.insert({ three: 'three' });
doublyLinkedList.insert(false);
doublyLinkedList.insert('FIVE');
// Get the length of the Doubly Linked-List
length = doublyLinkedList.length; // 5
// Search for a Node by value
const node = doublyLinkedList.search(false);
/*
Node {
next: Node {
next: undefined;
value: 'FIVE';
};
value: false;
}
*/
// Delete some values from the Doubly Linked-List
doublyLinkedList.delete(1);
doublyLinkedList.delete('two');
doublyLinkedList.delete({ three: 'three' }, (a, b) => a.three === b.three);
doublyLinkedList.delete(false);
doublyLinkedList.delete('FIVE');
// Get the length of the Doubly Linked-List
length = doublyLinkedList.length; // 0
Testing
Use the following command to run all the tests described below together:
$ docker-compose run --rm app npm test
Commit messages
Commit messages are linted through the use of husky and @commitlint/cli using the @commitlint/config-conventional commit convention.
Please read through the AngularJS Git Commit Message Conventions to get a better understanding of how commit messages are formatted.
After doing an npm install
the required git hooks wil be added automatically and commit messages
will be linted automatically.
Linting
Linting is done using eslint using the eslint-config-airbnb-base configuration with very few alterations, all of which can be seen in the .eslintrc file in the root of this repository.
Linting can be run in isolation through the command:
$ docker-compose run --rm app npm run test:lint
Auditing
Auditing of dependencies is done through the npm audit command-line tool.
Auditing can be run in isolation through the command:
$ docker-compose run --rm app npm run test:vulnerabilities
Unit testing
Unit testing is done with jest. The test file for each file to be tested is to
be placed alongside the file in testing and marked with the .test.js
extension.
Unit testing can be run in isolation through the command:
$ docker-compose run --rm app npm run test:scripts
Contributing
Contributions are always welcome, just submit a PR to get the conversation going. Please make sure all tests pass before submitting a PR.
Releases
The moment a PR is merged into the master
branch
semantic-release will kick-off a new
release, thus the importance of clear commit messages.