Lists in Python PDF

## Lists in Python ### 7.1 Introduction Sequences arise naturally in many real-life situations. A year has 12 months (January, February, March, April, May, June, July, August, September, October, November and December). The months of the year are in a sequence. After January, it will always be Feb...

## Lists in Python ### 7.1 Introduction Sequences arise naturally in many real-life situations. A year has 12 months (January, February, March, April, May, June, July, August, September, October, November and December). The months of the year are in a sequence. After January, it will always be February. It is impossible to jump from March to July because it has to go in a sequence. So, we say a Sequence is an object that contains multiple items of data. The items are stored in a sequence one after the other such as a sequence of events, movements, items, or a sequence in which a player records (music) with a sound recorder/sequencer. Consider the example of a sequence of cars as shown in Fig. 7.1. > *A Sequence of Cars* As is evident from the above figure, there is a sequence of cars and each car becomes an element/item of this particular sequence. Here, we have a grey-colored car, a blue car, a red car and so on. So, all these cars combined together form a sequence. Python also supports sequences which can be considered as containers and in those containers, certain items are stored. A sequence may have repeated items in the list. The number of elements is called the length of the sequence. The various sequences available in Python are shown in Fig. 7.2. > *Sequences in Python* | Lists | Strings | Dictionaries | |---|---|---| | Tuples | Sets | | ### 7.2 List A list is a collection of values or an ordered sequence of values/items. The elements in a list can be of any type such as string, integers, float, objects or even a list. The values that make up a list are called its elements. Elements of a list are enclosed in square brackets [], separated by commas. Lists allow duplicate values as well. The element of the list can be accessed by its index. Lists are mutable, i.e., values in the list can be modified, which means that Python will not create a new list when you make changes to an element of a list. Elements in a list need not be of the same type. In other words, we say that lists are heterogeneous (of multiple types) in nature. Like a string (sequence of characters), list also is a sequenced data type. > *A list is a collection of comma-separated values (items) within square brackets. Items in a list need not be of the same type.* ### 7.2.1 Declaring/Creating/Initializing List Lists can be created by putting comma-separated values/items within square brackets []. Square brackets indicate start and end of the list, consisting of elements separated by a comma. List elements/items are ordered, changeable and can be repeated. Indexes are used to access the items. The syntax for creating a list is: ``` <list_name> = [] ``` For example, ``` L = [] # List Display Construct ``` The above construct is termed as a "List Display Construct". Square brackets in the above syntax contain the set of values/elements constituting the list with the name given as `<list_name>`. This is termed as initialization of the list with a blank or no values or we can say an empty list. A list can be populated with any type of values/collection of items by enclosing inside square brackets [] as shown in the example given below: For example, ``` Fruits = ['Mango', 'Apple', 'Grapes'] ``` > *Learning Tip: Make sure that strings are enclosed in single/double quotes while declaring them as list elements. Python can't differentiate between single or double quotes. So, we can use whatever we want.* In the above example, we have a list of fruits having three items-Mango, Apple, Grapes, separated by commas and enclosed inside square brackets []. Other examples of lists are: **List Types and Examples:** Lists in Python can be broadly classified into three types: 1. Empty Lists 2. Long Lists 3. Nested Lists ### 7.2.2 Accessing List Elements (Indexing) A list consists of any collection of items which is stored according to its index. Like strings, any item in a list can be accessed by using the slice operator[] by specifying its index value. List indices start with 0 (zero) and go to length-1. The list index can be a positive or negative integer value, or an expression which evaluates to an integer value. Hence, indexing in lists can be positive or negative, i.e., you can access the elements from a list either moving from left to right (positive index) or from right to left (negative index). The index of -1 refers to the last item, -2 to the second last item and so on. For example, consider list1 containing 10 elements. ``` list1 = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100] ``` This list in computer memory shall be represented as shown in Fig. 7.5 below: > *Positive and Negative Indexes in a List* | | | | | | | | | | | |---|---|---|---|---|---|---|---|---|---| | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | | 10 | 20 | 30 | 40 | 50 | 60 | 70 | 80 | 90 | 100 | | -10 | -9 | -8 | -7 | -6 | -5 | -4 | -3 | -2 | -1 | | | | | | | | | | | **List** | | | | | | | | | | | **Positive Index** | | | | | | | | | | | **Negative Index** | Each element of the above list can be accessed through their indexes enclosed inside square brackets. ### 7.2.3 Traversing a List Traversing a list means accessing each element of a list. This can be done by using either for or while looping statement. Traversing can be done in the following three ways: 1. **Using 'in' operator inside for loop** The elements of a list can be accessed individually using for loop as follows: > *Traversing the elements of a list* As is evident from the output, in the first iteration, variable 'i' will be assigned the first element, i.e., T, then the second element, 'e', and in this way each letter is accessed and displayed on the Python shell upon execution. Each element is displayed on a new line till all the elements are traversed and displayed. Here, 'in' operator using for loop iterates each element of a list in sequence. 2. **Using range() function** We have already discussed this function in Chapter 6. It checks for the given set of values mentioned as the argument to range() function. This function can be used for accessing individual elements of a list, using indexes of elements only, along with len() method which gives length of the list and specifies how many times for loop will iterate. 3. **Using while loop** The list elements/items in Python can also be iterated or accessed using a while loop. Firstly, the len() function is used to determine the length of the list, then the while loop starts from index 0 and is iterated through the list items by referring to their indexes. Unlike a for loop, it is a must to increase the index by 1 after each iteration as shown in Example 3 given on next page. ### 7.2.4 Aliasing In Python, variables refer to objects. The lists we create in Python are also objects we are referring to. Since lists are mutable, they can be modified. If we assign the elements of one list to another list, both shall refer to the same object. For example, Let us create a list named subjects containing names of four subjects as string type. ``` >>> subjects= ['Hindi', 'English', 'Maths', 'History'] ``` > *Global Frame, Subjects List* | | | | | |---|---|---|---| | 0 | 1 | 2 | 3 | | "Hindi" | "English" | "Maths" | "History" | The elements of subjects list in memory are represented according to their index values. Since the list index always starts with 0, so Hindi is stored at index value 0, English at index 1, Maths at index 2, and History at index 3. Now we will assign it to create a temporary list of the already created list, subjects, by giving the statement as: ``` >>> temporary = subjects ``` > *Global frame, Subjects List, temporary List* | | | | | |---|---|---|---| | 0 | 1 | 2 | 3 | | "Hindi" | "English" | "Maths" | "History" | Now we have two lists having the same set of values. In other words, temporary is an alias (alternate) name for subjects list as assignment with an `=` operator does not make a copy; instead makes both these lists referring to the same location. We can modify the contents of these lists by referring to its individual index value. Suppose we have to modify 'temporary' list by changing the subject 'Hindi' to 'Sanskrit', which is stored at index 0, by giving the command as: ``` >>> temporary [0] = 'Sanskrit' >>> print (temporary) ['Sanskrit', 'English', 'Maths', 'History'] >>> print(subjects) ['Sanskrit', 'English', 'Maths', 'History'] ``` It is evident from the given example that the modifications made in the temporary list are reflected in the subjects (original) list as well since the same list is having two different names. So, we can say that changes made with one alias get reflected in the other alias. Although this behaviour can be useful, yet it is sometimes unexpected or undesirable, so aliasing should be avoided. The above list can be modified and represented with two values at one index position. ``` >>>>> subjectCodes = [['Sanskrit', 43], ['English', 85], ['Maths', 65], >>> subjectCodes [1] ['English', 85] ['History', 36]] >>> print (subjectCodes [1] [0], subjectCodes [1] [1]) English 85 ``` In the above example, the list is represented in two-dimensional manner. Therefore, in order to access their individual element from the nested list, we have to mention the row and column of index value. ### 7.2.5 Comparing Lists Python allows us to compare two lists. Each element is individually compared in lexicographical (alphabetical or dictionary) order. We can apply all the relational operators (>, <, ==, !=, etc.) to compare two lists if they are of comparable types, otherwise Python flashes an error. For example, Consider the following lists, ``` >>> L1,L2 [10,20,30], [10,20,30] >>> L3 [10, [20,30]] #Nested list >>> L1 L2 True >>> L1 == L3 False ``` As shown in the given example, the second statement evaluates to False because L3 is a nested list and L1 is a simple list. Thus, on comparing, it generates False because both lists are different. Further, Python generates the final result of non-equality comparisons as either True/False from corresponding elements' comparison. While comparing two lists, it checks element-by-element comparison. If the corresponding elements are equal, it goes on to the next element and so on, until it finds the element that differs. ### 7.3 Operations un L۱۵۱۵ Python provides us with several basic operations which can be performed on lists as shown in Fig. 7.6. > *List Operations* | Concatenation | Repetition | Membership Testing | Indexing | Slicing | |---|---|---|---|---| Let us discuss some of the important operations using an example: ``` list1 = ['Red', 'Green'] list2 = [10, 20, 30] ``` ### 7.3.1 Concatenation Concatenation or joining is a process in which multiple sequences/lists can be combined together with the help of certain operators. Python allows combining or adding of two lists using `+` concatenation operator (addition operation). We can add two lists using this operator. > *Adding two strings* > *Adding two lists* ``` >>> List1 = [1, 2, 3, 4] >>> List2 = [5, 6, 7, 8] #the + operator concatenates lists: ``` > *Note: '+' operator simply performs a concatenation with list.* ### 7.3.2 Repetition/Replication Multiply (\* asterisk) operator replicates the List for a specified number of times and creates a new list. ``` >>> list2 = [10, 20, 30] >>> list2 * 2 [10, 20, 30, 10, 20, 30] ``` > *Replicating a List* In the above example，list2 is multiplied by 2 and string 'Python' represented as a list is multiplied by 3. Thus, list is printed two times and Python gets printed three times (Fig. 7.7(a)). However, we cannot multiply one list with another as shown in Fig. 7.7(b). ### 7.3.3 Membership Testing Membership testing is an operation carried out to check or test whether a particular element/item is a member of that sequence or not. As you can see in Fig. 7.8(a), the car on the left-hand side does not belong to the sequence of cars, whereas the car on the right-hand side belongs to this sequence. Hence, we say that the left-hand side car is not a member and the right-hand side car is a member of the sequence of cars. > *Membership Testing* Python also allows us to check for membership of individual characters or substrings in strings using 'in' operator. The `in` operator checks whether a given element is contained in a list. It returns True if the element appears in the list, otherwise returns False (Fig. 7.8(b)). > *Membership Operator 'in'* The reverse of `in` is `not in`. `not in` operator returns True if the element does not appear in the list, otherwise returns False (Fig. 7.8(c)). > *Membership Operator 'not in'* > *`in` operator used with for loop* In this method, the membership operator `in` can be used to display the elements of a list through for loop (Fig. 7.8(d)). ### 7.3.4 Indexing Index is nothing but an integer value for each item present in the sequence. So, you have 0th index, 1st index, 2nd index, 3rd index, and so on, depending upon the sequence that you have. In Python, indexing starts from 0 like other programming languages. As shown in the example of sequence of cars in Fig. 7.9(a), we have 8 items in this particular sequence and the index range is from 0 to 7. Thus, lists in Python can have/store different types of elements stored in a particular sequence such as integers, strings, etc. > *Indexing in lists* Similarly, in Python, an index is a number specifying the position of an element in a list. It enables access to individual element in the list. Index of first element in the list is 0, second element is 1, and nth element is n-1. Negative indexes identify positions relative to the end of the list. The index -1 identifies the last element, -2 identifies next to the last element, etc., as shown in Fig. 7.9(b). ### 7.3.5 Slicing Indexing and slicing are two inter-related operations in lists. Slicing is done through indexing. Let us first understand what slicing is. > *Slicing Operation* Slicing is an operation in which we can slice a particular range from a sequence. In the context of Fig. 7.10, imagine you want to access only three cars (starting with blue car) out of eight cars given as a sequence. So, the range to be taken shall be from index 1 – index 4, where index 4 car is to be excluded. Now we will see this operation on lists. List slices are the sub-parts extracted from a list. List slices can be created through the use of indexes. Slicing is used to retrieve a subset of values. A slice of a list is basically its sub-list. While indexing is used to obtain individual items, slicing allows us to obtain a subset of items. When we enter a range that we want to extract, it is called range slicing. The syntax used for slicing is: ``` list[start:stop:step] ``` where `start` is the starting point; `stop` is the stopping point, which is not included; and `step` is the step size-also known as stride—and is optional. Its default value is 1. To take an example, let us consider a list/sequence as `x=['c', 'o', 'm', 'p', 'u', 't', 'e', 'r']`. The various slicing operations performed on this sequence shall generate the following set of items as shown in the table given below: | Code | Result | Explanation | |---|---|---| | `x [1:4]` | `['o', 'm', 'p']` | items 1 to 3 | | `x [1:6:2]` | `['o', 'p', 't']` | items 1, 3, 5 | | `x[3:]` | `['p', 'u', 't', 'e', 'r']` | items 3 to end | | `x[:5]` | `['c', 'o', 'm', 'p', 'u']` | items 0 to 4 | | `x[-1]` | `['r']` | last item | | `x[-3:]` | `['t', 'e', 'r']` | last 3 items | | `x[:-2]` | `['c', 'o', 'm', 'p', 'u', 't']` | all except last 2 items | Let us consider another list, 'list1', with the following values and results after slicing operation: ``` list1 = [100, 50.75, "Radhika", "Shaurya", 900, 897.60] ``` ### 7.4 Nested Lists When a list appears as an element of another list, it is called a nested list, i.e., a list can have one or more lists as its elements. ``` >>> list1= [1,2,'a','c', (6,7,8),4,9] >>> #fifth element of list is also a list >>> list1 (4) [6, 7, 8] ``` To access the element of nested list of list1, we have to specify two indexes >>> list1 [4] [1] `list1[i][j]`. The first index `i` will take us to the desired nested list and the 7 second index `j` will take us to the desired element in that nested list. The output shown above is generated as 7 because index `i` giving the fifth element as 4 is passed as an argument, whereas index `j` giving the second element as 1 is passed as an argument in the nested list. ``` >>> list1=[1,2,3,'a', ['apple', 'green'],5,6,7, ['red', 'orange']] >>> list1 [4] [1] 'green' >>> list1 [6] 6 >>> list1 [8] [0] [2] 'd' >>> list1[4:6] [['apple', 'green'], 5] >>> list1[4]='mango' >>> list1 [1, 2, 3, 'a', 'mango', 5, 6, 7, ['red', 'orange']] >>> listl[-1] ['red', 'orange'] >>> list1 [8] [0]='black' >>> list1 [1, 2, 3, 'a', 'mango', 5, 6, 7, ['black', 'orange']] >>> len (list1) 9 >>> ``` ### 7.5 Copying Lists The simplest way to make a copy of the given list is to assign it to another list. ``` >>> list = [1,2,3] >>> list1.append(10) >>> list1 [1, 2, 3] >>> list2 = listl >>> listl [1, 2, 3, 10] >>> list2 [1, 2, 3, 10] ``` The statement list2 = list1 does not create a new list. Rather, it just makes list1 and list2 refer to the same list object. Here, list2 actually becomes an alias of list1. Therefore, any changes made to either of them will be reflected in the other list. We can also create a copy or clone of the list as a distinct object by three methods. The first method uses slicing, the second method uses built-in function list() and the third method uses copy() function of Python library. **Method 1:** We can slice our original list and store it into a new list variable as follows: ``` newList = oldList[:] >>> list = [1,2,3,4,5] >>> list2 = list1[:) >>> list2 [1, 2, 3, 4, 5] ``` **Method 2:** We can use the list constructor function `list()` as follows: ``` newList = list(oldList) >>> listl [10,20,30,40] >>> list2 list (list1) >>>> list2 [10, 20, 30, 40] ``` Calling it without any arguments will create an empty list. **Method 3:** We can use the `copy()` function as follows: ``` newList = oldList.copy() >>> list1=[1,2,3,4,5] >>> list2-listl.copy() >>>> list2 [1, 2, 3, 4, 5] >>> list1[0]=100 >>> listl [100, 2, 3, 4, 5] >>> list2 [1, 2, 3, 4, 5] >>> list2[2]=300 >>> list2 [1, 2, 300, 4, 5] >>>> list1 [100, 2, 3, 4, 5] ``` The `copy()` function returns a new list stored in a different memory location. It doesn't modify the original list or the modifications made in the new list will not be reflected in the base list. ### 7.6 Built-in Functions (Manipulating Lists) Python offers several built-in 'in-place' functions that can alter the elements of the list rather than creating a new list, such as adding new elements, changing the elements in a list, etc. These functions perform various operations on lists which are described in Fig. 7.11. > *Built-in List operations* | Function | Syntax | |---|---| | append | `List.append(elem)` | | extend | `List.extend(list 2)` | | insert | `List.insert(index,elem)` | | reverse | `List.reverse()` | | index | `List.index(elem)` | | length | `List.len (list 2)` | | sort | `List.sort()` | | clear | `List.clear()` | | count | `List.count(elem)` | | remove | `List.remove (elem)` | #### 7.6.1 append() The append() method adds a single item to the end of the list. It doesn't create a new list; rather it modifies the original list. The single element can also be a list. The syntax of append() method is: ``` Syntax: list.append(item) ``` The `item` can be numbers, strings, another list, dictionary, etc. #### 7.6.2 extend() The extend() method adds one list at the end of another list. In other words, all the items of a list are added at the end of an already created list. ``` Syntax: listl.extend(list2) ``` The list which will be added to list1. →list1 is the primary list which will be extended.) brengs.<<< #### 7.6.3 insert() The insert() function can be used to insert an element/object at a specified index. This function takes two arguments: the index where an item/object is to be inserted and the item/element itself. ``` Syntax: list name.insert(index_number, value) ``` where, - `list_name` is the name of the list - `index number` is the index where the new value is to be inserted - `value` is the new value to be inserted in the list #### 7.6.4 reverse() The reverse() function in Python reverses the order of the elements in a list. This function reverses the item of the list. It replaces a new value "in place" of an item that already exists in the list, i.e., it does not create a new list. #### 7.6.5 index() The index() function in Python returns the index of first matched item from the list. It returns the first occurrence of an item for which the index position is to be searched in the list. If the element is not present, ValueError is generated. #### 7.6.6 Updating List Lists are mutable; you can assign new value to existing value. We can use assignment operator (=) to change an item or a range of items. ``` Syntax: List [index] =<new value> ``` #### 7.6.7 len() The len() function returns the length of the list, i.e., the number of elements in a list. #### 7.6.8 sort() This function sorts the items of the list by default in ascending/increasing order. This modification is done "in place", i.e., it does not create a new list. ``` Syntax: List.sort() ``` #### 7.6.9 clear() The clear() method removes all items from the list. This method doesn't take any parameter. The clear() method only empties the given list. It doesn't return any value. #### 7.6.10 count () The `count()` method counts how many times an element has occurred in a list and returns it. The syntax of `count()` method is: ``` list.count (element) ``` ### 7.7 Deletion Operation Python provides operator for deleting/removing an item from a list. There are many methods for deletion: 1. If the index is known, you can use `pop()` function or `del` statement. 2. If the element is known, not the index, `remove()` can be used. 3. To remove more than one element, `del` with list slice can be used. #### 7.7.1 pop() It removes the element from the specified index and also returns the element which was removed. ``` Syntax: List.pop (index) ``` #### 7.7.2 del Statement The `del` statement removes the specified element from the list but does not return the deleted value. #### 7.7.3 del with slicing #### 7.7.4 remove() The `remove()` function is used when we know the element to be deleted, not the index of the element. ### 7.8 Sorting* Sorting is to arrange the list in an ascending or descending order. Sorting algorithm specifies the way to arrange data in a particular order. The importance of sorting lies in the fact that data searching can be optimized to a very high level if data is stored in a sorted manner. Sorting is also used to represent data in more readable formats. There are various sorting techniques that can be used to sort the list in ascending or descending order. Here we will discuss two techniques: 1. Bubble Sort 2. Insertion Sort #### 7.8.1 Bubble Sort Bubble Sort is one of the simplest sorting techniques where it traverses the whole list by comparing its adjacent elements, sorting them and swapping the elements until the whole list is sorted. **Algorithm:** 1. START 2. Read the array elements and store it in `list a[]`. 3. Store the length in a variable `n`. 4. For `i=0` to `n-1`, repeat steps 5 and 6. 5. For `j=0` to `n-i-1`, repeat step 4. 6. If `a[j] > a[j+1]`, then swap elements. 7. Display the sorted list. 8. END **Steps:** 1. Bubble sort algorithm starts by comparing the first two elements in the list. If and only if the first element is greater than the second, these elements will be swapped. This ensures that the greater of the first two elements is on the second position. In the next step, the second element is compared with the third element, and following the same logic, they are swapped if and only if the second element is greater than the third element. With these two steps, it is ensured that the greatest of the first 3 elements is on the third position. If this process is repeated until the last element, the greatest element will end up on the last position in the list. This completes the first step in Bubble Sort. 2. After the first step gets completed, the largest element in array will get placed in the last position of the list. 3. If there are `n` elements to be sorted, then the process mentioned above should be repeated `n-1` times to get the required result. 4. For performance optimization, in the second step, the last and the second last elements are not compared since this comparison was already done in the previous step, and the last element is already present in its correct position. 5. Similarly, in the third step, second last and third last elements are not compared and so on. Let us see this with the help of an example. **Sorting in ascending order using bubble sort:** Suppose list is `[42, 29, 74, 11, 65, 58]` **First pass** | Original | Result | Comment | |---|---|---| | `[42, 29, 74, 11, 65, 58]` | `[29, 42, 74, 11, 65, 58]` | it will swap since `29<42` | | `[29, 42, 74, 11, 65, 58]` | `[29, 42, 74, 11, 65, 58]` | no swapping as `42<74` | | `[29, 42, 74, 11, 65, 58]` | `[29, 42, 11, 74, 65, 58]` | it will swap since `11<74` | | `[29, 42, 11, 74, 65, 58]` | `[29, 42, 11, 65, 74, 58]` | it will swap since `65<74` | | `[29, 42, 11, 65, 58, 74]` | `[29, 42, 11, 65, 58, 74]` | it will swap since `58<74` | > *The largest element is settled at its correct place, i.e., at the end. So, the first five elements form the unsorted part while the last element forms the sorted part and will be compared for the next pass.* **Second pass** | Original | Result | Comment | |---|---|---| | `[29, 42, 11, 65, 58, 74]` | `[29, 42, 11, 65, 58, 74]` | no swapping as `29<42` | | `[29, 42, 11, 65, 58, 74]` | `[29, 11, 42, 65, 58, 74]` | it will swap since `11<42` | | `[29, 11, 42, 65, 58, 74]` | `[29, 11, 42, 65, 58, 74]` | no swapping as `65>42` | | `[29, 11, 42, 65, 58, 74]` | `[29, 11, 42, 58, 65, 74]` | it will swap since `58<65` | > *The next largest element is settled at its correct place. So, the first four elements form the unsorted part while the last two elements form the sorted part and will be compared for the next pass.* **Third pass** | Original | Result | Comment | |---|---|---| | `[29, 11, 42, 58, 65, 74]` | `[11, 29, 42, 58, 65, 74]` | it will swap since `29>11` | | `[11, 29, 42, 58, 65, 74]` | `[11, 29, 42, 58, 65, 74]` | no swapping as `29<42` | | `[11, 29, 42, 58, 65, 74]` | `[11, 29, 42, 58, 65, 74]` | no swapping as `42<58` | > *The next largest element is settled at its correct place. So, the first three elements form the unsorted part while the last three elements form the sorted part.* **Fourth pass** | Original | Result | Comment | |---|---|---| | `[11, 29, 42, 58, 65, 74]` | `[11, 29, 42, 58, 65, 74]` | no swapping as `29>11` | | `[11, 29, 42, 58, 65, 74]` | `[11, 29, 42, 58, 65, 74]` | no swapping as `42>29` | > *The next largest element is settled at its correct place. So, the first two elements form the unsorted part while the last four elements form the sorted part.* **Fifth pass** | Original | Result | Comment | |---|---|---| | `[11, 29, 42