Bản chất Cấu trúc & Sự khác biệt với Mảng

Khác với Mảng, Danh sách liên kết (Linked List) bao gồm tập hợp các Nút (Node) nằm rải rác ở các vị trí ngẫu nhiên trên RAM (Non-contiguous Memory). Each Node chứa hai thành phần:

1. Data: Giá trị dữ liệu cần lưu trữ.

2. Next Pointer: Con trỏ/Địa chỉ trỏ tới Node kế tiếp trong bộ nhớ.

    [ HEAD ]
       |
       v
  +----+----+      +----+----+      +----+------+
  |Data|Next| ---> |Data|Next| ---> |Data| None |
  | 12 | *  |      | 45 | *  |      | 78 |      |
  +----+----+      +----+----+      +----+------+

So sánh Đặc tính Kỹ thuật: Mảng vs. Danh sách Liên kết

2. Mã nguồn Cài đặt từ Đầu (Object-Oriented Python)

Dưới đây là cách tự xây dựng một Node và một SinglyLinkedList (Danh sách liên kết đơn) hoàn chỉnh:

# 1. Định nghĩa cấu trúc Nút (Node)
class Node:

    def __init__(self, data):
        self.data = data  # Dữ liệu của node
        self.next = None  # Con trỏ mặc định chưa trỏ đi đâu


# 2. Định nghĩa cấu trúc Danh sách liên kết đơn
class SinglyLinkedList:

    def __init__(self):
        self.head = None  # Con trỏ quản lý nút đầu tiên

    # Thêm phần tử vào đầu danh sách - O(1)
    def insert_at_head(self, data):
        new_node = Node(data)
        new_node.next = self.head  # Trỏ node mới vào head cũ
        self.head = new_node  # Cập nhật head là node mới

    # Thêm phần tử vào cuối danh sách - O(N)
    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return

        # Duyệt tới nút cuối cùng
        curr = self.head
        while curr.next:
            curr = curr.next
        curr.next = new_node  # Gắn nút mới vào đuôi

    # Duyệt và in toàn bộ danh sách - O(N)
    def display(self):
        elements = []
        curr = self.head
        while curr:
            elements.append(str(curr.data))
            curr = curr.next
        print(" -> ".join(elements) + " -> None")


# Demo vận hành
sll = SinglyLinkedList()
sll.insert_at_head(20)  # List: 20
sll.insert_at_head(10)  # List: 10 -> 20
sll.append(30)  # List: 10 -> 20 -> 30

sll.display()  # In ra: 10 -> 20 -> 30 -> None

BÀI TẬP 

Bài tập 1: Tư duy Cấu trúc Dữ liệu

Trong kịch bản hệ thống của một Xưởng chế biến & đóng gói trái cây, ta cần chọn cấu trúc dữ liệu phù hợp:

1. Kịch bản A: Lưu danh sách mã định danh của 10.000 lô hàng. Mỗi lô hàng có chỉ số thứ tự cố định từ 0 đến 9999 và các thao tác chủ yếu là tra cứu tức thì trạng thái lô hàng theo chỉ số.

2. Kịch bản B: Quản lý hàng chờ nguyên liệu đầu vào, nơi các xe tải liên tục đưa nguyên liệu mới bổ sung vào ngay đầu danh sách, và hệ thống cần chèn/xóa lượt ưu tiên ở đầu danh sách liên tục.

Ta sẽ chọn Mảng (Array) hay Danh sách liên kết (Linked List) cho từng kịch bản? Vì sao?

Bài tập 2: Thử thách Cài đặt Thuật toán (Thực hành Code)

Bổ sung hàm reverse() vào lớp SinglyLinkedList ở đoạn mã trên để Đảo ngược danh sách liên kết ngay trên bộ nhớ (In-place) với độ phức tạp thời gian $O(N)$ và độ phức tạp bộ nhớ phụ $O(1)$.

Gợi ý: Sử dụng 3 con trỏ chạy song song: prev (nút phía trước), curr (nút hiện tại), và next_node (nút kế tiếp để tránh mất dấu danh sách).

Ban đầu:   10  ->  20  ->  30  -> None
Sau đảo:   30  ->  20  ->  10  -> None