Big-O notation and BST

ArrayList addAtIndex()

O(1) amortized for index at size and O(n) for the rest; Requires shifting elements to the right of the index

ArrayList addToFront()

O(n); Requires shifting all elements to the right.

ArrayList addToBack()

O(1) amortized; adding to back is O(1) but resizing the array can occasionally be O(n)

ArrayList removeAtIndex()

O(1) for index size - 1 and O(n) for other cases; requires shifting elements to the left of the index.

ArrayList removeFromFront()

O(n); requires shifting all elements to the left after removal.

ArrayList removeFromBack()

O(1); removing from the back is a constant time operation if the array is not resized.

Singly LinkedList addAtIndex()

O(n) unless its at the front; requires traversing the list to reach the specified index before adding the new element.

Singly LinkedList addAtFront()

O(1); adding an element at the front of a linked list is a constant time operation since it only involves updating the head pointer.

Singly LinkedList addAtBack()

O(1) with a tail, O(n) without a tail. With a tail, simply update the tail pointer. Without a tail, you have to traverse the entire list to find the last element before adding the new node.

Singly LinkedList removeAtFront()

O(1); simply update the head pointer.

Singly LinkedList removeAtIndex()

O(n); removing an element at a specific index requires traversing the list to that index.

Singly LinkedList removeAtBack()

O(n) always for a SLL; removing from the back requires traversing the list

Doubly LinkedList addAtIndex()

O(n) unless at the front or at the back with a tail; Still have to traverse the list to get to that given index

Doubly LinkedList addFront()

O(1); update head pointer

Doubly LinkedList addBack()

O(1) with a tail pointer; O(n) without. Need a tail pointer to update the back in constant time.

Doubly LinkedList removeAtIndex()

O(n) unless at the front or at the back with a tail pointer; Have to traverse the list to get to the given index

Doubly LinkedList removeFront()

O(1); update head and remove the node by pointing head at the second node

Doubly LinkedList removeBack()

O(1) with a tail pointer, O(n) without; Need a tail pointer to update the back by using the tail’s previous node, without you have to traverse the entire list

CSLL addAtIndex()

O(n) unless at front; Have to traverse the circular list to

CSLL addFront()

O(1); To add at front, you have to essentially point the newNode at the second node and then point the head node to that newNode and then swap their data

CSLL addAtBack()

O(n), O(1) with a tail pointer; Have to traverse the list to get to the back

CSLL removeAtIndex()

O(n) unless at the head

CSLL removeFront()

O(1); essentially get rid of the second node by pointing 1st node to 3rd node and then copying the data from the 2nd to the 1st.

CSLL removeBack()

O(n) without a tail pointer.

Stack Array push()

O(1) amortized; add to the back of the array and resizing if needed (addToBack() essentially)

Stack Array pop()

O(1); removing the top element from the stack is done in constant time. (removeFromBack() essentially)

Queue Array enqueue()

O(1) amortized; add to the back and resizing if needed

Queue Array dequeue()

O(1) amortized; using a circular buffer allows constant time removal from the front of the queue.

Stack LL push()

O(1), update the head pointer by doing the temp swap thing. head is the top of the stack

Stack LL pop()

O(1), update the head pointer by moving it back a node, removing the top of the stack

Queue LL enqueue()

O(1), update tail pointer. ADD to the back. use tail pointer as your back of your queue

Queue LL dequeue()

O(1); update the head pointer. REMOVE from the front. Use head pointer as the front and update to the next

Deque Array addFront()

O(1)*; circular deque starts with front at the back and decrementing the pointer. potential resizew

Deque Array addBack()

O(1)*; adding to the back actually starts at the front of the array and increments the back pointer. potential resize

Deque Array removeFront()

O(1); removing an element from the front increments front with wrap around modulo arithmetic

Deque Array removeBack()

O(1) removing an element from the back involves decrementing the back pointer (with wrap around using modulo)

Deque DLL addFront()

O(1) insert newnode at head and update head pointer

Deque DLL addBack()

O(1); insert newNode at the tail and update tail pointer

Deque DLL removeFront()

O(1); remove the node at the head and update head pointer

Deque DLL removeBack()

O(1); remove the node at the tail and update the tail pointer

Pre-Order Traversal

O(n); Visits the nodes in order; Root → Left→ Right; Uses Recursion

In-order traversal

O(n); Visits nodes in order: Left → Root → Right; Uses Recursion

Post-Order Traversal

O(n); Visits nodes in the order: Left → Right → Root. Uses recursion

Level-Order Traversal

O(n) Visits nodes level by level, from top to bottom; Uses a queue

Predecessor

In an in-order traversal, predecessor of a node is the previous node in sorted order

Successor

The successor of a node is the next node in sorted order

Full Binary Tree

Every node has either 0 or 2 children (no nodes with a single child)

Complete Binary Tree

All levels are fully filled except possibly the last, which is filled from left to right

Degenerate Tree

Each parent node has only one child, making it resemble a linked list

Balanced Tree

The height difference between left and right subtrees is at most 1 for all nodes

Binary Tree search()

O(log n) average case; O(n) worst case b/c of unbalanced BST;
Starts at root and checks if target is smaller, go left or right based on that

Binary Tree add()

O(log n) for balanced tree, O(n) unbalanced/degenerate
Start at root, compare value with current node. smaller = go left, greater = go right

Binary Tree remove()

O(log n) average case; O(n) worst case
Traverse tree, find in order successor (greater node to the right), replace the node with successor, delete successor from original position