LinkedList

Singly linked, doubly linked, and circular LinkedList classes.


- LinkedList
- Instance Properties
- head
- tail
- size
- double
- circular
- Constructor Properties
- ListElement
- Prototype Methods
- @@iterator
- values
- elements
- forEach
- fromIterable
- coerceElement
- item
- find
- includes
- getPrev
- first
- last
- clear
- concat
- remove
- insertBefore
- insertAfter
- prepend
- unshift
- append
- push
- shift
- pushBack
- copyWithin
- DoubleLinkedList
- CircularLinkedList
- CircularDoubleLinkedList
- ListElement
- Prototype Methods
- fromElement

You can import the list constructors like so:

``JavaScript
const listlib = require("listlib");
const LinkedList = listlib.LinkedList;
const DoubleLinkedList = listlib.DoubleLinkedList;
const CircularLinkedList = listlib.CircularLinkedList;
const CircularDoubleLinkedList = listlib.CircularDoubleLinkedList;

// Using ES6 Destructuring Assignment
const {
LinkedList,
DoubleLinkedList,
CircularLinkedList,
CircularDoubleLinkedList
} = require("listlib");
`

---

LinkedList

Constructor

`JavaScript
new LinkedList( [ iterable = null ] );
`
> Uses ListElement to represent the list structure.

Acyclic Singly Linked List.

Constructor Parameters


- iterable (Optional) Iterable

The values of the optional Iterable will be used to populate the new LinkedList.

Examples

Example 1: Basic Usage:

`JavaScript
// Array of arbitrary numbers.
var arr = [1,2,3,4,5];

// New LinkedList is created using the contents of arr.
var list = new LinkedList(arr);

// Append "6" to the end of the list, returns a new ListElement.
var six = list.push(6);

// Prepends "7" to the beginning of the list, returns a new ListElement.
var seven = list.unshift(7);

// Moves "7" to the end of the list.
list.pushBack(seven);

// Logs 1, 2, 3, 4, 5, 6, and 7.
for (const element of list) {
console.log(element.payload);
}
`

Instance Properties

$3

ListElement
`JavaScript
LinkedList.head
`
A ListElement which is considered the head/start of the list, and is used to begin enumeration of subsequent ListElements.

$3

ListElement
`JavaScript
LinkedList.tail
`
A ListElement which is considered the tail/end of the list, and is used to end enumeration of preceding ListElements.

$3

Number
`JavaScript
LinkedList.size
`
A number representing the quantity of ListElements within the LinkedList, not counting the head and tail elements.

$3

Boolean
`JavaScript
LinkedList.double
`
Indicates if the LinkedList is doubly linked, linking every ListElement in both directions.

$3

Boolean
`JavaScript
LinkedList.circular
`
Indicates if the LinkedList is circular, linking the head and tail elements.

---

Constructor Properties

$3

See the ListElement documentation.

---

Prototype Methods

$3

Iterator
`JavaScript
LinkedListSymbol.iterator;
`
An iterator which yields each ListElement in the LinkedList, except for the head and tail elements.

#### Parameters
- ends Boolean

If set to true, the iterator will include the head/tail ListElements in iteration. In a circular LinkedList, this will cause the iterator to infinitely loop through the list unless some user-supplied break condition is in place.

#### Examples
Example 1: Basic Usage:

`JavaScript
// Array of arbitrary numbers.
var arr = [1,2,3,4,5];

// New LinkedList is created using the contents of arr.
var list = new LinkedList(arr);

// Logs 1, 2, 3, 4, and 5.
for (const value of list) console.log(element.payload);
`

Example 1: ends Usage:

`JavaScript
// Array of arbitrary numbers.
var arr = [1,2,3,4,5];

// New LinkedList is created using the contents of arr.
var list = new LinkedList(arr);

// Logs null, 1, 2, 3, 4, 5, and null.
for (const value of listSymbol.iterator) console.log(element.payload);
`

---

$3

Iterator
`JavaScript
LinkedList.values();
`
An iterator which yields the value of each ListElement in the LinkedList.

#### Examples
Example 1: Basic Usage:

`JavaScript
// Array of arbitrary numbers.
var arr = [1,2,3,4,5];

// New LinkedList is created using the contents of arr.
var list = new LinkedList(arr);

// Logs 1, 2, 3, 4, and 5.
for (const value of list.values()) console.log(value);
`

---

$3

Iterator
`JavaScript
LinkedList.elements();
`
An iterator which yields each ListElement in the LinkedList, except for the head and tail elements.

#### Examples
Example 1: Basic Usage:

`JavaScript
// Array of arbitrary numbers.
var arr = [1,2,3,4,5];

// New LinkedList is created using the contents of arr.
var list = new LinkedList(arr);

// Logs 1, 2, 3, 4, and 5.
for (const value of list.values()) console.log(value);
`

---

forEach

Higher-Order Function
`JavaScript
LinkedList.forEach( callback );
`
Calls callback with the value of each ListElement.

Parameters


- callback Function

The callback function to execute for each ListElement value.

$3

- value

The value of the current ListElement being enumerated over.

- index

The index (Starting at zero) of the current ListElement being enumerated over.

- list

The target LinkedList being iterated through.

Examples

Example 1: Basic Usage:

`JavaScript
// Array of arbitrary numbers.
var arr = [1,2,3,4,5];

// New LinkedList is created using the contents of arr.
var list = new LinkedList(arr);

// Logs 1, 2, 3, 4, and 5.
list.forEach(function (value, index, list) {
console.log(value);
});
`

---

$3

Function
`JavaScript
LinkedList.fromIterable( iterable );
`
Inserts the values of the Iterable into the LinkedList.

#### Parameters
- iterable Iterable

The iterable to copy values from.

#### Examples
Example 1: Basic Usage:

`JavaScript
// Array of arbitrary numbers.
var arr = [1,2,3,4,5];

// New empty LinkedList is created.
var list = new LinkedList();

// Contents of arr are inserted into the list.
list.fromIterable(arr);
`

---

$3

Function
`JavaScript
LinkedLst.coerceElement( value );
`
Creates a new ListElement using value. If value is already a ListElement, it is returned.

#### Parameters
- value Any

A ListElement, or a value to create a new ListElement with.

#### Examples
Example 1: Basic Usage:

`JavaScript
// Arbitrary number.
var numbers = 123;

// Returns a new ListElement with numbers assigned to element.payload.
var element = LinkedList.coerceElement(numbers);
`

---

$3

Function
`JavaScript
LinkedList.item( index );
`
Returns the ListElement at the specified 0-indexed offset from the head element, or null if it was not found.

#### Parameters
- index Number

An offset from the head element, starting at zero, to look for a ListElement at.

#### Examples
Example 1: Basic Usage:

`JavaScript
// Array of arbitrary numbers.
var arr = [1,2,3,4,5];

// New LinkedList is created using the contents of arr.
var list = new LinkedList(arr);

// Returns the ListElement at index 4, the last element in the list, which contains "5".
var foundElement = list.item(4);
`

---

$3

Function
`JavaScript
LinkedList.find( value );
`
Returns the first ListElement encountered that contains a payload matching value, or null if one was not found.

#### Parameters
- value Any

A value to search for in the LinkedList.

#### Examples
Example 1: Basic Usage:

`JavaScript
// Array of arbitrary numbers.
var arr = [1,2,3,4,5];

// New LinkedList is created using the contents of arr.
var list = new LinkedList(arr);

// Returns the ListElement containing "3".
var foundElement = list.find(3);
`

---

$3

Function
`JavaScript
LinkedList.includes( value );
`
Returns true if a ListElement is found which contains a payload matching value, or false if one was not found.

#### Parameters
- value Any

A value to search for in the LinkedList.

#### Examples
Example 1: Basic Usage:

`JavaScript
// Array of arbitrary numbers.
var arr = [1,2,3,4,5];

// New LinkedList is created using the contents of arr.
var list = new LinkedList(arr);

// Returns true.
var wasFound = list.includes(3);
`

---

$3

Function
`JavaScript
LinkedList.getPrev( element );
`
Returns the ListElement located before element, or null if it was not found.

#### Parameters
- element ListElement

A ListElement to search for the preceding ListElement of in the LinkedList.

#### Examples
Example 1: Basic Usage:

`JavaScript
// Array of arbitrary numbers.
var arr = [1,2,3,4,5];

// New LinkedList is created using the contents of arr.
var list = new LinkedList(arr);

// Returns the element containing "2".
var two = list.find(2);

// Returns the ListElement containing "1".
var one = list.getPrev(two);
`

---

$3

Function
`JavaScript
LinkedList.first();
`
Returns the element at the beginning of the LinkedList, or null if the list is empty.

#### Examples
Example 1: Basic Usage:

`JavaScript
// Array of arbitrary numbers.
var arr = [1,2,3,4,5];

// New LinkedList is created using the contents of arr.
var list = new LinkedList(arr);

// Returns the element containing "1".
var one = list.first();
`

---

$3

Function
`JavaScript
LinkedList.last();
`
Returns the element at the end of the LinkedList, or null if the list is empty.

#### Examples
Example 1: Basic Usage:

`JavaScript
// Array of arbitrary numbers.
var arr = [1,2,3,4,5];

// New LinkedList is created using the contents of arr.
var list = new LinkedList(arr);

// Returns the element containing "5".
var five = list.last();
`

---

$3

Function
`JavaScript
LinkedList.clear();
`
Removes all elements from the LinkedList.

#### Examples
Example 1: Basic Usage:

`JavaScript
// Array of arbitrary numbers.
var arr = [1,2,3,4,5];

// New LinkedList is created using the contents of arr.
var list = new LinkedList(arr);

// List becomes empty.
list.clear();
`

---

$3

Function
`JavaScript
LinkedList.concat( list1 [, list2, ..., listN ] );
`
Concatenates multiple LinkedLists into the callee LinkedList.

#### Parameters
- list1...listN ListElement

An argument list of LinkedLists to concatenate.

#### Examples
Example 1: Basic Usage:

`JavaScript
// Array of arbitrary numbers.
var arr = [1,2,3,4,5];

// New LinkedLists are created using the contents of arr.
var list1 = new LinkedList(arr);
var list2 = new LinkedList(arr);
var list3 = new LinkedList(arr);

// Appends list2 and list3 to the end of list1.
list1.concat(list2, list3);

// Logs 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5.
for (const element of list) {
console.log(element.payload);
}
`

---

$3

Function
`JavaScript
LinkedList.remove( element );
`
Removes and returns an element from the LinkedList.

#### Parameters
- element ListElement

A ListElement object to remove from the LinkedList.

#### Examples
Example 1: Basic Usage:

`JavaScript
// Array of arbitrary numbers.
var arr = [1,2,3,4,5];

// New LinkedList is created using the contents of arr.
var list = new LinkedList(arr);

// Get the element which contains "3".
var three = list.find(3);

// Removes the element from the list.
list.remove(three);
`

---

$3

Function
`JavaScript
LinkedList.insertBefore( element, newElement );
`
Inserts a ListElement before element

#### Parameters
- element ListElement

A ListElement object to prepend with newElement.

- newElement Any

A ListElement or arbitrary value to add to the LinkedList before element.

#### Examples
Example 1: Basic Usage:

`JavaScript
// Array of arbitrary numbers.
var arr = [1,2,3,4,5];

// New LinkedList is created using the contents of arr.
var list = new LinkedList(arr);

// Get the element which contains "3".
var three = list.find(3);

// Inserts "2.5" before "3".
var twoPointFive = list.insertBefore(three, 2.5);
`

---

$3

Function
`JavaScript
LinkedList.insertAfter( element, newElement );
`
Inserts a ListElement after element

#### Parameters
- element ListElement

A ListElement object to prepend with newElement.

- newElement Any

A ListElement or arbitrary value to add to the LinkedList after element.

#### Examples
Example 1: Basic Usage:

`JavaScript
// Array of arbitrary numbers.
var arr = [1,2,3,4,5];

// New LinkedList is created using the contents of arr.
var list = new LinkedList(arr);

// Get the element which contains "3".
var three = list.find(3);

// Inserts "3.5" after "3".
var threePointFive = list.insertAfter(three, 3.5);
`

---

$3

Function
`JavaScript
LinkedList.prepend( element );
`
> Alias: unshift

Inserts a ListElement at the beginning of the LinkedList.

#### Parameters
- element Any

A ListElement or arbitrary value to prepend the LinkedList with.

#### Examples
Example 1: Basic Usage:

`JavaScript
// Array of arbitrary numbers.
var arr = [1,2,3,4,5];

// New LinkedList is created using the contents of arr.
var list = new LinkedList(arr);

// Inserts "0" at the beginning of the list.
var zero = list.prepend(0);
`

---

$3

Function
`JavaScript
LinkedList.unshift( element );
`
An alias of LinkedList.prepend.

---

$3

Function
`JavaScript
LinkedList.append( element );
`
> Alias: push

Inserts a ListElement at the end of the LinkedList.

#### Parameters
- element Any

A ListElement or arbitrary value to append the LinkedList with.

#### Examples
Example 1: Basic Usage:

`JavaScript
// Array of arbitrary numbers.
var arr = [1,2,3,4,5];

// New LinkedList is created using the contents of arr.
var list = new LinkedList(arr);

// Inserts "6" at the end of the list.
var six = list.append(6);
`

---

$3

Function
`JavaScript
LinkedList.push( element );
`
An alias of LinkedList.prototype.append.

---

$3

Function
`JavaScript
LinkedList.shift();
`
Removes an element from the beginning of the LinkedList and returns it.

#### Examples
Example 1: Basic Usage:

`JavaScript
// Array of arbitrary numbers.
var arr = [1,2,3,4,5];

// New LinkedList is created using the contents of arr.
var list = new LinkedList(arr);

// Removes and returns the first element in the list.
var one = list.shift();
`

---

$3

Function
`JavaScript
LinkedList.pushBack( element );
`
Moves a ListElement to the end of the LinkedList.

#### Parameters
- element Any

A ListElement object to move to the end of the LinkedList.

#### Examples
Example 1: Basic Usage:

`JavaScript
// Array of arbitrary numbers.
var arr = [1,2,3,4,5];

// New LinkedList is created using the contents of arr.
var list = new LinkedList(arr);

// Returns the element containing "2".
var two = list.find(2);

// Moves "2" to the end of the list.
list.pushBack(two);
`

---

$3

Function
`JavaScript
LinkedList.copyWithin( target [, start = 0 [, end = LinkedList.size ]] );
`
Shallow copies ListElements to another location in the same LinkedList and returns it, without modifying its size.

#### Parameters
- target Number

Zero based index at which to copy the sequence to. If negative, target will be counted from the end. If target is at or greater than LinkedList.size, nothing will be copied. If target is positioned after start, the copied sequence will be trimmed to fit LinkedList.size.

- start (Optional) Number

Zero based index at which to start copying elements from. If negative, start will be counted from the end. If start is omitted, copyWithin will copy from the start of the LinkedList (defaults to 0).

- end (Optional) Number

Zero based index at which to end copying elements from. Copies up to but not including end. If negative, end will be counted from the end.

#### Examples
Example 1: Basic Usage:

`JavaScript
// Array of arbitrary numbers.
var arr = [1,2,3,4,5];

// New LinkedList is created using the contents of arr.
var list = new LinkedList(arr);

// Copy to index 0 the element at index 3.
list.copyWithin(0, 3, 4);

// Logs 4, 2, 3, 4, 5
for (const element of list) {
console.log(element.payload);
}

// Copy to index 1 all elements from index 3 to the end.
list.copyWithin(1, 3);

// Logs 4, 4, 5, 4, 5
for (const element of list) {
console.log(element.payload);
}
`

---

DoubleLinkedList

Constructor

`JavaScript
new DoubleLinkedList( [ iterable = null ] );
`
> Inherits from LinkedList

> Uses ListElement to represent the list structure.

> Refer to the LinkedList documentation for member methods & properties.

Circular Doubly Linked List. Elements have references to previous elements, making some operations faster.

Constructor Parameters


- iterable (Optional) Iterable

The values of the optional Iterable will be used to populate the new CircularDoubleLinkedList.

Examples

Example 1: Basic Usage:

`JavaScript
// Array of arbitrary numbers.
var arr = [1,2,3,4,5];

// New DoubleLinkedList is created using the contents of arr.
var list = new DoubleLinkedList(arr);

// Append "6" to the end of the list, returns a new ListElement.
var six = list.push(6);

// Prepends "7" to the beginning of the list, returns a new ListElement.
var seven = list.unshift(7);

// Moves "7" to the end of the list.
list.pushBack(seven);

// Logs 1, 2, 3, 4, 5, 6, and 7.
for (const element of list) {
console.log(element.payload);
}
`

---

CircularLinkedList

Constructor

`JavaScript
new CircularLinkedList( [ iterable = null ] );
`
> Inherits from LinkedList

> Uses ListElement to represent the list structure.

> Refer to the LinkedList documentation for member methods & properties.

Circular Singly Linked List. The tail and head elements are connected to create a cycle. Iterators will infinitely loop through this list unless they are either interrupted or the list structure becomes broken.

Constructor Parameters


- iterable (Optional) Iterable

The values of the optional Iterable will be used to populate the new CircularDoubleLinkedList.

Examples

Example 1: Basic Usage:

`JavaScript
// Array of arbitrary numbers.
var arr = [1,2,3,4,5];

// New CircularLinkedList is created using the contents of arr.
var list = new CircularLinkedList(arr);

// Append "6" to the end of the list, returns a new ListElement.
var six = list.push(6);

// Prepends "7" to the beginning of the list, returns a new ListElement.
var seven = list.unshift(7);

// Moves "7" to the end of the list.
list.pushBack(seven);

// Repeatedly logs 1, 2, 3, 4, 5, 6, and 7, in an infinite loop.
for (const element of list) {
console.log(element.payload);
}
`

---

CircularDoubleLinkedList

Constructor

`JavaScript
new CircularDoubleLinkedList( [ iterable = null ] );
`
> Inherits from LinkedList

> Uses ListElement to represent the list structure.

> Refer to the LinkedList documentation for member methods & properties.

Circular Doubly Linked List. Elements have references to previous elements, making some operations faster. The tail and head elements are connected to create a cycle. Iterators will infinitely loop through this list unless they are either interrupted or the list structure becomes broken.

Constructor Parameters


- iterable (Optional) Iterable

The values of the optional Iterable will be used to populate the new CircularDoubleLinkedList.

Examples

Example 1: Basic Usage:

`JavaScript
// Array of arbitrary numbers.
var arr = [1,2,3,4,5];

// New CircularDoubleLinkedList is created using the contents of arr.
var list = new CircularDoubleLinkedList(arr);

// Append "6" to the end of the list, returns a new ListElement.
var six = list.push(6);

// Prepends "7" to the beginning of the list, returns a new ListElement.
var seven = list.unshift(7);

// Moves "7" to the end of the list.
list.pushBack(seven);

// Logs 1, 2, 3, 4, 5, 6, and 7.
for (const element of list) {
console.log(element.payload);
}
`

---

ListElement

Constructor
`JavaScript
new ListElement( [ payload = null ], [ next = null ], [ prev = null ] );
`
The class used internally by LinkedList to represent an element of the Linked List.

Parameters


- payload (Optional) Any

Arbitrary data which is assigned to ListElement.payload.

- next (Optional) ListElement

A ListElement to refer to as being next the next element.

- prev (Optional) ListElement

A ListElement to refer to as being the previous element.

Examples

Example 1: Basic Usage

`JavaScript
// A Number
var num = 123;

// Creates a new empty LinkedList.
var list = new LinkedList();

// Creates a new ListElement with num assigned to element.payload
var element = new list.ListElement(num);

// Appends element to the end of the list.
list.push(element);

// Removes element from the list.
list.remove(element);
`

Prototype Methods

$3

Function
`JavaScript
ListElement.fromElement( element );
`
Copies the payload of a ListElement into the callee ListElement.

#### Parameters
- element ListElement

A ListElement to copy the payload from.

#### Examples
Example 1: Basic Usage:

`JavaScript
// A source ListElement
var element1 = new LinkedList.ListElement(123);

// A destination ListElement
var element2 = new LinkedList.ListElement();

// Copies the payload of element1 into element2.
element2.fromElement(element1);
``