CS 3354 data structures sheet

Insert in unordered array with lazy deletion?

Amortized O(1) — occasional resizing; average O(1).

Find in unordered array?

O(N) — linear scan required.

Update in unordered array?

O(N) — must locate element first.

Delete in unordered array with lazy deletion?

O(N) — find (O(N)) + mark deleted (O(1)).

Delete in unordered array with shift?

O(N) — find (O(N)) + shift elements (O(N)).

Insert at head in unordered singly linked list?

O(1) — change head pointer.

Insert at tail in unordered SLL with tail pointer?

O(1) — tail pointer allows direct insertion.

Insert at tail in SLL without tail pointer?

O(N) — must traverse from head.

Find/update/delete in SLL?

O(N) — traversal dominates; pointer changes are O(1).

Insert in ordered array?

O(N) — may need to shift elements to maintain order.

Find/update/delete in ordered array with lazy deletion?

O(log N) — binary search for element; marking deleted O(1).

Delete in ordered array with shift?

O(N) — binary search O(log N) + shift up to N elements.

Insert in ordered SLL/DLL?

O(N) — must traverse to correct position.

Find/update/delete in ordered SLL/DLL?

O(N) — traversal dominates; pointer changes are O(1).

Can you binary search a linked list?

No — nodes aren’t contiguous; only know next/prev pointers.

Push in dynamic array stack?

Amortized O(1) — occasional resize O(N) but average O(1).

Pop or peek in array stack?

O(1) — constant time.

Push/Pop/Peek at head in SLL stack?

O(1) — head insertion/removal.

Push at tail, pop from tail in SLL with tail pointer?

Push O(1), Pop O(N) — must traverse to predecessor of tail.

DLL stack at head/tail?

O(1) for all — prev pointers allow constant-time removal at tail or head.

Enqueue in normal array queue?

Amortized O(1) — insertion at end; may require resize.

Dequeue in array queue?

O(N) — shift all elements left.

Enqueue/dequeue in circular array?

O(1) — no shifting required; wrap-around indexing.

Enqueue at head, dequeue at tail in SLL queue without tail pointer?

Enqueue O(1), Dequeue O(N) — must traverse to remove tail.

Enqueue at tail, dequeue at head in SLL queue with tail pointer?

Both O(1) — standard queue implementation.

DLL queue enqueue/dequeue?

O(1) — head or tail insertion/removal possible.