Built-in Data Structures trong Python

Đây là phần đầu tiên trong series Data Structures và Algorithms trong Python

Built-in Data Structures

Vì chúng ta thường xuyên phải xử lý việc thao tác dữ liệu, nên việc tổ chức dữ liệu một cách hiệu quả và có ý nghĩa là điều vô cùng quan trọng.

Python được trang bị nhiều built-in data structures (cấu trúc dữ liệu tích hợp sẵn) để giúp chúng ta xử lý hiệu quả lượng lớn dữ liệu.

Bốn cấu trúc dữ liệu tích hợp chính mà Python cung cấp là:

• List
• Tuple
• Dictionary
• Set

List

List là một trong những cấu trúc dữ liệu phổ biến và linh hoạt nhất trong Python. Nó cho phép chúng ta lưu trữ các phần tử có kiểu dữ liệu khác nhau trong một vùng chứa. Nội dung của một list được đặt bên trong dấu ngoặc vuông [], và các phần tử được phân tách bởi dấu phẩy ,.

Đặc điểm của List:

• Ordered: Các phần tử được lưu trữ tuyến tính tại một index cụ thể, chúng có một thứ tự nhất định. Khi bạn thêm các phần tử vào list, chúng sẽ được lưu trữ theo thứ tự mà bạn đã thêm vào.
• Có thể thay đổi (Mutable): Bạn có thể thay đổi, thêm, hoặc xóa các phần tử trong list sau khi nó đã được tạo ra.
• Cho phép các giá trị trùng lặp: List có thể chứa các phần tử giống nhau.

Tạo một list

Bạn có thể tạo một list đơn giản như sau:

# Tạo một list với các kiểu dữ liệu khác nhau
mixed_list = [1, "Hello", 3.14, True]

Sử dụng hàm range() để tạo một list:

Hàm range() trong Python được sử dụng để tạo ra một dãy số theo một quy tắc nhất định, range(start, stop, step).

# Tạo list từ 0 đến 9
numbers = list(range(10))
print(numbers)  # Output: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

# Tạo list từ 5 đến 9
numbers = list(range(5, 10))
print(numbers)  # Output: [5, 6, 7, 8, 9]

# Tạo list từ 0 đến 9 với bước nhảy là 2
numbers = list(range(0, 10, 2))
print(numbers)  # Output: [0, 2, 4, 6, 8]

# Tạo list từ 10 đến 1 với bước nhảy là -1
numbers = list(range(10, 0, -1))
print(numbers)  # Output: [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

Truy cập các phần tử trong List:

fruits = ["apple", "banana", "watermelon", "cherry"]

# Truy cập phần tử đầu tiên
print(fruits[0])  # Output: apple

# Truy cập phần tử thứ hai
print(fruits[1])  # Output: banana

# Truy cập phần tử cuối cùng
print(fruits[-1])  # Output: cherry

Thêm, xóa và thay đổi phần tử trong List:

Thêm phần tử

Bạn có thể thêm phần tử vào cuối list bằng phương thức append() hoặc thêm phần tử vào vị trí cụ thể bằng insert().

fruits = ["apple", "banana", "cherry"]

# Thêm phần tử vào cuối list
fruits.append("orange")

# Thêm phần tử vào vị trí thứ hai
fruits.insert(1, "mango")

print(fruits)  # Output: ['apple', 'mango', 'banana', 'cherry', 'orange']

Xóa phần tử

Bạn có thể xóa một phần tử bằng remove(), pop(), hoặc del.

fruits = ["apple", "banana", "cherry"]

# Xóa phần tử cụ thể
fruits.remove("banana") # Output: ['apple', 'cherry']

# Xóa phần tử cuối cùng
last_fruit = fruits.pop() # Output: ['apple']

# Xóa phần tử theo index
del fruits[0]

print(fruits)  # Output: []

Thay đổi phần tử

Bạn có thể thay đổi giá trị của phần tử bằng cách truy cập trực tiếp vào index của nó.

fruits = ["apple", "banana", "cherry"]

# Thay đổi giá trị của phần tử thứ hai
fruits[1] = "blueberry"

print(fruits)  # Output: ['apple', 'blueberry', 'cherry']

Một số phương thức hữu ích khác cho List:

• sort(): Sắp xếp các phần tử trong list.
• reverse(): Đảo ngược thứ tự các phần tử trong list.
• len(): Trả về số lượng các phần tử trong list.
• index(): Trả về chỉ số của phần tử đầu tiên khớp với giá trị được chỉ định.

numbers = [3, 1, 4, 1, 5, 9]

# Sắp xếp list
numbers.sort()
print(numbers)  # Output: [1, 1, 3, 4, 5, 9]

# Đảo ngược list
numbers.reverse()
print(numbers)  # Output: [9, 5, 4, 3, 1, 1]

# Độ dài của list
print(len(numbers))  # Output: 6

# Index của phần tử đầu tiên có giá trị 4
print(numbers.index(4))  # Output: 2

List sclicing

numbers = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

# Lấy các phần tử từ index 2 đến index 5 (không bao gồm index 5)
subset = numbers[2:5]
print(subset)  # Output: [2, 3, 4]

# Lấy các phần tử từ đầu đến index 4 (không bao gồm index 4)
start_slice = numbers[:4]
print(start_slice)  # Output: [0, 1, 2, 3]

# Lấy các phần tử từ index 5 đến hết list
end_slice = numbers[5:]
print(end_slice)  # Output: [5, 6, 7, 8, 9]

# Lấy các phần tử từ index 1 đến index 7 với step (bước nhảy) là 2
step_slice = numbers[1:8:2]
print(step_slice)  # Output: [1, 3, 5, 7]

# Đảo ngược list
reversed_list = numbers[::-1]
print(reversed_list)  # Output: [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

# Sao chép toàn bộ list
copied_list = numbers[:]
print(copied_list)  # Output: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

# Lấy 3 phần tử cuối cùng
last_three = numbers[-3:]
print(last_three)  # Output: [7, 8, 9]

List Comprehension

List Comprehension là một cách ngắn và gọn gàng để tạo ra các list mới từ các list hiện có bằng cách sử dụng cú pháp đơn giản kết hợp giữa vòng lặp for và điều kiện if

Cú pháp của list comprehension như sau:

new_list = [expression for item in iterable if condition]

• expression: Biểu thức được áp dụng lên từng phần tử.
• item: Từng phần tử trong iterable (list, tuple, string, v.v.).
• condition (tuỳ chọn): Điều kiện để chọn các phần tử đưa vào list mới.

Tạo một list mới từ một list hiện có

numbers = [1, 2, 3, 4, 5]
squares = [x**2 for x in numbers]

print(squares)  # Output: [1, 4, 9, 16, 25]

Sử dụng if-else trong List Comprehension

numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
evens = [x for x in numbers if x % 2 == 0]

print(evens)  # Output: [2, 4, 6, 8, 10]

numbers = [1, 2, 3, 4, 5]
results = [x*2 if x % 2 == 0 else x*3 for x in numbers]

print(results)  # Output: [3, 4, 9, 8, 15]

List comprehension dùng với nhiều list

list1 = [30, 50, 110, 40, 15, 75]
list2 = [10, 60, 20, 50]

sum_list = [(n1, n2) for n1 in list1 for n2 in list2 if n1 + n2 > 100]

print(sum_list) # Output: [(50, 60), (110, 10), (110, 60), (110, 20), (110, 50), (75, 60), (75, 50)]

Tuple

Tuple thì gần giống như list, ngoại trừ việc tuple là immutable (không thể thay đổi). Điều này có nghĩa là sau khi ta tạo một tuple, ta không thể thay đổi, thêm, hoặc xóa các phần tử bên trong nó. Tuy nhiên, nó có thể chứa các phần tử có thể thay đổi (mutable elements) như một list.

Nội dung của tuple được đặt bên trong dấu ngoặc đơn () và các phần tử được phân tách bởi dấu phẩy ,.

Tạo một tuple

# Tạo một tuple rỗng
empty_tuple = ()

# Tạo một tuple với nhiều phần tử
my_tuple = (1, 2, 3, "Hello", True)

Python cũng cho phép ta tạo tuple mà không cần dấu ngoặc đơn, chỉ cần sử dụng dấu phẩy:

my_tuple = 1, 2, 3, "Hello", True

Truy cập các phần tử trong Tuple

my_tuple = (1, 2, 3, "Hello", True)

# Truy cập phần tử đầu tiên
print(my_tuple[0])  # Output: 1

# Truy cập phần tử cuối cùng
print(my_tuple[-1])  # Output: True

Merging tuples

Tuples có thể được merged bằng cách sử dụng toán tử +.

hero1 = ("Batman", "Wonder Woman")
hero2 = ("Wonder Woman", "Diana Prince")
awesome_team = hero1 + hero2
print(awesome_team) # Output: ('Batman', 'Wonder Woman', 'Wonder Woman', 'Diana Prince')

Nested Tuples

nested_tuple = (1, 2, (3, 4), 5)

# Truy cập phần tử bên trong tuple lồng nhau
print(nested_tuple[2][1])  # Output: 4

Một ví dụ khác về nested tuples:

hero1 = ("Batman", "Bruce Wayne")
hero2 = ("Wonder Woman", "Diana Prince")
awesome_team = (hero1, hero2)
print(awesome_team) # Output: (('Batman', 'Bruce Wayne'), ('Wonder Woman', 'Diana Prince'))

Một số thao tác với Tuple

Tìm kiếm

Chúng ta có thể kiểm tra xem một phần tử có tồn tại trong một tuple hay không bằng cách sử dụng toán tử in như sau:

cities = ("London", "Paris", "Los Angeles", "Tokyo")
print("Moscow" in cities) # Output: False

Hàm index() có thể cung cấp cho chúng ta index của một giá trị cụ thể:

cities = ("London", "Paris", "Los Angeles", "Tokyo")
print(cities.index("Tokyo")) # Output: 3

Slicing tuple

Tương tự như với list

my_tuple = (1, 2, 3, 4, 5)
slice_tuple = my_tuple[1:4]
print(slice_tuple)  # Output: (2, 3, 4)

Vậy tại sao cần tuple khi đã có list?

• Immutable: Tính không thể thay đổi giúp tuple an toàn hơn khi ta cần lưu trữ các giá trị không muốn bị thay đổi sau khi tạo ra.
• Hiệu suất: Tuple thường có hiệu suất tốt hơn list trong các tình huống không cần thay đổi dữ liệu.
• Tuple có thể làm key cho dictionary: Do tính immutable, tuple có thể được sử dụng làm key trong dictionary (trong khi list thì không).

Ví dụ về sử dụng tuple làm key trong dictionary:

# Tạo dictionary với khóa là tuple (tọa độ) và giá trị là tên thành phố
cities = {
    (40.7128, -74.0060): "New York",
    (34.0522, -118.2437): "Los Angeles",
    (51.5074, -0.1278): "London",
    (48.8566, 2.3522): "Paris"
}

# Truy cập tên thành phố dựa trên tọa độ
location = (40.7128, -74.0060)
city_name = cities[location]
print(f"Thành phố tại tọa độ {location} là {city_name}")
# Output: Thành phố tại tọa độ (40.7128, -74.0060) là New York

Tham khảo thêm

Dictionary

So với list hoặc tuple, dictionary có cấu trúc phức tạp hơn một chút.

Dictionary trong Python là một cấu trúc dữ liệu cho phép ta lưu trữ các cặp key-value (khóa-giá trị). Mỗi khóa là duy nhất và được sử dụng để truy xuất giá trị tương ứng. Dictionary là một kiểu dữ liệu mutable, có nghĩa là ta có thể thay đổi nội dung của nó sau khi tạo.

Trong Python, nội dung của dictionary được đặt bên trong dấu ngoặc nhọn {}, và mỗi cặp key-value được phân tách bởi dấu hai chấm :. Các cặp key-value được phân tách bởi dấu phẩy ,.

Trong các phiên bản Python trước 3.6, dictionary là unordered. Kể từ Python 3.7, các dictionary trở nên ordered theo mặc định. Ta sẽ xem ví dụ ngay dưới đây

Tạo một dictionary

empty_dict = {}  # Dictionary rỗng
print(empty_dict) # {}

Python version 3

films = {"The Gentlemen": 2019,
            "The Terminal List": 2022,
            "Guy Ritchie's The Covenant": 2023}
print(films) # {'The Terminal List': 2022, "Guy Ritchie's The Covenant": 2023, 'The Gentlemen': 2019}

Python version 3.9.6

films = {"The Gentlemen": 2019,
            "The Terminal List": 2022,
            "Guy Ritchie's The Covenant": 2023}
print(films) # {'The Gentlemen': 2019, 'The Terminal List': 2022, "Guy Ritchie's The Covenant": 2023}

dict() Constructor

Như tên gọi, dict() constructor có thể được sử dụng để tạo ra một dictionary.

Nếu các khóa (keys) của chúng ta là các chuỗi đơn giản không có ký tự đặc biệt, chúng ta có thể tạo các item trong dictionary trực tiếp trong constructor. Trong trường hợp này, giá trị sẽ được gán cho các khóa bằng cách sử dụng toán tử =.

Việc sử dụng dict() có thể làm cho code của ta ngắn gọn và dễ đọc hơn trong một số trường hợp nhất định.

Refactor các ví dụ ở trên:

Thay vì viết:

empty_dict = {}

Có thể viết lại như sau:

empty_dict = dict()

Thay vì viết:

phone_book = {
    'John': 123456789,
    'Alice': 987654321,
    'Bob': 456789123
}

Ta có thể viết lại thành:

phone_book = dict(John=123456789, Alice=987654321, Bob=456789123)

Truy cập giá trị trong Dictionary

Đối với nhiều người, đây là điểm mà dictionary có ưu thế hơn so với list hoặc tuple. Vì không có các chỉ mục tuyến tính (linear indices), chúng ta không cần phải theo dõi vị trí lưu trữ của các giá trị.

Thay vào đó, chúng ta có thể truy cập một giá trị của dict theo cú pháp [key]. Điều này có ý nghĩa hơn so với việc sử dụng các chỉ số nguyên (integer indices) mà chúng ta sử dụng cho tuples và lists.

Ngoài ra, chúng ta cũng có thể sử dụng phương thức get() để truy cập giá trị như sau:

# Ví dụ về việc truy cập giá trị bằng key trong dictionary
phone_book = {'John': 123456789, 'Alice': 987654321, 'Bob': 456789123}

# Truy cập giá trị bằng dấu ngoặc vuông []
john_number = phone_book['John']
print(john_number)  # Output: 123456789

# Truy cập giá trị bằng phương thức get()
alice_number = phone_book.get('Alice')
print(alice_number)  # Output: 987654321

Lợi ích của việc sử dụng get():

An toàn hơn khi key không tồn tại: Khi sử dụng dấu ngoặc vuông [] để truy cập một giá trị mà key không tồn tại trong dictionary, Python sẽ phát sinh lỗi KeyError. Tuy nhiên, với phương thức get(), nếu key không tồn tại, thay vì phát sinh lỗi, Python sẽ trả về None hoặc một giá trị mặc định mà ta có thể xác định.

Ví dụ

# Sử dụng dấu ngoặc vuông có thể gây lỗi nếu key không tồn tại
try:
  non_existent = phone_book['Michael']  # KeyError nếu 'Michael' không có trong dictionary
except KeyError:
  print("Key không tồn tại")

# Sử dụng get() để tránh lỗi
non_existent = phone_book.get('Michael')
print(non_existent)  # Output: None (không gây lỗi)

# Trả về giá trị mặc định khi key không tồn tại
non_existent_with_default = phone_book.get('Michael', 'Không tìm thấy')
print(non_existent_with_default)  # Output: Không tìm thấy

Dictionary Operations

Thêm/Cập nhật

# Tạo một dictionary
phone_book = {'John': 123456789, 'Alice': 987654321}

# Thêm item mới
phone_book['Bob'] = 456789123
print(phone_book)  # Output: {'John': 123456789, 'Alice': 987654321, 'Bob': 456789123}

# Cập nhật item hiện có
phone_book['Alice'] = 111111111
print(phone_book)  # Output: {'John': 123456789, 'Alice': 111111111, 'Bob': 456789123}

Xóa

• Dùng del: Xóa một mục bằng cách chỉ định key.
• Dùng pop(): Xóa một mục và trả về giá trị của mục đó.
• Dùng popitem(): Xóa và trả về cặp key-value cuối cùng trong dictionary.
• Dùng clear(): Xóa tất cả các mục trong dictionary.

# Xóa item bằng del
del phone_book['John']
print(phone_book)  # Output: {'Alice': 111111111, 'Bob': 456789123}

# Xóa item bằng pop()
bob_number = phone_book.pop('Bob')
print(bob_number)  # Output: 456789123
print(phone_book)  # Output: {'Alice': 111111111}

# Xóa và trả về item cuối cùng bằng popitem()
last_item = phone_book.popitem()
print(last_item)  # Output: ('Alice', 111111111)
print(phone_book)  # Output: {}

# Xóa tất cả các item bằng clear()
phone_book.clear()
print(phone_book)  # Output: {}

Độ dài của một Dictionary

phone_book = {'John': 123456789, 'Alice': 111111111, 'Bob': 456789123}
length = len(phone_book)
print(length)  # Output: 3

Kiểm tra Sự Tồn tại của Key

Ta có thể kiểm tra xem một key có tồn tại trong dictionary hay không bằng cách sử dụng từ khóa in:

if 'Alice' in phone_book:
    print("Alice có trong danh bạ")
else:
    print("Alice không có trong danh bạ")

# Output: Alice có trong danh bạ

Sao chép nội dung

# Sao chép bằng copy()
phone_book_copy = phone_book.copy()
print(phone_book_copy) # Output: {'John': 123456789, 'Alice': 111111111, 'Bob': 456789123}

# Sao chép bằng dict()
phone_book_copy_2 = dict(phone_book)
print(phone_book_copy_2) # Output: {'John': 123456789, 'Alice': 111111111, 'Bob': 456789123}

Dictionary Comprehension

Dictionary Comprehension là một cách ngắn gọn và mạnh mẽ để tạo dictionary mới từ một iterable (như list, tuple, hay một dictionary khác). Cú pháp của nó tương tự như List Comprehension nhưng kết quả là một dictionary.

# Tạo dictionary với các số và bình phương của chúng
squares = {x: x**2 for x in range(6)}
print(squares)  # Output: {0: 0, 1: 1, 2: 4, 3: 9, 4: 16, 5: 25}

# Dictionary Comprehension từ một dictionary có sẵn
phone_book = {'John': 123456789, 'Alice': 111111111, 'Bob': 456789123}
filtered_phone_book = {k: v for k, v in phone_book.items() if v != 111111111}
print(filtered_phone_book)  # Output: {'John': 123456789, 'Bob': 456789123}

Set

Set trong Python là một cấu trúc dữ liệu được sử dụng để lưu trữ một tập hợp các phần tử mà mỗi phần tử là duy nhất và không có thứ tự (unordered).

Ta có thể tạo một set bằng cách đặt các phần tử vào trong dấu ngoặc nhọn {}, hoặc sử dụng hàm set().

Tạo một set

# Tạo một set rỗng
empty_set = set()
print(empty_set)  # Output: set()

# Tạo một set
random_set = {"Educative", 1408, 3.142, (True, False)}
print(random_set) # Output: {1408, (True, False), 3.142, 'Educative'}

# Tạo một set từ một chuỗi, các ký tự sẽ là các phần tử trong set
char_set = set("hello")
print(char_set)  # Output: {'h', 'e', 'l', 'o'}

Các thao tác cơ bản với Set

Thêm phần tử vào Set

my_set = {1, 2, 3}
my_set.add(4)
print(my_set)  # Output: {1, 2, 3, 4}

Xóa phần tử khỏi Set

Ta có thể xóa một phần tử khỏi set bằng cách sử dụng remove() hoặc discard():

• remove() sẽ phát sinh lỗi nếu phần tử không tồn tại trong set.
• discard() sẽ không phát sinh lỗi nếu phần tử không tồn tại.

my_set = {1, 2, 3, 4}
my_set.remove(2)
print(my_set)  # Output: {1, 3, 4}

my_set.discard(5)  # Không phát sinh lỗi mặc dù 5 không có trong set
print(my_set)  # Output: {1, 3, 4}

Kiểm tra sự tồn tại của phần tử trong Set

Ta có thể sử dụng toán tử in để kiểm tra xem một phần tử có tồn tại trong set hay không.

my_set = {1, 2, 3}
print(2 in my_set)  # Output: True
print(5 in my_set)  # Output: False

Các phép toán trên tập hợp

Union

Tạo một set mới chứa tất cả các phần tử từ cả hai set.

set1 = {1, 2, 3}
set2 = {3, 4, 5}
union_set = set1.union(set2)
print(union_set)  # Output: {1, 2, 3, 4, 5}

Intersection

Tạo một set mới chứa các phần tử có trong cả hai set.

intersection_set = set1.intersection(set2)
print(intersection_set)  # Output: {3}

Difference

Tạo một set mới chứa các phần tử có trong set đầu tiên nhưng không có trong set thứ hai.

difference_set = set1.difference(set2)
print(difference_set)  # Output: {1, 2}

Symmetric Difference

Tạo một set mới chứa các phần tử có trong set này hoặc set kia nhưng không có trong cả hai set.

symmetric_difference_set = set1.symmetric_difference(set2)
print(symmetric_difference_set)  # Output: {1, 2, 4, 5}

Ứng dụng của Set

Loại bỏ các phần tử trùng lặp

Set rất hữu ích khi ta cần loại bỏ các phần tử trùng lặp từ một danh sách.

my_list = [1, 2, 2, 3, 4, 4, 5]
unique_set = set(my_list)
print(unique_set)  # Output: {1, 2, 3, 4, 5}

Thực hiện các phép toán tập hợp

Như đã đề cập, set cho phép ta dễ dàng thực hiện các phép toán tập hợp như hợp, giao, hiệu, hiệu đối xứng.

Tóm tắt

List

Đặc điểm: List là một cấu trúc dữ liệu có thứ tự (ordered), có thể thay đổi (mutable), và cho phép các phần tử trùng lặp.

Tuple

Đặc điểm: Tuple là một cấu trúc dữ liệu có thứ tự (ordered) nhưng không thể thay đổi (immutable), và cũng cho phép các phần tử trùng lặp.

Dictionary

Đặc điểm: Dictionary là một cấu trúc dữ liệu không có thứ tự (unordered) trong các phiên bản Python trước 3.7, và có thứ tự (ordered) từ Python 3.7 trở đi. Dictionary có thể thay đổi (mutable) và lưu trữ các cặp key-value (khóa-giá trị), trong đó các key là duy nhất.

Set

Đặc điểm: Set là một cấu trúc dữ liệu không có thứ tự (unordered) và không chứa các phần tử trùng lặp. Set có thể thay đổi (mutable).