Lecture Notes on Lists and Queues 15 122 Principles of Imperative Computation Frank Pfenning Lecture 7 September 14 2010 1 Introduction In this lecture we first review amortized analysis with another example this time studying binary counters Then we will introduce queues as a data structure and linked lists that underly their implementation In order to implement them we need recursive types which are quite common in the implementation of data structures 2 Amortized Analysis of Binary Counters A binary counter is a sequence of bits representing a number in binary form that can be incremented We do not presume a fixed precision but allow the counter to be extended in case it overflows To simplify the analysis we assume we start at 0 and count upwards We are interested in measuring the cost of incrementing the counter in terms of the number of bits we have to flip For example incrementing 0 2 to 1 2 requires 1 bit flip incrementing 1 2 to 10 2 requires 2 we complement the lowest bit and then we add another digit on the left which we consider the same as flipping a hypothetical 0 to 1 What is the cost of a single increment It looks mostly like constant time but not quite For example when the number is 11111111 2 then the increment will take 9 bit flips which is equal to the number of bits we have 8 plus 1 In general after we incremented n 2k times we will have k 1 bits in our representation So the maximal number of bit flips during a single increment is O k O log n L ECTURE N OTES S EPTEMBER 14 2010 Lists and Queues L7 2 But what is the cost of incrementing a counter n times Naively multiplying we might think the cost is O n log n but we might suspect it could be less like O n if we analyze the situation more carefully A perfect example where we can try an amortized analysis Let s do some counting of bit flips starting at 0 to see if we can form a conjecture Since we are working with binary numbers throughout we omit the base 2 number op flips 0 inc 1 2 1 inc 10 inc 1 11 inc 3 100 inc 1 101 inc 2 110 inc 1 111 inc 4 1000 inc 1 1001 Looking at the structure we see at on each increment there is exactly one flip from 0 to 1 and some variable number of flips from 1 to 0 Let s separate these out number op 0 1 1 0 0 inc 1 0 1 1 1 inc 10 inc 1 0 11 inc 1 2 100 inc 1 0 101 inc 1 1 110 inc 1 0 111 inc 1 3 1000 inc 1 0 1001 The question is how to account for the 1 0 flips The idea behind amortized analysis here is to set aside a constant number of tokens on each increment so that we have enough saved up to perform the 1 0 flips Recall that each token represents an operation we could have performed and stayed within constant time for each of the n increments but did not Therefore we can perform these operations later without violating the O n bound for the total number of n increments L ECTURE N OTES S EPTEMBER 14 2010 Lists and Queues L7 3 The crucial insight here is that on each increment we create exactly one new 1 that was not in the previous number namely the 0 1 flip So if we put aside one token for every increment we should have one token for every digit 1 in the number That s enough to pay for the flips 1 0 because the number of these flips on each increment is bounded by the number of 1 s Let s run through this again and count the number of tokens we we have We save one on each operation tokens before inc 0 1 1 2 1 2 2 3 1 2 number 0 1 10 11 100 101 110 111 1000 1001 op 0 1 1 0 inc 1 0 inc 1 1 inc 1 0 inc 1 2 inc 1 0 inc 1 1 inc 1 0 inc 1 3 inc 1 0 tokens saved 1 1 1 1 1 1 1 1 1 tokens spent 0 1 0 2 0 1 0 3 0 From this table we form the conjecture that if we save a token on every increment and we spend a token for every 1 0 flip during an increment then we always have exactly as many tokens as 1 s Since number of 1 s can never become negative the number of tokens never becomes negative To prove this we note two things First when we start we have no tokens saved and also no 1 s in the number so the invariant holds Assume after some number of steps we have k 1 s If the rightmost bit is a 0 we flip it to become a 1 which is the only operation we perform We also add one token which accounts for the additional 1 in the number If the rightmost r bits are 1 s we flip them all to 0 s costing r tokens and the next 0 to a 1 gaining one token So we spend r tokens and gained one so we have k r 1 But this is also the number of 1 s because we started with k performed r flips from 1 to 0 and one from 0 to 1 Taking these two together we know the invariant that the number of tokens equals the number of 1s is true at the beginning and preserved by every increment It therefore must always be true The total number of operations for n increments is the sum of the 0 1 flips which is n and 1 0 flips The latter is bounded by the number of L ECTURE N OTES S EPTEMBER 14 2010 Lists and Queues L7 4 tokens of which we put aside n over n operations It is therefore O n and the total number of bit flips is O 2 n O n 3 Linked Lists Linked lists are a common alternative to arrays in the implementation of data structures Each item in a linked list contains a data element of some type and a pointer to the next item in the list It is easy to insert and delete elements in a linked lists which is not a natural operation on arrays On the other hand access to an element in the middle of the list is usually O n where n is the length of the list An item in a linked list consists of a struct containing the data element and a pointer to another linked list This gives rise to the following definition struct list string data struct list next typedef struct list list This definition is an example of a recursive type A struct of this type contains a …