DSA - Chapter 4: Lists | Cấu trúc dữ liệu và thuật toán (Lương Thế Nhân)

Trong lĩnh vực khoa học máy tính, cấu trúc dữ liệu và thuật toán là nền tảng cốt lõi. 100 trang.

• Đề tài: Data Structure And Algorithms Cấu Trúc Dữ Liệu Và Thuật Toán Dsa Ch4 Lists 1

Mục lục chi tiết

• MỤC TIÊU
• 4. CHƯƠNG 4: DANH SÁCH
• 4.1. Khái niệm danh sách tuyến tính
• 4.2. Cài đặt bằng mảng
• 4.3. Danh sách liên kết đơn
• 4.4. Các danh sách liên kết khác
• 4.5. So sánh các phương pháp cài đặt danh sách

Tóm tắt

I. Khám phá Cấu trúc dữ liệu và Thuật toán List DSA từ A Z

Trong lĩnh vực khoa học máy tính, cấu trúc dữ liệu và thuật toán là nền tảng cốt lõi. Chương 4 tập trung vào một trong những cấu trúc cơ bản nhất: List (Danh sách). Theo định nghĩa từ tài liệu của Luong The Nhan và Tran Giang Son, danh sách tuyến tính là một cấu trúc dữ liệu trong đó mỗi phần tử có một phần tử kế thừa duy nhất. Điều này tạo ra một chuỗi các phần tử có thứ tự, làm cho List trở thành một công cụ cực kỳ linh hoạt để lưu trữ và quản lý dữ liệu. Khái niệm trừu tượng của nó được định nghĩa thông qua List ADT (Abstract Data Type), đặc tả các thao tác cơ bản mà không cần quan tâm đến cách cài đặt cụ thể. Các thao tác này bao gồm khởi tạo danh sách, chèn phần tử vào list, xóa phần tử khỏi list, tìm kiếm và truy xuất phần tử. Hiểu rõ về List ADT là bước đầu tiên để làm chủ cấu trúc dữ liệu này, cho phép lập trình viên tập trung vào logic của vấn đề thay vì chi tiết cài đặt. Danh sách có thể được phân loại thành hai dạng chính: danh sách tổng quát (General List) và danh sách bị giới hạn (Restricted List). Danh sách tổng quát không có giới hạn về vị trí chèn/xóa, trong khi danh sách bị giới hạn như Queue (hàng đợi) và Stack (ngăn xếp) chỉ cho phép thao tác ở các đầu của danh sách. Việc lựa chọn giữa các loại danh sách phụ thuộc hoàn toàn vào yêu cầu của bài toán cụ thể.

1.1. Định nghĩa List ADT và các thao tác cơ bản

Một List ADT định nghĩa một tập hợp các giá trị và một tập hợp các thao tác trên những giá trị đó. Về cơ bản, một danh sách các phần tử kiểu T là một chuỗi hữu hạn các phần tử của T. Các thao tác trên danh sách nền tảng bao gồm: khởi tạo danh sách rỗng, chèn một phần tử vào vị trí xác định, xóa một phần tử, tìm kiếm sự tồn tại của một phần tử, và duyệt danh sách để thực hiện một hành động trên mỗi phần tử. Ngoài ra, các thao tác mở rộng cũng rất quan trọng, chẳng hạn như kiểm tra danh sách rỗng/đầy, lấy kích thước danh sách, hoặc xóa toàn bộ danh sách. Sự thành công của các thao tác này thường phụ thuộc vào trạng thái của danh sách; ví dụ, việc chèn chỉ thành công khi danh sách chưa đầy, và việc xóa/truy xuất chỉ thành công khi danh sách không rỗng. Các thao tác này là giao diện chuẩn để tương tác với bất kỳ loại danh sách nào, dù nó được cài đặt bằng mảng hay con trỏ.

1.2. Phân biệt General List và Restricted List trong DSA

Sự khác biệt chính giữa General List và Restricted List nằm ở các quy tắc thao tác dữ liệu. General List (danh sách tổng quát) cho phép chèn phần tử vào list và xóa phần tử khỏi list tại bất kỳ vị trí nào. Nó có hai biến thể: Unordered List (dữ liệu ngẫu nhiên) và Ordered List (dữ liệu được sắp xếp theo một khóa nhất định). Ngược lại, Restricted List (danh sách bị giới hạn) chỉ cho phép các thao tác này diễn ra ở các đầu của danh sách. Hai ví dụ kinh điển là Queue (Hàng đợi), hoạt động theo nguyên tắc FIFO (First-In-First-Out), và Stack (Ngăn xếp), hoạt động theo nguyên tắc LIFO (Last-In-First-Out). Việc lựa chọn cấu trúc nào phụ thuộc vào bản chất của vấn đề cần giải quyết, ví dụ như quản lý tác vụ trong hệ điều hành (Queue) hay chức năng hoàn tác (Undo) trong trình soạn thảo (Stack).

II. Thách thức cài đặt List Mảng tĩnh và Cấp phát bộ nhớ động

Việc lựa chọn phương pháp cài đặt List là một quyết định quan trọng, ảnh hưởng trực tiếp đến hiệu suất của chương trình. Hai phương pháp chính là sử dụng mảng (Array-based) và sử dụng con trỏ (Pointer-based). Thách thức lớn nhất khi cài đặt list bằng mảng là kích thước cố định. Một mảng được cấp phát tự động (Automatically Allocated Array) có kích thước tối đa được xác định trước tại thời điểm biên dịch. Nếu số lượng phần tử vượt quá giới hạn này, chương trình sẽ gặp lỗi tràn bộ nhớ. Ngược lại, nếu số lượng phần tử quá ít, một phần lớn bộ nhớ sẽ bị lãng phí. Vấn đề này đặt ra yêu cầu về một giải pháp linh hoạt hơn trong quản lý bộ nhớ. Đây là lúc khái niệm cấp phát bộ nhớ động (Dynamic Memory Allocation) và dynamic array (mảng động) phát huy tác dụng. Mảng động cho phép thay đổi kích thước trong quá trình chạy, giải quyết được bài toán về sự lãng phí hoặc thiếu hụt bộ nhớ. Tuy nhiên, việc thay đổi kích thước một mảng động không phải là một thao tác miễn phí; nó đòi hỏi phải cấp phát một vùng nhớ mới lớn hơn, sao chép toàn bộ dữ liệu từ mảng cũ sang, và giải phóng mảng cũ. Thao tác này có thể tốn kém về mặt thời gian, đặc biệt với các danh sách lớn.

2.1. Hạn chế của mảng cấp phát tĩnh trong cài đặt list

Mảng cấp phát tĩnh, hay Automatically Allocated Array, là cách tiếp cận đơn giản nhất để cài đặt danh sách. Tuy nhiên, nó đi kèm với những hạn chế cố hữu. Vấn đề chính là kích thước cố định. Lập trình viên phải đoán trước số lượng phần tử tối đa mà danh sách sẽ chứa. Nếu ước tính quá cao, bộ nhớ sẽ bị lãng phí. Nếu ước tính quá thấp, ứng dụng sẽ không thể xử lý dữ liệu vượt quá giới hạn, dẫn đến lỗi hoặc hành vi không mong muốn. Hơn nữa, các thao tác như chèn hoặc xóa một phần tử ở giữa danh sách yêu cầu phải dịch chuyển vật lý tất cả các phần tử phía sau, dẫn đến độ phức tạp của list cho các thao tác này là O(n), không hiệu quả với các tập dữ liệu lớn và thay đổi thường xuyên.

2.2. Giải pháp Dynamic Array và cơ chế cấp phát bộ nhớ động

Để khắc phục nhược điểm của mảng tĩnh, dynamic array được giới thiệu. Đây là một cấu trúc dữ liệu cho phép mảng phát triển về kích thước khi cần thiết. Trong C++, điều này thường được thực hiện thông qua cấp phát bộ nhớ động bằng toán tử new. Khi mảng hiện tại đầy, một mảng mới với dung lượng lớn hơn (ví dụ: gấp 1.5 hoặc 2 lần) được tạo ra. Tất cả các phần tử từ mảng cũ được sao chép sang mảng mới, và vùng nhớ của mảng cũ được giải phóng. Mặc dù thao tác thay đổi kích thước này có chi phí (amortized cost), nó cung cấp sự linh hoạt cần thiết để xử lý số lượng phần tử không xác định trước. Đây là nền tảng cho các cấu trúc dữ liệu như std::vector trong C++, một dạng array list cực kỳ mạnh mẽ và được sử dụng rộng rãi.

III. Hướng dẫn cài đặt List bằng Mảng Array List trong DSA

Phương pháp cài đặt list bằng mảng, thường được gọi là Array List, là một kỹ thuật nền tảng trong cấu trúc dữ liệu và thuật toán. Cách tiếp cận này sử dụng một vùng bộ nhớ liền kề để lưu trữ các phần tử của danh sách. Ưu điểm lớn nhất của nó là khả năng truy cập phần tử ngẫu nhiên với thời gian không đổi, O(1), thông qua chỉ số (index). Điều này làm cho thao tác truy xuất (Retrieve) và thay thế (Replace) tại một vị trí cụ thể trở nên cực kỳ hiệu quả. Tuy nhiên, điểm yếu của Array List lại nằm ở các thao tác làm thay đổi cấu trúc danh sách. Khi thực hiện chèn phần tử vào list hoặc xóa phần tử khỏi list ở vị trí bất kỳ (không phải cuối danh sách), tất cả các phần tử phía sau vị trí đó phải được dịch chuyển. Việc dịch chuyển này gây ra chi phí thời gian tỷ lệ thuận với số lượng phần tử cần di dời, dẫn đến time complexity list operations cho các thao tác này là O(n) trong trường hợp xấu nhất. Theo tài liệu của Luong The Nhan và Tran Giang Son, các thao tác Insert và Remove trên một danh sách liền kề với n phần tử hoạt động trong thời gian xấp xỉ tỷ lệ thuận với n. Ngược lại, các thao tác như Clear, Empty, Full, Size thường chỉ tốn thời gian không đổi O(1).

3.1. Phân tích độ phức tạp thời gian của Array List

Việc phân tích độ phức tạp của list khi cài đặt bằng mảng là rất quan trọng để đánh giá hiệu suất. Truy cập phần tử tại chỉ số i (Get/Set) là O(1) vì vị trí bộ nhớ có thể được tính toán trực tiếp. Tuy nhiên, chèn phần tử vào list ở đầu hoặc giữa danh sách yêu cầu dịch chuyển trung bình n/2 phần tử, do đó có độ phức tạp là O(n). Tương tự, xóa phần tử khỏi list cũng có độ phức tạp O(n). Chèn/xóa ở cuối danh sách, nếu mảng chưa đầy, chỉ tốn O(1). Nếu mảng đầy và cần cấp phát lại (trong trường hợp dynamic array), chi phí sẽ là O(n). Hiểu rõ time complexity list operations giúp lập trình viên đưa ra lựa chọn đúng đắn giữa Array List và Linked List tùy thuộc vào tần suất của các loại thao tác trong ứng dụng.

3.2. Các thao tác chính Chèn xóa và tìm kiếm trong mảng

Các thao tác trên danh sách cài đặt bằng mảng có đặc điểm riêng. Để chèn một giá trị vào vị trí index, các phần tử từ index đến cuối phải được dịch sang phải một vị trí để tạo chỗ trống. Sau đó, giá trị mới được đặt vào index. Ngược lại, để xóa phần tử tại index, các phần tử từ index + 1 đến cuối phải được dịch sang trái một vị trí để lấp vào khoảng trống. Cả hai quá trình này đều đòi hỏi sự dịch chuyển dữ liệu vật lý. Đối với tìm kiếm trong list, nếu danh sách không có thứ tự, phương pháp tìm kiếm tuyến tính (Linear Search) được sử dụng, có độ phức tạp O(n). Nếu danh sách đã được sắp xếp, có thể áp dụng tìm kiếm nhị phân (Binary Search) để cải thiện hiệu suất xuống còn O(log n).

IV. Bí quyết làm chủ Danh sách liên kết Linked List cho người mới

Khác với mảng, danh sách liên kết (Linked List) là một cấu trúc dữ liệu động, trong đó các phần tử không được lưu trữ trong các vùng nhớ liền kề. Thay vào đó, mỗi phần tử, được gọi là một node trong DSA, chứa hai thành phần chính: dữ liệu (data) và một con trỏ (link/pointer) trỏ đến node tiếp theo trong danh sách. Cấu trúc này mang lại sự linh hoạt vượt trội trong việc quản lý bộ nhớ. Việc chèn phần tử vào list hoặc xóa phần tử khỏi list trở nên rất hiệu quả. Thay vì phải dịch chuyển hàng loạt phần tử như Array List, các thao tác này chỉ cần cập nhật lại một vài con trỏ, cho phép thực hiện trong thời gian không đổi, O(1), miễn là đã có con trỏ trỏ đến vị trí cần thao tác. Danh sách được quản lý thông qua một con trỏ đặc biệt gọi là con trỏ head, trỏ đến node đầu tiên. Đôi khi, một con trỏ tail trỏ đến node cuối cùng cũng được sử dụng để tối ưu hóa việc chèn vào cuối. Loại cơ bản nhất là danh sách liên kết đơn (Singly Linked List), nơi mỗi node chỉ có một con trỏ trỏ đến phần tử kế tiếp. Đây là nền tảng để xây dựng các biến thể phức tạp hơn. Việc cài đặt list bằng con trỏ là một kỹ năng thiết yếu cho bất kỳ lập trình viên nào làm việc với cấu trúc dữ liệu và thuật toán.

4.1. Cấu trúc của một Node và con trỏ Head trong Linked List

Một node trong DSA là đơn vị xây dựng cơ bản của một danh sách liên kết. Mỗi node là một cấu trúc bao gồm ít nhất hai trường: một trường để lưu trữ dữ liệu và một trường con trỏ để lưu địa chỉ của node tiếp theo. Trong một danh sách liên kết đơn (singly linked list), con trỏ này được gọi là next. Toàn bộ danh sách được truy cập thông qua con trỏ head, luôn giữ địa chỉ của node đầu tiên. Nếu head là NULL, danh sách được coi là rỗng. Con trỏ của node cuối cùng trong danh sách sẽ trỏ đến NULL, đánh dấu sự kết thúc của chuỗi. Cấu trúc đơn giản nhưng mạnh mẽ này cho phép danh sách phát triển hoặc thu nhỏ một cách linh hoạt trong quá trình chạy chương trình mà không cần cấp phát lại toàn bộ cấu trúc.

4.2. Hướng dẫn duyệt và chèn phần tử vào danh sách liên kết

Thao tác duyệt danh sách liên kết bắt đầu từ con trỏ head. Một con trỏ tạm thời (thường gọi là current hoặc temp) được khởi tạo bằng head. Sau đó, vòng lặp sẽ tiếp tục chừng nào con trỏ tạm thời chưa phải là NULL. Trong mỗi lần lặp, dữ liệu của node hiện tại được xử lý, và con trỏ tạm thời được cập nhật để trỏ đến node tiếp theo (current = current->next). Để chèn phần tử vào list, một node mới được tạo. Sau đó, tùy thuộc vào vị trí chèn (đầu, giữa, hoặc cuối), các con trỏ sẽ được điều chỉnh lại. Ví dụ, để chèn vào đầu, con trỏ next của node mới sẽ trỏ đến node mà head đang trỏ, và sau đó head được cập nhật để trỏ đến node mới. Các thao tác này chỉ liên quan đến việc thay đổi giá trị của các con trỏ, do đó rất nhanh chóng.

V. So sánh Array List và Linked List Đâu là lựa chọn tối ưu

Việc lựa chọn giữa Array List và Linked List là một bài toán kinh điển trong thiết kế phần mềm, phụ thuộc vào các yêu cầu cụ thể của ứng dụng. Mỗi cấu trúc dữ liệu có những điểm mạnh và điểm yếu riêng dựa trên độ phức tạp của list cho các thao tác khác nhau. Array List, với cấu trúc bộ nhớ liền kề, cung cấp khả năng truy cập ngẫu nhiên O(1), lý tưởng cho các ứng dụng yêu cầu đọc dữ liệu thường xuyên tại các vị trí bất kỳ. Tuy nhiên, nó lại không hiệu quả cho việc chèn và xóa ở giữa danh sách (O(n)) do chi phí dịch chuyển phần tử. Ngược lại, Linked List vượt trội trong các thao tác chèn và xóa (O(1)) vì chỉ cần thay đổi các liên kết con trỏ. Điểm yếu của nó là truy cập phần tử. Để đến được phần tử thứ n, cần phải duyệt danh sách từ đầu, dẫn đến độ phức tạp O(n). Về mặt sử dụng bộ nhớ, Array List có thể gây lãng phí nếu dung lượng cấp phát lớn hơn nhiều so với số phần tử thực tế. Trong khi đó, Linked List yêu cầu bộ nhớ bổ sung cho mỗi phần tử để lưu trữ con trỏ, điều này có thể trở nên đáng kể nếu dữ liệu trong mỗi node có kích thước nhỏ. Do đó, quyết định cuối cùng phải dựa trên sự phân tích kỹ lưỡng về tần suất các thao tác truy cập, chèn, xóa và các ràng buộc về bộ nhớ.

5.1. Phân tích Time Complexity cho các thao tác phổ biến

Bảng so sánh time complexity list operations là cách tốt nhất để thấy rõ sự khác biệt. Với Array List: truy cập theo chỉ số là O(1), chèn/xóa ở cuối (amortized) là O(1), chèn/xóa ở đầu/giữa là O(n), tìm kiếm là O(n). Với Linked List (cụ thể là danh sách liên kết đơn): truy cập theo chỉ số là O(n), chèn/xóa ở đầu là O(1), chèn/xóa ở cuối (nếu không có con trỏ tail) là O(n), chèn/xóa tại một node đã biết là O(1), và tìm kiếm là O(n). Sự đánh đổi này là yếu tố cốt lõi: Array List ưu tiên tốc độ truy cập, trong khi Linked List ưu tiên tốc độ sửa đổi cấu trúc.

5.2. Các trường hợp sử dụng thực tế cho từng loại danh sách

Trong thực tế, Array List (như std::vector trong C++) là lựa chọn mặc định cho nhiều trường hợp vì hiệu suất truy cập tốt và lợi ích từ cache locality (do dữ liệu liền kề). Nó phù hợp khi số lượng phần tử tương đối ổn định hoặc khi các thao tác chủ yếu là đọc và thêm vào cuối. Linked List (như std::list trong C++) lại tỏa sáng trong các kịch bản yêu cầu chèn và xóa nhiều ở giữa danh sách, ví dụ như triển khai hàng đợi ưu tiên, quản lý danh sách các đối tượng game cần thêm bớt liên tục, hoặc trong thuật toán mà việc duy trì các iterator ổn định sau khi xóa là quan trọng.

VI. Tổng kết và các biến thể danh sách liên kết nâng cao thường gặp

Tóm lại, cả Array List và Linked List đều là những cấu trúc dữ liệu và thuật toán nền tảng, mỗi loại có một bộ đặc điểm hiệu suất riêng. Việc hiểu rõ sự đánh đổi giữa chúng là chìa khóa để viết mã hiệu quả. Tuy nhiên, thế giới của danh sách liên kết không chỉ dừng lại ở danh sách liên kết đơn (Singly Linked List). Có nhiều biến thể nâng cao được phát triển để giải quyết các nhược điểm của cấu trúc cơ bản. Các biến thể này cung cấp thêm chức năng và cải thiện hiệu suất cho các trường hợp sử dụng cụ thể. Ví dụ, việc duyệt ngược trong một danh sách liên kết đơn là không thể. Để giải quyết vấn đề này, danh sách liên kết đôi đã được tạo ra. Tương tự, để tạo ra một cấu trúc vòng lặp, danh sách liên kết vòng được giới thiệu. Nắm vững không chỉ các cấu trúc cơ bản mà cả các biến thể nâng cao sẽ trang bị cho lập trình viên một bộ công cụ mạnh mẽ để giải quyết một loạt các vấn đề phức tạp trong lập trình cạnh tranh và phát triển phần mềm thực tế. Nghiên cứu sâu hơn về các cấu trúc này là bước tiếp theo tự nhiên trên con đường trở thành một kỹ sư phần mềm giỏi.

6.1. Giới thiệu Danh sách liên kết đôi Doubly Linked List

Một danh sách liên kết đôi (doubly linked list) là một sự cải tiến của singly linked list. Trong cấu trúc này, mỗi node không chỉ chứa một con trỏ next trỏ đến node kế tiếp, mà còn có một con trỏ previous trỏ đến node đứng trước nó. Lợi ích chính của cấu trúc này là khả năng duyệt danh sách theo cả hai chiều: xuôi và ngược. Điều này làm cho một số thao tác, như xóa một node (khi chỉ biết con trỏ đến chính node đó), trở nên hiệu quả hơn (O(1)) vì không cần phải duyệt từ đầu để tìm node phía trước. Tuy nhiên, nhược điểm là nó tốn nhiều bộ nhớ hơn do phải lưu trữ thêm một con trỏ cho mỗi node và các thao tác chèn/xóa cũng phức tạp hơn một chút vì phải cập nhật cả hai con trỏ.

6.2. Khái niệm và ứng dụng của Danh sách liên kết vòng

Trong một danh sách liên kết vòng (circular linked list), con trỏ next của node cuối cùng không trỏ đến NULL mà thay vào đó trỏ ngược lại về node đầu tiên (node head). Điều này tạo ra một vòng lặp khép kín. Cấu trúc này hữu ích trong các ứng dụng cần duyệt qua các phần tử một cách liên tục theo chu kỳ, ví dụ như quản lý các tiến trình trong hệ điều hành theo thuật toán Round Robin, hoặc triển khai bộ đệm vòng (circular buffer). Một danh sách liên kết vòng có thể là đơn hoặc đôi. Ưu điểm là bất kỳ node nào cũng có thể được coi là điểm bắt đầu, và việc duyệt sẽ không bao giờ kết thúc trừ khi có điều kiện dừng rõ ràng.

Nội dung chính

Tổng quan về giáo trình

Tài liệu học tập "Chapter 4: Lists" là một phần trong hệ thống bài giảng học phần Cấu trúc dữ liệu và Giải thuật (Data Structures and Algorithms - DSA), do ThS. Lương Thế Nhân và TS. Trần Giang Sơn biên soạn, thuộc chương trình đào tạo của Khoa Khoa học và Kỹ thuật Máy tính, Trường Đại học Bách khoa – Đại học Quốc gia TP.HCM (Faculty of Computer Science and Engineering, University of Technology, VNU-HCM). Môn học này giữ vị trí cốt lõi trong khối kiến thức cơ sở ngành của các chương trình đào tạo kỹ sư và cử nhân thuộc khối ngành Công nghệ Thông tin, Khoa học Máy tính và Kỹ thuật Phần mềm.

Mục tiêu học tập của tài liệu được thiết lập bám sát hệ thống Chuẩn đầu ra (Course Learning Outcomes) của học phần:

• L.1: Mô tả các khái niệm danh sách mảng (array list), danh sách liên kết (linked list gồm liên kết đơn, liên kết đôi, đa liên kết), ngăn xếp (stack), hàng đợi (queue) và hàng đợi vòng (circular queue).
• L.2: Đặc tả cấu trúc lưu trữ của các cấu trúc dữ liệu trên thông qua mã giả (pseudocode).
• L.3: Liệt kê và mô tả các phương thức xử lý cơ bản bằng mã giả; hiện thực cấu trúc danh sách, stack, queue bằng ngôn ngữ C/C++.
• L.4: Xây dựng thuật toán đệ quy cho các thao tác trên danh sách, cây, heap, tìm kiếm và đồ thị.
• L.5: Ứng dụng danh sách, stack, queue vào giải quyết các bài toán thực tế và lựa chọn dạng hiện thực phù hợp (mảng so với danh sách liên kết).
• L.6: Phân tích độ phức tạp thuật toán sử dụng ký pháp Big-O ($O$) và xây dựng chương trình thực nghiệm để đánh giá hiệu năng của các phương thức.

Cấu trúc bài giảng tiếp cận tuần tự theo quy trình kỹ thuật phần mềm: từ mô hình trừu tượng hóa dữ liệu (Abstract Data Type - ADT), phân loại danh sách, thiết kế cấu trúc lưu trữ bộ nhớ, cài đặt chi tiết trên C++ đến phân tích hiệu năng thuật toán.

---

Nội dung kiến thức cốt lõi

Các chương/chủ đề chính

Nội dung bài giảng được tổ chức thành 5 phần chuyên đề chính:

1. Linear list concepts (Khái niệm danh sách tuyến tính): Định nghĩa danh sách tuyến tính là cấu trúc dữ liệu trong đó mỗi phần tử đều có một phần tử kế tiếp duy nhất (unique successor). Phân loại danh sách thành hai nhóm lớn:

   • General list: Không bị giới hạn về phép toán hay vị trí chèn/xóa; bao gồm Unordered list (danh sách ngẫu nhiên, không theo thứ tự) và Ordered list (danh sách có thứ tự sắp xếp dựa trên khóa key).
   • Restricted list: Giới hạn vị trí thao tác tại các đầu mút danh sách, tiêu biểu là Ngăn xếp (Stack - cơ chế LIFO) và Hàng đợi (Queue - cơ chế FIFO).
   • List ADT: Đặc tả kiểu dữ liệu trừu tượng với các thao tác cơ bản (Construct, Insert, Remove, Search, Retrieve, Traverse) và thao tác mở rộng (IsEmpty, IsFull, Size, Clear, Replace, Merge, Append).

2. Array implementation (Hiện thực danh sách bằng mảng): Nghiên cứu hai kỹ thuật quản lý vùng nhớ liên tục:

   • Automatically Allocated Array: Mảng tĩnh có kích thước tối đa định trước (maxsize) và biến đếm count.
   • Dynamically Allocated Array: Mảng động cấp phát trên vùng nhớ Heap (int* storage), tự động điều chỉnh dung lượng (capacity) và quản lý kích thước thực tế (size).

3. Singly linked list (Danh sách liên kết đơn): Mô hình tập hợp phần tử có thứ tự, trong đó mỗi phần tử (node) chứa giá trị dữ liệu (data) và địa chỉ trỏ tới phần tử kế tiếp (next/link). Cấu trúc danh sách quản lý thông qua con trỏ đầu danh sách (head) và số lượng phần tử (count).

4. Other linked lists (Các dạng danh sách liên kết khác): Mở rộng sang danh sách liên kết đôi (doubly linked list), danh sách liên kết vòng (circular linked list) và danh sách đa liên kết (multiple links).

5. Comparison of implementations of list (So sánh các mô hình hiện thực): Đối chiếu ưu và nhược điểm giữa cấu trúc mảng và danh sách liên kết về chi phí bộ nhớ và thời gian thực thi.

Kiến thức nền tảng được xây dựng

• Nguyên lý trừu tượng hóa dữ liệu (Data Abstraction): Tách biệt giữa giao diện đặc tả (interface/ADT) và cơ chế cài đặt nội bộ (implementation details). Điều kiện thành công của thao tác: phép chèn (Insertion) thành công khi danh sách chưa đầy, phép xóa/truy xuất (Removal/Retrieval) thành công khi danh sách không rỗng.
• Mô hình tổ chức bộ nhớ:
  • Bộ nhớ liền kề (Contiguous Allocation): Các phần tử nằm tại các ô nhớ liên tiếp nhau, tính toán địa chỉ phần tử trực tiếp qua chỉ số (index).
  • Bộ nhớ liên kết (Chained Allocation): Các node phân tán tại các vùng nhớ khác nhau, duy trì quan hệ thứ tự thông qua biến con trỏ.
• Lý thuyết độ phức tạp tính toán (Computational Complexity): Đánh giá thời gian chạy dựa trên cấu trúc điều khiển (tuần tự, rẽ nhánh, lặp) bằng ký pháp Big-O:
  • Cài đặt bằng mảng liên tục: Thao tác Clear, Empty, Full, Size, Replace, Retrieve có độ phức tạp thời gian hằng số $O(1)$. Thao tác Insert và Remove có độ phức tạp $O(n)$ do đòi hỏi dịch chuyển vật lý dữ liệu trong bộ nhớ.

Kỹ năng phát triển

• Kỹ năng lập trình hệ thống và quản trị bộ nhớ C++:
  • Cài đặt lớp DynamicArray với cơ chế quản lý bộ nhớ thủ công: khởi tạo mảng động bằng toán tử new, giải phóng bộ nhớ bằng delete[] storage, kiểm tra biên rangeCheck với ngoại lệ throw "Index out of bounds!".
  • Kỹ thuật cấp phát mở rộng dung lượng ensureCapacity theo công thức: $$\text{newCapacity} = \frac{\text{capacity} \times 3}{2} + 1$$
  • Tối ưu hóa việc sao chép và dịch chuyển vùng nhớ bằng các hàm cấp thấp memcpy và memmove.
• Kỹ năng lập trình tổng quát (Generic Programming): Sử dụng C++ Template (template <class ItemType>, template <class List_ItemType>) để xây dựng cấu trúc Node và lớp LinkedList, cho phép cấu trúc dữ liệu lưu trữ đa dạng các kiểu dữ liệu khác nhau.
• Kỹ năng thiết kế giải thuật danh sách: Xây dựng thuật toán định vị con trỏ (pPre, p), cập nhật liên kết trong các trường hợp chèn node vào danh sách liên kết rỗng, chèn ở đầu (beginning), chèn ở giữa (middle) và chèn ở cuối (end).

---

Phương pháp giảng dạy và học tập

Phương pháp	Nội dung chi tiết
Tiếp cận sư phạm	Tuân thủ tiến trình sư phạm 4 bước: Đặc tả lý thuyết ADT $\rightarrow$ Biểu diễn mã giả $\rightarrow$ Hiện thực hóa bằng mã C++ $\rightarrow$ Phân tích độ phức tạp Big-O.
Thực hành mã nguồn	Sinh viên trực tiếp xây dựng và biên dịch mã nguồn lớp DynamicArray và LinkedList với các hàm thành phần: insertAt, removeAt, get, set, setCapacity, rangeCheck.
Bài toán ứng dụng	Triển khai mô hình danh sách liên kết để giải quyết bài toán biểu diễn đa thức đại số (Polynomial representation), trong đó mỗi node lưu trữ hệ số và số mũ.
Phương pháp đánh giá	Đánh giá qua bài tập lập trình C/C++, kiểm tra khả năng phân tích chi phí thuật toán, và bài toán tối ưu hóa lựa chọn cấu trúc lưu trữ phù hợp với yêu cầu thực tế.

Trong quá trình tự học, sinh viên cần thực hiện vẽ sơ đồ trạng thái bộ nhớ và con trỏ trước khi viết mã, sau đó kiểm chứng thuật toán bằng cách viết các chương trình thực nghiệm để đo thời gian thực thi của các phương thức.

---

Điểm nổi bật và cập nhật

• Độ chính xác kỹ thuật cao trong mã nguồn: Tài liệu cung cấp cài đặt mã nguồn C++ hoàn chỉnh và tối ưu. Điển hình là việc sử dụng memmove thay vì vòng lặp thủ công khi chèn/xóa phần tử trong DynamicArray, hạn chế lỗi chồng lấn vùng nhớ (memory overlap):

  // Trích đoạn thuật toán insertAt trong tài liệu
  void DynamicArray::insertAt(int index, int value) {
      if (index < 0 || index > size) throw "Index out of bounds!";
      ensureCapacity(size + 1);
      int moveCount = size - index;
      if (moveCount != 0)
          memmove(storage + index + 1, storage + index, sizeof(int) * moveCount);
      storage[index] = value;
      size++;
  }
  

• Áp dụng chuẩn lập trình hiện đại: Cấu trúc dữ liệu danh sách liên kết được chuẩn hóa dưới dạng C++ Template, giúp mã nguồn có tính trừu tượng cao, tái sử dụng được cho nhiều kiểu dữ liệu nguyên thủy hoặc cấu trúc dữ liệu tự định nghĩa.
• Gắn kết với các cấu trúc dữ liệu nâng cao: Phân loại danh sách tuyến tính được liên kết trực tiếp với các cấu trúc dữ liệu trừu tượng tiếp theo trong chương trình như Stack (ngăn xếp), Queue (hàng đợi), Heap, Tree (cây) và Graph (đồ thị).

---

Đối tượng sử dụng giáo trình

• Sinh viên đại học: Sinh viên các học kỳ đầu ngành Khoa học Máy tính, Kỹ thuật Máy tính, Công nghệ Thông tin, Kỹ thuật Phần mềm và Hệ thống Thông tin.
• Điều kiện tiên quyết (Prerequisites):
  • Nắm vững kiến thức lập trình cơ bản và nâng cao với C/C++ (kiểu dữ liệu, cấu trúc điều khiển tuần tự, rẽ nhánh, vòng lặp).
  • Hiểu rõ cơ chế con trỏ (pointers), tham chiếu (references), cấp phát bộ nhớ động (new/delete).
  • Kiến thức căn bản về lập trình hướng đối tượng (Class, Struct, Constructor, Destructor, Access Modifiers).
• Giảng viên: Sử dụng tài liệu làm khung bài giảng chuẩn cho các buổi học lý thuyết và định hướng thực hành tại phòng máy.
• Tài liệu tham khảo chuyên môn: Phục vụ người học tự nghiên cứu nền tảng cấu trúc dữ liệu phục vụ các kỳ thi tuyển dụng kỹ thuật phần mềm hoặc tối ưu hóa mã nguồn.

---

Câu hỏi thường gặp

1. Giáo trình này phù hợp với ai?

Tài liệu được thiết kế cho sinh viên đại học khối ngành Công nghệ Thông tin - Khoa học Máy tính đang theo học học phần Cấu trúc dữ liệu và Giải thuật, cũng như lập trình viên cần củng cố kiến thức nền tảng về tổ chức bộ nhớ và giải thuật.

2. Cần chuẩn bị kiến thức nền tảng nào trước khi học?

Người học cần hoàn thành học phần Kỹ thuật Lập trình hoặc Nhập môn Lập trình, thành thạo ngôn ngữ C/C++, đặc biệt là kỹ thuật thao tác với biến con trỏ, quản lý bộ nhớ động và cú pháp C++ Template.

3. Sự khác biệt cốt lõi giữa Mảng động (Dynamic Array) và Danh sách liên kết đơn (Singly Linked List) là gì?

• Mảng động: Lưu trữ trên vùng nhớ liên tục; truy xuất phần tử ngẫu nhiên đạt thời gian hằng số $O(1)$; thao tác chèn/xóa tốn chi phí $O(n)$ do phải dịch chuyển dữ liệu vật lý.
• Danh sách liên kết: Lưu trữ trên các node phân tán; truy xuất tuần tự qua con trỏ tốn chi phí $O(n)$; thao tác chèn/xóa tại vị trí đã định vị con trỏ đạt chi phí $O(1)$ mà không cần dời chuyển các phần tử khác.

4. Hệ số tăng trưởng dung lượng của mảng động trong tài liệu được tính như thế nào?

Trong phương thức ensureCapacity, khi dung lượng hiện tại không đủ chứa dữ liệu mới, dung lượng mới được tính theo công thức: $$\text{newCapacity} = \frac{\text{capacity} \times 3}{2} + 1$$ tương đương mức tăng trưởng xấp xỉ 1.5 lần, giúp giảm thiểu tần suất cấp phát lại bộ nhớ và sao chép dữ liệu.

5. Có những cấu trúc dữ liệu nào được phát triển tiếp nối từ danh sách tuyến tính?

Từ khái niệm danh sách tuyến tính giới hạn vị trí thao tác (Restricted list), chương trình tiếp tục phát triển cấu trúc Ngăn xếp (Stack - LIFO) và Hàng đợi (Queue - FIFO), sau đó mở rộng sang các cấu trúc phi tuyến như Cây (Tree), Heap và Đồ thị (Graph).

---

Kết luận

Chương 4 "Lists" cung cấp hệ thống lý thuyết chặt chẽ về cấu trúc dữ liệu danh sách tuyến tính, bao gồm định nghĩa kiểu dữ liệu trừu tượng (ADT), hai mô hình cài đặt bộ nhớ chính (mảng liên tục và danh sách liên kết) cùng phương pháp phân tích độ phức tạp thuật toán bằng ký pháp Big-O. Các cài đặt bằng C++ Template và quản lý bộ nhớ cấp thấp trong bài giảng chuẩn hóa nền tảng tư duy lập trình và giải thuật, phục vụ trực tiếp cho việc học tập các cấu trúc dữ liệu nâng cao tiếp theo.