An abstract data type says what the operations are; it does not say what they cost. The cost is a property of the representation, and the two oldest representations of a sequence disagree about every operation except one. Both are run here on the same sequence in the word-RAM model, with a counter on each, and the totals are 122 against 92.
Core ideas
One idea, stated three ways, because it is the idea the rest of the course is quoted in: the cost of an operation is a fact about how the data is stored, not about what the operation is called.
“Insert at position i” is one operation with two different prices. On an array the position is free and making room is not: every element after the gap moves. On a linked list making room is free and the position is not: you walk to it. An abstract data type deliberately hides which of those you are paying for, which is exactly why a cost cannot be read off it.
This is the whole of the linked-list misunderstanding. Splicing a node into a doubly-linked list is a fixed number of pointer writes — genuinely O(1). Getting to the node you splice beside costs i + 1 hops, and nothing about the list makes that cheaper. The two costs add, and only one of them is constant.
The lab prints 122 and 92 for the sixteen operations on screen. That is evidence about those sixteen operations on a table of that size. The cost model above is the claim about every sequence, and the two are different kinds of statement — which is the habit this whole course is built to install.
The material
What one step costs, what each representation charges for each operation, and the one entry in the table that is an average rather than a worst case.
Memory is an array of words. Reading or writing a word at a known address costs 1, arithmetic on a word costs 1, and nothing else is charged for. Under this model an array index A[i] is one operation, because the address is computed from i; reaching the i-th node of a linked list is i + 1 operations, because the only way to the i-th node is through the ones before it.
This is the model every cost on this course is stated in. It has no cache, no page, and no notion of one access being nearer than another — System Design’s storage course is where that assumption is dropped and the answers change.
A dynamic array stores the elements contiguously, with spare capacity at the end. A doubly-linked list stores each element in its own node with pointers to its neighbours, and keeps a pointer to the head and to the tail. Both implement the same abstract sequence. Here is what each charges:
Read the two rows against each other rather than down. insert front is n + 1 on the array because every one of the n elements shifts up one place and then the new element is written; it is 1 on the list because two pointers change. index i is 1 on the array because the address is arithmetic; it is i + 1 on the list because the walk is the only route. delete at i costs the array the n − i elements it must shift down, and costs the list i + 2: i + 1 to arrive and one splice.
With n = 8 elements, inserting at the front costs the array 9 and the list 1. The lab reports exactly that pair, and it is the single most quoted comparison in this subject. It is also the comparison that produces the mistake, because the next operation in almost every real sequence is a lookup, and the lookup reverses it.
The lab’s opening sequence is the four operations the model is stated on — index, insert at the front, insert at the end, delete from the middle — repeated four times from n = 16, reaching halfway along for the two that take a position. Sixteen operations. Grouped by kind, the counters read:
The list wins this sequence, 92 against 122, and the operation that decided it is the insertion at the front: four of them cost 74 on the array and 4 on the list, a gap of 70 in a contest settled by 30. Every other row is either close or the wrong way round. That is the useful way to read a cost comparison — find the row with the largest gap, because that row is the answer and the rest is noise.
Change nothing but the mix. Three insertions at the front and one index, four times over from n = 24: array 370, list 78. Three indexes and one insertion at the end, same size: array 16, list 250. Same two representations, same counters, same model — a factor of nearly five one way and a factor of fifteen the other. The representation does not win or lose; a workload decides.
One entry in that table is not a worst case. insert end on a dynamic array is written 1, and sometimes it is not 1: when the spare capacity runs out the array is reallocated and every element is copied. The 1 is the amortised cost — the average over a run of insertions, which is O(1) because doubling makes the copies rare. The lab charges 1 every time and never shows the copy, so the array column is a little optimistic about any single insertion at the end, and honest about a run of them.
That gap is worth naming on the first page of the course, because it is the shape of every disagreement to come. Three different promises hide behind a single small number: a worst case that no input beats, an amortised cost that holds on average over a sequence, and an expected cost that holds on average over some randomness. A measurement cannot tell them apart. 122 and 92 are two integers produced by running sixteen operations; they are not a bound, and the next lesson is about a structure whose whole interest is that the distinction matters.
Interactive
One operation sequence, two representations, two counts
Method
The order matters: the operation list comes before either representation, and the label on the cost comes last.
“Mostly lookups with some insertions” cannot be costed. index at 8, insert front, insert end, delete at 9 can. A position is part of an operation here, because two of the four costs depend on it.
One row per operation, one column per representation, from the table above. Keep the running size in its own column: an insertion changes n, and the operation after it is priced at the new size.
The totals answer the question; the widest row explains it. If the widest gap is small relative to the totals, the honest report is that the representation barely matters for this mix — which happens, and is worth saying.
Everything in the table above is worst-case except the array’s insertion at the end, which is amortised. Writing the label beside the number is the habit that keeps a fast measurement from being read as a guarantee.
One round of the lab’s opening sequence, by hand, with the running size carried down. The lab does four rounds; the first is where the arithmetic is visible.
The array’s 17 at step 2 is the whole of its loss, and it grows as the sequence runs: by the fourth round that one operation costs 20, because three insertions have made the array longer. The list’s 9 and 11 at steps 1 and 4 are its loss, and they grow the same way and more slowly.
Notice what the round total does not tell you. 28 against 22 is a true statement about four operations at one size. It does not establish that the list is cheaper for this pattern at every size, and it does not settle where you might guess: the lab reports 61 : 46 at n = 16, 109 : 78 at n = 32 and 205 : 142 at n = 64, creeping toward 3 : 2 as the array’s front insertion grows like n against the list’s walk of n/2. Reading a bound off two integers is the thing to distrust.
For a faded rehearsal, price search, insert end, search, delete at the middle at n = 20, one round. The supplied first move is that search costs n on both, so the two columns are equal for steps 1 and 3 and the contest is decided by steps 2 and 4 alone. Predict the winner before you total it; then run that preset in the lab, which reports 212 against 216 over four rounds, and say why it is nearly a tie.
You should be able to fill in both rows of the cost table from memory, price a stated sequence on both representations with the running size carried correctly, name the operation whose gap decided the total, and say which single entry in the table is amortised rather than worst-case.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.