wooorm / linked-list

Minimalistic linked lists

linked-list

Small double linked list.

Contents

• What is this?
• When should I use this?
• Install
• Use
• API
  • List([items…])
  • Item()
• Types
• Compatibility
• Security
• Contribute
• License

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

linked-list's Issues

Question: Can I republish library with some changes?

Hi, I used your code from your library to create mine with minor modifications and published it under a different name (@aintts/linked-list). I have added links to this repository, kept the license as it was, and listed you as the author.

Changes:

• Created a project from scratch using tsdx.
• Rewrote all the code to Typescript.
• Rewrote tests using Jest.
• Added observer pattern (in test mode).

If you don't want me to republish the library, please let me know - I will remove it immediately.

Swap node feature request

I'd like to request that a swap function is built into the library. Looking at dozens of linked list implementations on NPM none of them have a swap function.

Below is the code I'm using for swapping nodes. Theres a lot of references that need to be updated with a swap and many use cases such as being neighbors, or tail/head. From what I tell this code works for all those use cases but I haven't done extensive testing on it.

swap(item1, item2) {
    const temp1 = {prev: item1.prev, cur: item1, next: item1.next};
    const temp2 = {prev: item2.prev, cur: item2, next: item2.next};

    // Same node do nothing
    if(item1 === item2) {
      return;
    }

    // Update head
    if(item1 === this.head) {
      this.head = item2;
    } else if(item2 === this.head) {
      this.head = item1;
    }

    // Update tail
    if(item1 === this.tail) {
      this.tail = item2;
    } else if(item2 === this.tail) {
      this.tail = item1;
    }

    // Swap item1
    this.swapItems(item1, 'next', temp2);
    this.swapItems(item1, 'prev', temp2);

    // Swap item2
    this.swapItems(item2, 'next', temp1);
    this.swapItems(item2, 'prev', temp1);
  }

  swapItems(item, position, swap) {
    if(item !== swap[position]) {
      // Items are not neighbors
      item[position] = swap[position];
      if(item[position]) {
        // Update surrounding nodes
        if(position === 'next') {
          item[position].prev = item;
        } else if(position === 'prev') {
          item[position].next = item;
        }
      }
    } else {
      // Items are neighbors
      item[position] = swap.cur;
    }
  }

Heres a visualization of this code to show it can swap any positions and a use case for this feature:

add a length property

It will be nice if we can know the number of items at any given moment in the list

Iterator support

Would you be interested in adding first-class iterator support to the library? This would allow someone to use the linked list in places support iterations (e.g. for (const item of list)) or in iteration libraries (e.g. iterative). You can also then use Array.from(list) to turn the linked list into an array, or use it in other places that support an iterator such as Set() and Map().

This would likely be a breaking change, however, since it's an ES2015 feature.

Edit: Actually, it's probably easy enough to keep it backward compatible if needed - just more verbose.

tail should always be set for non-empty lists

List tail should always be set for non-empty lists, including when a list has only one item. In the one item case, head and tail should be the same, both pointing to the single item in the list. This preserves the defining capabilities of a doubly linked list:

• start at the head and walk forward through the entire list using next
• start at the tail and walk backward through the entire list using prev

At this time, linked-list sets the tail to null if there is only one item in the list. This is incorrect, IMO, and difficult to work with.

Consider using List to implement a FIFO queue.

• The writer is obvious. It calls list.prepend(item) whenever it needs to add an item to the queue.
• The reader should also be obvious. It should be able to drain the queue with this simple loop:

while (list.tail) {
  process(list.tail.detach())
}

Sadly, the current implementation of List requires something like

while (list.size > 0) {
  const item = (list.size === 1) ? list.head : list.tail
  process(item.detach())
}

which is uglier, but maybe more clear, or

while (list.tail || list.head) {
  process((list.tail || list.head).detach())
}

which is prettier, but mysterious.

Both of these loops are implementation specific, and I find them difficult to understand.

There is special case code here to make tail go away when the list shrinks to a single item, and two one-liners are omitted here and here to leave tail null when the first item is added. This behavior is also asserted in test.js, so I'm guessing there was a reason for this null tail behavior.

Thoughts?

the document might have something wrong

the part of

Item#prev

var item1 = new Item()
var item2 = new Item()

new List(item) // <- the `item` may have to be `item1`

// ...

index.d.ts is not included in the published npm package

index.d.ts is not included in the published npm package

TypeScript definition

Would you be interested in accepting a TypeScript definition for the library so people using TypeScript can get type safety? It's a separate file from the .js which will basically act as a header file only and I'd be happy to be a continual resource to help maintain it or respond to any queries.