Node definition
- Algorithms course
- Beginner
- Lesson 58/80
- 4 min
A node has data and next fields.
Traversing the list
To traverse a linked list, start from head and advance with node = node['next']. Continue until node is None.
Traversal is O(n) because you must visit each node in order. There is no direct access like arr[i] in an array.
Length calculation
To find the length of a linked list, you traverse and count nodes. You increment the counter for each node.
This operation is O(n). It is not O(1) like len(arr) in arrays because the length is not stored in a linked list.
Practice Traverse list
Write traverse_list(head). Print each node's data. Call traverse_list(make_chain()) to print 1, 2, 3.
Starter code
def traverse_list(head):
# Traverse listSample solution
def traverse_list(head):
# Traverse list
node = head
while node is not None:
print(node['data'])
node = node['next']
traverse_list(make_chain())Expected output
1 2 3
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Traversal
Question
Traversal: advance with node = node[____].
Answer
Traversal: advance with node = node['next'].Explanation: 'next' is right.
2 Node definition: match the terms
| Term | Meaning |
|---|---|
head |
Start |
next |
Advance |
None |
End |
O(n) |
Traversal |
3 What is the traversal complexity in a linked list?
- O(n) Correct answer
- O(log n)
- O(1)
- O(n^2)
Explanation: Traversal is O(n).