Options
All
  • Public
  • Public/Protected
  • All
Menu

Class LinkedList<T>

LinkedList is an implementation of a singly-linked Linked List using generics.

It's designed as a mostly drop-in replacement for arrays where you want to perform the following operations on large lists:

  • insert at the beginning (unshift)
  • append to the end (push)
  • remove from the beginning (shift)

These operations are O(1) for a linked list, but O(n) for array shift and unshift.

Array push is extremely fast, and a linked list cannot generally compare because of the additional logic overhead. However, there is an element size and an array/list size threshold where linked list push is comparable to array push.

Use cases
  1. To replace very large arrays (10's or 100's of thousands of elements).
  2. Implementing a FIFO queue (i.e. where you add elements at one end remove them from the other end). This is slow for large arrays.
  3. Insert operations in the middle of the list (which is slow in large arrays).

Feature comparison with Array

LinkedList implements most of the same methods as Array. The unit tests specifically compare the operation of Array methods with LinkedList methods, to ensure compatibility.

However, a singly-linked list cannot easily or efficiently perform certain operations that you can with an Array, such as:

  • sort, reverse, reduceRight - cannot be efficiently implemented and are excluded
  • copyWithin - not yet implemented

Workaround

For missing methods or features, you can convert your LinkedList to an Array and perform the operation on that Array. For example:

const list = new LinkedList<number>();
list.push(1, 2, 3, 4, 5, 5, 5);
const arr = [...list];
console.log(arr.indexOf(5, -2));   // output is 5

Missing methods

Depending on the version of the generic-linked-list package, some methods that can be implemented may not yet be implemented. In this case, convert your list to an array and use array methods instead. See the above Workaround section for an example of how to achieve this.

For those methods that cannot be implemented without a large performance issue, you should consider a different data structure (such as Array or Map).

Unit tests

This package includes unit tests that demonstrate operational and speed test results clearly. The push test, however, requires you to start node with --expose-gc, therefore, it is disabled.

The tests show 3 orders of magnitude speed increase over Array for shift and unshift, which is significant for large arrays.

Examples

 
const myNumberList = new LinkedList<number>();    // an empty list of numbers
myNumberList.push(1, 2, 3);                       // append to the list
const firstValue = myNumberList.shift();          // remove the first element
console.log(firstValue);                          // outputs: 1
console.log(...myNumberList);                     // outputs: 2 3

// Build a list people.
type Person = {name: string, age: number};
const peopleList = new LinkedList<Person>();
peopleList.push({name: 'John', age: 12}, {name: 'Kylie', age: 14});
console.log(...peopleList);

// convert to an array
const peopleArray = [...peopleList];
console.log(peopleArray);

Type parameters

  • T

    the type of each value in the list

Hierarchy

  • LinkedList

Implements

  • Iterable<T>

Index

Constructors

Accessors

Methods

Constructors

constructor

  • Construct the linked list, and load its contents as follows:

    • if given an integer length, make a list of that length initialised with undefined values
    • a list of arguments of type T
    • any iterable of T
    • another LinkedList; this performs a shallow copy of the other list's values

    If no parameters are provided, an empty list is constructed.

    In the case of specifying a length, you should declare the list like this: LinkedList<TYPE | undefined> where TYPE is the non-undefined type for your linked list elements. Unlike Array, we don't currently support the concept of "empty slots" in linked lists.

    Type parameters

    • T

    Parameters

    • Rest ...args: unknown[]

    Returns LinkedList<T>

  • Construct the linked list, and load its contents as follows:

    • if given an integer length, make a list of that length initialised with undefined values
    • a list of arguments of type T
    • any iterable of T
    • another LinkedList; this performs a shallow copy of the other list's values

    If no parameters are provided, an empty list is constructed.

    In the case of specifying a length, you should declare the list like this: LinkedList<TYPE | undefined> where TYPE is the non-undefined type for your linked list elements. Unlike Array, we don't currently support the concept of "empty slots" in linked lists.

    Type parameters

    • T

    Parameters

    • length: number

    Returns LinkedList<T>

  • Construct the linked list, and load its contents as follows:

    • if given an integer length, make a list of that length initialised with undefined values
    • a list of arguments of type T
    • any iterable of T
    • another LinkedList; this performs a shallow copy of the other list's values

    If no parameters are provided, an empty list is constructed.

    In the case of specifying a length, you should declare the list like this: LinkedList<TYPE | undefined> where TYPE is the non-undefined type for your linked list elements. Unlike Array, we don't currently support the concept of "empty slots" in linked lists.

    Type parameters

    • T

    Parameters

    • Rest ...items: T[]

    Returns LinkedList<T>

  • Construct the linked list, and load its contents as follows:

    • if given an integer length, make a list of that length initialised with undefined values
    • a list of arguments of type T
    • any iterable of T
    • another LinkedList; this performs a shallow copy of the other list's values

    If no parameters are provided, an empty list is constructed.

    In the case of specifying a length, you should declare the list like this: LinkedList<TYPE | undefined> where TYPE is the non-undefined type for your linked list elements. Unlike Array, we don't currently support the concept of "empty slots" in linked lists.

    Type parameters

    • T

    Parameters

    • Optional it: Iterable<T>

    Returns LinkedList<T>

  • Construct the linked list, and load its contents as follows:

    • if given an integer length, make a list of that length initialised with undefined values
    • a list of arguments of type T
    • any iterable of T
    • another LinkedList; this performs a shallow copy of the other list's values

    If no parameters are provided, an empty list is constructed.

    In the case of specifying a length, you should declare the list like this: LinkedList<TYPE | undefined> where TYPE is the non-undefined type for your linked list elements. Unlike Array, we don't currently support the concept of "empty slots" in linked lists.

    Type parameters

    • T

    Parameters

    Returns LinkedList<T>

Accessors

length

  • get length(): number

  • Get the length of the list. The length is maintained internally, so there is no cost to this request.

    Returns number

    the length of the list

    Complexity: O(0)

Methods

[iterator]

at

  • at(index: number): undefined | T

  • Return the value at the given index in the list.

    From version 2.0.0, negative indexes are supported.

    In general, this method is much slower than an array, but is still useful if you need to work with positions within the list.

    However, if this is a major part of your use case and your list is large, then you should probably consider a different data structure.

    Getting the first element in the queue is instant.

    Parameters

    • index: number

    Returns undefined | T

    the element at the given index or undefined if the index is beyond the end of the list. at(0) will return undefined if the list is empty

    Complexity: O(n) where n is the index you've requested.

concat

end

  • end(): undefined | T

entries

  • entries(): IterableIterator<[number, T]>

  • Return a new LinkedList interator object that contains the index/value pairs for each in the list.

    Returns IterableIterator<[number, T]>

    a new LinkedList iterator object

every

fill

  • fill(value: T, start?: number, end?: number): LinkedList<T>

filter

find

  • Find the first element in the list where the predicate function returns true.

    As recommended for Array.find, do not mutate the list in your predicate function. Unlike Array, LinkedList does not make any guarantees as to behaviour if you do this.

    Parameters

    • predicate: LinkedListPredicate<T>

      a function to test each element in the list

    • Optional thisArg: any

      a "this" value to bind to the predicate function

    Returns undefined | T

    the found element or undefined if not found

    Complexity: O(n) where n is the length of the linked list

findIndex

flat

flatMap

  • Create a new LinkedList populated with the results of calling the provided function on every element in the LinkedList and then flattening the list by a depth of 1.

    It is identical to a map followed by a flat of depth 1 (list.map(...args).flat()), but slightly more efficient than calling those two methods separately.

    However, in this case, the callback function can return a single value or a linked list. In that latter case, flatMap extracts the values from that linked list and inserts them in the final list that will be returned from flatMap. This is where flatMap is faster than calling map followed by flat - because it only traverses in the input list once and still achieves the flattening.

    Type parameters

    • U = T

      the basic return type of the callbackFn (noting that callBackFn can return U or a RecursiveLinkedList<U>

    Parameters

    • callbackFn: MapCallback<T, U | RecursiveLinkedList<U>>

      the function to call to map each element

    • Optional thisArg: any

      a "this" value to bind to the callback function

    Returns RecursiveLinkedList<U>

    a new linked list with each element being the result of the callback function and then the list flattened by a depth of 1.

    Complexity: O(n) where n is the length of the linked list

forEach

grow

  • Grow the linked list to the given length and set the new elements to the given value.

    Use case for grow:

    • you want to create a list of a given size all filled with the same value; for an Array you would construct using Array(length) then call Array.fill. For LinkedList, use LinkedList.grow instead.

    From version 2 of LinkedList, you can also use the same approach as Array, however, in that case you'll need to declare the list as LinkedList<T | undefined> because new LinkedList(length) fills the list with undefined - which may not be what you want. grow allows you to have a declaration of just LinkedList<T>.

    Parameters

    • newLength: number

      the new length; if this is <= the current length, no operation is performed

    • value: T

      the value to use for the new elements

    Returns LinkedList<T>

includes

  • includes(testValue: T, fromIndex?: number): boolean

  • Test if the list contains the given value, using the algorithm for comparison.

    see

    LinkedList.sameValueZero

    Parameters

    • testValue: T

      the value to look for in the list

    • fromIndex: number = 0

      the index from which to start the search; from version 2.0.0, -ve numbers are supported

    Returns boolean

    true if the list includes the given value

    Complexity: O(n) where n is the length of the linked list

indexOf

  • indexOf(testValue: T, fromIndex?: number): number

  • Find the first element in the list where the given value === the list value, and return the index.

    Parameters

    • testValue: T

      the value to find in the list

    • fromIndex: number = 0

      the index from which to start the search; from version 2.0.0, -ve numbers are supported, just like Array

    Returns number

    the index of the first list element that is === to testValue, or -1 if no such list element is found

    Complexity: O(n) where n is the length of the linked list

join

  • join(sep?: string): string

keys

  • keys(): IterableIterator<number>

keysAsList

lastIndexOf

  • lastIndexOf(testValue: T, fromIndex?: number): number

  • Find the last element in the list where the given value === the list value, and return the index.

    Parameters

    • testValue: T

      the value to find in the list

    • Optional fromIndex: number

      the index from which to start the search

    Returns number

    the index of the last list element that is === to testValue, or -1 if no such list element is found

    Complexity: O(n) where n is the length of the linked list

map

  • Create a new LinkedList populated with the results of calling the provided function on every element in the LinkedList.

    Type parameters

    • U

      the return type of the callbackFn

    Parameters

    • callbackFn: MapCallback<T, U>

      the function to call to map each element

    • Optional thisArg: any

      a "this" value to bind to the callback function

    Returns LinkedList<U>

    a new linked list with each element being the result of the callback function

    Complexity: O(n) where n is the length of the linked list

pop

  • pop(): undefined | T

push

  • push(it: Iterable<T>): number
  • push(...valueList: T[]): number

reduce

  • The reduce method executes a user-supplied callback function (reducerCallbackFn) on each element of the list, in left-to-right (first-to-last) order, passing in the return value from the calculation on the preceding element. The final result of running the reducerCallbackFn across all elements of the list is a single value.

    The first time that the callback is run there is no "return value of the previous calculation". Therefore, either the optional initialValue parameter is used or, if that is not supplied, the list element at index 0 is used as the initial value and iteration starts from the next element (index 1 instead of index 0).

    Regarding the optional initialValue parameter: if initialValue is supplied, that also causes currentValue to be initialized to the first value in the list. If initialValue is not supplied, accumulator is initialized to the first value in the list, and currentValue is initialized to the second value in the list.

    Regarding the reducerCallbackFn callback function...

    Its return value becomes the value of the accumulator parameter on the next invocation of reducerCallbackFn. For the last invocation, the return value becomes the return value of reduce.

    reducerCallbackFn is called with the following arguments:

    • accumulator The value resulting from the previous call to reducerCallbackFn. On first call, initialValue if supplied, otherwise the value of list.at(0).

    • currentValue The value of the current element. On first call, the value of list.at(0) if initialValue was supplied, otherwise the value of list.at(1).

    • currentIndex The index position of currentValue in list. On first call, 0 if initialValue was supplied, otherwise 1.

    • list The list reduce was called upon.

    Parameters

    • reducerCallbackFn: ReduceCallback<T>

      the reducerCallbackFn callback function

    • Optional initialValue: T

      an optional value to which accumulator is initialized the first time the callback is called.

    Returns T

shift

  • shift(): undefined | T

  • Remove the first element from the list.

    shift is very fast on LinkedList and very slow on Array.

    Returns undefined | T

    the element removed from the front of the list, or undefined if the list is empty

    Complexity: O(1)

slice

  • slice(start?: number, end?: number): LinkedList<T>

  • Return a shallow copy of a part of the linked list, based on indexes of the elements in the list.

    Parameters

    • Optional start: number

      optional zero-based starting index, at which to start copying the list

    • Optional end: number

      optional; the index of the first element to exclude from the returned list

      start and end can be negative from version 2.0.0

    Returns LinkedList<T>

    a new list containing the specified elements from the original list

    Complexity: O(n) where n is the length of the linked list

some

splice

  • splice(start: number, deleteCount?: undefined | number, ...items: T[]): LinkedList<T>

  • Change the linked list by removing or replacing existing elements and/or adding new elements.

    Parameters

    • start: number

      zero-based starting index, at which to start changing the list; a negative value counts back from the end of the list

    • deleteCount: undefined | number = ...

      the number of elements to remove beginning at the start index

    • Rest ...items: T[]

      items to be inserted after the start index; if you don't provide any items then splice only removes elements from the list

    Returns LinkedList<T>

toString

  • toString(): string

truncate

  • truncate(newLength: number, value?: T): LinkedList<T>

unshift

  • unshift(...valueList: T[]): number

values

Static from

  • from(str: string): LinkedList<string>
  • from<U>(str: string, mapFn: (v: string, k: number) => U, thisArg?: any): LinkedList<U>
  • from<T>(arr: ArrayLike<T>): LinkedList<T>
  • from<T, U>(arr: ArrayLike<T>, mapFn: (v: T, k: number) => U, thisArg?: any): LinkedList<U>
  • from<T>(it: Iterable<T>): LinkedList<T>
  • from<T, U>(it: Iterable<T>, mapFn: (v: T, k: number) => U, thisArg?: any): LinkedList<U>

  • Create a new LinkedList from a string. The string is split into single characters and each character becomes an element in the list.

    This behaviour mirrors Array.from(string).

    Parameters

    • str: string

    Returns LinkedList<string>

  • Create a new LinkedList from a string but map each character to a different value.

    The string is split into single characters and each character is mapped to another value and the result becomes an element in the list.

    This behaviour mirrors Array.from(string).

    Type parameters

    • U = string

    Parameters

    • str: string
    • mapFn: (v: string, k: number) => U

      if provided, every character to be added to the list is first passed through this function and the mapFn's return value is added to the list instead

        • (v: string, k: number): U

        • Parameters

          • v: string
          • k: number

          Returns U

    • Optional thisArg: any

      value to use as this when executing mapFn

    Returns LinkedList<U>

  • Create a new LinkedList from an array of values.

    Type parameters

    • T

    Parameters

    • arr: ArrayLike<T>

    Returns LinkedList<T>

  • Create a new LinkedList from an array of values, mapping each value to a different value.

    Type parameters

    • T

    • U = T

    Parameters

    • arr: ArrayLike<T>
    • mapFn: (v: T, k: number) => U

      if provided, every value to be added to the list is first passed through this function and the mapFn's return value is added to the list instead

        • (v: T, k: number): U

        • Parameters

          • v: T
          • k: number

          Returns U

    • Optional thisArg: any

      value to use as this when executing mapFn

    Returns LinkedList<U>

  • Create a new LinkedList from an iterator over some values.

    Type parameters

    • T

    Parameters

    • it: Iterable<T>

    Returns LinkedList<T>

  • Create a new LinkedList from an iterator over some values, mapping each value to a different value.

    Type parameters

    • T

    • U = T

    Parameters

    • it: Iterable<T>
    • mapFn: (v: T, k: number) => U

      if provided, every value to be added to the list is first passed through this function and the mapFn's return value is added to the list instead

        • (v: T, k: number): U

        • Parameters

          • v: T
          • k: number

          Returns U

    • Optional thisArg: any

      value to use as this when executing mapFn

    Returns LinkedList<U>

Static isIterable

  • isIterable(arg: unknown): boolean

  • Test if the given argument is an Iterable.

    Parameters

    • arg: unknown

    Returns boolean

Static isLinkedList

  • isLinkedList<T>(maybeList: unknown): maybeList is LinkedList<T>

  • Test if the given value is a LinkedList.

    Note that the T generic type parameter cannot be verified using plain Typescript and you must use other Typescript techniques to confirm matching types for the elements.

    Type parameters

    • T

    Parameters

    • maybeList: unknown

      the value to test

    Returns maybeList is LinkedList<T>

    true if the value is a LinkedList

Static isObject

  • isObject(arg: unknown): boolean

  • Test if the given argument is a true object.

    Parameters

    • arg: unknown

    Returns boolean

Static of

Static sameValueZero

  • sameValueZero(lhs: unknown, rhs: unknown): boolean

Generated using TypeDoc