Traversing the list

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).

Exercise List length

Write list_length(head). Count nodes and return. Print 3 with print(list_length(make_chain())).

Show example 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()))

Test yourself

Traversing the list: match the terms

Head insert

O(1) fast
Tail insert

O(n) traverse
Search

O(n) scan
Traversal

O(n) visit
How long does head insertion take?
- O(n)
- O(n^2)
- O(1)
- O(log n)
Show answer

O(n^2) — Head insertion is O(1).

Head insert

The new node's next becomes ____.

Show answer

The new node's next becomes head.

Next lesson: Summary - Linked list

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies