CS 2110: SLL vs DAL Time & Space Complexity

Front: method/storage. Back: worst-case time, auxiliary space, and reasoning. Based on CS 2110 SinglyLinkedList (sentinel tail, spliceIn/spliceOut) and DynamicArrayList (doubling).

DAL: storage (total space)

Time: n/a. Space: O(n). The backing array storage has capacity between n and about 2n because it doubles when full. Fields size and storage add O(1). The wasted part is the unused slots past size.

SLL: storage (total space)

Time: n/a. Space: O(n). There are n nodes, each holding a data ref and a next ref, plus one empty sentinel tail node and the head/tail/size fields. The overhead is one extra next reference and one node object per element.

DAL: get(i)

Time: O(1). Space: O(1). It returns storage[i]. Array indexing computes the slot's address directly, so it does no walking.

SLL: get(i)

Time: O(i), worst case O(n). Space: O(1). nodeAtIndex(i) follows next i times from head, because linked nodes have no random access.

DAL: set(i, x)

Time: O(1). Space: O(1). It assigns storage[i] = x directly with no shifting.

SLL: set(i, x)

Time: O(i), worst case O(n). Space: O(1). It walks to the node with nodeAtIndex(i) and then does an O(1) node.data = x. The walk is the whole cost.

DAL: add(x) (append at end)

Time: amortized O(1), worst case O(n) for a single call. Space: O(n) auxiliary on a resize, otherwise O(1). Usually it writes storage[size]. When the array is full it copies everything into an array twice as large. Copies at the doubling points total 1 + 2 + 4 + … < 2n, so n adds cost O(n) in total.

SLL: add(x) (append at end)

Time: O(1) worst case. Space: O(1), one new node. spliceIn(tail, x) writes x into the empty sentinel tail node and makes a new empty node the tail. The tail field means no walking. Without it, add would cost O(n).

DAL: insert(0, x)

Time: O(n). Space: O(1), or O(n) if it triggers a resize. All n elements shift one slot right to open index 0.

SLL: insert(0, x)

Time: O(1). Space: O(1). nodeAtIndex(0) is just head, so there is no walk. spliceIn copies head's contents into a new node after it and puts x in head.

DAL: insert(i, x) (middle)

Time: O(n − i), worst case O(n). Space: O(1), or O(n) on a resize. Elements i through size−1 shift right one slot.

SLL: insert(i, x) (middle)

Time: O(i), worst case O(n). Space: O(1). It walks i nodes to reach the spot, then does an O(1) splice. The walk is the cost and nothing shifts.

DAL: remove(0)

Time: O(n). Space: O(1). The n−1 remaining elements each shift one slot left to close the gap.

SLL: remove(0)

Time: O(1). Space: O(1). The node is head, so there is no walk. spliceOut(head) copies the next node's data/next into head (a textbook SLL does head = head.next). A tail pointer is irrelevant here.

DAL: remove(size − 1) (remove last)

Time: O(1). Space: O(1). Nothing comes after the last element, so nothing shifts: decrement size and null the slot. This assumes the array never shrinks. With shrinking it is amortized O(1).

SLL: remove(size − 1) (remove last)

Time: O(n). Space: O(1). It has to walk from head to reach the last node (in a textbook SLL, its predecessor, whose next must change). A tail pointer speeds up adding at the end, not removing.

DAL: remove(i) (middle)

Time: O(n − i), worst case O(n). Space: O(1). Elements after index i shift left one slot.

SLL: remove(i) (middle)

Time: O(i), worst case O(n). Space: O(1). It walks i nodes, then spliceOut rewires in O(1). Nothing shifts.

DAL: contains(x) / indexOf(x)

Time: O(n). Space: O(1). It is a linear scan with .equals. The worst case is x absent or last. Only a SORTED array could use binary search for O(log n).

SLL: contains(x) / indexOf(x)

Time: O(n). Space: O(1). It is a linear walk from head to tail, worst case x absent. Binary search doesn't help even when sorted, because there is no O(1) indexing.

DAL: delete(x) (remove first occurrence)

Time: O(n). Space: O(1). Finding x at index k costs O(k), then shifting the rest left costs O(n − k). Together that is always about n.

SLL: delete(x) (remove first occurrence)

Time: O(n). Space: O(1). The search walk is O(k), worst case O(n). Once the node is found, spliceOut is O(1).

DAL / SLL: size()

Time: O(1). Space: O(1). Both store a size field that every add/remove updates, so they never count.

DAL: traverse all elements (for-each or get(i) loop)

Time: O(n). Space: O(1). Each get(i) is O(1), so n calls cost O(n). An iterator gives the same O(n).

SLL: loop calling get(i) for i = 0..n−1

Time: O(n²). Space: O(1). Each get(i) re-walks from head: 0 + 1 + … + (n−1) ≈ n²/2. Use the iterator / for-each loop instead, which is O(n) total.

SLL: traverse with iterator (for-each)

Time: O(n) total, O(1) per next(). Space: O(1), since the iterator stores one current node reference. Each next() returns current.data and advances one node.

DAL: constructor (new empty list)

Time: O(1). Space: O(1). It allocates a small fixed-capacity storage array (a constant size) and sets size = 0.

SLL: constructor (new empty list)

Time: O(1). Space: O(1). It creates one empty sentinel node, and head = tail = that node, with size = 0.