Cấu trúc dữ liệu và Giải thuật Bài 29: Các thao tác cơ bản trên Linked List: Thêm, Xóa, Tìm kiếm.

Thao tác trên Danh sách liên kết (Linked List) mang lại một cảm giác hoàn toàn khác biệt so với Mảng. Nếu làm việc với Mảng giống như việc bạn phải di dời cả một dãy nhà để chen một ngôi nhà mới vào giữa, thì làm việc với Linked List giống như một ca "phẫu thuật" mạch máu: Bạn chỉ cần cắt đứt các sợi dây liên kết cũ và nối các sợi dây liên kết mới lại với nhau. Phần tử bị mất kết nối sẽ tự động bị hệ thống thu gom rác (Garbage Collector của Golang/Java) dọn dẹp.

Để làm được điều này, chúng ta cần nắm vững thứ tự thao tác con trỏ. Chỉ một sai lầm nhỏ trong việc gán nhầm thứ tự, bạn sẽ làm đứt chuỗi và vĩnh viễn đánh mất toàn bộ dữ liệu phía sau.

1. Tìm Kiếm Phần Tử (Search)

Như đã phân tích ở Bài 28, Linked List không có khả năng truy xuất ngẫu nhiên (Random Access). Bạn không thể gõ list[5] để nhảy đến phần tử thứ 5. Cách duy nhất là bắt đầu từ Head và lần mò theo từng con trỏ Next cho đến khi tìm thấy dữ liệu.

// Tìm kiếm một Node có chứa giá trị target
func (list *LinkedList) Search(target int) *Node {
    current := list.Head // Luôn xuất phát từ Head
    
    for current != nil { // Duyệt cho đến khi đụng nil (cuối danh sách)
        if current.Data == target {
            return current // Tìm thấy, trả về địa chỉ của Node
        }
        current = current.Next // Nhảy sang Node tiếp theo
    }
    
    return nil // Không tìm thấy
}

• Độ phức tạp thời gian: $O(n)$ trong trường hợp xấu nhất (phần tử nằm ở cuối hoặc không tồn tại).
• Độ phức tạp không gian: $O(1)$.

2. Thêm Phần Tử (Insertion)

Sức mạnh tuyệt đối của Linked List bộc lộ ở thao tác thêm và chèn. Có 3 kịch bản phổ biến:

A. Thêm vào đầu danh sách (Insert Front / Prepend)

Bạn muốn một Node mới trở thành Head của danh sách.

1. Cho con trỏ Next của Node mới trỏ vào Head cũ.
2. Cập nhật lại biến Head trỏ vào Node mới.

func (list *LinkedList) InsertFront(data int) {
    newNode := &Node{Data: data}
    newNode.Next = list.Head // Nối Node mới vào chuỗi hiện tại
    list.Head = newNode      // Gắn mác Head cho Node mới
}

• Độ phức tạp: $O(1)$. Thao tác siêu tốc, bất chấp danh sách dài 10 phần tử hay 10 triệu phần tử.

B. Chèn vào giữa (Insert After)

Bạn đã có con trỏ trỏ đến một Node cụ thể (prevNode), và bạn muốn chèn một Node mới ngay sau nó.

⚠️ Quy tắc sinh tử: Phải nối Node mới với phần sau của danh sách TRƯỚC, sau đó mới ngắt kết nối của prevNode để trỏ vào Node mới. Nếu làm ngược lại, bạn sẽ làm mất địa chỉ của phần sau danh sách.

func (list *LinkedList) InsertAfter(prevNode *Node, data int) {
    if prevNode == nil {
        return // Không thể chèn sau một Node không tồn tại
    }
    
    newNode := &Node{Data: data}
    
    // BƯỚC 1: Node mới nắm lấy phần đuôi của danh sách
    newNode.Next = prevNode.Next 
    
    // BƯỚC 2: Node trước buông phần đuôi ra và nắm lấy Node mới
    prevNode.Next = newNode 
}

• Độ phức tạp: $O(1)$ (Nếu đã biết trước vị trí prevNode). Nếu cộng cả thời gian phải dùng hàm Search để tìm prevNode, tổng thời gian sẽ là $O(n)$.

3. Xóa Phần Tử (Deletion)

Việc xóa một Node trong Linked List bản chất là việc điều hướng lại con trỏ (bỏ qua Node đó). Khi không còn con trỏ nào trỏ đến Node cần xóa, nó sẽ trở thành rác vô chủ và bị hệ điều hành thu hồi bộ nhớ.

Để xóa một Node, bạn bắt buộc phải biết được Node đứng ngay trước nó (prevNode), vì bạn cần nối prevNode.Next bỏ qua Node hiện tại và trỏ thẳng đến Node tiếp theo.

func (list *LinkedList) DeleteValue(target int) {
    if list.Head == nil {
        return // Danh sách rỗng
    }
    
    // Kịch bản 1: Cần xóa ngay Node Head
    if list.Head.Data == target {
        list.Head = list.Head.Next // Bỏ qua Head cũ, dời Head sang Node thứ 2
        return
    }
    
    // Kịch bản 2: Tìm Node đứng ngay trước Node cần xóa
    current := list.Head
    // Chạy vòng lặp kiểm tra trước 1 bước (current.Next)
    for current.Next != nil && current.Next.Data != target {
        current = current.Next
    }
    
    // Nếu tìm thấy, thực hiện nối tắt (bypass)
    if current.Next != nil {
        // current.Next.Next chính là Node nằm sau Node bị xóa
        current.Next = current.Next.Next 
    }
}

• Độ phức tạp: $O(n)$ để tìm kiếm, nhưng quá trình phẫu thuật con trỏ để cắt bỏ chỉ mất $O(1)$ và hoàn toàn không phải dời các phần tử phía sau lên trước như Mảng.

4. Tóm Tắt Đánh Đổi (Array vs. Linked List)

Việc chọn Mảng hay Danh sách liên kết là quyết định kiến trúc đầu tiên của mọi hệ thống. Dưới đây là bảng đối chiếu:

💡 Lời Kết

Nắm vững việc điều hướng các con trỏ Next là bước đệm bắt buộc. Bài toán phỏng vấn liên quan đến Linked List hiếm khi yêu cầu bạn thao tác thêm xóa cơ bản, mà thường đòi hỏi bạn phải uốn nắn các con trỏ này theo những hình thù phức tạp. Đứng đầu trong danh sách các bài toán đó là việc quay ngược toàn bộ dòng chảy của danh sách.