Neon Papier Mâché

    linked-list
    TypeScript icon, indicating that this package has built-in type declarations

    3.1.0 • Public • Published

    linked-list

    Build Coverage Downloads Size

    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 14.14+, 16.0+), install with npm:

    npm install linked-list

    In Deno with esm.sh:

    import {List, Item} from 'https://esm.sh/linked-list@3'

    In browsers with esm.sh:

    <script type="module">
      import {List, Item} from 'https://esm.sh/linked-list@3?bundle'
    </script>

    Use

    import {List, Item} from 'linked-list'
    
    const item1 = new Item()
    const item2 = new Item()
    const item3 = new Item()
    const list = new List(item1, item2, item3)
    
    list.head // => item1
    list.head.next // => item2
    list.head.next.next // => item3
    list.head.next.prev // => item1
    list.tail // => item3
    list.tail.next // => `null`

    Subclassing:

    import {List, Item} from 'linked-list'
    
    class Tokens extends List {
      /** @param {string} delimiter */
      join(delimiter) {
        return this.toArray().join(delimiter)
      }
    }
    
    class Token extends Item {
      /** @param {string} value */
      constructor(value) {
        super()
        this.value = value
      }
    
      toString() {
        return this.value
      }
    }
    
    const dogs = new Token('dogs')
    const and = new Token('&')
    const cats = new Token('cats')
    const tokens = new Tokens(dogs, and, cats)
    
    console.log(tokens.join(' ')) // => 'dogs & cats'
    
    and.prepend(cats)
    and.append(dogs)
    
    console.log(tokens.join(' ') + '!') // => 'cats & dogs!'

    API

    This package exports the identifiers List and Item. There is no default export.

    List([items…])

    new List()
    new List(new Item(), new Item())

    Create a new list from the given items.

    Ignores null or undefined values. Throws an error when a given item has no detach, append, or prepend methods.

    List.from([items])

    List.from()
    List.from([])
    List.from([new Item(), new Item()])

    Create a new this from 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())

    Create a new this from the given arguments.

    Ignores null or undefined values. Throws an error when a given item has no detach, append, or prepend methods.

    List#append(item)

    const list = new List()
    const item = new Item()
    
    console.log(list.head === null) // => true
    console.log(item.list === null) // => true
    
    list.append(item)
    
    console.log(list.head === item) // => true
    console.log(item.list === list) // => true

    Append 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)

    const list = new List()
    const item = new Item()
    
    list.prepend(item)

    Prepend 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()

    const item1 = new Item()
    const item2 = new Item()
    const list = new List(item1, item2)
    const array = list.toArray()
    
    console.log(array[0] === item1) // => true
    console.log(array[1] === item2) // => true
    console.log(array[0].next === item2) // => true
    console.log(array[1].prev === item1) // => true

    Returns the items of the list as an array.

    This does not detach the items.

    Note: List also implements an iterator. That means you can also do [...list] to get an array.

    List#head

    const item = new Item()
    const list = new List(item)
    
    console.log(list.head === item) // => true

    The first item in a list or null otherwise.

    List#tail

    const list = new List()
    const item1 = new Item()
    const item2 = new Item()
    
    console.log(list.tail === null) // => true
    
    list.append(item1)
    console.log(list.tail === null) // => true, see note.
    
    list.append(item2)
    console.log(list.tail === item2) // => true

    The last item in a list and null otherwise.

    👉 Note: a list with only one item has no tail, only a head.

    List#size

    const list = new List()
    const item1 = new Item()
    const item2 = new Item()
    
    console.log(list.size === 0) // => true
    
    list.append(item1)
    console.log(list.size === 1) // => true
    
    list.append(item2)
    console.log(list.size === 2) // => true

    The number of items in the list.

    Item()

    const item = new Item()

    Create a new linked list item.

    Item#append(item)

    const item1 = new Item()
    const item2 = new Item()
    
    new List().append(item1)
    
    console.log(item1.next === null) // => true
    
    item1.append(item2)
    console.log(item1.next === item2) // => true

    Add 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)

    const item1 = new Item()
    const item2 = new Item()
    
    new List().append(item1)
    
    console.log(item1.prev === null) // => true
    
    item1.prepend(item2)
    console.log(item1.prev === item2) // => true

    Add 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()

    const item = new Item()
    const list = new List(item)
    
    console.log(item.list === list) // => true
    
    item.detach()
    console.log(item.list === null) // => true

    Remove the operated on item from its parent list.

    Removes references to it on its parent list, and prev and next items. Relinks all references. Returns the operated on item. Even when it was already detached.

    Item#next

    const item1 = new Item()
    const item2 = new Item()
    
    const list = new List(item1)
    
    console.log(item1.next === null) // => true
    console.log(item2.next === null) // => true
    
    item1.append(item2)
    
    console.log(item1.next === item2) // => true
    
    item1.detach()
    
    console.log(item1.next === null) // => true

    The following item or null otherwise.

    Item#prev

    const item1 = new Item()
    const item2 = new Item()
    
    const list = new List(item1)
    
    console.log(item1.prev === null) // => true
    console.log(item2.prev === null) // => true
    
    item1.append(item2)
    
    console.log(item2.prev === item1) // => true
    
    item2.detach()
    
    console.log(item2.prev === null) // => true

    The preceding item or null otherwise.

    Item#list

    const item = new Item()
    const list = new List()
    
    console.log(item.list === null) // => true
    
    list.append(item)
    
    console.log(item.list === list) // => true
    
    item.detach()
    
    console.log(item.list === null) // => true

    The list this item belongs to or null otherwise.

    Types

    This package is fully typed with TypeScript. It exports no additional types.

    Compatibility

    This package is at least compatible with all maintained versions of Node.js. As of now, that is Node.js 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

    Install

    npm i linked-list

    DownloadsWeekly Downloads

    61,919

    Version

    3.1.0

    License

    MIT

    Unpacked Size

    26.6 kB

    Total Files

    5

    Last publish

    Collaborators

    • wooorm