Summary - Linked list
- Algorithms course
- Beginner
- Lesson 60/80
- 4 min
Build three nodes and print their values in a mini task.
Summary - Linked list
In this group you learned what a linked list is, node definition, traversal and insertion. Access and search are O(n), head insertion is O(1).
Linked lists offer flexible size and fast head insertion but require linear access. Arrays offer O(1) access.
Practice Append to list
Write list_append(head, data). Add a new node at the end, return head. Print 7 with print(list_append(None, 7)['data']).
Starter code
def list_append(head, data):
# AppendSample solution
def list_append(head, data):
# Append
new_node = {'data': data, 'next': None}
if head is None:
return new_node
node = head
while node['next'] is not None:
node = node['next']
node['next'] = new_node
return head
print(list_append(None, 7)['data'])Expected output
7
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Summary - Linked list: match the terms
| Term | Meaning |
|---|---|
Node |
data + next |
head |
First node |
Head insert |
O(1) |
Traversal |
O(n) |
2 Linked list
Question
Each node in a linked list contains a ____ pointer.
Answer
Each node in a linked list contains a next pointer.Explanation: next is right.
3 What is the advantage of a linked list?
- O(1) access
- Fixed size
- Flexible size, O(1) head insert Correct answer
- O(log n) search
Explanation: Flexible size and O(1) head insert.