❓Q/A

Linked List

Question #1

What two properties are typically stored in the nodes of a singly linked list?

value and next

Question #2

What terms are commonly used to describe the first node & last node of a linked list?

HEAD for first-node

TAIL for last-node

Question #3

What is the dummy head pattern for a linked-list?

The dummy head pattern is where we use a fake node to act as the HEAD of the linked-list. The dummy-head is used to simplify edge cases such as inserting teh first node into an empty linked-list.

Question #4

Why might the expression current_node.next.val be UNSAFE?

If the current node is a TAIL-node then its .next will be None and None object does not have .val attribute.

Question #5

What is the OPTIMAL COMPLEXITY for searching a target value in a tandard singly-linked-list?

\(O(n)\) time-complexity and \(O(1)\) space-complexity for ITERATIVE Solution.

\(O(n)\) time-complexity and \(O(n)\) space-complexity for RECURSIVE solution.