Linked lists

Linked lists trade direct indexing for cheap pointer rewiring when you already have the node. Interview tasks usually test careful traversal: reverse a list, detect a cycle, merge sorted lists, or remove a node with previous pointer tracking.

On interviews: A strong answer draws the nodes, names current and previous pointers, and explains when a dummy head removes edge cases around the first node.

Common pitfalls: The search cost is still O(n). Updating next pointers in the wrong order can lose the rest of the list. Always test empty, single-node, and head-removal cases.

Checklist:

• Track previous, current, and next.
• Consider a dummy head.
• Avoid losing references.
• Handle cycles explicitly.