Overview of Collections

Question 1

What is a collection?

Answer 1

Container for zero or more data objects

Tracks its own size and resizing is automatic

Comes with built-in operations for access, insertions, removals, etc.

Question 2

What do we do with the details of a collection’s underlying data structures and operations? Why?

Answer 2

We ignore them because they are hidden in the implementation

Question 3

Built-in python collections

Answer 3

String, Tuple, List, Set, Dictionary

Question 4

Basic categories of collections

Answer 4

Linear, Hierarchical, Graph, Unordered

Question 5

Types of linear collections

Answer 5

List, Stack, Queue, Priority Queue

Question 6

Linear collection characteristics

Answer 6

Elements are ordered by position

Each element except the first has a unique predecessor

Each element except the last has a unique successor

Question 7

List characteristics

Answer 7

Allow accesses, replacements, insertions, and removals at any position

Question 8

Stack characteristics

Answer 8

Allow accesses, insertions, and removals at one end only

Question 9

Queue characteristics

Answer 9

Allow insertions at one end and removals and accesses at the other end

Question 10

Priority Queue characteristics

Answer 10

Sort elements by priority, but elements with equal priority are added and removed in queue-like order

Question 11

Types of hierarchical collections

Answer 11

Binary tree, General tree, Binary search tree, Heap

Question 12

Hierarchical collection characteristics

Answer 12

Each element except the root has a unique predecessor

Each can have zero or more successors

Question 13

Types of graph collections

Answer 13

Undirected graph, Directed graph

Question 14

Graph collection characteristics

Answer 14

Each element can have zero or more predecessors

Each can have zero or more successors

Question 15

Types of unordered collections

Answer 15

Bag, Set, Dictionary

Question 16

Unordered collection characteristics

Answer 16

No notion of position from the user’s perspective

We can visit all the objects with a for loop

Question 17

Types of sorted collections

Answer 17

Sorted Set, Sorted Dictionary

Question 18

Sorted collection characteristics

Answer 18

The elements are not ordered by position, but they are ordered by content (ascending order)

Question 19

Aspects of a collection

Answer 19

Formal properties (what it is and what you can do with it - as expressed in its interface)

Implementations - array-based, link-based, etc.

Performance characteristics - space/time tradeoffs of different implementations

Question 20

Basic types of operations

Answer 20

Create a collection: collection()

Obtain the string representation: str(collection)

Obtain the number of items currently in the collection: len(collection

Test an item for membership: item in collection

Iterate through the items: for item in collection:

Concatenate two collections (of the same type): collection1 + collection2

Test for equality: collection == object

Make the collection empty: collection.clear()

Add an item: collection.add(item)

Remove an item: collection.remove(item)