\documentclass[12pt]{article}

\title{Python: Data Structures}

\author{FOSSEE}

\usepackage{listings}

\lstset{language=Python,

    basicstyle=\ttfamily,

commentstyle=\itshape\bfseries, 

showstringspaces=false

}

\newcommand{\typ}[1]{\lstinline{#1}}

\usepackage[english]{babel}

\usepackage[latin1]{inputenc}

\usepackage{times}

\usepackage[T1]{fontenc}

\usepackage{ae,aecompl}

\usepackage{mathpazo,courier,euler}

\usepackage[scaled=.95]{helvet}

\begin{document}

\date{}

\vspace{-1in}

\begin{center}

\LARGE{Python: Data Structures}\\

\large{FOSSEE}

\end{center}

\section{Basic Looping}

\subsection{\typ{while}}

  \begin{lstlisting}

In []: a, b = 0, 1

In []: while b < 10:  

  ...:     print b,

  ...:     a, b = b, a + b # Fibonacci Sequence

  ...:

\end{lstlisting}

Basic syntax of \typ{while} loop is:

\begin{lstlisting}

while condition:

    statement1

    statement2

\end{lstlisting}

All statements are executed, till the condition statement evaluates to True.

\subsection{\typ{for} and \typ{range}}

\typ{range(start, stop, step)}\\

returns a list containing an arithmetic progression of integers.\\

Of the arguments mentioned above, both start and step are optional.\\

For example, if we skip third argument, i.e \typ{step}, default is taken as 1. So:

\begin{lstlisting}

In []: range(1,10)

Out[]: [1, 2, 3, 4, 5, 6, 7, 8, 9]

\end{lstlisting}

\textbf{Note:} stop value is not included in the list.\\

Similarly if we don't pass \typ{first} argument (in this case \typ{start}), default is taken to be 0.

\begin{lstlisting}

In []: range(10)

Out[]: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

\end{lstlisting}

In case third argument is mentioned(\typ{step}), the jump between consecutive members of the list would be equal to that.

\begin{lstlisting}

In []: range(1,10,2)

Out[]: [1, 3, 5, 7, 9]

\end{lstlisting}

%Notice the jump between two consecutive elements is 2, i.e step.\\

\typ{for} and \typ{range}\\

As mentioned previously \typ{for} in Python is used to iterate through the list members. So \typ{for} and \typ{range} can be used together to iterate through required series. For example to get square of all numbers less then 5 and greater then equal to 0, code can be written as:

\begin{lstlisting}

In []: for i in range(5):

 ....:     print i, i * i

 ....:

 ....:

0 0

1 1

2 4

3 9

4 16

\end{lstlisting}

\section{list}

\begin{lstlisting}

In []: num = [1, 2, 3, 4] # Initializing a list

In []: num

Out[]: [1, 2, 3, 4]

\end{lstlisting}

\subsection{Accessing individual elements}

\begin{lstlisting}

In []: num[1]

Out[]: 2  

\end{lstlisting}

\textbf{Note:} Index of list starts from 0.

\begin{lstlisting}

In []: num[5]  # ERROR: throws a index error

IndexError: list index out of range

In []: num[-1]

Out[]: 4

\end{lstlisting}

\textbf{Note: }\typ{-1} points to last element in a list. Similarly to access third last element of a list one can use: 

\begin{lstlisting}

In []: num[-3]

Out[]: 2  

\end{lstlisting}

\subsection{\typ{list} operations}

\begin{lstlisting}

In []: num += [9, 10, 11] # Concatenating two lists

In []: num

Out[]: [1, 2, 3, 4, 9, 10, 11]

\end{lstlisting}

\typ{list} provides \typ{append} function to append objects at the end. 

\begin{lstlisting}

In []: num = [1, 2, 3, 4] 

In []: num.append(-2) 

In []: num

Out[]: [1, 2, 3, 4, -2]

\end{lstlisting}

%% In []: num += [-5] 

%% In []: num

%% Out[]: [1, 2, 3, 4, -2, -5]

Working of \typ{append} is different from \typ{+} operator on list. Till here both will behave as same. But in following case:

\begin{lstlisting}

In []: num = [1, 2, 3, 4]

In []: num + [9, 10, 11]

Out[]: [1, 2, 3, 4, 9, 10, 11]

In []: num.append([9, 10, 11]) # appending a list to a list

In []: num

Out[]: [1, 2, 3, 4, [9, 10, 11]] # last element is a list

\end{lstlisting}

when one attempts to append a list(in above case [9, 10, 11]) to a list(num) it adds list as a single element. So the resulting list will have a element which itself is a list. But \typ{+} operator would simply add the elements of second list.\\

\subsection{Miscellaneous}

\begin{lstlisting}

In []: num = [1, 2, 3, 4]

In []: num.extend([5, 6, 7])  # extend list by adding elements

In []: num

Out[]: [1, 2, 3, 4, 5, 6, 7]

In []: num.reverse()  # reverse the current list

In []: num

Out[]: [7, 6, 5, 4, 3, 2, 1]

In []: num.remove(6) # removing first occurrence of 6

In []: num

Out[]: [7, 5, 4, 3, 2, 1]

In []: len(num) # returns the length of list

Out[]: 6

In []: a = [1, 5, 3, 7, -2, 4]

In []: min(a) # returns smallest item in a list.

Out[]: -2

In []: max(a) # returns largest item in a list.

Out[]: 7

\end{lstlisting}

\subsection{Slicing} 

General syntax for getting slice out of a list is \\

\typ{list[initial:final:step]}

\begin{lstlisting}

In []: a = [1, 2, 3, 4, 5]

In []: a[1:-1:2] 

Out[]: [2, 4]

\end{lstlisting}

Start slice from second element(1), till the last element(-1) with step size of 2.

\begin{lstlisting}

In []: a[::2]

Out[]: [1, 3, 5]

\end{lstlisting}

Start from beginning(since \typ{initial} is blank), till last(this time last element is included, as \typ{final} is blank), with step size of 2.\\

Apart from using \typ{reverse} command on list, one can also use slicing in special way to get reverse of a list.

\begin{lstlisting}

In []: a[-1:-4:-1]

Out[]: [5, 4, 3]

\end{lstlisting}

Above syntax of slice can be expressed as, ``start from last element(\typ{-1}), go till fourth last element(\typ{-4}), with step size \typ{-1}, which implies, go in reverse direction. That is, first element would be \typ{a[-1]}, second element would be \typ{a[-2]} and so on and so forth.''\\

So to get reverse of whole list one can write following slice syntax:

\begin{lstlisting}

In []: a[-1::-1]

Out[]: [5, 4, 3, 2, 1]

\end{lstlisting}

Since \typ{final} is left blank, it will traverse through whole list in reverse manner.\\

\textbf{Note:} While \typ{reverse} reverses the original list, slicing will just result in a instance list with reverse of original, which can be used and worked upon independently.

%%Should we include  list copy concept here?

\subsection{Containership}

\typ{in} keyword is used to check for containership of any element in a given list.

\begin{lstlisting}

In []: a = [2, 5, 4, 6, 9]

In []: 4 in a

Out[]: True

In []: b = 15

In []: b in a

Out[]: False

\end{lstlisting}

\section{Tuples}

Tuples are sequences just like Lists, but they are \textbf{immutable}, or items/elements cannot be changed in any way.

\begin{lstlisting}

In []: t = (1, 2, 3, 4, 5, 6, 7, 8) 

\end{lstlisting}

\textbf{Note:} For tuples we use parentheses in place of square brackets, rest is same as lists.

\begin{lstlisting}

In []: t[0] + t[3] + t[-1] # elements are accessed via indices

Out[]: 13

In []: t[4] = 7 # ERROR: tuples are immutable

\end{lstlisting}

\textbf{Note:} elements cant be changed!

\section{Dictionaries}

Dictionaries are data structures that provide key-value mappings. They are similar to lists except that instead of the values having integer indexes, they have keys or strings as indexes.\\

A simple dictionary can be created by:

\begin{lstlisting}

In []: player = {'Mat': 134,'Inn': 233,

          'Runs': 10823, 'Avg': 52.53}

\end{lstlisting}

For above case, value on left of ':' is key and value on right is corresponding value. To retrieve value related to key 'Avg'

\begin{lstlisting}

In []: player['Avg']

Out[]: 52.530000000000001

\end{lstlisting}

\subsection{Element operations}

\begin{lstlisting}

In []: player['Name'] = 'Rahul Dravid' #Adds new key-value pair.

In []: player

Out[]: 

{'Avg': 52.530000000000001,

 'Inn': 233,

 'Mat': 134,

 'Name': 'Rahul Dravid',

 'Runs': 10823}

In []: player.pop('Mat') # removing particular key-value pair

Out[]: 134

In [21]: player

Out[21]: {'Avg': 52.530000000000001, 'Inn': 233, 

          'Name': 'Rahul Dravid', 'Runs': 10823}

\end{lstlisting}

\begin{lstlisting}

In []: player['Name'] = 'Dravid'

In []: player

Out[23]: {'Avg': 52.530000000000001, 'Inn': 233, 

          'Name': 'Dravid', 'Runs': 10823}

\end{lstlisting}

\textbf{Note:} Duplicate keys are overwritten!

\subsection{containership}

\begin{lstlisting}

In []: 'Inn' in player

Out[]: True

In []: 'Econ' in player

Out[]: False

\end{lstlisting}

\textbf{Note:} Containership is always checked on 'keys' of dictionary, never on 'values'.\\

\subsection{Methods}

\begin{lstlisting}

In []: player.keys() # returns list of all keys

Out[]: ['Runs', 'Inn', 'Avg', 'Mat']

In []: player.values() # returns list of all values.

Out[]: [10823, 233, 

        52.530000000000001, 134]  

\end{lstlisting}

\section{Sets}

are an unordered collection of unique elements.\\

Creation:

\begin{lstlisting}

In []: s = set([2,4,7,8,5]) # creating a basic set

In []: s

Out[]: set([2, 4, 5, 7, 8])

In []: g = set([2, 4, 5, 7, 4, 0, 5])

In []: g

Out[]: set([0, 2, 4, 5, 7]) # No repetition allowed.

\end{lstlisting}

Some other operations which can be performed on sets are:

\begin{lstlisting}

In []: f = set([1,2,3,5,8])

In []: p = set([2,3,5,7])

In []: f | p # Union of two sets

Out[]: set([1, 2, 3, 5, 7, 8])

In []: f & p # Intersection of two sets

Out[]: set([2, 3, 5])

In []: f - p # Elements in f not is p

Out[]: set([1, 8])

In []: f ^ p # (f - p) | (p - f)

Out[]: set([1, 7, 8])) 

In []: set([2,3]) < p # Test for subset

Out[]: True

\end{lstlisting}

\end{document}