More Data Structures

7. More Data Structures#

7.1. Summarising the basic python data structures#

Here are some of the more commonly used python data structures

7.1.1. set#

S = {1,2,7,3,2,5}
print(S)

{1, 2, 3, 5, 7}

7.1.2. list#

L = [1,2,7,3,2,5]
print(L)

[1, 2, 7, 3, 2, 5]

7.1.3. dictionary#

D = {"first" : 1,"second" : 2,"third" : 7,"fourth" : 3,"fifth" : 2,"sixth" : 5}
print(D)

{'first': 1, 'second': 2, 'third': 7, 'fourth': 3, 'fifth': 2, 'sixth': 5}

7.1.4. tuple#

T = (1,2,7,3,2,5)
print(T)

(1, 2, 7, 3, 2, 5)

In what way(s) could these data structures be characterised ? Here is one possibility. It characterises the data structures according to what methods can be (meaningfully) applied to them.

method

list

dictionary

set

tuple

sort

✓

add

append

bisect

remove

pop

7.2. Exercise 1#

Complete the above table. Bear in mind, the method name is meant to be descriptive. The actual method (or technique) you use in python to achieve it may not have this name.

7.3. Exercise 2#

Try and think of a use case for each one of the data structures listed above.

7.4. Exercise 3#

Can you provide a “mathematical” description of these data structures ?

7.5. Exercise 4#

Here is a less commonly used data structure.

Hide code cell source

 
!python3 -m pip install sortedcontainers

Hide code cell output

 
Collecting sortedcontainers
  Using cached sortedcontainers-2.4.0-py2.py3-none-any.whl.metadata (10 kB)
Using cached sortedcontainers-2.4.0-py2.py3-none-any.whl (29 kB)
Installing collected packages: sortedcontainers
Successfully installed sortedcontainers-2.4.0

from sortedcontainers import SortedList
L = [1,2,7,3,2,5]
print(L[2])
SL = SortedList([1,2,7,3,2,5])
print(SL[2])

7
2

Find out what “methods” a SortedList has.

What is the difference between a SortedList and a standard python list ?

Can you think of a scenario in which a SortedList would be preferable to an ordinary list ?

Can you think of a scenario in which an ordinary list is preferable to a SortedList ?

Have a look at some of the other data structures available in the sortedcontainers library.

7.6. Point of Departure#

How would you explain to someone with a mathematical background (but limited knowledge of computer science) what a data stucture is ?

Contents