Cấu trúc dữ liệu và Giải thuật Bài 12: Các thao tác cơ bản: Duyệt, Thêm, Chèn, Xóa phần tử.

Ở bài trước, chúng ta đã thấy Mảng tĩnh tỏa sáng rực rỡ với khả năng truy xuất phần tử cực nhanh $O(1)$ nhờ cơ chế bộ nhớ liên tục. Nhưng cái giá phải trả cho sự liên tục đó là gì?

Trong bài học này, chúng ta sẽ bắt tay vào thao tác dữ liệu trên mảng. Hãy nhớ lại khái niệm trọng tâm: Một mảng tĩnh có Sức chứa (Capacity) cố định do RAM cấp phát, nhưng Kích thước thực tế (Size/Length) là số lượng phần tử mà chúng ta đang sử dụng bên trong nó.

1. Duyệt mảng (Traversal)

Đây là thao tác cơ bản nhất: Đi qua từng phần tử của mảng một lần duy nhất để in ra màn hình, tính tổng, hoặc tìm kiếm.

Go

func traverse(arr [10]int, size int) {
    for i := 0; i < size; i++ {
        fmt.Println(arr[i])
    }
}

• Cơ chế: Dùng một vòng lặp chạy chỉ mục i từ 0 đến size - 1.

• Độ phức tạp thời gian: $O(n)$ (Với $n$ là kích thước mảng).

• Độ phức tạp không gian: $O(1)$ (Không cần tạo thêm cấu trúc lưu trữ nào).

2. Thêm vào cuối mảng (Append / Push)

Thao tác này cực kỳ nhẹ nhàng. Bạn chỉ cần đảm bảo mảng vẫn còn sức chứa (size < capacity). Nếu còn chỗ, bạn gán giá trị mới vào ô nhớ ngay sau phần tử cuối cùng hiện tại, rồi tăng biến đếm size lên 1.

Go

// arr là mảng tĩnh có sức chứa 10 (Capacity = 10)
// size là số lượng phần tử đang có (Giả sử đang là 3)
func appendElement(arr *[10]int, size *int, value int) {
    if *size >= 10 {
        fmt.Println("Mảng đã đầy, không thể thêm!")
        return
    }
    arr[*size] = value
    *size++
}

• Cơ chế: Truy cập trực tiếp qua index $size.

• Độ phức tạp thời gian: $O(1)$ (Tuyệt vời! Không phụ thuộc vào mảng đang có bao nhiêu phần tử).

3. Chèn phần tử vào giữa mảng (Insertion)

Đây là lúc sự "liên tục" của bộ nhớ trở thành gánh nặng. Giả sử bạn đang xếp hàng mua vé xem phim. Có một người bạn chen ngang vào vị trí số 2 của hàng. Để người này đứng được vào hàng, tất cả những người từ vị trí số 2 trở về sau đều phải lùi lại đúng một bước.

Bộ nhớ máy tính cũng vậy. Để chèn một số vào index = i, bạn không thể cứ thế ghi đè lên dữ liệu cũ. Bạn phải dời tất cả phần tử từ i đến cuối mảng sang phải 1 ô.

Go

func insertElement(arr *[10]int, size *int, index int, value int) {
    if *size >= 10 || index < 0 || index > *size {
        return // Xử lý lỗi
    }
    
    // Dịch chuyển phần tử từ cuối mảng lùi về sau 1 ô
    for i := *size; i > index; i-- {
        arr[i] = arr[i-1]
    }
    
    // Nhét phần tử mới vào khoảng trống vừa tạo ra
    arr[index] = value
    *size++
}

• Trường hợp tốt nhất: Chèn vào cuối mảng $\rightarrow$ Không cần dịch chuyển ai $\rightarrow$ $\Omega(1)$.

• Trường hợp xấu nhất: Chèn vào đầu mảng (index = 0) $\rightarrow$ Phải dịch chuyển toàn bộ $n$ phần tử $\rightarrow$ $O(n)$.

• Chi phí: Rất đắt đỏ. Đây là nút thắt cổ chai lớn nhất khi dùng mảng.

4. Xóa phần tử (Deletion)

Tương tự như chèn, thao tác xóa sẽ để lại một "lỗ hổng" trong bộ nhớ. Để giữ tính liên tục, hệ thống buộc phải lấp lỗ hổng đó bằng cách dời toàn bộ phần tử đứng sau vị trí bị xóa sang trái 1 ô.

Go

func deleteElement(arr *[10]int, size *int, index int) {
    if index < 0 || index >= *size {
        return // Xử lý lỗi
    }
    
    // Dịch chuyển phần tử tiến lên trước 1 ô để lấp chỗ trống
    for i := index; i < *size - 1; i++ {
        arr[i] = arr[i+1]
    }
    
    *size--
}

• Trường hợp tốt nhất: Xóa phần tử cuối cùng $\rightarrow$ $\Omega(1)$ (Chỉ cần giảm biến size, rác trong bộ nhớ sẽ tự bị ghi đè sau này).

• Trường hợp xấu nhất: Xóa phần tử đầu tiên $\rightarrow$ Dịch chuyển toàn bộ $n-1$ phần tử $\rightarrow$ $O(n)$.

5. Kỹ thuật "Hack" Xóa phần tử trong $O(1)$ (Pro Tip)

Đây là một kỹ thuật cực kỳ thực dụng trong thiết kế game và các hệ thống thời gian thực (như theo dõi các socket connection).

Nếu bài toán không yêu cầu giữ nguyên thứ tự của các phần tử trong mảng, bạn có thể biến thao tác xóa $O(n)$ thành $O(1)$ bằng một mẹo nhỏ: Thay vì dịch chuyển cả ngàn phần tử để lấp lỗ hổng, hãy lấy luôn phần tử cuối cùng của mảng ném vào cái lỗ hổng đó, rồi giảm size đi 1.

Go

func fastDeleteUnordered(arr *[10]int, size *int, index int) {
    // Thay thế phần tử cần xóa bằng phần tử cuối cùng
    arr[index] = arr[*size - 1]
    *size-- // Thu hẹp kích thước mảng
}

Chỉ với 2 dòng code, một thao tác nặng nề đã được tối ưu hóa về mặt không - thời gian tuyệt đối.

Như vậy, chúng ta đã thấy giới hạn chí mạng của mảng tĩnh: Kích thước bị đóng băng. Trong thực tế, dữ liệu người dùng thay đổi liên tục, chúng ta không thể cứ cấp phát một mảng 1 triệu phần tử chỉ để phòng hờ, cũng không thể để hệ thống crash vì mảng bị đầy.

Đó là lý do các kỹ sư tạo ra một cấu trúc linh hoạt hơn dựa trên nền tảng của mảng tĩnh. Ở bài học tiếp theo, chúng ta sẽ mổ xẻ Mảng động (Dynamic Array) — thứ mà bạn vẫn gọi là "Array" trong PHP hay "Slice" trong Golang.