DoublyLinkedList
Defined in: packages/data/src/list/doubly-linked-list.ts:112
A doubly linked list implementation.
Time complexity: - Access (by index): O(n) - Update (by index): O(n) - Insert: O(1) at head and tail, O(n) otherwise - Remove: O(1) at head and tail, O(n) otherwise - Search: O(n) Space complexity: O(n)
IIndexed is deliberately not declared — indexing is O(n) on this backing.
See CircularArrayList for O(1) throughout.
Unbounded. For a capacity, wrap it in BoundedDoublyLinkedList or
BlockingDoublyLinkedList.
Type Parameters
Section titled “Type Parameters”T extends DefinedValue
The type of elements in the list.
Implements
Section titled “Implements”IList<T>IPushBackStorage<T>IPopBackStorage<T>IPushFrontStorage<T>IPopFrontStorage<T>IBidirectionalCursorSequence<T,DoublyLinkedListCursor<T>>
Constructors
Section titled “Constructors”Constructor
Section titled “Constructor”new DoublyLinkedList<
T>(iterable?):DoublyLinkedList<T>
Defined in: packages/data/src/list/doubly-linked-list.ts:125
Parameters
Section titled “Parameters”iterable?
Section titled “iterable?”Iterable<T, any, any>
Returns
Section titled “Returns”DoublyLinkedList<T>
Methods
Section titled “Methods”[asyncIterator]()
Section titled “[asyncIterator]()”[asyncIterator]():
AsyncIterator<T>
Defined in: packages/data/src/list/doubly-linked-list.ts:150
Returns
Section titled “Returns”AsyncIterator<T>
[iterator]()
Section titled “[iterator]()”[iterator]():
Iterator<T>
Defined in: packages/data/src/list/doubly-linked-list.ts:143
Returns
Section titled “Returns”Iterator<T>
Implementation of
Section titled “Implementation of”back()
Section titled “back()”back():
T|undefined
Defined in: packages/data/src/list/doubly-linked-list.ts:246
Returns
Section titled “Returns”T | undefined
Implementation of
Section titled “Implementation of”begin()
Section titled “begin()”begin():
DoublyLinkedListCursor<T>
Defined in: packages/data/src/list/doubly-linked-list.ts:506
The first element; invalid when empty.
Returns
Section titled “Returns”Implementation of
Section titled “Implementation of”IBidirectionalCursorSequence.begin
clear()
Section titled “clear()”clear():
void
Defined in: packages/data/src/list/doubly-linked-list.ts:133
Removes all elements from the collection.
Returns
Section titled “Returns”void
Implementation of
Section titled “Implementation of”count()
Section titled “count()”count():
number
Defined in: packages/data/src/list/doubly-linked-list.ts:139
The number of elements in the collection.
A method, not a getter: its async counterpart needs a round trip to the backing store, and a member must have the same shape in both.
Returns
Section titled “Returns”number
Implementation of
Section titled “Implementation of”cursorAt()
Section titled “cursorAt()”cursorAt(
index):DoublyLinkedListCursor<T>
Defined in: packages/data/src/list/doubly-linked-list.ts:514
O(1) for random-access backings, O(n) otherwise.
Parameters
Section titled “Parameters”number
Returns
Section titled “Returns”Implementation of
Section titled “Implementation of”IBidirectionalCursorSequence.cursorAt
end():
DoublyLinkedListCursor<T>
Defined in: packages/data/src/list/doubly-linked-list.ts:510
The past-the-end position, used to append.
Returns
Section titled “Returns”Implementation of
Section titled “Implementation of”IBidirectionalCursorSequence.end
front()
Section titled “front()”front():
T|undefined
Defined in: packages/data/src/list/doubly-linked-list.ts:281
Returns
Section titled “Returns”T | undefined
Implementation of
Section titled “Implementation of”get(
index):T|undefined
Defined in: packages/data/src/list/doubly-linked-list.ts:211
Returns the item at the specified index.
If the index is negative, it counts from the end of the list. If the index
is out of bounds, undefined is returned.
Not uniformly O(1). This member reads as positional access, but only a
random-access backing answers it in constant time. On a linked backing, it
walks from an end, so a loop calling get over every index is quadratic.
Iterate the list, or take a cursor
(ICursorSequence/IBidirectionalCursorSequence), whenever
the access pattern is sequential. Each implementation states its own
complexity.
Parameters
Section titled “Parameters”number
The index of the item to retrieve.
Returns
Section titled “Returns”T | undefined
The item at the specified index, or undefined if the index is
out of bounds.
Implementation of
Section titled “Implementation of”insertAfter()
Section titled “insertAfter()”insertAfter(
cursor,item):void
Defined in: packages/data/src/list/doubly-linked-list.ts:519
Inserts an item after cursor. O(1).
Parameters
Section titled “Parameters”cursor
Section titled “cursor”The position after which to insert.
T
The item to insert.
Returns
Section titled “Returns”void
Implementation of
Section titled “Implementation of”IBidirectionalCursorSequence.insertAfter
insertAllAfter()
Section titled “insertAllAfter()”insertAllAfter(
cursor,items):void
Defined in: packages/data/src/list/doubly-linked-list.ts:525
Inserts every item after cursor, keeping their relative order. O(n) in
the number of items.
Parameters
Section titled “Parameters”cursor
Section titled “cursor”The position after which to insert.
readonly T[]
The items to insert.
Returns
Section titled “Returns”void
Implementation of
Section titled “Implementation of”IBidirectionalCursorSequence.insertAllAfter
insertAllBefore()
Section titled “insertAllBefore()”insertAllBefore(
cursor,items):void
Defined in: packages/data/src/list/doubly-linked-list.ts:541
Inserts every item before cursor, keeping their relative order. O(n) in
the number of items.
Parameters
Section titled “Parameters”cursor
Section titled “cursor”The position before which to insert.
readonly T[]
The items to insert.
Returns
Section titled “Returns”void
Implementation of
Section titled “Implementation of”IBidirectionalCursorSequence.insertAllBefore
insertBefore()
Section titled “insertBefore()”insertBefore(
cursor,item):void
Defined in: packages/data/src/list/doubly-linked-list.ts:535
Inserts an item before cursor. O(1).
Parameters
Section titled “Parameters”cursor
Section titled “cursor”The position before which to insert.
T
The item to insert.
Returns
Section titled “Returns”void
Implementation of
Section titled “Implementation of”IBidirectionalCursorSequence.insertBefore
popBack()
Section titled “popBack()”popBack():
T|undefined
Defined in: packages/data/src/list/doubly-linked-list.ts:227
Returns
Section titled “Returns”T | undefined
Implementation of
Section titled “Implementation of”popFront()
Section titled “popFront()”popFront():
T|undefined
Defined in: packages/data/src/list/doubly-linked-list.ts:262
Returns
Section titled “Returns”T | undefined
Implementation of
Section titled “Implementation of”pushBack()
Section titled “pushBack()”pushBack(
item):void
Defined in: packages/data/src/list/doubly-linked-list.ts:217
Parameters
Section titled “Parameters”T
Returns
Section titled “Returns”void
Implementation of
Section titled “Implementation of”pushBackAll()
Section titled “pushBackAll()”pushBackAll(
items):void
Defined in: packages/data/src/list/doubly-linked-list.ts:221
Parameters
Section titled “Parameters”readonly T[]
Returns
Section titled “Returns”void
Implementation of
Section titled “Implementation of”pushFront()
Section titled “pushFront()”pushFront(
item):void
Defined in: packages/data/src/list/doubly-linked-list.ts:250
Parameters
Section titled “Parameters”T
Returns
Section titled “Returns”void
Implementation of
Section titled “Implementation of”pushFrontAll()
Section titled “pushFrontAll()”pushFrontAll(
items):void
Defined in: packages/data/src/list/doubly-linked-list.ts:254
Parameters
Section titled “Parameters”readonly T[]
Returns
Section titled “Returns”void
Implementation of
Section titled “Implementation of”IPushFrontStorage.pushFrontAll
remove()
Section titled “remove()”remove(
condition):IterableIterator<T>
Defined in: packages/data/src/list/doubly-linked-list.ts:170
Removes every item matching the given predicate.
Parameters
Section titled “Parameters”condition
Section titled “condition”Predicate<[T]>
A predicate function to identify the items to remove.
Returns
Section titled “Returns”IterableIterator<T>
An iterator of the removed items.
Implementation of
Section titled “Implementation of”removeAfter()
Section titled “removeAfter()”removeAfter(
cursor):T|undefined
Defined in: packages/data/src/list/doubly-linked-list.ts:554
Removes the element after cursor. O(1). Cursors at the removed element
become invalid.
Parameters
Section titled “Parameters”cursor
Section titled “cursor”The position before the element to remove.
Returns
Section titled “Returns”T | undefined
The removed element, or undefined if there was none.
Implementation of
Section titled “Implementation of”IBidirectionalCursorSequence.removeAfter
removeAt()
Section titled “removeAt()”removeAt(
cursor):T|undefined
Defined in: packages/data/src/list/doubly-linked-list.ts:568
Removes the element at cursor. O(1). Cursors at the removed element
become invalid.
Parameters
Section titled “Parameters”cursor
Section titled “cursor”The position to remove.
Returns
Section titled “Returns”T | undefined
The removed element, or undefined if cursor was not valid.
Implementation of
Section titled “Implementation of”IBidirectionalCursorSequence.removeAt
removeFirst()
Section titled “removeFirst()”removeFirst(
condition):boolean
Defined in: packages/data/src/list/doubly-linked-list.ts:158
Removes the first occurrence of the item matching the given predicate.
Parameters
Section titled “Parameters”condition
Section titled “condition”Predicate<[T]>
A predicate function to identify the item to remove.
Returns
Section titled “Returns”boolean
true if the item was found and removed, false otherwise.
Implementation of
Section titled “Implementation of”replace()
Section titled “replace()”replace(
condition,newItemFactory):IterableIterator<T>
Defined in: packages/data/src/list/doubly-linked-list.ts:195
Replaces every item matching the given predicate.
Parameters
Section titled “Parameters”condition
Section titled “condition”Predicate<[T]>
A predicate function to identify the items to replace.
newItemFactory
Section titled “newItemFactory”Callable<[T], T>
A function that takes the old item and returns the new item to insert.
Returns
Section titled “Returns”IterableIterator<T>
An iterator of the replaced items.
Implementation of
Section titled “Implementation of”replaceFirst()
Section titled “replaceFirst()”replaceFirst(
condition,newItem):boolean
Defined in: packages/data/src/list/doubly-linked-list.ts:183
Replaces the first occurrence of the item matching the given predicate.
Parameters
Section titled “Parameters”condition
Section titled “condition”Predicate<[T]>
A predicate function to identify the item to replace.
newItem
Section titled “newItem”T
The new item to insert.
Returns
Section titled “Returns”boolean
true if the item was found and replaced, false otherwise.
Implementation of
Section titled “Implementation of”set(
index,item):void
Defined in: packages/data/src/list/doubly-linked-list.ts:285
Sets the item at the specified index.
If the index is negative, it counts from the end of the list. If the index is equal to the length of the list, the item is appended to the end. If the index is out of bounds, a RangeError is thrown.
Parameters
Section titled “Parameters”number
The index at which to set the item.
T
The item to set.
Returns
Section titled “Returns”void
Throws
Section titled “Throws”If the index is out of bounds.
Implementation of
Section titled “Implementation of”setAt()
Section titled “setAt()”setAt(
cursor,item):void
Defined in: packages/data/src/list/doubly-linked-list.ts:579
Replaces the element at cursor.
Parameters
Section titled “Parameters”cursor
Section titled “cursor”The position to replace.
T
The new item.
Returns
Section titled “Returns”void
Implementation of
Section titled “Implementation of”IBidirectionalCursorSequence.setAt
slice()
Section titled “slice()”slice(
start?,end?):IterableIterator<T>
Defined in: packages/data/src/list/doubly-linked-list.ts:328
Slice the list to a new list from start to end.
This method does not mutate the original list.
The range is specified by the start and end parameters, which are
inclusive and exclusive, respectively. If start is omitted, it defaults
to 0. If end is omitted, it defaults to the length of the list.
If either start or end is negative, they refer to positions from the
end of the list. For example, -1 refers to the last element, -2 refers
to the second last element, and so on.
If start is greater than or equal to end, the result is an empty
iterator.
If the start index is out of bounds, a RangeError is thrown. If end is
out of bounds, it is clamped to the valid range.
Parameters
Section titled “Parameters”start?
Section titled “start?”number = 0
Optional start index of the range (inclusive).
number
Optional end index of the range (exclusive).
Returns
Section titled “Returns”IterableIterator<T>
An iterator for the elements in the specified range.
Throws
Section titled “Throws”If the start index is out of bounds.
Implementation of
Section titled “Implementation of”splice()
Section titled “splice()”splice(
start,deleteCount?,item?):IterableIterator<T>
Defined in: packages/data/src/list/doubly-linked-list.ts:300
Change the content of the list by removing or replacing existing elements and/or adding new elements in place.
If the start index is negative, it counts from the end of the list. If the start index is equal to the length of the list, no elements are removed and the items are appended to the end of the list. If the start index is out of bounds, a RangeError is thrown.
If deleteCount is omitted, it defaults to Infinity, meaning all elements
from the start index to the end of the list will be removed. If deleteCount
is greater than the number of elements from start to the end of the list,
it will remove all elements from start to the end of the list. If
deleteCount is 0 or negative, no elements will be removed.
If items are provided, they will be inserted starting at the start index.
Parameters
Section titled “Parameters”number
The index at which to start changing the list.
deleteCount?
Section titled “deleteCount?”number = Infinity
The number of elements to remove from the list. Defaults
to Infinity
T
An optional element to add to the list at the start index.
Returns
Section titled “Returns”IterableIterator<T>
An iterable of the removed items.
Throws
Section titled “Throws”If the start index is out of bounds.
Implementation of
Section titled “Implementation of”spliceAll()
Section titled “spliceAll()”spliceAll(
start,deleteCount?,items?):IterableIterator<T>
Defined in: packages/data/src/list/doubly-linked-list.ts:312
Same as IList.splice, but inserts every element of items at the
start index, keeping their relative order.
Parameters
Section titled “Parameters”number
The index at which to start changing the list.
deleteCount?
Section titled “deleteCount?”number = Infinity
The number of elements to remove from the list. Defaults
to Infinity
items?
Section titled “items?”readonly T[] = []
The elements to add to the list, beginning at the start index.
Returns
Section titled “Returns”IterableIterator<T>
An iterable of the removed items.
Throws
Section titled “Throws”If the start index is out of bounds.