Sự khác biệt giữa Cấu trúc dữ liệu Tuyến tính và Phi tuyến tính

Hiểu khác biệt giữa Linear và Non-linear Data Structure.

Linear Data Structure (Cấu trúc tuyến tính)

• Phần tử sắp xếp tuần tự.
• Mọi phần tử truy cập được bằng duyệt tuyến tính.
• Tất cả phần tử ở một cấp độ (không phân cấp).
• Dễ triển khai và dùng.
• Tốn bộ nhớ nhiều hơn, không thân thiện bộ nhớ.
• Độ phức tạp thời gian thường tăng khi size tăng.
• Ví dụ: list, array, stack.

Ví dụ list Python:

my_list = [45, 42, 12, 34, 56, 7]
print(my_list)

Output

[45, 42, 12, 34, 56, 7]

Non-linear Data Structure (Cấu trúc phi tuyến tính)

• Phần tử lưu theo phân cấp (hierarchical).
• Kết nối nhau bằng 'nodes'.
• Phần tử ở nhiều cấp độ khác nhau.
• Triển khai không dễ.
• Không duyệt dễ dàng - cần nhiều lần lặp để đi hết.
• Thân thiện bộ nhớ, dùng bộ nhớ hiệu quả.
• Độ phức tạp thời gian không đổi khi dữ liệu tăng.
• Ví dụ: Map, tree, graph.

Ví dụ định nghĩa graph (chỉ ra kết nối nút):

graph = {'A': ['B', 'C'],
         'B': ['C'],
         'C': ['D', 'E'],
         'D': ['C'],
         'E': ['F', 'G'],
         'F': ['C']}