A SCLL is a linked list where each node points to the next, and the last node points back to the head.
| Operation | Description | Time Complexity |
|---|---|---|
| Display | Traverse using do-while loop till it loops back to head. |
O(n) |
| Add First | Insert before head. If empty, point node to itself. Else, adjust tail.next. | O(1) |
| Add Last | Insert after tail and update tail. Link to head to maintain circularity. | O(1) |
| Add at Position | Traverse to (pos-1), insert between nodes. | O(n) |
| Delete First | If only one node, make head/tail null. Else, move head forward and fix tail.next. | O(1) |
| Delete Last | Traverse to second last node and update its next to head. | O(n) |
| Delete at Position | Traverse to (pos-1), remove next node. | O(n) |
A DCLL has nodes with both prev and next pointers forming a two-way loop.
| Operation | Description | Time Complexity |
|---|---|---|
| Display | Traverse forward or backward starting from head. | O(n) |
| Add First | New node before head, update head/tail pointers. | O(1) |
| Add Last | New node after tail, adjust circular links. | O(1) |
| Add at Position | Traverse to (pos-1), insert node between. | O(n) |
| Delete First | Update head and fix prev/next links. | O(1) |
| Delete Last | Update tail and fix links. | O(n) |
| Delete at Position | Remove node at pos by adjusting prev/next. | O(n) |
Efficient method to handle contiguous subarrays or substrings using a “window”.
| Type | Use Case | Strategy |
|---|---|---|
| Fixed Size | E.g., Max average of k-size subarray | Slide window, update result |
| Variable Size | E.g., Longest substring with unique chars | Expand/shrink window dynamically |