Node definition

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.

Exercise Traverse list

Write traverse_list(head). Print each node's data. Call traverse_list(make_chain()) to print 1, 2, 3.

Show example solution

def traverse_list(head):
    # Traverse list
    node = head
    while node is not None:
        print(node['data'])
        node = node['next']
traverse_list(make_chain())

Test yourself

Traversal

Traversal: advance with node = node[____].

Show answer

Traversal: advance with node = node['next'].

Node definition: match the terms

head

Start
next

Advance
None

End
O(n)

Traversal
What is the traversal complexity in a linked list?
- O(n)
- O(log n)
- O(1)
- O(n^2)
Show answer

O(n) — Traversal is O(n).

Next lesson: Traversing the list

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies