One of the fundamental data structures in Python is the list. A list is a mutable sequence of elements that can be of any type, and it allows you to store and manipulate data efficiently.
In this blog post, we will take a closer look at Python lists, their properties, and some common use cases.
Creating Lists
To create a list in Python, you can use square brackets and separate each element with a comma. For example, to create a list of integers, you can use the following code:
numbers = [1, 2, 3, 4, 5]
You can also create a list of strings:
names = ['Sachin', 'Virat', 'Rohit', 'Ramesh']
Lists can also contain elements of different types:
mixed = [1, 'Sachin', True, 3.14]
Accessing Elements
You can access elements in a list by their index, which starts at 0. For example, to access the first element of the list numbers
, you can use the following code:
first_number = numbers[0]
You can also access elements from the end of the list by using negative indices. For example, to access the last element of the list numbers
, you can use the following code:
last_number = numbers[-1]
Slicing Lists
You can also slice a list to create a new list that contains a subset of the elements. To slice a list, you can use the colon :
operator. For example, to create a new list that contains the first three elements of the list numbers
, you can use the following code:
first_three_numbers = numbers[0:3]
This will create a new list [1, 2, 3]
. You can also omit the starting or ending index to slice from the beginning or to the end of the list, respectively. For example, to create a new list that contains the last three elements of the list numbers
, you can use the following code:
last_three_numbers = numbers[-3:]
This will create a new list [3, 4, 5]
.
Modifying Lists
Lists are mutable, which means that you can modify them by adding, removing, or changing elements. To add an element to a list, you can use the append
method. For example, to add the number 6 to the end of the list numbers
, you can use the following code:
numbers.append(6)
To insert an element at a specific position in a list, you can use the insert
method. For example, to insert the number 0 at the beginning of the list numbers
, you can use the following code:
numbers.insert(0, 0)
To remove an element from a list, you can use the remove
method. For example, to remove the number 3 from the list numbers
, you can use the following code:
numbers.remove(3)
To remove the last element of a list, you can use the pop
method. For example, to remove the number 6 from the end of the list numbers
, you can use the following code:
numbers.pop()
List Methods
Here are some of the most commonly used methods:
len()
: This method returns the number of elements in a list.
numbers = [1, 2, 3, 4, 5]
print(len(numbers)) # Output: 5
index()
: This method returns the index of the first occurrence of a specified element in a list.
fruits = ['apple', 'banana', 'orange', 'banana']
print(fruits.index('banana')) # Output: 1
count()
: This method returns the number of times a specified element appears in a list.
fruits = ['apple', 'banana', 'orange', 'banana']
print(fruits.count('banana')) # Output: 2
sort()
: This method sorts the elements in a list in ascending order by default.
numbers = [4, 2, 5, 1, 3]
numbers.sort()
print(numbers) # Output: [1, 2, 3, 4, 5]
You can also specify the reverse argument to sort the list in descending order:
numbers = [4, 2, 5, 1, 3]
numbers.sort(reverse=True)
print(numbers) # Output: [5, 4, 3, 2, 1]
reverse()
: This method reverses the order of the elements in a list.
numbers = [1, 2, 3, 4, 5]
numbers.reverse() # or numbers[::-1]
print(numbers) # Output: [5, 4, 3, 2, 1]
extend()
: This method adds the elements of one list to another list.
fruits = ['apple', 'banana', 'orange']
more_fruits = ['grape', 'pineapple']
fruits.extend(more_fruits)
print(fruits) # Output: ['apple', 'banana', 'orange', 'grape', 'pineapple']
copy()
: This method creates a shallow copy of a list.
numbers = [1, 2, 3, 4, 5]
numbers_copy = numbers.copy()
print(numbers_copy) # Output: [1, 2, 3, 4, 5]
It’s important to note that copy()
creates a new list object, but the elements inside the list still refer to the same objects as the original list.
List Comprehension
List comprehension is a concise way of creating a new list in Python by iterating over an existing iterable object, such as a list, string, or tuple, and applying a condition to filter or transform its elements.
The basic syntax of a list comprehension is:
new_list = [expression for item in iterable if condition]
Here, expression
is an operation performed on each item
in the iterable
that will be included in the new list. The if
condition is optional and can be used to filter out elements that do not meet a certain condition.
For example, let’s say we have a list of numbers and we want to create a new list that contains only the even numbers:
numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
even_numbers = [num for num in numbers if num % 2 == 0]
print(even_numbers) # Output: [2, 4, 6, 8, 10]
In this example, we use a list comprehension to iterate over the numbers
list and only include the elements that satisfy the condition num % 2 == 0
, which checks if the number is even.
List comprehension can also be used to transform the elements of an iterable object. For example, let’s say we have a list of names and we want to create a new list that contains the lengths of each name:
names = ['Sachin', 'Virat', 'Rohit', 'Ramesh']
name_lengths = [len(name) for name in names]
print(name_lengths) # Output: [6, 5, 5, 6]
In this example, we use a list comprehension to iterate over the names
list and apply the len()
function to each name, resulting in a new list that contains the lengths of each name.
List comprehension can be a powerful tool for writing concise and efficient code, especially when dealing with large datasets. However, it’s important to use it judiciously and not sacrifice readability for brevity.
Time complexities
Here are some of the most commonly used methods and their time complexities:
Method | Time Complexity |
---|---|
append() |
This method adds an element to the end of a list. The time complexity is O(1) on average, but it can be O(n) in the worst case if the list needs to be resized. |
extend() |
This method adds the elements of one list to another list. The time complexity is O(k), where k is the length of the list being added. |
insert() |
This method inserts an element at a specified index. The time complexity is O(n) in the worst case because all the elements after the index need to be shifted one position to the right. |
remove() |
This method removes the first occurrence of a specified element from a list. The time complexity is O(n) in the worst case because all the elements after the removed element need to be shifted one position to the left. |
pop() |
This method removes and returns the last element from a list. The time complexity is O(1). |
index() |
This method returns the index of the first occurrence of a specified element in a list. The time complexity is O(n) in the worst case because all the elements need to be checked until the specified element is found. |
sort() |
This method sorts the elements in a list. The time complexity is O(n log n) in the average case, but it can be O(n^2) in the worst case for certain input patterns. |
reverse() |
This method reverses the order of the elements in a list. The time complexity is O(n). |
Example
Implementation of Depth First Search (DFS) using List in Python.
Time complexity of the following implementation is O(V+E)
, where V is the number of vertices and E is the number of edges in the graph.
from typing import List, Dict
def dfs(graph: Dict[str, List[str]], start: str) -> None:
"""Performs depth-first search on a graph starting from a given node.
This function does not return anything, but prints out the nodes visited during the search.
Args:
graph: A dictionary representing the graph, where each key is a node and its value is a list of its neighbors.
start: The node to start the search from.
"""
# create a visited set to keep track of visited nodes
visited = set()
# create a stack using a list
stack = [start]
# mark the start node as visited
visited.add(start)
while stack:
# get the next node from the top of the stack
node = stack.pop() # O(1) constant complexity in removing element from the last or most recent.
print(node, end="\n")
# iterate over the neighbors of the current node
for neighbor in graph[node]:
# if the neighbor has not been visited, add it to the stack and mark it as visited
if neighbor not in visited:
stack.append(neighbor) # O(1) constant complexity
visited.add(neighbor)
if __name__ == "__main__":
# example graph represented as an adjacency list
graph = {'A': ['B', 'C'], 'B': ['D', 'E'], 'C': ['F'], 'D': [], 'E': ['F'], 'F': []}
# run DFS starting from node 'A'
dfs(graph, 'A')