Traversing the list
- Algorithms course
- Beginner
- Lesson 59/80
- 4 min
Walk from the head to the end of the list.
Adding a node
Adding a node at the head is O(1): the new node's next becomes head, and head becomes the new node.
Adding at the tail is O(n) because you must traverse the whole list to find the last node.
Searching a node
To search for a value in a linked list, you traverse and check each node's data. This is O(n).
Binary search does not work here because there is no direct access in a linked list, and even if sorted, reaching the middle takes O(n).
Practice List length
Write list_length(head). Count nodes and return. Print 3 with print(list_length(make_chain())).
Starter code
def list_length(head):
# Compute lengthSample solution
def list_length(head):
# Compute length
count = 0
node = head
while node is not None:
count = count + 1
node = node['next']
return count
print(list_length(make_chain()))Expected output
3
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Traversing the list: match the terms
| Term | Meaning |
|---|---|
Head insert |
O(1) fast |
Tail insert |
O(n) traverse |
Search |
O(n) scan |
Traversal |
O(n) visit |
2 How long does head insertion take?
- O(n)
- O(n^2) Correct answer
- O(1)
- O(log n)
Explanation: Head insertion is O(1).
3 Head insert
Question
The new node's next becomes ____.
Answer
The new node's next becomes head.Explanation: head is right.