Section 7: Linked Lists — Operations and Complexity (73–84)

Time complexity of linked-list size() when size is stored as a field

$$O(1)$$

Time complexity of linked-list add() at the end when a tail reference is maintained

$$O(1)$$

Time complexity of linked-list nodeAtIndex(i)

$$O(n)$$

Time complexity of linked-list get(i)

$$O(n)$$

Time complexity of linked-list contains(element)

$$O(n)$$

Time complexity of linked-list indexOf(element)

$$O(n)$$

Function of set(i, element) in a linked list

Finds the node at index $i$ and replaces its stored data.

Time complexity of linked-list set(i, element)

$O(n)$, because finding the node at index $i$ requires linear traversal.

Function of spliceIn in a linked list

Inserts a new element at a specified node position by instantiating a node and updating adjacent references.

Time complexity of spliceIn once the insertion position is known

$$O(1)$$

Function of spliceOut in a linked list

Removes a node by updating references so that surrounding nodes are linked directly together.

Time complexity of spliceOut once the node position is known

$$O(1)$$