Python 101: Python data structures such as `list`, `dict`, `set`, and others

Python data structures such as list, dict, set, and others.

1. List (列表)

哈希表中的数组类比 (Array Analogy):

A list in Python is similar to the array component in the hash table structure. Like an array, Python’s list provides indexed access to elements.

• List Internal Structure:

  • Python’s list is implemented as a dynamic array. This means when you add elements to the list and it exceeds the current allocated space, the list dynamically resizes itself, typically by doubling its size.
  • Each element is stored in a contiguous block of memory, allowing for O(1) time complexity when accessing elements by index.

• Usage:

  • Lists are great for storing ordered collections of items where fast indexed access is needed.
  • However, insertion and deletion operations that require shifting elements have a time complexity of O(n) in the worst case.

Code Example:

# Create a list
my_list = [1, 2, 3, 4]

# Accessing elements by index is O(1)
print(my_list[2])  # Output: 3

# Inserting at the end is amortized O(1)
my_list.append(5)

# Inserting at a specific position (e.g., at the beginning) is O(n)
my_list.insert(0, 0)

2. Dictionary (字典)

哈希表类比 (Hash Table Analogy):

The dictionary (dict) in Python is directly implemented as a hash table, just like the one described in the 哈希表结构示例.

• Dict Internal Structure:

  • Each key-value pair is hashed, and the key is mapped to an index in the internal array. The values are stored in buckets at these positions.
  • Python uses dynamic arrays (not linked lists) for chaining in case of collisions.
  • Average time complexity for insertion, deletion, and lookup is O(1).

• Usage:

  • A dict is used when you need to map unique keys to values and want to retrieve them quickly.
  • The keys must be immutable (like strings, tuples), and the values can be any object.

Code Example:

# Create a dictionary
my_dict = {'apple': 1, 'banana': 2}

# Inserting or updating a key-value pair is O(1)
my_dict['carrot'] = 3

# Accessing a value by key is O(1)
print(my_dict['apple'])  # Output: 1

# Deleting a key-value pair is O(1)
del my_dict['banana']

3. Set (集合)

哈希表类比 (Hash Table Analogy):

A set in Python is also built using a hash table, similar to the dictionary but without associated values. The set only stores unique keys.

• Set Internal Structure:

  • Like a dictionary, elements in a set are hashed to an index in an internal array.
  • Since there are no values, only the keys are stored, and the main purpose is to ensure that all elements are unique.
  • Lookup, insertion, and deletion in a set have an average time complexity of O(1).

• Usage:

  • A set is useful when you want to store unique elements and need fast membership testing.

Code Example:

# Create a set
my_set = {1, 2, 3}

# Inserting an element is O(1)
my_set.add(4)

# Checking if an element exists is O(1)
print(2 in my_set)  # Output: True

# Deleting an element is O(1)
my_set.remove(3)

4. Tuple (元组)

类似数组的结构 (Array-like Structure):

A tuple in Python is a fixed-size, immutable version of a list. Like the array in a hash table, its elements are stored in contiguous memory.

• Tuple Internal Structure:

  • The elements of a tuple are stored in a contiguous memory block, like an array, but a tuple’s size is fixed upon creation and cannot be modified.
  • Accessing tuple elements by index is O(1), just like with lists.

• Usage:

  • Tuples are useful for storing collections of items where immutability is desired (e.g., as keys in a dictionary, since tuples are hashable and lists are not).

Code Example:

# Create a tuple
my_tuple = (1, 2, 3)

# Accessing elements by index is O(1)
print(my_tuple[1])  # Output: 2

# Tuples are immutable, so you cannot modify or append elements
# my_tuple[1] = 4  # This would raise an error

5. String (字符串)

类似数组的结构 (Array-like Structure):

A string in Python is an immutable sequence of characters, similar to an immutable array.

• String Internal Structure:

  • Strings are stored in contiguous memory and are immutable, meaning once they are created, they cannot be modified.
  • Like arrays, accessing characters by index is O(1).

• Usage:

  • Strings are used to store text data. Since they are immutable, every modification (like concatenation) creates a new string.

Code Example:

# Create a string
my_string = "hello"

# Accessing characters by index is O(1)
print(my_string[1])  # Output: 'e'

# Strings are immutable, so you cannot modify them
# my_string[1] = 'a'  # This would raise an error

Summary of Data Structures:

中文总结：

• 列表 (List)：使用动态数组实现，适用于有序数据集合，按索引快速访问。
• 字典 (Dict)：基于哈希表，适用于存储键-值对，提供常数时间复杂度的查找、插入和删除操作。
• 集合 (Set)：类似字典的哈希表实现，适用于存储唯一值并支持快速查找。
• 元组 (Tuple)：类似于不可变的列表，适用于需要不变的数据集合。
• 字符串 (String)：不可变的字符序列，适用于存储文本数据。