Data Structures in Python: list()
Tags: python, beginners, algorithms, programming
Published: 2022-02-11 04:50:58

Arrays are one of the most fundamental data structures. Python does not have built-in support for arrays, but python lists can be used instead.

## Characteristics

Python lists have the following characteristics:
1. Lists are ordered. Items in a list have a defined order and the order will not change. Inserted items are placed at the end.
2. List items are changeable. Items can be modified, added or removed.
3. Lists allow duplicates. It can contain the same value multiple times.
4. List items can be accessed using indexes.

## Time Complexities For Different List Methods

| Operation             	| Average Case  	| Amortized Worst Case  	|
|-----------------------	|---------------	|-----------------------	|
|  Copy                 	| O(n)          	| O(n)                  	|
|  Append[1]            	| O(1)          	| O(1)                  	|
|  Pop last             	| O(1)          	| O(1)                  	|
|  Pop intermediate[2]  	| O(n)          	| O(n)                  	|
|  Insert               	| O(n)          	| O(n)                  	|
|  Get Item             	| O(1)          	| O(1)                  	|
|  Set Item             	| O(1)          	| O(1)                  	|
|  Delete Item          	| O(n)          	| O(n)                  	|
|  Iteration            	| O(n)          	| O(n)                  	|
|  Get Slice            	| O(k)          	| O(k)                  	|
|  Del Slice            	| O(n)          	| O(n)                  	|
|  Set Slice            	| O(k+n)        	| O(k+n)                	|
|  Extend[1]            	| O(k)          	| O(k)                  	|
|  Sort                 	| O(n log n)    	| O(n log n)            	|
|  Multiply             	| O(nk)         	| O(nk)                 	|
|  x in s               	| O(n)          	|                       	|
|  min(s), max(s)       	| O(n)          	|                       	|
|  Get Length           	| O(1)          	| O(1)                  	|


Now let's look at the list methods and how to use them:


## append()

This method adds an element at the end of the list.

```python
a = [1, 2, 4, 7]
a.append(8)
print(a)
# Output: [1, 2, 4, 7, 8]
```

## clear()

Removes all the elements from the list.

```python
a = [1, 2, 4, 7]
a.clear()
print(a)
# Output: []
```

## copy()

Returns a copy of the list.

```python
a = [1, 2, 4, 7]
x = a.copy()
print(x)
# Output: [1, 2, 4, 7]
```

## count()

Returns the number of elements with the specified value.

```python
a = [1, 0, 1, 1, 0, 0, 1]
countOnes = a.count(1)
print(countOnes)
# Output: 4
```

## extend()

Add the elements of a list (or any iterable), to the end of the current list. It only takes one argument.

```python
a = [1, 0, 2]
b = ['cat', 'dog', 2]
a.extend(b)
print(a)
# Output: [1, 0, 2, 'cat', 'dog', 2]
```

## index()

Returns the index of the first element with the specified value. If the specified value does not exist in the list, then a **ValueError** is raised.

```python
a = [1, 0, 2, 'cat', 'dog', 2]
k = a.index('cat')
print(k)
# Output: 3
```

## insert()

This method takes a position and a value and inserts the value at the specified position.

```python
a = [1, 0, 2, 'cat', 'dog', 2]
# Insert 'orange' at the index 1
a.insert(1, 'orange')
print(a)
# Output: [1, 'orange', 0, 2, 'cat', 'dog', 2]
```

## pop()

Removes the element at the specified position. If no argument is passed then the last element is removed from the list and returned. 

```python
a = [1, 0, 3, 'cat', 'dog', 2]
x = a.pop()
print(x)
# Output: 2
print(a)
# Output: [1, 0, 3, 'cat', 'dog']
```
But if an index is passed as argument, then the item at that position is removed and returned.

```python
a = [1, 0, 3, 'cat', 'dog', 2]
x = a.pop(3)
print(x)
# Output: cat
print(a)
# Output: [1, 0, 3, 'dog', 2]
```

## remove()

Removes the first item with the specified value. But if the specified value does not exist in the list then a **ValueError** is raised.

```python
a = [1, 0, 7, 'cat', 'dog', 7]
a.remove(7)
print(a)
# Output: [1, 0, 'cat', 'dog', 7]
```

## reverse()

This method reverses the order of the list.

```python
a = [1, 0, 7, 'cat', 'dog', 7]
a.reverse()
print(a)
# Output: [7, 'dog', 'cat', 7, 0, 1]
```

## sort()

This method sorts the list. By default the sorting is done in ascending order (small to large).

```python
a = [1, 0, 7, 3, 5, 7]
a.sort()
print(a)
# Output: [0, 1, 3, 5, 7, 7]
```

The sort() method can accept two arguments `reverse` and `key`.

The `reverse` argument can be `True` or `False`.
`reverse=True` will sort the list in descending order. (large to small)

```python
a = [1, 0, 7, 3, 5, 7]
a.sort(reverse=True)
print(a)
# Output: [7, 7, 5, 3, 1, 0]
```

The `key` argument however, accepts a function. For example, if I have a list of strings and I want to sort them according to their lengths, I can do the following:

```python
a = ['cat', 'mouse', 'hare', 'elephant']
a.sort(key=len)
print(a)
# Output: ['cat', 'hare', 'mouse', 'elephant']
```

However, the next example is more interesting and can help us in a lot of scenarios.

Suppose you have a list of dictionaries. The dictionaries each contain the name and age of a person. You want to sort the dictionaries according to the age values. You can do this:

```python
# This function returns the age value
def myFunc(d):
    return d['age']

a = [
        {'name':'Abu Hurayra', 'age': 23},
        {'name':'Obayed', 'age': 27},
        {'name':'Shariful Islam', 'age': 25},
        {'name':'Khairul Islam', 'age': 14}
]

a.sort(key=myFunc)

print(a)
# Output: [
#    {'name': 'Khairul Islam', 'age': 14}, 
#    {'name': 'Abu Hurayra', 'age': 23}, 
#    {'name': 'Shariful Islam', 'age': 25}, 
#    {'name': 'Obayed', 'age': 27}
#    ]
```


References:
* https://wiki.python.org/moin/TimeComplexity
* https://www.w3schools.com/python/python_ref_list.asp
* https://www.ics.uci.edu/~pattis/ICS-33/lectures/complexitypython.txt