Linked Lists using Generics
npm install generic-linked-listThis project implements a Single-Linked List that you can use for a linked list of any data type.
The motivations for this project are:
- to provide a _mostly_ drop-in replacement for Arrays (see below);
- that works with any data type;
- written in a strongly-typed language (TypeScript);
- that is well-documented;
- and is well-tested;
- and is suitable for professional Software Engineering projects.
The project focuses on backend development with NodeJs in mind. However, as it is written
in TypeScript (which compiles to JavaScript), you can use it in code targeting browsers.
Arrays are a powerful and well-used data structure in both JavaScript and TypeScript.
However, some array operations are O(n) in Time Complexity. These include shift and unshift.
This means working with large datasets is usually faster with a Linked List compared to an Array.
Linked lists are a classic time-space tradeoff when compared with arrays
for some operations.
Because a linked list has a "pointer" to the next element in the list,
each element in the list uses slightly more memory than the same list stored in an array.
But, that extra memory provides huge speed improvement for some
operations.
Most linked list operations are similar in speed to array.
_These operations are many hundreds to thousands of times faster than an array!_
If you're working with lists of 10's or 100's of thousands of elements, and you need these operations,
you should consider a linked list instead of an array for storing those elements.
Some linked list operations are significantly slower than an array because the list must
be traversed from beginning to some point in the list (usually all the way to the end).
* at
* fill
* lastIndexOf
* pop
* slice
If your use case requires these operations on a large lists, then you should consider using
a different data structure (such as Array).
The following operations cannot be implemented efficiently in a singly-linked list and
are not implemented.
These can be implemented in a doubly-linked list, and such a data structure is planned for a
future release of this package.
* reverse
* reduceRight
Code sizes:
* The compiled Typescript is 7 kilobytes when minified.
* The full JavaScript code including comments is around 40 kilobytes.
* The unit tests are around 120 kilobytes.
1. Import the library.
2. Create your linked list.
3. Use it!
With yarn:
``shell`
yarn add generic-linked-list --save
With npm:
`shell`
npm --save-prod i generic-linked-list
shell
$ node dist/examples/plainjs.js
A simple numeric list is [ 0, 1, 2 ]
`Typescript (directly):
`shell
$ ts-node src/examples/example.ts a b c
Your linked list is a,b,cA list of numbers expanded using spread syntax [ 1, 2, 3 ]
The same list converted to a string [1,2,3]
Let us build a list of Person objects...
A list of people expanded using spread syntax { name: 'John', age: 12, parent: { name: 'John', age: 42 } } { name: 'Kylie', age: 14 }
The same list converted to a string {"name":"John","age":12,"parent":{"name":"John","age":42}},{"name":"Kylie","age":14}
Here's the array after converting the people list to an array:
[
{ name: 'John', age: 12, parent: { name: 'John', age: 42 } },
{ name: 'Kylie', age: 14 }
]
`Typescript (compiled):
`shell
$ yarn build
$ node dist/examples/example.js a b c
`
_Same output as above._$3
Example 1
`typescript
import { LinkedList } from 'generic-linked-list';const numList = new LinkedList([1, 2, 3]);
console.log(...numList);
console.log(numList.toString());
`Expected output:
`text
[ 1, 2, 3 ]
[1,2,3]
`Example 2
`typescript
import { LinkedList } from 'generic-linked-list';type Person = { name: string, age: number; parent?: Person };
const peopleList = new LinkedList();
peopleList.push(
{name: 'John', age: 12, parent: {name: 'John', age: 42}},
{name: 'Kylie', age: 14}
);
console.log(...peopleList);
console.log(peopleList.toString());
`Expected output:
`text
{ name: 'John', age: 12, parent: { name: 'John', age: 42 } } { name: 'Kylie', age: 14 }
{"name":"John","age":12,"parent":{"name":"John","age":42}},{"name":"Kylie","age":14}
`Example 3 (plain JavaScript)
`javascript
const LinkedList = require('generic-linked-list').LinkedList;const sampleList = new LinkedList([0, 1, 2]);
console.log(
Your linked list is ${[...sampleList]});
`Expected output:
`text
Your linked list is 0,1,2
`Where to next?
The documentation is generated using TypeDoc using
comments in the source code.
The project's GitHub page contains the documentation and
is the best place to start.
Example code
To access example code that actually runs:
- download the package;
- look in the
src/examples folder.Version 2 Compatibility
Version 2 aims to be even closer to a drop-in replacement for Array.Version 2 implements additional constructor options to make LinkedList more similar to Array construction.
It also clarifies the semantics of the
from method.In particular, the constructor now implements both a length and an item list constructor.
$3
This means that the following code in Version 1:`typescript
const list = new LinkedList([1, 2]);
`
must be changed to:
`typescript
const list = new LinkedList(...[1, 2]);
`
or
`typescript
const list = new LinkedList(1, 2);
`If you want to build a LinkedList from an array with the spread operator, use the
from method:
`typescript
const list = LinkedList.from([1, 2]);
`$3
LinkedList.from behaves differently to Array when called with non-array constructors. See the
documentation for Array about this.Version History
| Version | Date | Description |
|---------|-------------|----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| 2.0.1 | 11-Dec-2022 | Some documentation improvements. |
| 2.0.0 | 11-Dec-2022 | Version 2 is mostly compatible with version 1, except for the following:
Constructor and
from enhancements may require some refactoring of your existing version 1 code.
The push method also accepts an iterator. Array.push does not support this.
Added support for negative indexes in these methods:
atindexOfincludesslice
Added the following methods:
entriesflatflatMapfromgrowjoinkeyskeysAsListlastIndexOfofmappopreducesplicetruncate |
| 1.1.3 | 11-Nov-2022 | Documentation and test improvements. |
| 1.1.2 | 15-Oct-2022 | Added missing index.ts file. |
| 1.1.1 | 15-Oct-2022 | Test improvements. |
| 1.1.0 | 15-Oct-2022 | Added slice and end` methods. |The project was developed in NodeJs version 14.15.4 and should run seamlessly in any later
version of Node.js.
The project was developed with TypeScript 4.5.5 and should compile seamlessly in any later
version of TypeScript.
Russell Robinson is a Software Engineer with decades of experience across a range of industries.
He lives in Melbourne, Australia and can be contacted via email (russellr@openconcepts.com.au).