Skip to content
Buy me a coffee

LinkedList

Defined in: src/list/LinkedList.ts:42

Doubly linked list that implements both List and Deque, so one object serves as a list, a FIFO queue and a stack.

Adding, removing and reading at either end is O(1), and so are add, set and remove through a ListIterator. Positional access (get, set, add(i, e), removeAt) walks from the nearer end, O(min(i, n − i)). contains, indexOf and remove(o) are O(n).

Permits null and undefined elements. Because poll() and peek() return null when the list is empty, check isEmpty() when null may be stored. Iterates head to tail; iterators, forEach and views are fail-fast.

E

new LinkedList<E>(): LinkedList<E>

Defined in: src/list/LinkedList.ts:48

Creates an empty list.

LinkedList<E>

AbstractSequentialList.constructor

new LinkedList<E>(c): LinkedList<E>

Defined in: src/list/LinkedList.ts:53

Creates a list holding the elements of c, in its iteration order. O(n).

Collection<E>

LinkedList<E>

NullPointerException if c is null or undefined

AbstractSequentialList<E>.constructor

modCount: number = 0

Defined in: src/abstract/AbstractList.ts:41

Structural modification counter. Iterators, sublists and spliterators record it and throw ConcurrentModificationException when it changes behind them. Subclasses increment it once per structural change (add, remove, clear); set leaves it alone.

AbstractSequentialList.modCount

[INSPECT](): string

Defined in: src/abstract/AbstractCollection.ts:195

Node’s util.inspect hook: console.log prints the toString() form.

string

AbstractSequentialList.[INSPECT]


[iterator](): IterableIterator<E>

Defined in: src/list/LinkedList.ts:430

Returns a JS iterator over the elements, head to tail, for for...of and spread; fail-fast.

IterableIterator<E>

Deque.[iterator]

AbstractSequentialList.[iterator]


add(e): boolean

Defined in: src/list/LinkedList.ts:204

Appends e at the tail, in O(1). null and undefined are allowed.

E

boolean

always true

Deque.add

AbstractSequentialList.add

add(index, e): void

Defined in: src/list/LinkedList.ts:210

Inserts e at index, shifting the element there and all later ones one position to the right. Walks from the nearer end: O(min(index, n − index)), then O(1) to link.

number

E

void

IndexOutOfBoundsException if index < 0 or index > size()

List.add

AbstractSequentialList.add


addAll(c): boolean

Defined in: src/abstract/AbstractList.ts:100

Appends the elements of c in its iteration order (via addAllAt); returns true if c was not empty.

Collection<E>

boolean

NullPointerException if c is null

Deque.addAll

AbstractSequentialList.addAll

addAll(index, c): boolean

Defined in: src/abstract/AbstractList.ts:106

Inserts the elements of c at index in its iteration order (via addAllAt); returns true if c was not empty.

number

Collection<E>

boolean

IndexOutOfBoundsException if index < 0 || index > size()

NullPointerException if c is null

List.addAll

AbstractSequentialList.addAll


addFirst(e): void

Defined in: src/list/LinkedList.ts:437

Inserts e at the head, in O(1). null and undefined are allowed.

E

void

Deque.addFirst

AbstractSequentialList.addFirst


addLast(e): void

Defined in: src/list/LinkedList.ts:442

Appends e at the tail, in O(1). null and undefined are allowed.

E

void

Deque.addLast

AbstractSequentialList.addLast


clear(): void

Defined in: src/list/LinkedList.ts:340

Removes all elements. O(n): unlinks every node, so a stray reference to one cannot keep the others alive.

void

Deque.clear

AbstractSequentialList.clear


clone(): LinkedList<E>

Defined in: src/list/LinkedList.ts:68

Returns a shallow, independent copy of the same runtime class, in O(n).

LinkedList<E>


contains(o): boolean

Defined in: src/list/LinkedList.ts:291

Returns true if this list contains an element equal to o (by Objects.equals). O(n) scan from the head; null is allowed.

unknown

boolean

Deque.contains

AbstractSequentialList.contains


containsAll(c): boolean

Defined in: src/abstract/AbstractCollection.ts:83

Returns true if this collection contains every element of c (calls contains for each).

Collection<unknown>

boolean

NullPointerException if c is null

Deque.containsAll

AbstractSequentialList.containsAll


descendingIterator(): Iterator<E>

Defined in: src/list/LinkedList.ts:610

Returns a fail-fast iterator over the elements from tail to head. Its remove is O(1).

Iterator<E>

Deque.descendingIterator


element(): E

Defined in: src/list/LinkedList.ts:553

Returns the head without removing it, in O(1); same as getFirst().

E

NoSuchElementException if the list is empty

Deque.element


equals(o): boolean

Defined in: src/list/LinkedList.ts:625

Returns true if o is a List of any class with equal elements in the same order. O(n).

unknown

boolean

Deque.equals

AbstractSequentialList.equals


forEach(action): void

Defined in: src/list/LinkedList.ts:358

Calls action for each element, head to tail.

(e) => void

void

NullPointerException if action is null

ConcurrentModificationException if action structurally modifies this list

Deque.forEach

AbstractSequentialList.forEach


get(index): E

Defined in: src/list/LinkedList.ts:261

Returns the element at index. O(min(index, n − index)), walking from the nearer end.

number

E

IndexOutOfBoundsException if index < 0 or index >= size()

List.get

AbstractSequentialList.get


getFirst(): E

Defined in: src/list/LinkedList.ts:450

Returns the first element. O(1).

E

NoSuchElementException if the list is empty

Deque.getFirst

AbstractSequentialList.getFirst


getLast(): E

Defined in: src/list/LinkedList.ts:460

Returns the last element. O(1).

E

NoSuchElementException if the list is empty

Deque.getLast

AbstractSequentialList.getLast


hashCode(): number

Defined in: src/list/LinkedList.ts:639

Returns the list hash code, h = 31 * h + hash(e) from 1 in 32-bit arithmetic, consistent with equals. O(n).

number

Deque.hashCode

AbstractSequentialList.hashCode


indexOf(o): number

Defined in: src/list/LinkedList.ts:299

Returns the index of the first element equal to o (by Objects.equals), or -1 if there is none. O(n) scan from the head; NaN matches NaN.

unknown

number

List.indexOf

AbstractSequentialList.indexOf


isEmpty(): boolean

Defined in: src/list/LinkedList.ts:196

Returns true if this list has no elements. O(1).

boolean

Deque.isEmpty

AbstractSequentialList.isEmpty


iterator(): Iterator<E>

Defined in: src/list/LinkedList.ts:408

Returns a fail-fast iterator over the elements, head to tail. Its remove is O(1).

Iterator<E>

Deque.iterator

AbstractSequentialList.iterator


lastIndexOf(o): number

Defined in: src/list/LinkedList.ts:314

Returns the index of the last element equal to o (by Objects.equals), or -1 if there is none. O(n) scan from the tail; NaN matches NaN.

unknown

number

List.lastIndexOf

AbstractSequentialList.lastIndexOf


listIterator(index?): ListIterator<E>

Defined in: src/list/LinkedList.ts:418

Returns a fail-fast list iterator starting at index: the first next() returns the element at index. Reaching it takes O(min(index, n − index)); then add, set and remove through it are O(1).

number = 0

start position, 0 by default

ListIterator<E>

IndexOutOfBoundsException if index < 0 or index > size()

List.listIterator

AbstractSequentialList.listIterator


offer(e): boolean

Defined in: src/list/LinkedList.ts:490

Inserts e at the tail, in O(1). null and undefined are allowed.

E

boolean

always true

Deque.offer


offerFirst(e): boolean

Defined in: src/list/LinkedList.ts:499

Inserts e at the head, in O(1). null and undefined are allowed.

E

boolean

always true

Deque.offerFirst


offerLast(e): boolean

Defined in: src/list/LinkedList.ts:508

Inserts e at the tail, in O(1). null and undefined are allowed.

E

boolean

always true

Deque.offerLast


parallelStream(): Stream<E>

Defined in: src/abstract/AbstractCollection.ts:180

Returns a stream over spliterator() flagged as parallel.

Stream<E>

Deque.parallelStream

AbstractSequentialList.parallelStream


peek(): E | null

Defined in: src/list/LinkedList.ts:532

Returns the head without removing it, in O(1), or null if this list is empty (ambiguous when null is stored: check isEmpty()).

E | null

Deque.peek


peekFirst(): E | null

Defined in: src/list/LinkedList.ts:538

Returns the first element without removing it, in O(1), or null if this list is empty (ambiguous when null is stored: check isEmpty()).

E | null

Deque.peekFirst


peekLast(): E | null

Defined in: src/list/LinkedList.ts:544

Returns the last element without removing it, in O(1), or null if this list is empty (ambiguous when null is stored: check isEmpty()).

E | null

Deque.peekLast


poll(): E | null

Defined in: src/list/LinkedList.ts:514

Removes and returns the head in O(1), or null if this list is empty (ambiguous when null is stored: check isEmpty()).

E | null

Deque.poll


pollFirst(): E | null

Defined in: src/list/LinkedList.ts:520

Removes and returns the first element in O(1), or null if this list is empty (ambiguous when null is stored: check isEmpty()).

E | null

Deque.pollFirst


pollLast(): E | null

Defined in: src/list/LinkedList.ts:526

Removes and returns the last element in O(1), or null if this list is empty (ambiguous when null is stored: check isEmpty()).

E | null

Deque.pollLast


pop(): E

Defined in: src/list/LinkedList.ts:566

Pops the top of the stack this list represents, that is, removes and returns the head; same as removeFirst(). O(1).

E

NoSuchElementException if the list is empty

Deque.pop


push(e): void

Defined in: src/list/LinkedList.ts:558

Pushes e onto the stack this list represents, that is, inserts it at the head; same as addFirst(e). O(1).

E

void

Deque.push


remove(): E

Defined in: src/list/LinkedList.ts:574

Removes and returns the head; same as removeFirst(). O(1).

E

NoSuchElementException if the list is empty

Deque.remove

AbstractSequentialList.remove

remove(o): boolean

Defined in: src/list/LinkedList.ts:580

Removes the first element equal to o (by Objects.equals), if present; same as removeFirstOccurrence(o). O(n).

unknown

boolean

true if an element was removed

Deque.remove

AbstractSequentialList.remove


removeAll(c): boolean

Defined in: src/abstract/AbstractCollection.ts:108

Removes every element that c contains, through the iterator’s remove(); returns true if any was removed.

Collection<unknown>

boolean

NullPointerException if c is null

Deque.removeAll

AbstractSequentialList.removeAll


removeAt(index): E

Defined in: src/list/LinkedList.ts:285

Removes the element at index. O(min(index, n − index)) to reach the node, then O(1) to unlink it.

number

E

the removed element

IndexOutOfBoundsException if index < 0 or index >= size()

List.removeAt

AbstractSequentialList.removeAt


removeFirst(): E

Defined in: src/list/LinkedList.ts:470

Removes and returns the first element. O(1).

E

NoSuchElementException if the list is empty

Deque.removeFirst

AbstractSequentialList.removeFirst


removeFirstOccurrence(o): boolean

Defined in: src/list/LinkedList.ts:590

Removes the first element (from head to tail) equal to o. O(n) scan from the head, then O(1) to unlink.

unknown

boolean

true if an element was removed

Deque.removeFirstOccurrence


removeIf(filter): boolean

Defined in: src/list/LinkedList.ts:374

Removes every element for which filter returns true. O(n), unlinking each match as it goes, so elements removed before a throwing predicate stay removed.

(e) => boolean

boolean

true if any element was removed

NullPointerException if filter is null

ConcurrentModificationException if filter structurally modifies this list

Deque.removeIf

AbstractSequentialList.removeIf


removeLast(): E

Defined in: src/list/LinkedList.ts:480

Removes and returns the last element. O(1).

E

NoSuchElementException if the list is empty

Deque.removeLast

AbstractSequentialList.removeLast


removeLastOccurrence(o): boolean

Defined in: src/list/LinkedList.ts:602

Removes the last element (the first found from tail to head) equal to o. O(n) scan from the tail, then O(1) to unlink.

unknown

boolean

true if an element was removed

Deque.removeLastOccurrence


removeRange(fromIndex, toIndex): void

Defined in: src/abstract/AbstractList.ts:160

Removes [fromIndex, toIndex). Public so views can delegate.

number

number

void

IndexOutOfBoundsException for a bad range, before anything is removed

AbstractSequentialList.removeRange


replaceAll(operator): void

Defined in: src/list/LinkedList.ts:398

Replaces each element with the result of operator applied to it, head to tail. O(n); not a structural change.

(e) => E

void

NullPointerException if operator is null

ConcurrentModificationException if operator structurally modifies this list

List.replaceAll

AbstractSequentialList.replaceAll


retainAll(c): boolean

Defined in: src/abstract/AbstractCollection.ts:118

Removes every element that c does not contain, through the iterator’s remove(); returns true if any was removed.

Collection<unknown>

boolean

NullPointerException if c is null

Deque.retainAll

AbstractSequentialList.retainAll


reversed(): LinkedList<E>

Defined in: src/list/LinkedList.ts:618

Returns a live, reverse-ordered view in O(1). The view is itself a LinkedList whose reads and writes go through to this list, with the ends swapped.

LinkedList<E>

Deque.reversed

AbstractSequentialList.reversed


set(index, e): E

Defined in: src/list/LinkedList.ts:272

Replaces the element at index with e. O(min(index, n − index)), walking from the nearer end; not a structural change.

number

E

E

the element previously at index

IndexOutOfBoundsException if index < 0 or index >= size()

List.set

AbstractSequentialList.set


size(): number

Defined in: src/list/LinkedList.ts:191

Returns the number of elements. O(1).

number

Deque.size

AbstractSequentialList.size


sort(c?): void

Defined in: src/abstract/AbstractList.ts:222

Sorts the list stably by c (natural ordering when null or omitted): sorts a copy, then writes it back with the list iterator’s set, so it is not a structural change.

Comparator<E> | null = null

void

ClassCastException if natural ordering meets values that cannot be compared

List.sort

AbstractSequentialList.sort


spliterator(): Spliterator<E>

Defined in: src/list/LinkedList.ts:424

Returns a spliterator over the elements, used to build streams: ORDERED | SIZED | SUBSIZED, late-binding, fail-fast, splits off growing array batches.

Spliterator<E>

Deque.spliterator

AbstractSequentialList.spliterator


stream(): Stream<E>

Defined in: src/abstract/AbstractCollection.ts:175

Returns a sequential stream over spliterator().

Stream<E>

Deque.stream

AbstractSequentialList.stream


subList(fromIndex, toIndex): List<E>

Defined in: src/abstract/AbstractList.ts:193

Returns a live view of [fromIndex, toIndex): changes through it write to this list, and a structural change made to this list directly makes the view throw ConcurrentModificationException. Carries the RandomAccess brand when this list does.

number

number

List<E>

IndexOutOfBoundsException if fromIndex < 0 or toIndex > size()

IllegalArgumentException if fromIndex > toIndex

List.subList

AbstractSequentialList.subList


toArray(): E[]

Defined in: src/list/LinkedList.ts:326

Returns a new array with all elements, head to tail. Changing the array does not affect this list. O(n).

E[]

Deque.toArray

AbstractSequentialList.toArray

toArray<A>(generator): A

Defined in: src/list/LinkedList.ts:331

Fills an array created by generator(size()) with the elements head to tail, and returns it. O(n).

A extends WritableArrayLike<E>

(length) => A

creates the target array for a given length

A

Deque.toArray

AbstractSequentialList.toArray


toString(): string

Defined in: src/list/LinkedList.ts:649

Returns the elements head to tail as [a, b, c]; an element that is this list prints as (this Collection).

string

Deque.toString

AbstractSequentialList.toString


static of<E>(…xs): LinkedList<E>

Defined in: src/list/LinkedList.ts:61

Creates a mutable list holding xs in argument order; null and undefined are allowed.

E

…E[]

LinkedList<E>