Data Structures

Data Structures #

WHAT is this? #

My version: #

Data structures are organized ways to store and manage data efficiently, such as arrays, lists, and trees.

WHY is this important? #

My version: #

They impact the efficiency and performance algorithms and applications.

WHY should I learn this? #

My version: #

Helps you write efficient code and solve complex problems, essential for tech careers.

WHEN will I need this? #

My version: #

You’ll need them in algorithm design, software development, technical interviews, system design, and database management.

HOW does this work? #

lists #

A list is a built-in data structure that allows you to store a collection of items.

Lists are mutable, and their elements are usually homogeneous and are accessed by iterating over the list.

You can create a list by placing items inside square brackets [], separated by commas:

my_list = ['banana', 'watermelon', 'snake fruit', 'apple', 'durian']

You can access elements using their index (starting from 0).

>>> first_item = my_list[0]
>>> first_item
'banana'

You can retrieve a subset of the list using slicing.

>>> sub_list = my_list[1:4]
>>> sub_list
['watermelon', 'snake fruit', 'apple']

more on lists #

The list data type has some more methods. Here are all of the methods of list objects:

list.append(x)

Add an item to the end of the list. Similar to a[len(a):] = [x].

>>> my_list[len(my_list):] = ['guava']
>>> my_list.append('papaya')
>>> my_list
['banana', 'watermelon', 'snake fruit', 'apple', 'durian', 'guava', 'papaya']

list.extend(iterable)

Extend the list by appending all the items from the iterable. Similar to a[len(a):] = iterable.

>>> more_list = ['orange', 'grape', 'kiwi']
>>> more_list2 = ['dragon fruit', 'jackfruit']
>>> my_list[len(my_list):] = more_list
>>> my_list.extend(more_list2)
>>> my_list
['banana', 'watermelon', 'snake fruit', 'apple', 'durian', 'guava', 'papaya', 'orange', 'grape', 'kiwi', 'dragon fruit', 'jackfruit']

list.insert(i, x)

Insert an item at a given position. The first argument is the index of the element before which to insert, so a.insert(0, x) inserts at the front of the list, and a.insert(len(a), x) is equivalent to a.append(x).

>>> my_list.insert(3, 'kasturi')
>>> my_list
['banana', 'watermelon', 'snake fruit', 'kasturi', 'apple', 'durian', 'guava', 'papaya', 'orange', 'grape', 'kiwi', 'dragon fruit', 'jackfruit']

list.remove(x)

Remove the first item from the list whose value is equal to x. It raises a ValueError if there is no such item.

>>> my_list.remove('kasturi')
>>> my_list.remove('lai')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: list.remove(x): x not in list
>>> my_list
['banana', 'watermelon', 'snake fruit', 'apple', 'durian', 'guava', 'papaya', 'orange', 'grape', 'kiwi', 'dragon fruit', 'jackfruit']

list.pop([i])

Remove the item at the given position in the list, and return it. If no index is specified, a.pop() removes and returns the last item in the list. It raises an IndexError if the list is empty or the index is outside the list range.

>>> my_list.pop()
'jackfruit'
>>> my_list
['banana', 'watermelon', 'snake fruit', 'apple', 'durian', 'guava', 'papaya', 'orange', 'grape', 'kiwi', 'dragon fruit']
>>> my_list.pop(2)
'snake fruit'
>>> my_list
['banana', 'watermelon', 'apple', 'durian', 'guava', 'papaya', 'orange', 'grape', 'kiwi', 'dragon fruit']

list.clear()

Remove all items from the list. Similar to del a[:].

>>> del my_list[:]
>>> my_list
[]
>>> my_list = ['banana', 'watermelon', 'snake fruit', 'apple', 'durian']
>>> my_list.clear()
>>> my_list
[]

list.index(x[, start[, end]])

Return zero-based index in the list of the first item whose value is equal to x. Raises a ValueError if there is no such item.

The optional arguments start and end are interpreted as in the slice notation and are used to limit the search to a particular subsequence of the list.

>>> my_list = ['banana', 'watermelon', 'snake fruit', 'apple', 'durian', 'apple']
>>> my_list.index('apple')
3
>>> my_list.index('apple', 4)
5
>>> my_list.index('durian', 0, 5)
4

list.count(x)

Return the number of times x appears in the list.

>>> my_list.count('apple')
2

list.sort(*, key=None, reverse=False)

Sort the items of the list in place.

>>> numbers = [5, 2, 9, 1, 5, 6]
>>> numbers.sort()
>>> numbers
[1, 2, 5, 5, 6, 9]
>>> numbers.sort(reverse=True)
>>> numbers
[9, 6, 5, 5, 2, 1]

list.reverse()

Reverse the elements of the list in place.

>>> numbers = [5, 2, 9, 1, 5, 6]
>>> numbers.reverse()
>>> numbers
[6, 5, 1, 9, 2, 5]

list.copy()

Return a shallow copy of the list. Similar to a[:].

>>> numbers = [5, 2, 9, 1, 5, 6]
>>> numbers1 = numbers[:]
>>> numbers1
[5, 2, 9, 1, 5, 6]
>>> numbers2 = numbers.copy()
>>> numbers2
[5, 2, 9, 1, 5, 6]

using lists as stacks #

The list methods make it very easy to use a list as a stack, where the last element added is the first element retrieved (“last-in, first-out”). To add an item to the top of the stack, use append(). To retrieve an item from the top of the stack, use pop() without an explicit index. For example:

>>> stack = [3, 4, 5]
>>> stack.append(6)
>>> stack.append(7)
>>> stack
[3, 4, 5, 6, 7]
>>> stack.pop()
7
>>> stack
[3, 4, 5, 6]
>>> stack.pop()
6
>>> stack
[3, 4, 5]

using lists as queues #

It is also possible to use a list as a queue, where the first element added is the first element retrieved (“first-in, first-out”); however, lists are not efficient for this purpose. While appends and pops from the end of list are fast, doing inserts or pops from the beginning of a list is slow (because all of the other elements have to be shifted by one).

To implement a queue, use collections.deque which was designed to have fast appends and pops from both ends. For example:

>>> from collections import deque
>>> queue = deque(["Eric", "John", "Michael"])
>>> queue.append("Terry")
>>> queue.append("Graham")
>>> queue
deque(['Eric', 'John', 'Michael', 'Terry', 'Graham'])
>>> queue.popleft()
'Eric'
>>> queue.popleft()
'John'
>>> queue
deque(['Michael', 'Terry', 'Graham'])

list comprehensions #

List comprehensions provide a concise way to create lists. Common applications are to make new lists where each element is the result of some operations applied to each member of another sequence or iterable, or to create a subsequence of those elements that satisfy a certain condition.

>>> squares = []
>>> for x in range(10):
...     squares.append(x**2)
...
>>> squares
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

We can calculate the list of squares without any side effects using:

>>> squares = list(map(lambda x: x**2, range(10)))
>>> squares
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

or, equivalently:

>>> squares = [x**2 for x in range(10)]
>>> squares
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

which is more concise and readable.

>>> [(x, y) for x in [1,2,3] for y in [3,1,4] if x != y]
[(1, 3), (1, 4), (2, 3), (2, 1), (2, 4), (3, 1), (3, 4)]

In the real world, you should prefer built-in functions to complex flow statements. The zip() function would do a great job for this use case:

>>> matrix = [
...     [1, 2, 3, 4],
...     [5, 6, 7, 8],
...     [9, 10, 11, 12],
... ]
>>> list(zip(*matrix))
[(1, 5, 9), (2, 6, 10), (3, 7, 11), (4, 8, 12)]

tuples and sequences #

We saw that lists and strings have many common properties, such as indexing and slicing operations. They are two examples of sequence data types. Since Python is an evolving language, other sequence data types may be added. There is also another standard sequence data type: the tuple.

A tuple consists of a number of values separated by commas, for instance:

>>> t = 12345, 54321, 'hello!'
>>> t[0]
12345
>>> t
(12345, 54321, 'hello!')
>>> # Tuples may be nested:
>>> u = t, (1, 2, 3, 4, 5)
>>> u
((12345, 54321, 'hello!'), (1, 2, 3, 4, 5))
>>> # Tuples are immutable:
>>> t[0] = 88888
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'tuple' object does not support item assignment
>>> # but they can contain mutable objects:
>>> v = ([1, 2, 3], [3, 2, 1])
>>> v
([1, 2, 3], [3, 2, 1])

As you see, on output tuples are always enclosed in parentheses, so that nested tuples are interpreted correctly; they may be input with or without surrounding parentheses, although often parentheses are necessary anyway (if the tuple is part of a larger expression).

Though tuples may seem similar to lists, they are often used in different situations and for different purposes.

Tuples are immutable, and usually contain a heterogeneous sequence of elements that are accessed via unpacking or indexing.

A special problem is the construction of tuples containing 0 or 1 items.

>>> empty = ()
>>> singleton = 'hello', # <-- note trailing comma
>>> len(empty)
0
>>> len(singleton)
1

>>> x, y, z = t
>>> z
'hello!'
>>> x
12345
>>> y
54321

This is called, appropriately enough, sequence unpacking and works for any sequence on the right-hand side.

sets #

Python also includes a data type for sets.

A set is an unordered collection with no duplicate elements.

Basic uses include membership testing and eliminating duplicate entries.

Curly braces or the set() function can be used to create sets.

To create an empty set you have to use set(), not {}; the latter creates an empty dictionary.

>>> basket = {'apple', 'orange', 'apple', 'pear', 'orange', 'banana'}
>>> print(basket)
{'apple', 'pear', 'banana', 'orange'}
>>> 'orange' in basket
True
>>> 'kiwi' in basket
False

Set objects also support mathematical operations like union, intersection, difference, and symmetric difference.

>>> a
{'c', 'b', 'r', 'd', 'a'}
>>> b
{'a', 'z', 'c', 'm', 'l'}
>>> a - b
{'r', 'd', 'b'}
>>> a | b
{'m', 'c', 'b', 'z', 'r', 'd', 'a', 'l'}
>>> a & b
{'c', 'a'}
>>> a ^ b
{'m', 'r', 'd', 'z', 'b', 'l'}

Similarly to list comprehensions, set comprehensions are also supported:

>>> a = {x for x in 'abracadabra' if x not in 'abc'}
>>> a
{'d', 'r'}

dictionaries #

Dictionaries are sometimes found in other languages as “associative memories” or “associative arrays”.

Dictionaries are indexed by keys, which can be any immutable type; strings and numbers can always be keys.

>>> tel = {'jack': 4098, 'sape': 4139}
>>> tel['guido'] = 4127
>>> tel
{'jack': 4098, 'sape': 4139, 'guido': 4127}
>>> tel['jack']
4098
>>> del tel['sape']
>>> tel['irv'] = 4127
>>> tel
{'jack': 4098, 'guido': 4127, 'irv': 4127}
>>> list(tel)
['jack', 'guido', 'irv']
>>> sorted(tel)
['guido', 'irv', 'jack']
>>> 'guido' in tel
True
>>> 'jack' not in tel
False

The dict() constructor builds dictionaries directly from sequences of key-value pairs:

>>> dict([('sape', 4139), ('guido', 4127), ('jack', 4098)])
{'sape': 4139, 'guido': 4127, 'jack': 4098}

In addition, dict comprehensions can be used to create dictionaries from arbitrary key and value expressions:

>>> {x: x**2 for x in (2, 4, 6)}
{2: 4, 4: 16, 6: 36}

When the keys are simple strings, it is sometimes easier to specify pairs using keyword arguments:

>>> dict(sape=4139, guido=4127, jack=4098)
{'sape': 4139, 'guido': 4127, 'jack': 4098}

looping techniques #

When looping through dictionaries, the key and corresponding value can be retrieved at the same time using the items() method.

>>> knights = {'gallahad': 'the pure', 'robin': 'the brave'}
>>> for k, v in knights.items():
...     print(k, v)
...
gallahad the pure
robin the brave

When looping through a sequence, the position index and corresponding value can be retrieved at the same time using the enumerate() function.

>>> for i, v in enumerate(['tic', 'tac', 'toe']):
...     print(i, v)
...
0 tic
1 tac
2 toe

To loop over two or more sequences at the same time, the entries can be paired with the zip() function.

>>> questions = ['name', 'quest', 'favorite color']
>>> answers = ['lancelot', 'the holy grail', 'blue']
>>> for q, a in zip(questions, answers):
...     print('What is your {0}?  It is {1}.'.format(q, a))
...
What is your name?  It is lancelot.
What is your quest?  It is the holy grail.
What is your favorite color?  It is blue.

To loop over a sequence in reverse, first specify the sequence in a forward direction and then call the reversed() function.

>>> for i in reversed(range(1, 10, 2)):
...     print(i)
...
9
7
5
3
1

To loop over a sequence in sorted order, use the sorted() function which returns a new sorted list while leaving the source unaltered.

>>> basket = ['apple', 'orange', 'apple', 'pear', 'orange', 'banana']
>>> for i in sorted(basket):
...     print(i)
...
apple
apple
banana
orange
orange
pear

Using set() on a sequence eliminates duplicate elements.

>>> basket = ['apple', 'orange', 'apple', 'pear', 'orange', 'banana']
>>> for f in sorted(set(basket)):
...     print(f)
...
apple
banana
orange
pear

more on conditions #

It is possible to assign the result of a comparison or other Boolean expression to a variable. For example

>>> string1, string2, string3 = '', 'Trondheim', 'Hammer Dance'
>>> non_null = string1 or string2 or string3
>>> non_null
'Trondheim'

comparing sequences and other types #

Sequence objects typically may be compared to other objects with the same sequence type.

The comparison uses lexicographical ordering:

  • first the first two items are compared, and if they differ this determines the outcome of the comparison;

  • if they are equal, the next two items are compared, and so on, until either sequence is exhausted.

If two items to be compared are themselves sequences of the same type, the lexicographical comparison is carried out recursively.

If all items of two sequences compare equal, the sequences are considered equal.

If one sequence is an initial sub-sequence of the other, the shorter sequence is the smaller (lesser) one.

Lexicographical ordering for strings uses the Unicode code point number to order individual characters.

Some examples of comparisons between sequences of the same type:

>>> (1, 2, 3)              < (1, 2, 4)
True
>>> [1, 2, 3]              < [1, 2, 4]
True
>>> 'ABC' < 'C' < 'Pascal' < 'Python'
True
>>> (1, 2, 3, 4)           < (1, 2, 4)
True
>>> (1, 2)                 < (1, 2, -1)
True
>>> (1, 2, 3)             == (1.0, 2.0, 3.0)
True
>>> (1, 2, ('aa', 'ab'))   < (1, 2, ('abc', 'a'), 4)
True

Note that comparing objects of different types with < or > is legal provided that the objects have appropriate comparison methods.