Linked List Operations

By the end, you can

• Describe the structure of a linked list and explain why it is only reachable through HEAD.
• Explain the O(1) vs O(n) trade-off between arrays and linked lists for lookup and modification.
• Write the two pointer assignments needed to insert a node at the head, in the middle, and at the tail.
• Explain why the pointer assignments must be written in the order "save the forward link first, then redirect the predecessor" — reversing the order overwrites the only reference to the rest of the list and orphans every node downstream.
• Identify the self-loop bug caused by reversing those two writes and explain why it orphans the rest of the list.
• Trace the single pointer write needed to remove the head node and explain why it is O(1).
• Trace the pointer write needed to remove a middle node (prev.next = target.next) and explain the O(n) traversal cost.
• Apply the dummy-node pattern to eliminate head and empty-list special cases.
• List the three edge cases every linked-list implementation must handle: empty list, single node, and null-pointer guard.
• State how a tail pointer and a doubly linked list each reduce tail operation complexity to O(1).