Mnemonist

Linked List


A linked list is basically a list in which every items keep a reference to the next item in the list.

They are a bit different from arrays - which we are more used to handle in JavaScript - in that they don’t need to store their items in contiguous memory blocks and therefore do not allow for random access in constant time.

However, and this is where this structure shine, a linked list is able to modify its order in constant time, which is impossible with an ordinary array.

For more information about the Linked List, you can head here.

var LinkedList = require('mnemonist/linked-list');

Constructor

The LinkedList takes no argument.

Static #.from

Alternatively, one can build a LinkedList from an arbitrary JavaScript iterable likewise:

var list = LinkedList.from([1, 2, 3]);

Members

Methods

Mutation

Read

Iteration

#.size

Number of items in the list.

var list = new LinkedList();
list.size
>>> 0

#.push

Adds an item at the end of the list.

O(1)

var list = new LinkedList();

list.push(1);

#.unshift

Adds an item at the beginning of the list.

O(1)

var list = new LinkedList();

list.unshift(1);

#.shift

Remove & retrieves the first item of the list.

O(1)

var list = new LinkedList();

list.unshift(1);
list.shift();
>>> 1

#.clear

Completely clears the list of its items.

O(1)

var list = new LinkedList();

list.unshift(1);
list.clear();
list.toArray();
>>> []

#.first, #.peek

Retrieves the first item of the list.

O(1)

var list = new LinkedList();

list.unshift(1);
list.first();
>>> 1

#.last

Retrieves the last item of the list.

O(1)

var list = new LinkedList();

list.push(1);
list.push(2);
list.last();
>>> 2

#.forEach

Iterates over the list by applying the callback on every item.

var list = new LinkedList();

list.push(1);
list.push(2);

list.forEach(function(item, index, list) {
  console.log(index, item);
});

#.toArray

Converts the list into a JavaScript array.

var list = new LinkedList();

list.push(1);
list.push(2);

list.toArray();
>>> [1, 2]

#.values

Returns an iterator over the list’s values.

var list = LinkedList.from([1, 2, 3]);

var iterator = list.values();

iteraror.next().value
>>> 1

#.entries

Returns an iterator over the list’s entries.

var list = LinkedList.from([1, 2, 3]);

var iterator = list.entries();

iterator.next().value
>>> [0, 1]

Iterable

Alternatively, you can iterate over a list’s values using ES2015 for...of protocol:

var list = LinkedList.from([1, 2, 3]);

for (var item of list) {
  console.log(item);
}