Singly Linked-List

A JavaScript Singly Linked-List data structure.

Installation

Install @truck/singly-linked-list via npm:

$ npm install --save @truck/singly-linked-list

Methods

constructor()

Build a new Singly Linked-List.

delete(value: any): boolean

O(n). Deletes a value from the Singly Linked-List. The default === comparator is used.

delete(comparator: (value: any) => boolean): boolean

O(n). Deletes a value from the Singly 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 Singly 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 Singly 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 Singly 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 Singly 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 Singly Linked-List.

search(value: any): Node|undefined

O(n). Returns the first value in the Singly 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 Singly Linked-List that matches. Uses comparator to determine whether the value matches.

toArray(): any[]

O(n). Converts the Singly Linked-List's values to an array.

toArray(callback: (node: Node) => any): any[]

O(n). Converts the Singly Linked-List to an array, the callback receives the Node with each iteration.

Properties

.length: number

Returns the current length of the Singly Linked-List.

Examples

A Singly Linked-List is a standard class which can be instantiated with the new keyword:

// Build a new Singly Linked-List
const singlyLinkedList = new SinglyLinkedList();
// Get the length of the Singly Linked-List
let length = singlyLinkedList.length; // 0
// Add some values to the Singly Linked-List
singlyLinkedList.insert(1);
singlyLinkedList.insert('two');
singlyLinkedList.insert({ three: 'three' });
singlyLinkedList.insert(false);
singlyLinkedList.insert('FIVE');
// Get the length of the Singly Linked-List
length = singlyLinkedList.length; // 5
// Search for a Node by value
const node = singlyLinkedList.search(false);
/*
  Node {
    next: Node {
      next: undefined;
      value: 'FIVE';
    };
    value: false;
  }
*/
// Delete some values from the Singly Linked-List
singlyLinkedList.delete(1);
singlyLinkedList.delete('two');
singlyLinkedList.delete({ three: 'three' }, (a, b) => a.three === b.three);
singlyLinkedList.delete(false);
singlyLinkedList.delete('FIVE');
// Get the length of the Singly Linked-List
length = singlyLinkedList.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.