Lecture Data structures and algorithms in Java (6th edition): Chapter 10.2 - Goodrich, Tamassia, Goldwasser

This chapter provides knowledge of maps. Data structures and algorithms in java provides an introduction to data structures and algorithms, including their design, analysis, and implementation. | Maps 3/19/14 Presentation for use with the textbook Data Structures and Algorithms in Java, 6th edition, by M. T. Goodrich, R. Tamassia, and M. H. Goldwasser, Wiley, 2014 Maps © 2014 Goodrich, Tamassia, Goldwasser Maps 1 Maps A map models a searchable collection of key-value entries q   The main operations of a map are for searching, inserting, and deleting items q   Multiple entries with the same key are not allowed q   Applications: q   address book n   student-record database n   © 2014 Goodrich, Tamassia, Goldwasser Maps 2 1 Maps 3/19/14 The Map ADT q   q   q   q   q   q   q   get(k): if the map M has an entry with key k, return its associated value; else, return null put(k, v): insert entry (k, v) into the map M; if key k is not already in M, then return null; else, return old value associated with k remove(k): if the map M has an entry with key k, remove it from M and return its associated value; else, return null size(), isEmpty() entrySet(): return an iterable collection of the entries in M keySet(): return an iterable collection of the keys in M values(): return an iterator of the values in M © 2014 Goodrich, Tamassia, Goldwasser Maps 3 Example Operation isEmpty() put(5,A) put(7,B) put(2,C) put(8,D) put(2,E) get(7) get(4) get(2) size() remove(5) remove(2) get(2) isEmpty() Output true null null null null C B null E 4 A E null false © 2014 Goodrich, Tamassia, Goldwasser Map Ø (5,A) (5,A),(7,B) (5,A),(7,B),(2,C) (5,A),(7,B),(2,C),(8,D) (5,A),(7,B),(2,E),(8,D) (5,A),(7,B),(2,E),(8,D) (5,A),(7,B),(2,E),(8,D) (5,A),(7,B),(2,E),(8,D) (5,A),(7,B),(2,E),(8,D) (7,B),(2,E),(8,D) (7,B),(8,D) (7,B),(8,D) (7,B),(8,D) Maps 4 2 Maps 3/19/14 A Simple List-Based Map q   We can implement a map using an unsorted list n   We store the items of the map in a list S (based on a doublylinked list), in arbitrary order nodes/positions header 9 c 6 c 5 c trailer 8 c entries © 2014 Goodrich, Tamassia, Goldwasser Maps 5 The get(k) .