Skip to content

Latest commit

 

History

History
549 lines (412 loc) · 24.5 KB

05-02-DataStructure(list).md

File metadata and controls

549 lines (412 loc) · 24.5 KB

Lists in Python:

Lists in Python are versatile data structures that store collections of elements. With their ability to hold heterogeneous data types and support dynamic resizing, lists are fundamental for various programming tasks.

Creating a List:

  • Lists in Python are created by enclosing comma-separated values within square brackets [ ] and list() constructor.

    • Using Square Brackets: The most common method is to enclose comma-separated values within square brackets [ ].

      my_list = [1, 2, 3, 4, 5]

    • Using the list() Constructor: You can use the list() constructor to create a list from another iterable object like a tuple, string, or range.

      my_tuple = (1, 2, 3)
converted_list = list(my_tuple)
      empty_list = list()
print(empty_list)

    Lists can contain elements of different data types, including integers, strings, or even other lists.

  • In the example:

    • my_list contains integers [1, 2, 3, 4, 5].
    • fruits contains strings ['apple', 'banana', 'cherry'].
    • empty_list is an empty list [].
# Create a list of integers
my_list = [1, 2, 3, 4, 5]

# Create a list of strings
fruits = ['apple', 'banana', 'cherry']

# Create an empty list
empty_list = []

Accessing Elements:

  • Elements in a list are accessed using square bracket notation [ ] with the index of the element.
  • Indexing in Python starts from 0, so the first element is at index 0.
  • Negative indices count from the end of the list.
  • In the example:
    • my_list[0] accesses the first element 1.
    • fruits[1] accesses the second element 'banana'.
    • my_list[-1] accesses the last element 5.
# Access elements by index
print(my_list[0])  # Output: 1
print(fruits[1])   # Output: banana

# Negative indexing (counting from the end)
print(my_list[-1])  # Output: 5

Negative indexing

Negative indexing in Python allows you to access elements of a sequence (such as a list, tuple, or string) from the end rather than from the beginning. It provides a convenient way to access elements relative to the end of the sequence.

Here's a deeper explanation of negative indexing:

  1. Counting from the End:

    • Negative indices count backward from the end of the sequence.
    • Index -1 refers to the last element, -2 refers to the second-to-last element, and so on.

    Example:

    my_list = [10, 20, 30, 40, 50]
print(my_list[-1])  # Output: 50 (last element)
print(my_list[-2])  # Output: 40 (second-to-last element)

  2. Convenient Access:

    • Negative indexing provides a concise way to access elements at the end of a sequence without needing to know its length.
    • This is particularly useful when the length of the sequence is unknown or variable.

  3. Looping Backwards:

    • Negative indexing can be useful when iterating over a sequence in reverse.
    • By combining negative indexing with a loop, you can iterate over a sequence from end to beginning.

    Example: Looping Backwards:

    for i in range(-1, -len(my_list) - 1, -1):
    print(my_list[i])

  4. Handling Boundary Cases:

    • Negative indices allow easy access to the last element of a sequence, which is otherwise cumbersome to obtain using positive indices, especially when the length of the sequence is unknown.

  5. Common Pitfalls:

    • Be cautious when using large negative indices, as they may cause IndexError if they exceed the length of the sequence.
    • Negative indices can also make code less readable if used excessively or inappropriately.

Understanding negative indexing enables you to work more effectively with sequences in Python, especially when dealing with elements relative to the end of the sequence. It provides a convenient and concise way to access elements without needing to know the length of the sequence in advance.

Slicing:

  • Slicing allows you to create a sublist by specifying start and end indices.
  • The start index is inclusive, while the end index is exclusive.
  • Omitting the start index implies starting from the beginning, and omitting the end index implies ending at the end of the list.
  • In the example:
    • my_list[1:4] creates a sublist [2, 3, 4].
    • fruits[:2] creates a sublist ['apple', 'banana'].
    • fruits[1:] creates a sublist ['banana', 'cherry'].
# Slice the list to get a subset of elements
print(my_list[1:4])  # Output: [2, 3, 4]

# Omitting start and end indices
print(fruits[:2])   # Output: ['apple', 'banana']
print(fruits[1:])   # Output: ['banana', 'cherry']

Modifying Elements:

  • List elements can be modified by assigning a new value to a specific index.
  • Elements can be added to the end of a list using the append() method.
  • In the example:
    • my_list[2] = 10 modifies the third element to 10.
    • fruits.append('orange') adds 'orange' to the end of the fruits list.
# Modify elements by index
my_list[2] = 10
print(my_list)  # Output: [1, 2, 10, 4, 5]

# Append elements to the end
fruits.append('orange')
print(fruits)   # Output: ['apple', 'banana', 'cherry', 'orange']

List Length:

  • The len() function returns the number of elements in a list.
  • In the example:
    • len(my_list) returns 5.
    • len(fruits) returns 4.
# Get the length of the list
print(len(my_list))   # Output: 5
print(len(fruits))    # Output: 4

Removing Elements:

  • Elements can be removed by value using the remove() method or by index using the del statement.
  • In the example:
    • fruits.remove('banana') removes 'banana' from the fruits list.
    • del my_list[0] removes the first element from my_list.
# Remove an element by value
fruits.remove('banana')
print(fruits)   # Output: ['apple', 'cherry']

# Remove an element by index
del my_list[0]
print(my_list)  # Output: [2, 10, 4, 5]

Iterating Through a List:

  • You can iterate through a list using a for loop to access each element sequentially.
  • In the example, the for loop iterates through the fruits list, printing each fruit on a new line.
# Iterate through the list using a for loop
for fruit in fruits:
    print(fruit)
# Output:
# apple
# cherry

List Concatenation and Repetition:

  • Lists can be concatenated using the + operator or repeated using the * operator.
  • In the example:
    • combined_list contains elements from my_list and [6, 7, 8].
    • repeated_list contains two repetitions of the fruits list.
# Concatenate two lists
combined_list = my_list + [6, 7, 8]
print(combined_list)  # Output: [2, 10, 4, 5, 6, 7, 8]

# Repeat a list
repeated_list = fruits * 2
print(repeated_list)  # Output: ['apple', 'cherry', 'apple', 'cherry']

Checking for Membership:

  • The in operator checks if an element is present in a list, returning True if found and False otherwise.
  • In the example:
    • 'apple' in fruits returns True.
    • 10 in my_list returns True.
# Check if an element is in the list
print('apple' in fruits)  # Output: True
print(10 in my_list)       # Output: True

List Comprehension:

  • List comprehension provides a concise way to create lists based on existing lists.
  • It consists of an expression followed by a for loop inside square brackets.
  • In the example, squared_numbers contains the squares of numbers from 1 to 5.
# Generate a new list using list comprehension
squared_numbers = [x ** 2 for x in range(1, 6)]
print(squared_numbers)  # Output: [1, 4, 9, 16, 25]

Nested lists in Python:

Nested lists in Python refer to lists that contain other lists as elements. This concept allows for the creation of multidimensional arrays or matrices. Accessing elements in nested lists involves using multiple index values to navigate through the levels of nesting.

1. Creating Nested Lists:

  • Nested lists can be created by including lists as elements within another list.
  • Elements of nested lists can be of any data type, including other lists.
  • Example: 
    nested_list = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]

2. Accessing Elements in Nested Lists:

  • To access an element in a nested list, you use multiple index values, separated by square brackets [ ].
  • The first index specifies the row, and the second index specifies the column (for 2D nested lists).
  • Example: 
    print(nested_list[0][1])  # Output: 2

3. Iterating Over Nested Lists:

  • Nested loops are typically used to iterate over elements in nested lists.
  • Outer loops iterate over rows, and inner loops iterate over columns.
  • Example: 
    for row in nested_list:
    for element in row:
        print(element, end=' ')
    print()  # Move to the next line for the next row

4. Modifying Elements in Nested Lists:

  • Elements in nested lists can be modified using the same indexing syntax as for accessing elements.
  • Example: 
    nested_list[1][2] = 10

5. Length of Nested Lists:

  • The len() function returns the number of rows in a nested list.
  • To find the length of a specific row, you can use the len() function again on that row.
  • Example: 
    print(len(nested_list))  # Output: 3 (number of rows)
print(len(nested_list[0]))  # Output: 3 (length of the first row)

6. Flatten a Nested List:

  • To convert a nested list into a flat list (single-dimensional), you can use list comprehension or itertools module.
  • Example using list comprehension: 
    flat_list = [item for sublist in nested_list for item in sublist]

Nested lists are versatile data structures that allow for representing and manipulating structured data in Python. Understanding how to create, access, modify, and iterate over nested lists is essential for working with multidimensional data and implementing algorithms that require nested structures.

Common methods:

These methods provide powerful functionality for manipulating and working with Python lists, allowing you to add, remove, modify, and search for elements efficiently.

Method Name Description Example
append() Adds an element to the end of the list. my_list.append(10)
extend() Extends the list by appending elements from an iterable. my_list.extend([6, 7, 8])
insert() Inserts an element at the specified position. my_list.insert(2, 20)
remove() Removes the first occurrence of a specified value. my_list.remove(10)
pop() Removes and returns the element at the specified position. removed_element = my_list.pop(2)
clear() Removes all elements from the list. my_list.clear()
index() Returns the index of the first occurrence of a value. index = my_list.index(20)
count() Returns the number of occurrences of a value in the list. count = my_list.count(10)
sort() Sorts the list in ascending order. my_list.sort()
reverse() Reverses the order of elements in the list. my_list.reverse()
copy() Returns a shallow copy of the list. new_list = my_list.copy()
__getitem__() Returns the element at the specified index. element = my_list[2]
__setitem__() Sets the value of the element at the specified index. my_list[2] = 30
__delitem__() Deletes the element at the specified index. del my_list[2]
__contains__() Checks if a value is present in the list. if 20 in my_list:

Important: In Python, copying a list involves creating a new list that contains the same elements as the original list. However, there are different approaches to copying lists, each with its own implications. One common distinction is between shallow copy and deep copy.

1. Shallow Copy:

  • A shallow copy creates a new list object, but it does not recursively copy the elements within the list.
  • Instead, it copies references to the objects stored in the original list. If the objects are mutable, changes to them will affect both the original and copied lists.
  • Shallow copy can be performed using the copy() method or the slice notation [:].

Example of Shallow Copy:

original_list = [[1, 2], [3, 4]]
copied_list = original_list.copy()

# Modify an element in the copied list
copied_list[0][0] = 10

print(original_list)  # Output: [[10, 2], [3, 4]]

2. Deep Copy:

  • A deep copy creates a new list object and recursively copies all objects contained within the original list.
  • This ensures that changes to objects in the copied list do not affect the original list, as they reference distinct objects.
  • Deep copy can be performed using the deepcopy() function from the copy module.

Example of Deep Copy:

import copy

original_list = [[1, 2], [3, 4]]
deep_copied_list = copy.deepcopy(original_list)

# Modify an element in the deep copied list
deep_copied_list[0][0] = 10

print(original_list)  # Output: [[1, 2], [3, 4]]

3. Other Methods for Copying Lists:

  • Besides copy() and deepcopy(), there are other methods for copying lists in Python:
    • Using list slicing: new_list = old_list[:]
    • Using the list() constructor: new_list = list(old_list)
  • These methods create shallow copies, similar to the copy() method, and their behavior is equivalent.

4. Choosing the Right Copy Method:

  • When working with simple lists containing immutable objects, shallow copy methods like copy() or list slicing are usually sufficient and more efficient.
  • For nested lists or lists containing mutable objects, deep copy may be necessary to ensure independent copies.
  • Carefully consider the nature of the data in your list and the desired behavior before choosing a copy method.

Understanding the distinction between shallow copy and deep copy, as well as the various methods available for copying lists, allows you to make informed decisions when working with lists in Python and avoid unexpected behavior or unintended side effects.

Example:

import copy

# Original list
original_list = [1, 2, [3, 4], 5, {'a': 6, 'b': 7}]

# 1. Accessing elements
print("Element at index 2:", original_list[2])  # Output: [3, 4]

# 2. Modifying elements
original_list[0] = 10
print("Modified list:", original_list)  # Output: [10, 2, [3, 4], 5, {'a': 6, 'b': 7}]

# 3. Appending elements
original_list.append(8)
print("Appended list:", original_list)  # Output: [10, 2, [3, 4], 5, {'a': 6, 'b': 7}, 8]

# 4. Inserting elements
original_list.insert(2, 'inserted')
print("Inserted list:", original_list)  # Output: [10, 2, 'inserted', [3, 4], 5, {'a': 6, 'b': 7}, 8]

# 5. Removing elements
original_list.remove('inserted')
print("Removed list:", original_list)  # Output: [10, 2, [3, 4], 5, {'a': 6, 'b': 7}, 8]

# 6. Deleting elements
del original_list[3]
print("List after deleting element at index 3:", original_list)  # Output: [10, 2, [3, 4], {'a': 6, 'b': 7}, 8]

# 7. Slicing
sliced_list = original_list[1:4]
print("Sliced list:", sliced_list)  # Output: [2, [3, 4], {'a': 6, 'b': 7}]

# 8. Copying lists
shallow_copied_list = original_list.copy()
deep_copied_list = copy.deepcopy(original_list)

# Modify an element in the original list
original_list[0] = 20

print("Shallow copied list after modifying original:", shallow_copied_list)
# Output: [10, 2, [3, 4], {'a': 6, 'b': 7}, 8]

print("Deep copied list after modifying original:", deep_copied_list)
# Output: [10, 2, [3, 4], {'a': 6, 'b': 7}, 8]

# 9. Sorting and reversing
numbers = [4, 2, 1, 3]
numbers.sort()
print("Sorted list:", numbers)  # Output: [1, 2, 3, 4]

numbers.reverse()
print("Reversed list:", numbers)  # Output: [4, 3, 2, 1]

# 10. Checking for membership
if 2 in original_list:
    print("2 is present in the original list")

# 11. List comprehension
squared_numbers = [x ** 2 for x in range(1, 5)]
print("Squared numbers:", squared_numbers)  # Output: [1, 4, 9, 16]

This example demonstrates various operations on lists, including accessing, modifying, appending, inserting, removing, deleting, slicing, copying, sorting, reversing, checking for membership, and using list comprehension. It covers a wide range of features and functionalities of Python lists.

Optional Reading Topics

Here are some key points to consider to using lists in Python:

1. Performance Considerations:

  • Lists in Python are implemented as dynamic arrays, allowing for fast access to elements by index.
  • Appending elements to the end of a list has amortized constant-time complexity (O(1)), but occasionally may require resizing the underlying array, which has a time complexity of O(n) where n is the current size of the list.
  • Inserting or deleting elements at arbitrary positions within a list has a time complexity of O(n) since it may involve shifting elements.
  • Accessing elements by index or slicing has constant-time complexity (O(1)).
  • Iterating over a list using a for loop has linear-time complexity (O(n)), where n is the number of elements in the list.

2. Common Techniques for Lists:

  • List Comprehension: List comprehension offers a concise and efficient way to create lists based on existing lists or other iterables. 
    squares = [x ** 2 for x in range(1, 6)]
  • Slice Assignment: Slice assignment allows you to replace or modify multiple elements in a list with a single assignment statement. 
    my_list[1:3] = [10, 20]
  • Sorting Lists: Python's built-in sort() method and the sorted() function are efficient ways to sort lists in ascending or descending order. 
    my_list.sort()
sorted_list = sorted(my_list)
  • Reversing Lists: The reverse() method can reverse the elements of a list in place, while the reversed() function returns an iterator that yields the elements in reverse order. 
    my_list.reverse()
reversed_list = list(reversed(my_list))
  • Copying Lists: Use caution when copying lists. Assignment (list2 = list1) creates a shallow copy, while slicing (list2 = list1[:]) or using the copy() method (list2 = list1.copy()) creates a new list with a separate memory allocation.

3. Performance Optimization Techniques:

  • Use Built-in Functions: Python's built-in functions and methods for list manipulation are optimized for performance and should be preferred over manual implementations.
  • Avoid Excessive Resizing: When possible, preallocate lists to their expected size to minimize the need for resizing during append operations.
  • Consider Alternative Data Structures: For specific use cases where performance is critical, consider using alternative data structures such as arrays (from the array module) or collections like deque or numpy arrays, which offer specialized performance characteristics for certain operations.

Memory allocation for lists in Python involves several considerations, including the initial allocation of memory when creating a list, resizing the underlying array as needed, and managing memory usage efficiently. Let's delve into these aspects with a detailed example:

4. Initial Memory Allocation:

  • When you create a new list in Python, an initial amount of memory is allocated to accommodate a small number of elements.
  • The initial size of this memory allocation depends on factors such as the system architecture and Python implementation.
  • For example, on a 64-bit system running CPython, the initial allocation might reserve space for 4 or 8 elements, depending on the size of the individual elements.

5. Resizing the Underlying Array:

  • As you append elements to the list, Python dynamically resizes the underlying array to accommodate the growing number of elements.
  • When the number of elements exceeds the current capacity of the array, Python allocates a new, larger array and copies the existing elements to the new array.
  • This resizing process incurs a performance overhead, particularly for large lists, as it involves allocating new memory and copying existing data.

6. Example: Memory Allocation in Lists:

# Create an empty list
my_list = []

# Append elements to the list
for i in range(10):
    my_list.append(i)

# Print the current capacity of the list
print("Initial Capacity:", len(my_list))

# Append more elements to trigger resizing
for i in range(10, 20):
    my_list.append(i)

# Print the new capacity of the list after resizing
print("Final Capacity:", len(my_list))

In this example:

  • Initially, the list my_list is empty, and memory is allocated for a small number of elements.
  • As elements are appended to the list, the underlying array grows dynamically to accommodate the increasing number of elements.
  • When the number of elements exceeds the initial capacity, Python resizes the array by allocating a larger memory block and copying the existing elements.

7. Memory Management Efficiency:

  • Python's memory management system employs techniques such as garbage collection and memory pooling to optimize memory usage and minimize memory fragmentation.
  • Efficient memory management is crucial for maintaining performance and preventing memory leaks, particularly in long-running applications or when dealing with large data sets.

In Python, lists are mutable data structures, meaning their elements can be modified after the list is created. This mutability is a fundamental characteristic of lists and distinguishes them from immutable data structures like tuples.

8. Mutable Nature of Lists:

  • Lists allow for in-place modifications, such as appending, inserting, deleting, or modifying elements.
  • You can change the value of an element at a specific index, reorder elements, or even change the length of the list dynamically.

Example: Mutability of Lists:

my_list = [1, 2, 3, 4, 5]

# Modify an element
my_list[2] = 10

# Append new elements
my_list.append(6)

# Delete an element
del my_list[0]

print(my_list)  # Output: [2, 10, 4, 5, 6]

9. Why Lists are Mutable:

  • Lists in Python are implemented as dynamic arrays, which can be resized and modified in place.
  • When you modify a list, you are actually modifying the contents of the underlying array, rather than creating a new list or copying the entire data structure.
  • This mutable behavior provides flexibility and efficiency, especially when dealing with large lists or when performing operations that involve modifying elements.

10. Immutability vs. Mutability:

  • Immutable data structures, like tuples or strings, cannot be modified after they are created. Any operation that appears to modify them actually creates a new object.
  • In contrast, mutable data structures, like lists, allow for direct modification of their elements without creating new objects, which can lead to better performance and memory efficiency in certain scenarios.

11. Performance Implications:

  • Mutability can lead to more efficient memory usage and faster operations when working with large data sets, as it avoids the overhead of creating new objects for every modification.
  • However, mutable data structures require careful handling to avoid unintended side effects, particularly in concurrent or multithreaded environments where multiple threads may attempt to modify the same object simultaneously.