Khi bắt đầu làm quen với các bài toán thuật toán, đặc biệt là các bài toán về danh sách liên kết, việc gặp phải các định nghĩa kiểu dữ liệu như Optional[ListNode] trong hàm có thể gây bối rối. Bài viết này sẽ làm rõ ý nghĩa của Optional và ListNode trong ngữ cảnh của Python và các bài toán lập trình.

Hiểu về Optional[ListNode] và ListNode

Trong định nghĩa hàm như def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:, có hai điểm chính cần làm rõ:

1. ListNode: Đây là một kiểu dữ liệu tùy chỉnh, đại diện cho một nút trong danh sách liên kết. Trong Python, kiểu dữ liệu này không có sẵn và cần được định nghĩa bởi người lập trình.
2. -> Optional[ListNode]: Đây là cú pháp trong Python dùng để chú thích kiểu dữ liệu trả về của hàm. Việc chú thích này đặt bên ngoài dấu ngoặc đơn của tham số.

Chi tiết về Optional

Optional[X] là một cách sử dụng nâng cao của tính năng Type Hints (chú thích kiểu) trong Python, được nhập từ module typing.

• Ý nghĩa đầy đủ: Optional[X] có nghĩa là biến đó có thể mang kiểu dữ liệu X hoặc có thể là None. Nó tương đương với việc viết Union[X, None].
• Trường hợp sử dụng: Kiểu Optional[X] được sử dụng để biểu thị một trạng thái có thể vắng mặt. Điều này rất phổ biến với các kiểu dữ liệu dạng tham chiếu hoặc con trỏ trong các cấu trúc dữ liệu:
  • Nút danh sách liên kết: head: Optional[ListNode] biểu thị rằng danh sách liên kết có thể rỗng (head là None).
  • Nút cây nhị phân: left: Optional[TreeNode] biểu thị rằng cây con bên trái có thể không tồn tại (left là None).

Khái niệm "Không tồn tại" dưới hai góc nhìn

Có hai cách hiểu về sự "không tồn tại":

1. Góc nhìn của C/C++ (Gần với phần cứng)

• Bản chất của con trỏ: Con trỏ lưu trữ một địa chỉ bộ nhớ.
• Quy ước về con trỏ NULL: Để biểu thị "con trỏ này không trỏ đến bất kỳ địa chỉ bộ nhớ hợp lệ nào", ngành công nghiệp phần mềm đã thống nhất sử dụng địa chỉ 0 làm giá trị đại diện cho "NULL" hay "không có gì".
• Lý do là địa chỉ 0: Hệ điều hành thường bảo vệ các vùng nhớ ở địa chỉ thấp (đặc biệt là địa chỉ 0). Bất kỳ chương trình nào cố gắng truy cập địa chỉ này sẽ gây ra lỗi (ví dụ: "segmentation fault"), giúp lập trình viên phát hiện sớm lỗi sử dụng con trỏ chưa được khởi tạo.

Trong C/C++, cấu trúc nút danh sách liên kết và cách thể hiện nút cuối cùng như sau:

struct ListNode {
    int val;
    struct ListNode *next; // 'next' lưu trữ một địa chỉ bộ nhớ
};

// Con trỏ 'next' của nút cuối cùng được gán bằng NULL (có giá trị là 0)
node->next = NULL;

Ở đây, biến next lưu trữ một giá trị số nguyên đại diện cho địa chỉ bộ nhớ.

2. Góc nhìn của Python (Trừu tượng hóa cao)

• Python không có con trỏ: Trong Python, biến giống như một "nhãn" gắn vào một đối tượng trong bộ nhớ. Cách gọi chính xác hơn là "tham chiếu".
• Biểu diễn tham chiếu "rỗng": Python sử dụng một đối tượng đặc biệt, duy nhất là None, để biểu thị rằng một tham chiếu không trỏ đến bất kỳ đối tượng nào.
• Lý do là None:
  • Sự thống nhất: None là một ký hiệu "rỗng" áp dụng chung cho mọi kiểu dữ liệu. Dù là số nguyên, chuỗi, danh sách hay ListNode tùy chỉnh, chúng ta đều dùng None để biểu thị sự vắng mặt.
  • Không gây nhầm lẫn: None là một đối tượng singleton trong Python (chỉ có một đối tượng None duy nhất trong toàn bộ chương trình). Nó có kiểu dữ liệu riêng (NoneType) và địa chỉ bộ nhớ riêng. Mục đích duy nhất của nó là biểu thị "trống rỗng" hoặc "không có gì".

Trong Python, cách triển khai danh sách liên kết và thể hiện nút cuối cùng như sau:

class ListNode:
    def __init__(self, val=0, next=None): # 'next' mong đợi nhận một tham chiếu
        self.val = val
        self.next = next   # 'next' là một biến lưu trữ một tham chiếu

# Tham chiếu 'next' của nút cuối cùng được gán cho đối tượng đặc biệt None
node.next = None

Ở đây, biến next lưu trữ một tham chiếu đến đối tượng None.

Tại sao lại sử dụng chú thích kiểu head: Optional[ListNode]?

Câu hỏi đặt ra là: Nếu đề bài cho head=[1,2,6,3,4,5,6], thì kiểu dữ liệu của head không phải là một danh sách (list) hay sao? Và liệu Python có kiểm tra sự phù hợp giữa kiểu dữ liệu thực tế và chú thích kiểu khi biên dịch không?

• Python không kiểm tra chặt chẽ: Python không bắt buộc kiểm tra chú thích kiểu khi chạy chương trình. Chúng chủ yếu phục vụ cho việc đọc hiểu mã nguồn và các công cụ phân tích tĩnh.
• head=[1,2,6,3,4,5,6] chỉ là mô tả: Dữ liệu đầu vào bạn thấy trong mô tả bài toán (ví dụ: một danh sách Python) không phải là cách mà đối số thực sự được truyền vào hàm trong môi trường chấm điểm của LeetCode. LeetCode sẽ thực hiện việc chuyển đổi dữ liệu đó thành một chuỗi các đối tượng ListNode được liên kết với nhau. Quá trình này tương tự như sau:

  
  # LeetCode thực thi mã giả như thế này ở hậu trường:
  my_list_description = [1, 2, 3, 4]
  
  # Tạo ra các đối tượng ListNode từ mô tả danh sách
  nodes = [ListNode(val=num) for num in my_list_description]
  
  # Liên kết các nút lại với nhau
  for i in range(len(nodes) - 1):
      nodes[i].next = nodes[i+1]
  
  # 'real_head' mới là đối tượng ListNode đầu tiên được truyền vào hàm của bạn
  real_head = nodes[0]
          

Vì vậy, mặc dù mô tả bài toán có thể dùng cấu trúc dữ liệu quen thuộc của Python như list, nhưng đối số head thực tế truyền vào hàm của bạn luôn là một đối tượng ListNode (hoặc None nếu danh sách rỗng), phù hợp với chú thích kiểu Optional[ListNode].