linked-list
Small double linked list.
Contents
What is this?
This package is a small double linked list.
Items in linked lists know about their next sibling (the item after them).
In double linked lists, items also know about their previous sibling (the item
before them).
When should I use this?
You can use this project as a reference for how to implement a linked list but
it’s also definitely possible to use it, directly or by subclassing its lists
and items.
Install
This package is ESM only.
In Node.js (version 12.20+, 14.14+, or 16.0+), install with npm:
npm install linked-list
In Deno with Skypack:
import {List, Item} from 'https://cdn.skypack.dev/linked-list@3?dts'
In browsers with Skypack:
<script type="module">
import {List, Item} from 'https://cdn.skypack.dev/linked-list@3?min'
</script>
Use
import {List, Item} from 'linked-list'
var item1 = new Item()
var item2 = new Item()
var item3 = new Item()
var list = new List(item1, item2, item3)
list.head
list.head.next
list.head.next.next
list.head.next.prev
list.tail
list.tail.next
Subclassing:
import {List, Item} from 'linked-list'
class Tokens extends List {
join(delimiter) {
return this.toArray().join(delimiter)
}
}
class Token extends Item {
constructor(value) {
super()
this.value = value
}
toString() {
return this.value
}
}
var dogs = new Token('dogs')
var and = new Token('&')
var cats = new Token('cats')
var tokens = new Tokens(dogs, and, cats)
console.log(tokens.join(' '))
and.prepend(cats)
and.append(dogs)
console.log(tokens.join(' ') + '!')
API
This package exports the following identifiers: List
, Item
.
There is no default export.
List([items…])
new List()
new List(new Item(), new Item())
Create a new linked list.
List.from([items])
List.from()
List.from([])
List.from([new Item(), new Item()])
Create a new this
and adds the given array of items.
Ignores null
or undefined
values.
Throws an error when a given item has no detach
, append
, or prepend
methods.
List.of([items…])
List.of()
List.of(new Item(), new Item())
Creates a new linked list from the given arguments.
Defers to List.from
.
List#append(item)
var list = new List()
var item = new Item()
list.head === null
item.list === null
list.append(item)
list.head === item
item.list === list
Appends an item to a list.
Throws an error when the given item has no detach
, append
, or prepend
methods.
Returns the given item.
List#prepend(item)
var list = new List()
var item = new Item()
list.prepend(item)
Prepends an item to a list.
Throws an error when the given item has no detach
, append
, or prepend
methods.
Returns the given item.
List#toArray()
var item1 = new Item()
var item2 = new Item()
var list = new List(item1, item2)
var array = list.toArray()
array[0] === item1
array[1] === item2
array[0].next === item2
array[1].prev === item1
Returns the items in the list in an array.
List#head
var item = new Item()
var list = new List(item)
list.head === item
The first item in a list, and null
otherwise.
List#tail
var list = new List()
var item1 = new Item()
var item2 = new Item()
list.tail === null
list.append(item1)
list.tail === null
list.append(item2)
list.tail === item2
The last item in a list, and null
otherwise.
Note that a list with only one item has no tail, only a head.
List#size
var list = new List()
var item1 = new Item()
var item2 = new Item()
list.size === 0
list.append(item1)
list.size === 1
list.append(item2)
list.size === 2
The number of items in the list.
Item()
var item = new Item()
Creates a new linked list Item.
Item#append(item)
var item1 = new Item()
var item2 = new Item()
new List().append(item1)
item1.next === null
item1.append(item2)
item1.next === item2
Adds the given item after the operated on item in a list.
Throws an error when the given item has no detach
, append
, or prepend
methods.
Returns false when the operated on item is not attached to a list, otherwise the
given item.
Item#prepend(item)
var item1 = new Item()
var item2 = new Item()
new List().append(item1)
item1.prev === null
item1.prepend(item2)
item1.prev === item2
Adds the given item before the operated on item in a list.
Throws an error when the given item has no detach
, append
, or prepend
methods.
Returns false when the operated on item is not attached to a list, otherwise
the given item.
Item#detach()
var item = new Item()
var list = new List(item)
item.list === list
item.detach()
item.list === null
Removes the operated on item from its parent list.
Removes references to it on its parent list
, and prev
and next
items;
relinking them when possible.
Returns the operated on item.
Even when it was already detached.
Item#next
var item1 = new Item()
var item2 = new Item()
new List(item1)
item1.next === null
item2.next === null
item1.append(item2)
item1.next === item2
item1.detach()
item1.next === null
The items succeeding item, and null
otherwise.
Item#prev
var item1 = new Item()
var item2 = new Item()
new List(item1)
item1.prev === null
item2.prev === null
item1.append(item2)
item1.prev === item2
item2.detach()
item2.prev === null
The items preceding item, and null
otherwise.
Item#list
var item = new Item()
var list = new List()
item.list === null
list.append(item)
item.list === list
item.detach()
item.list === null
The items parent list, and null
otherwise.
Types
This package is fully typed with TypeScript.
There are no extra exported types.
Compatibility
This package is at least compatible with all maintained versions of Node.js.
As of now, that is Node.js 12.20+, 14.14+, and 16.0+.
It also works in Deno and modern browsers.
Security
This package is safe.
Contribute
Yes please!
See How to Contribute to Open Source.
License
MIT © Titus Wormer