What is a Linked List?
A linked list is a linear data structure where each element (called a node) contains two parts:
- Data: The value stored in the node.
- Pointer: A reference to the next node in the sequence.
Unlike arrays, linked lists do not store elements in contiguous memory locations. Instead, each node points to the next, forming a chain.
Traversing a Linked List
Traversal means visiting each node in the list, typically to access or process its data. To traverse a singly linked list, you start at the head (first node) and follow the pointers until you reach the end (where the next pointer is null).
Step-by-Step Example
Suppose we have a linked list with three nodes containing the values $3$, $7$, and $10$. #### Pseudocode for Traversal ``` current = head while current is not null: print(current.data) current = current.next ``` #### Visualization Let the nodes be: - Node 1: data = $3$, next $to$ Node 2 - Node 2: data = $7$, next $to$ Node 3 - Node 3: data = $10$, next $to$ null #### Step-by-Step 1. **Start at head**: $current$ points \to Node 1 ($3$) 2. **Visit Node 1**: Output $3$, move \to Node 2 3. **Visit Node 2**: Output $7$, move \to Node 3 4. **Visit Node 3**: Output $10$, move \to null 5. **End**: $current$ is null, traversal complete #### Mathematical Representation If the list has $n$ nodes, traversal visits each node exactly once, so time complexity is: %%MATH_DISPLAY_0%% ## Takeaways - A linked list is a sequence of nodes, each pointing \to the next. - Traversal starts at the head and follows pointers until the end. - Traversal time is linear: $O(n)$ for $n$ nodes.