Scribd
Upload
22 views12 pages

Understanding Maps and Dictionaries in Python

The document discusses maps and dictionaries, highlighting that a map is a collection of key-value pairs with operations for searching, inserting, and deleting items. It emphasizes Python's dict class as a significant data structure representing a dictionary with unique keys. Additionally, it covers the implementation and performance of a list-based map, noting its efficiency for small sizes and frequent insertions.

Uploaded by

rlatkdrjf112
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
22 views12 pages

Understanding Maps and Dictionaries in Python

The document discusses maps and dictionaries, highlighting that a map is a collection of key-value pairs with operations for searching, inserting, and deleting items. It emphasizes Python's dict class as a significant data structure representing a dictionary with unique keys. Additionally, it covers the implementation and performance of a list-based map, noting its efficiency for small sizes and frequent insertions.

Uploaded by

rlatkdrjf112
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Maps and Dictionaries

© 2013 Goodrich, Tamassia, Goldwasser Maps and Dictionaries 1


Maps
q A map is a searchable collection of
items that are key-value pairs
q The main operations of a map are for
searching, inserting, and deleting items
q Multiple items with the same key are
not allowed
q Applications:
n address book
n student-record database
© 2013 Goodrich, Tamassia, Goldwasser Maps and Dictionaries 2
Dictionaries
q Python’s dict class is arguably the most
significant data structure in the language.
n It represents an abstraction known as a
dictionary in which unique keys are mapped to
associated values.
q Here, we use the term “dictionary” when
specifically discussing Python’s dict class, and
the term “map” when discussing the more
general notion of the abstract data type.

© 2013 Goodrich, Tamassia, Goldwasser Maps and Dictionaries 3


The Map ADT
(Using dict Syntax)

© 2013 Goodrich, Tamassia, Goldwasser Maps and Dictionaries 4


More Map Operations

© 2013 Goodrich, Tamassia, Goldwasser Maps and Dictionaries 5


A Few More Map Operations

© 2013 Goodrich, Tamassia, Goldwasser Maps and Dictionaries 6


Example

© 2013 Goodrich, Tamassia, Goldwasser Maps and Dictionaries 7


A Simple List-Based Map
q We can efficiently implement a map using an
unsorted list
n We store the items of the map in a list S (based
on a doubly-linked list), in arbitrary order

header nodes/positions trailer

9 c 6 c 5 c 8 c
Items (key-value pairs)

© 2013 Goodrich, Tamassia, Goldwasser Maps and Dictionaries 8


Our MapBase Class

© 2013 Goodrich, Tamassia, Goldwasser Maps and Dictionaries 9


The MapBase Abstract Class

© 2013 Goodrich, Tamassia, Goldwasser Maps and Dictionaries 10


An Unsorted List Implementation

© 2013 Goodrich, Tamassia, Goldwasser Maps and Dictionaries 11


Performance of a List-Based Map
q Performance:
n Inserting an item takes O(1) time since we can insert the
new item at the beginning or at the end of the unsorted list
n Searching for or removing an item takes O(n) time, since in
the worst case (the item is not found) we traverse the entire
listto look for an item with the given key
q The unsorted list implementation is effective only for
maps of small size or for maps in which insertions are
the most common operations, while searches and
removals are rarely performed (e.g., historical record
of logins to a workstation)

© 2013 Goodrich, Tamassia, Goldwasser Maps and Dictionaries 12

You might also like