6.006 Introduction to Algorithms, Lecture 2: Data Structures

Introduction to Algorithms: 6.006 Massachusetts Institute of Technology Instructors: Erik Demaine, Jason Ku, and Justin Solomon Lecture 2: Data Structures Lecture 2: Data Structures Data Structure Interfaces • A data structure is a way to store data, with algorithms that support operations on the data • Collection of supported operations is called an interface (also API or ADT) • Interface is a specification: what operations are supported (the problem!) • Data structure is a representation: how operations are supported (the solution!) • In this class, two main interfaces: Sequence and Set Sequence Interface (L02, L07) • Maintain a sequence of items (order is extrinsic) • Ex: (x0 , x1 , x2 , . . . , xn−1 ) (zero indexing) • (use n to denote the number of items stored in the data structure) • Supports sequence operations: Container Static Dynamic build(X) len() iter seq() get at(i) set at(i, x) insert at(i, x) delete at(i) insert first(x) delete first() insert last(x) delete last() given an iterable X, build sequence from items in X return the number of stored items return the stored items one-by-one in sequence order return the ith item replace the ith item with x add x as the ith item remove and return the ith item add x as the first item remove and return the first item add x as the last item remove and return the last item • Special case interfaces: stack queue insert last(x) and delete last() insert last(x) and delete first() 2 Lecture 2: Data Structures Set Interface (L03-L08) • Sequence about extrinsic order, set is about intrinsic order • Maintain a set of items having unique keys (e.g., item x has key x.key) • (Set or multi-set? We restrict to unique keys for now.) • Often we let key of an item be the item itself, but may want to store more info than just key • Supports set operations: Container Static Dynamic Order build(X) len() find(k) insert(x) delete(k) iter ord() find min() find max() find next(k) find prev(k) given an iterable X, build sequence from items in X return the number of stored items return the stored item with key k add x to set (replace item with key x.key if one already exists) remove and return the stored item with key k return the stored items one-by-one in key order return the stored item with smallest key return the stored item with largest key return the stored item with smallest key larger than k return the stored item with largest key smaller than k • Special case interfaces: dictionary set without the Order operations • In recitation, you will be asked to implement a Set, given a Sequence data structure. Array Sequence • Array is great for static operations! get at(i) and set at(i, x) in Θ(1) time! • But not so great at dynamic operations... • (For consistency, we maintain the invariant that array is full) • Then inserting and removing items requires: – reallocating the array – shifting all items after the modified item Data Structure Array Operation, Worst Case O(·) Dynamic Container Static build(X) get at(i) insert first(x) insert last(x) insert at(i, x) set at(i,x) delete first() delete last() delete at(i) 1 n n n n Lecture 2: Data Structures 3 Linked List Sequence • Pointer data structure (this is not related to a Python “list”) • Each item stored in a node which contains a pointer to the next node in sequence • Each node has two fields: node.item and node.next • Can manipulate nodes simply by relinking pointers! • Maintain pointers to the first node in sequence (called the head) • Can now insert and delete from the front in Θ(1) time! Yay! • (Inserting/deleting efficiently from back is also possible; you will do this in PS1) • But now get at(i) and set at(i, x) each take O(n) time... :( • Can we get the best of both worlds? Yes! (Kind of...) Data Structure Linked List Operation, Worst Case O(·) Dynamic Container Static build(X) get at(i) insert first(x) insert last(x) insert at(i, x) set at(i,x) delete first() delete last() delete at(i) n 1 n n n Dynamic Array Sequence • Make an array efficient for last dynamic operations • Python “list” is a dynamic array • Idea! Allocate extra space so reallocation does not occur with every dynamic operation • Fill ratio: 0 ≤ r ≤ 1 the ratio of items to space • Whenever array is full (r = 1), allocate Θ(n) extra space at end to fill ratio ri (e.g., 1/2) • Will have to insert Θ(n) items before the next reallocation • A single operation can take Θ(n) time for reallocation • However, any sequence of Θ(n) operations takes Θ(n) time • So each operation takes Θ(1) time “on average” 4 Lecture 2: Data Structures Amortized Analysis • Data structure analysis technique to distribute cost over many operations • Operation has amortized cost T (n) if k operations cost at most ≤ kT (n) • “T (n) amortized” roughly means T (n) “on average” over many operations • Inserting into a dynamic array takes Θ(1) amortized time • More amortization analysis techniques in 6.046! Dynamic Array Deletion • Delete from back? Θ(1) time without effort, yay! • However, can be very wasteful in space. Want size of data structure to stay Θ(n) • Attempt: if very empty, resize to r = 1. Alternating insertion and deletion could be bad... • Idea! When r < rd , resize array to ratio ri where rd < ri (e.g., rd = 1/4, ri = 1/2) • Then Θ(n) cheap operations must be made before next expensive resize • Can limit extra space usage to (1 + ε)n for any ε > 0 (set rd = 1 ,r 1+ε i = rd +1 ) 2 • Dynamic arrays only support dynamic last operations in Θ(1) time • Python List append and pop are amortized O(1) time, other operations can be O(n)! • (Inserting/deleting efficiently from front is also possible; you will do this in PS1) Data Structure Array Linked List Dynamic Array Operation, Worst Case O(·) Dynamic Container Static build(X) get at(i) insert first(x) insert last(x) insert at(i, x) set at(i,x) delete first() delete last() delete at(i) 1 n 1 n 1 n n n n n n 1(a) n n n