Dynamic array and linked list
Two ways to store a sequence: the array that doubles its capacity when full and the linked list. For each, the cost of access, insertion and deletion at the head, in the middle and at the end, amortised cost included.
- 25 cards
- 6 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
- The numbers
- Scenarios
- Understand
A few cards from the deck
Dynamic array: what is it?
Show the answer
A sequence stored in one contiguous block of memory which, once full, is copied into a block twice as large.
It is Python's
listand Java'sArrayList. Access by index is direct, but inserting at the head shifts every element.This code inserts
nouveauafterprecin a linked list. What happens to the list?
```python
nouveau = Maillon(7)
prec.suivant = nouveau
nouveau.suivant = prec.suivant`nouveaupoints to itself and the rest is lost- It is correct:
7is inserted afterprec nouveauis inserted, butprecloses its link to it- Python raises an exception:
suivantdoes not exist yet
Show the answer
nouveaupoints to itself and the rest is lostAt line 3,
prec.suivantalready equalsnouveau: we writenouveau.suivant = nouveau, and the old successor ofprecis no longer referenced. Firstnouveau.suivant = prec.suivant, thenprec.suivant = nouveau.When a full dynamic array receives an append, it allocates a block of … the capacity and … all its elements into it.
Show the answer
When a full dynamic array receives an append, it allocates a block of double the capacity and copies all its elements into it.
Growing by one slot each time would force a copy at every append: n appends would cost about n². Doubling spaces the copies out.
Capacity of a dynamic array: what is it?
Show the answer
The number of slots reserved in memory, which may exceed the number of elements actually stored.
The size counts the elements present, the capacity counts the slots available. Copying only happens when the size reaches the capacity.