02-01 Lists

Data Structures

In the previous modules, we learnt about python's built-in 'simple' types. In this module, we will learn about the different ways in which the data of those types can be organized, so that it can be used (algorithmically) efficiently.

we have already covered str, int, float, and complex. Here, we will also introduce the remaining two -- bool and None python's built-in types

Python's most basic data structure is the sequence. Each element of a sequence is assigned a number known as index number. Different types of sequences in Python are:

  • List
  • Tuple
  • Range
  • Text sequence types e.g. str
  • Binary sequence types e.g. bytearray, buffer

Python has several built-in data structures (or compound types) that act as containers and hold the other types. They are:

  • List
  • Tuples
  • Sets
  • Dictionaries

01 - 05 Lists

The list is the most versatile datatype available in Python which can be written as a list of comma-separated values between square brackets. Creating a list is as simple as putting different items separated by comma between square brackets.

Example:

In [1]:
# Notice the mix data types
my_list = ['Python', 'Julia', 1, 3.1415]
print("Contents of my_list: {}.\nType: {}".format(my_list, type(my_list)))
Contents of my_list: ['Python', 'Julia', 1, 3.1415].
Type: <type 'list'>

\n is the escape character for line break

Python is zero-index based, thus to get the first item we simply ask for the item/ element on the 0th index.

In [2]:
my_list[0]
Out[2]:
'Python'

We will now briefly go over the basic list manipulations (which are similar to strings) and then look at some more methods that makes lists unique.

.. 05.01 Slicing the List

A shallow copy of the list is performed and a new list is created containing the requested elements.

Example:

In [3]:
my_list = ['Python', 'Julia', 1, 3.1415]
# Performs shallow copy and returns a **new** list with first two elements
my_list[:2] # [:2] means between start=0 and stop=2 index values (excluding stop)
Out[3]:
['Python', 'Julia']

The slicing can also be done to get the n-th value from a list by passing n as the third argument.

In [4]:
my_list[1::2]
Out[4]:
['Julia', 3.1415]
In [5]:
# Remember, it doesn't include the nth index value when traversing a list.
my_list[-3:-2:1]  # Take every element between index value -3 and -2
Out[5]:
['Julia']

.. 05.02 Updating the List

Unlike strings and tuples which are immutable, elements in list can be changed without having to create a new list, thus making it mutable.

Example:

In [6]:
my_list = ['Python', 'Julia', 1, 3.1415]
my_list[2] = 'Java'
print('Original Contents: \n', my_list)
print('Original Length of array: \n', len(my_list))
# Remove some elements/ changing the size
my_list[2:4] = []
print('Modified Contents: \n', my_list)
print('Modified Length of array: \n', len(my_list))
('Original Contents: \n', ['Python', 'Julia', 'Java', 3.1415])
('Original Length of array: \n', 4)
('Modified Contents: \n', ['Python', 'Julia'])
('Modified Length of array: \n', 2)

.. 05.03 Appending to the List

New items can be easily added to the list by using the append() method.

Example:

In [7]:
my_list = ['Python', 'Julia', 1, 3.1415]
my_list.append('C++') # It will append the item to the end of the list
print(my_list)
['Python', 'Julia', 1, 3.1415, 'C++']

.. 05.04 Copying Lists

There are many ways to create a copy of the lists in python. Lets take a look at few techniques:

using copy package

copy packages is packaged with the python so you don't have to install it externally to use it. So what is the reason of creating a separate package? From our first week's session on variables, we know that it is very easy to create copy of objects,right? We do know one thing for sure that assignment statements ( '=' ) in python do not copy the objects, they merely create bindings between the target and the object, right? It so happens that for collections that are mutable or contains mutable items, a copy is sometimes needed so that one can change the content of the mutable item without changing the other. There are actually two ways of creating a copy of an object viz: shallow copy and deep copy. In shallow copy, python constructs a new object and then inserts references to into it that are found in the original list, whereas deepcopy, as you must've guessed it, creates an object and copies everything. (If you are curious to know more about it, head over the official documentation )

In [8]:
import copy
my_list  = ['Python', 'Julia', 1, 3.1415]
my_list1 = copy.copy(my_list)  # Shallow copy.. Fast
my_list2 = copy.deepcopy(my_list)  # Deep copy.. Slower
using slice
In [9]:
my_list = ['Python', 'Julia', 1, 3.1415]
my_list1 = my_list[:2]
print(my_list1)
['Python', 'Julia']
using list constructor
In [10]:
my_list = ['Python', 'Julia', 1, 3.1415]
# when list method takes a list as a parameter, it creates a copy of that list
my_list1 = list(my_list)
print(my_list1)
['Python', 'Julia', 1, 3.1415]

.. 05.05 Delete List Elements

To remove the list elements, one has two options to either use del statement or lists's remove method ( will be discussed later ).

Example:

In [11]:
my_list = [1, 2, 3, 4, 5]
del(my_list[4])
my_list
Out[11]:
[1, 2, 3, 4]

.. 05.06 Nested Lists

It is also possible to create a list of the lists.

Example:

In [12]:
my_list1 = [1, 2, 3, 4, 5]
my_list2 = ['a', 'b', 'c', 'd', 'e']
my_list3 = [my_list1, my_list2]
my_list3
Out[12]:
[[1, 2, 3, 4, 5], ['a', 'b', 'c', 'd', 'e']]

.. 05.07 List Concatenation, Repetition, Membership:

These are simple list manipulation methods similar to strings. Take a look at following example:

In [13]:
my_list1 = [1, 2, 3, 4, 5]
my_list2 = ['a', 'b', 'c', 'd', 'e']
my_list1 + my_list2  # List Concatenation
Out[13]:
[1, 2, 3, 4, 5, 'a', 'b', 'c', 'd', 'e']
In [14]:
# List Repition
my_list1 * 2
Out[14]:
[1, 2, 3, 4, 5, 1, 2, 3, 4, 5]
In [15]:
# Membership operator, returns true if member of list
3 in my_list1
Out[15]:
True

.. 05.08 Traversing a list:

The most straightforward way to traverse a list is using loops:

We will look at loops in detail in loops module

for loop:

Example:

In [16]:
my_list = [1, 2, 3, 4, 5]
for element in my_list:
    print(element)
1
2
3
4
5

Lets traverse using the index numbers

Example:

In [17]:
for index in range(len(my_list)): # start from 0 and go till the length of the list.
    print("my_list[{}] : {}".format(index, my_list[index]))
my_list[0] : 1
my_list[1] : 2
my_list[2] : 3
my_list[3] : 4
my_list[4] : 5
While loop:

Just like for loop, we can traverse the list based on its index numbers (again, we'll learn about loops in next module):

Example:

In [18]:
index = 0
# till index is less than length of list
while index < len(my_list):
    print("my_list[{}] : {}".format(index, my_list[index]))
    # increment index by 1 at every iteration
    index += 1
my_list[0] : 1
my_list[1] : 2
my_list[2] : 3
my_list[3] : 4
my_list[4] : 5

.. 05.09 enumerate( )

Python has a built-in method called enumerate which returns both index value and value of list ( or any other iterable object).

Example:

In [19]:
for ind, val in enumerate(my_list):
    print("my_list[{}] : {}".format(ind, val))
my_list[0] : 1
my_list[1] : 2
my_list[2] : 3
my_list[3] : 4
my_list[4] : 5

05.10 List Comprehension

List comprehension is a syntactic way of creating a list based on the existing list, just like we did in copying the lists above. The basic structure of the syntax includes a for loop that traverses the list and evaluates a condition using if.. else condition and stores the output of the condition as a new list. Lets take a look at a quick example.

Example:

In [20]:
my_list1 = [elem for elem in my_list if elem % 2 == 0]
print(my_list1)
[2, 4]

We simply create a list my_list1 from the elements in my_list that are completely divisible by 2.

There are many ways in which the list comprehension can be used. It is just a shorthand of writing better readable code.

05.11 Built- in List Functions and Methods:

Python provides following methods for lists:

max:

This method returns the elements from the list with maximum value.

Example:

In [21]:
my_list1 = [1, 2, 3]
max(my_list1)
Out[21]:
3

What do you think will happen if we compare a list of the lists (nested list)?

min:

This method returns the element from the list with minimum value.

In [22]:
min(my_list)
Out[22]:
1
list:

This method takes sequence types and converts them to lists. This is also used to convert a tuple to list.

Example:

In [23]:
my_list = list(('Python', 'Julia', 1, 3.1415))  # iterable as a tuple
my_list
Out[23]:
['Python', 'Julia', 1, 3.1415]

The above line might be a little confusing. list is a built-in function which can either create an empty list if it is called with no parameters, or create a new list of the iterable/ sequence that it is given as an input. That means that list can at most 1 argument. Thus we have to put our elements in a circular bracket (which makes it a tuple, btw) and then pass it as an argument to list method.

list.count(obj):

This method returns the number of times the object, that is passed as a parameter, occurs in the list.

Example:

In [24]:
my_list = ['Python', 'Julia', 1, 3.1415]
my_list.count('Python')
Out[24]:
1
list.extend(seq):

This method appends the contents of a sequence to a list.

Equivalent operation using slicing -- my_list1[len(my_list1):] = my_list2 and print my_list1.

In [25]:
my_list1 = ['Python', 'Julia', 1, 3.1415]
my_list2 = ['C++', 'Java', 2, 2.7182]
my_list1.extend(my_list2)
print(my_list1)
['Python', 'Julia', 1, 3.1415, 'C++', 'Java', 2, 2.7182]
list.index(obj):

This method returns the lowest index in the list that object appears.

In [26]:
my_list = ['Python', 'Julia', 1, 3.1415]
my_list.index('Julia')
Out[26]:
1
list.insert(index, obj):

This method is used to insert the object at the offset index.

In [27]:
my_list = ['Python', 'Julia', 1, 3.1415]
my_list.insert(3, 2.7182)
print(my_list)
['Python', 'Julia', 1, 2.7182, 3.1415]
list.pop(obj = list[-1]):

This method removes and returns the removed object from the list. If you don't pass the argument to the function, it will by default pop the last element from the list

In [28]:
my_list = ['Python', 'Julia', 1, 3.1415]
# pop the last element
my_list.pop(1)
Out[28]:
'Julia'
list.remove(obj):

This method is used to remove the object from the list. The object to be removed should be passed as an argument to the function. Unlike pop, this does not return anything.

In [29]:
my_list = ['Python', 'Julia', 1, 3.1415]
my_list.remove('Julia')
print(my_list)
['Python', 1, 3.1415]
list.reverse():

This method reverses the objects of list in place

In [30]:
my_list = ['Python', 'Julia', 1, 3.1415]
my_list.reverse()
print(my_list)
[3.1415, 1, 'Julia', 'Python']
list.sort([func]):

This method sorts objects of list by using the compare function passed as optional parameter. You can also sort the string in reverse by passing the optional parameter reverse=True

In [31]:
my_list = [7, 6, 1, 9, 2]
my_list.sort()
print("Sorted:         ", my_list)
my_list.sort(reverse=True)
print("Reverse Sorted: ", my_list)
('Sorted:         ', [1, 2, 6, 7, 9])
('Reverse Sorted: ', [9, 7, 6, 2, 1])

.. 05.12 Performance Characteristics:

The list has following performance characteristics:

  • The list object stores pointers to objects, not the actual objects themselves. The size of a list in memory depends on the number of objects in the list, not the size of the objects.
  • The time needed to get or set an individual item is constant, no matter what the size of the list is (also known as “O(1)” behaviour).
  • The time needed to append an item to the list is “amortized constant”; whenever the list needs to allocate more memory, it allocates room for a few items more than it actually needs, to avoid having to reallocate on each call (this assumes that the memory allocator is fast; for huge lists, the allocation overhead may push the behaviour towards O(n\*n)).
  • The time needed to insert an item depends on the size of the list, or more exactly, how many items that are to the right of the inserted item (O(n)). In other words, inserting items at the end is fast, but inserting items at the beginning can be relatively slow, if the list is large.
  • The time needed to remove an item is about the same as the time needed to insert an item at the same location; removing items at the end is fast, removing items at the beginning is slow.
  • The time needed to reverse a list is proportional to the list size (O(n)).
  • The time needed to sort a list varies; the worst case is O(n log n), but typical cases are often a lot better than that.

Related

comments powered by Disqus