Đây là bài viết số 2 thuộc bài học Cấp phát bộ nhớ động và Danh sách liên kết của chuyên đề lập trình C++ cơ bản. Để nắm vững bài viết này, trước tiên các bạn hãy tìm đọc lại các bài viết trước đây gồm các kiến thức liên quan:

• Địa chỉ ảo, Tham chiếu và Con trỏ trong C++.
• Hoạt động nâng cao với con trỏ trong C++.
• Kĩ thuật Cấp phát bộ nhớ động trong C++.

I. Giới thiệu chung

Đối với những ai học lập trình, bất kể cơ bản hay nâng cao, cấu trúc dữ liệu mảng luôn luôn là một cấu trúc dữ liệu được nghiên cứu đầu tiên, vì nó quá đơn giản và quen thuộc. Giả sử chúng ta cần phải lưu trữ một dãy số và tính trung bình cộng của nó, mảng là sự lựa chọn không thể tuyệt vời hơn. Đặc biệt, sức mạnh của mảng đến từ khả năng truy cập vị trí ngẫu nhiên trên mảng bằng chỉ số chỉ trong $O(1)$.

Tuy nhiên, không phải mảng không có hạn chế. Một số vấn đề có thể sinh ra khi sử dụng mảng là:

• Bắt buộc phải biết trước số lượng phần tử của dãy số cần lưu trữ.
• Do các phần tử của mảng được lưu trữ trên một đoạn vị trí liên tiếp nhau trong bộ nhớ máy tính, nên khi cần tăng kích thước mảng hoặc thêm/xóa một phần tử vào vị trí bất kì trong mảng sẽ cần tới độ phức tạp $O(n)$.

Để khắc phục những nhược điểm trên, người ta nghĩ ra một cấu trúc dữ liệu là danh sách liên kết.

Về bản chất, danh sách liên kết có chức năng giống như một mảng dùng để lưu trữ một tập các giá trị có cùng kiểu, nhưng nó được thiết kế để lưu trữ dãy số không biết trước số lượng phần tử hoặc các phần tử thường xuyên thay đổi dựa trên các con trỏ trỏ tới các phần tử trong danh sách. Nhờ thế, khi xóa một phần tử trong danh sách liên kết, nếu ta biết trước con trỏ trỏ vào phần tử đó, thì độ phức tạp của thao tác xóa chỉ là $O(1)$. Ngoài ra, các thao tác chèn phần tử vào đầu/cuối danh sách liên kết cũng có độ phức tạp chỉ là $O(1)$.

Có ba kiểu danh sách liên kết: Danh sách liên kết đơn, Danh sách liên kết đôi và Danh sách liên kết vòng.

Trước khi tìm hiểu về danh sách liên kết, các bạn cần nắm vững kiến thức về con trỏ, bởi vì đây là một cấu trúc dữ liệu hoàn toàn sử dụng con trỏ để cài đặt.

II. Danh sách liên kết đơn

1. Định nghĩa

Danh sách liên kết đơn là một tập hợp các nodes được phân bố ngẫu nhiên trong bộ nhớ, và sắp xếp theo cách sao cho mỗi node chứa một giá trị (data) và một ***con trỏ (next)***. Con trỏ sẽ trỏ đến địa chỉ của phần tử kế tiếp trong danh sách, hoặc trỏ đến địa chỉ NULL nếu như đó là phần tử cuối cùng của danh sách.

Bởi vì mỗi node đều lưu con trỏ tới phần tử tiếp theo trong danh sách, nên chúng ta chỉ cần lưu trữ node đầu tiên là head (cũng là một con trỏ). Nhờ vào node này chúng ta có thể đi tới lần lượt tất cả các node tiếp theo trong danh sách.

Hình ảnh dưới đây mô phỏng một danh sách liên kết đơn gồm $3$ phần tử:

2. Các thao tác của Danh sách liên kết đơn

Trong phần cài đặt, tôi sẽ minh họa các thao tác trên danh sách liên kết với kiểu dữ liệu của từng phần tử là int cho đơn giản. Các bạn có thể thay thế kiểu dữ liệu của các node trong danh sách theo ý của mình tùy vào tình huống.

2.1. Khai báo

Trước hết, ta khai báo một cấu trúc cho một node trong danh sách liên kết:

struct Node
{ int value; struct Node* next; Node() { value = 0; next = NULL; }
}

Mỗi node sẽ có trường $\text{value}$ lưu giá trị và trường $\text{next}$ là một con trỏ kiểu Node trỏ đến một node tiếp theo trong danh sách liên kết.

Danh sách liên kết đặc biệt ở chỗ, ta không cần phải tạo ra một danh sách thực sự như mảng hay vector, mà chỉ cần lưu trữ phần tử đầu tiên của danh sách thôi. Node $\text{head}$ sẽ là phần tử đầu tiên đó.

2.2. Tạo mới một node

Sử dụng một hàm để tạo ra một node mới lưu trữ giá trị $\text{value}$. Mỗi khi một node được tạo ra, ta sẽ cấp phát bộ nhớ động cho nó rồi cho con trỏ $\text{next}$ của nó mặc định trỏ tới NULL. Ta sẽ viết hàm này thành một hàm thành viên của cấu trúc $Node$:

struct Node
{ int value; struct Node* next; Node() { value = 0; next = NULL; } void create_node(int _value) { value = _value; next = NULL; }
};

2.3. Thêm node vào danh sách liên kết

Thêm node vào đầu danh sách liên kết

Để thêm một node vào đầu danh sách, ta cần phải cập nhật lại giá trị $\text{head}$ của danh sách đó. Với một giá trị $\text{value}$ mới, để thêm nó vào đầu danh sách ta làm như sau:

• Tạo node mới $\text{new\_node}$ có $\text{data} = \text{value}$.
• Nếu như $\text{head}$ đang trỏ tới NULL - nghĩa là danh sách đang rỗng, thì ta đặt luôn node mới là $\text{head}$. Ngược lại ta phải thay thế $\text{head}$ cũ thành node mới, thao tác hai bước:
  • Cho $\text{next}$ của $\text{new\_node}$ trỏ tới $\text{head}$ ban đầu.
  • Đặt $\text{head} = \text{new\_node}$.
• Trả về giá trị $\text{head}$ mới cho danh sách liên kết.

Node* add_to_front(int value, Node* head)
{ Node* new_node = create_node(value); if (head == NULL) head = new_node; else { new_node -> next = head; head = new_node; } return head;
}

Thao tác này có độ phức tạp là $O(1)$.

Thêm node vào cuối danh sách liên kết

Chúng ta sẽ cần node đầu tiên $\text{head}$ và giá trị $\text{value}$ cần thêm. Khi đó, làm các thao tác sau:

• Tạo node mới $\text{new\_node}$ với $\text{data} = \text{value}$.
• Nếu $\text{head} =$ NULL nghĩa là danh sách liên kết đang rỗng, ta đặt luôn $\text{head} = \text{new\_node}$.
• Ngược lại, ta duyệt liên tục từ $\text{head}$ tới node cuối cùng của danh sách (node có $\text{next} =$ NULL) và đặt $\text{next}$ của node đó trỏ vào $\text{new\_node}$.
• Cuối cùng trả về giá trị $\text{head}$ mới của danh sách liên kết.

Node* add_to_last(int value, Node* head)
{ // Node mới cần thêm vào. Node* new_node = create_node(value); // Danh sách rỗng thì gán luôn head bằng node mới. if (head == NULL) head = new_node; else { // Ngược lại, tạo một node p để duyệt tới phần tử cuối của danh sách. Node* p = head; while (p -> next != NULL) p = p -> next; // Cho next của phần tử cuối trỏ tới node mới. p -> next = new_node; } return head;
}

Độ phức tạp của thao tác này là $O(n)$.

Thêm một node vào giữa danh sách liên kết

Thao tác này sẽ phức tạp hơn một chút. Giả sử cần thêm một giá trị mới vào vị trí $x$ trên danh sách, ta cần làm như sau:

• Duyệt từ đầu danh sách tới node đang nằm ở vị trí $x - 1$ của danh sách. Giả sử đó là node $Q$ và coi như vị trí của các node trên danh sách sẽ bắt đầu từ $0$.
• Cho trường $\text{next}$ của node mới trỏ tới node mà $Q$ đang trỏ tới.
• Cho trường $\text{next}$ của node $Q$ trỏ tới node mới.

Các bạn chỉ cần lưu ý trường hợp nếu như $x = 0$ hoặc danh sách liên kết đang rỗng thì coi như đó chính là thao tác thêm một node vào đầu danh sách. Còn nếu như duyệt hết danh sách mà không thể tìm ra node $Q,$ thì thao tác chèn đó là một thao tác không hợp lệ, hoặc bạn có thể mặc định chèn vào cuối danh sách.

Hình ảnh dưới đây minh họa cho việc chèn một node vào vị trí thứ $2$ trong danh sách liên kết:

Node* add_to_position(Node* head, int value, int x)
{ // Danh sách đang rỗng hoặc x = 0 thì coi như là chèn vào đầu danh sách. if (x == 0 || head == NULL) // Hoặc x == 1 tùy vào cách đánh số trên danh sách. head = add_to_front(value, head); else { Node* p = head; int k = 0; while (p != NULL && k + 1 != x) { p = p -> next; ++k; } // Không tìm được node ở vị trí x - 1. if (k + 1 != x) { // Thông báo vị trí không hợp lệ cout << "Invalid position\n"; // Hoặc có thể coi như chèn vào cuối danh sách. // head = add_to_last(value, head); } // Chèn node mới vào vị trí x. else { Node* new_node = create_node(value); new_node -> next = p -> next; p -> next = new_node; } } return head;
}

Độ phức tạp của thao tác này là $O(n)$.

2.4. Xóa node khỏi danh sách liên kết

Xóa vị trí đầu

Rất đơn giản, khi xóa vị trí đầu nghĩa là ta thay đổi phần tử $\text{head}$ thành phần tử nó đang trỏ đến. Nghĩa là gán $\text{head} = \text{head} \to \text{next}$.

Sau đó trả về giá trị mới của $\text{head}$. Lưu ý trường hợp danh sách rỗng thì không có gì để xóa cả.

Node* del_front(Node* head)
{ if (head == NULL) cout << "The linked-list is empty!\n"; return (head = head -> next);
}

Thao tác này có độ phức tạp $O(1)$.

Xóa vị trí cuối

Đồng nghĩa với việc giảm kích thước của danh sách liên kết đi $1$ đơn vị. Ta sẽ tìm phần tử áp chót của danh sách liên kết, sau đó cho phần tử đó trỏ tới NULL. Còn nếu như danh sách đang rỗng hoặc chỉ có $1$ phần tử thì ta coi như đó là đang xóa phần tử đầu tiên.

Sau đó ta trả về giá trị mới của $\text{head}$.

Node* del_last(Node* head)
{ if (head == NULL || head -> next == NULL) return del_front(head); Node* p = head; while (p -> next -> next != NULL) p = p -> next; p -> next = NULL; return head;
}

Thao tác này có độ phức tạp $O(n)$.

Xóa node ở vị trí bất kì

Thao tác này cũng khá giống với thao tác xóa node ở vị trí cuối. Nó đơn giản là ta bỏ qua phần tử ở vị trí đó bằng cách cho $\text{next}$ của phần tử trước nó trỏ tới phần tử sau nó.

Tuy nhiên, cần lưu ý trường hợp vị trí cần xóa không tồn tại trong danh sách, đó là khi duyệt hết danh sách mà vẫn chưa tới được phần tử ở trước phần tử cần xóa.

Hình ảnh dưới đây minh họa thao tác xóa một phần tử trong danh sách liên kết (phần tử $\text{tmp}$):

Node* del_at_position(Node* head, int x)
{ if (x == 0 || head == NULL || head -> next == NULL) // Hoặc x == 1 tùy vào cách đánh số trên danh sách. return del_front(head); Node* p = head; int k = 0; while (p -> next -> next != NULL && k != x - 1) { p = p -> next; ++k; } // Đã duyệt tới phần tử áp chót mà vẫn chưa tới được phần tử liền trước // vị trí cần xóa, thì kết luận không tồn tại vị trí cần xóa. if (k != x - 1) cout << "The position is invalid\n"; // Đặt p trỏ tới phần tử liền sau phần tử cần xóa. else p -> next = p -> next -> next; return head;
}

Thao tác này có độ phức tạp $O(n)$. Tuy nhiên, nếu ta biết trước con trỏ trỏ tới phần tử cần xóa thì độ phức tạp sẽ chỉ còn là $O(1)$.

2.5. Lấy giá trị ở vị trí bất kì

Để lấy giá trị ở vị trí $x$ bất kì trên danh sách liên kết, không có cách nào khác ngoài việc duyệt từ đầu danh sách cho tới khi tìm được phần tử ở vị trí $x$. Các thao tác tìm kiếm trên danh sách cũng hoàn toàn tương tự. Có thể thấy, việc tìm kiếm và truy xuất giá trị không phải là một ưu thế của danh sách liên kết.

Dưới đây là code lấy giá trị ở vị trí $x$ bất kì trên danh sách liên kết. Đối với thao tác tìm kiếm một phần tử $\text{value}$ trên danh sách, các bạn cũng làm hoàn toàn tương tự. Ngoài ra, các bạn có thể viết thêm đoạn code kiểm tra vị trí cần truy xuất có hợp lệ hay không.

Node* value_at_index(int x)
{ int k = 0; // Hoặc int k = 1 tùy vào cách đánh số trên danh sách. Node* p = head; while (p -> next != NULL && k != x) { p = p -> next; ++k; } return p -> data;
}

Thao tác này có độ phức tạp $O(n)$.

2.6. Một số thao tác bổ trợ khác

Duyệt danh sách liên kết

Để duyệt và in ra danh sách liên kết, các bạn chỉ cần liên tục gán $\text{head} = \text{head} \to \text{next}$ là có thể làm được. Thao tác này có độ phức tạp $O(n)$.

void print_list(Node* head)
{ for (Node* p = head; p != NULL; p = p -> next) cout << p -> data << ' ';
}

Đếm số phần tử của danh sách liên kết

Cũng giống như duyệt qua danh sách liên kết, nhưng các bạn dùng thêm một biến để đếm số phần tử trong quá trình duyệt.

int get_size(Node* head)
{ int _size = 0; for (Node* p = head; p != NULL; p = p -> next) ++_size; return _size;
}

Nhập danh sách liên kết

Muốn nhập danh sách liên kết, ta chỉ cần nhập từng giá trị và thêm nó vào làm node cuối cùng trong danh sách liên kết. Thao tác này có độ phức tạp $O(n)$ với $n$ là số phần tử nhập vào.

Node* input_linked_list()
{ int n; cin >> n; Node* head = NULL; for (int i = 0; i < n; ++i) { int value; cin >> value; head = add_to_last(value); } return head;
}

Ngoài ra, tất cả các thao tác trên có thể được chỉnh sửa một chút để thu được danh sách liên kết đôi và danh sách liên kết vòng. Các bạn chỉ cần hiểu đơn giản như sau:

• Danh sách liên kết đôi là danh sách mà mỗi node sẽ có thêm một con trỏ $\text{prev}$ để trỏ vào phần tử liền trước nó.
• Danh sách liên kết vòng là danh sách có thêm một liên kết nữa giữa phần tử đầu tiên và phần tử cuối cùng của danh sách để tạo thành vòng tròn.

3. Cài đặt đầy đủ

Do Danh sách liên kết là một cấu trúc dữ liệu cung cấp khá nhiều thao tác đi kèm, nên để thuận tiện khi cài đặt, toàn bộ các thao tác cũng như các trường dữ liệu của nó sẽ được gói gọn trong một struct. Như vậy, các hàm tác động tới con trỏ $head$ sẽ có chút thay đổi ở kiểu hàm, các bạn quan sát chương trình mẫu để hiểu rõ hơn.

Dưới đây là chương trình minh họa cài đặt Danh sách liên kết đơn lưu số nguyên:

// Struct thể hiện một node trên danh sách liên kết.
struct Node
{ int value; struct Node* next; Node() { this -> value = 0; this -> next = NULL; } void create_node(int _value) { value = _value; next = NULL; }
}; // Struct thể hiện 1 danh sách liên kết, với head là node đại diện.
struct LinkedList
{ Node* head = new Node(); LinkedList() { head = NULL; } void add_to_front(int value) { Node* new_node = new Node(); new_node -> create_node(value); if (head == NULL) head = new_node; else { new_node -> next = head; head = new_node; } } void add_to_last(int value) { Node* new_node = new Node(); new_node -> create_node(value); // Danh sách rỗng thì gán luôn head bằng node mới. if (head == NULL) head = new_node; else { // Ngược lại, tạo một node p để duyệt tới phần tử cuối của danh sách. Node* p = new Node(); p = head; while (p -> next != NULL) p = p -> next; // Cho next của phần tử cuối trỏ tới node mới. p -> next = new_node; } } void add_to_position(int value, int x) { // Danh sách đang rỗng hoặc x = 0 thì coi như là chèn vào đầu danh sách. if (x == 0 || head == NULL) // Hoặc x == 1 tùy vào cách đánh số trên danh sách. { add_to_front(value); return; } Node* p = new Node(); p = head; int k = 0; while (p != NULL && k + 1 != x) { p = p -> next; ++k; } // Không tìm được node ở vị trí x - 1. if (k + 1 != x) { // Thông báo vị trí không hợp lệ cout << "Invalid position\n"; // Hoặc có thể coi như chèn vào cuối danh sách. // add_to_last(value); } // Chèn node mới vào vị trí x. else { Node* new_node = new Node(); new_node -> create_node(value); new_node -> next = p -> next; p -> next = new_node; } } void del_front() { if (head == NULL) cout << "The linked-list is empty!\n"; head = head -> next; } void del_last() { if (head == NULL || head -> next == NULL) { del_front(); return; } Node* p = head; while (p -> next -> next != NULL) p = p -> next; p -> next = NULL; } void del_at_position(int x) { if (x == 0 || head == NULL || head -> next == NULL) // Hoặc x == 1 tùy vào cách đánh số trên danh sách. { del_front(); return; } Node* p = head; int k = 0; while (p -> next -> next != NULL && k != x - 1) { p = p -> next; ++k; } // Đã duyệt tới phần tử áp chót mà vẫn chưa tới được phần tử liền trước // vị trí cần xóa, thì kết luận không tồn tại vị trí cần xóa. if (k != x - 1) cout << "The position is invalid\n"; // Đặt p trỏ tới phần tử liền sau phần tử cần xóa. else p -> next = p -> next -> next; } void print_list() { for (Node* p = head; p != NULL; p = p -> next) cout << p -> value << ' '; } int value_at_index(int x) { int k = 0; // Hoặc k = 1 tùy vào cách đánh số trên danh sách. Node* p = head; while (p -> next != NULL && k != x) { p = p -> next; ++k; } return p -> value; } int get_size() { int _size = 0; for (Node* p = head; p != NULL; p = p -> next) ++_size; return _size; } void input_linked_list(int n) { for (int i = 0; i < n; ++i) { int value; cin >> value; add_to_last(value); } }
};

Các bạn có thể xem thêm cài đặt đầy đủ của Danh sách liên kết đôi tại đây.

III. So sánh giữa mảng và danh sách liên kết

Tổng kết lại, ta có bảng so sánh giữa danh sách liên kết và mảng dưới đây:

Đồng thời độ phức tạp của từng thao tác tôi cũng đã đề cập kĩ ở cài đặt. Tùy vào tình huống mà các bạn có thể lựa chọn sử dụng cấu trúc dữ liệu mảng hay danh sách liên kết cho phù hợp.

IV. Bài tập áp dụng

1. DAQuery

Đề bài

Cho một danh sách liên kết $S$ ban đầu rỗng, các phần tử trong danh sách sẽ được đánh số từ vị trí $1$. Bạn cần thực hiện $q$ truy vấn có dạng như sau:

• $1 \ x$: Thêm giá trị $x$ vào đầu $S$.
• $2 \ x$: Thêm giá trị $x$ vào cuối $S$.
• $3$: Xóa giá trị đầu tiên của $S$. Đảm bảo lúc này dãy $S$ khác rỗng.
• $4$: Xóa giá trị cuối cùng của $S$. Đảm bảo lúc này dãy $S$ khác rỗng.
• $5 \ k$: In ra giá trị thứ $k$ của $S$. Đảm bảo $k \le |S|$.

Yêu cầu: Hãy thực hiện tất cả các truy vấn cho trước?

Input:

• Dòng đầu tiên chứa một số nguyên dương $q$ miêu tả số truy vấn.
• Trên $q$ dòng tiếp theo, mỗi dòng biểu diễn một truy vấn.

Ràng buộc:

• Các số trong Input đều là số nguyên.
• $1 \le x,q \le 1000$.

Output:

• In ra kết quả theo thứ tự xuất hiện của các truy vấn loại $5$. Nếu như truy vấn loại $5$ nào không tồn tại đáp án thì đưa ra Can't find the kth element.

Sample Input:

8
1 2
2 3
5 1
3
4
1 2
1 3
5 1

Sample Output:

2
3

Ý tưởng

Ta sử dụng các thao tác cơ bản của danh sách liên kết là Thêm, xóa ở đầu - cuối; Đưa ra giá trị ở vị trí cho trước; Đưa ra kích thước danh sách. Tuy nhiên, trong bài toán này các phần tử của danh sách được đánh số từ vị trí $1,$ nên các bạn phải sửa lại hàm get_value_at_index().

Code mẫu

#include <bits/stdc++.h> using namespace std; // Struct thể hiện một node trên danh sách liên kết.
struct Node
{ int value; struct Node *next; Node() { this -> value = 0; this -> next = NULL; } void create_node(int _value) { value = _value; next = NULL; }
}; // Struct thể hiện 1 danh sách liên kết, với head là node đại diện.
struct LinkedList
{ Node* head = new Node(); LinkedList() { head = NULL; } void add_to_front(int value) { Node* new_node = new Node(); new_node -> create_node(value); if (head == NULL) head = new_node; else { new_node -> next = head; head = new_node; } } void add_to_last(int value) { Node* new_node = new Node(); new_node -> create_node(value); // Danh sách rỗng thì gán luôn head bằng node mới. if (head == NULL) head = new_node; else { // Ngược lại, tạo một node p để duyệt tới phần tử cuối của danh sách. Node* p = new Node(); p = head; while (p -> next != NULL) p = p -> next; // Cho next của phần tử cuối trỏ tới node mới. p -> next = new_node; } } void del_front() { if (head == NULL) cout << "The linked-list is empty!"; head = head -> next; } void del_last() { // Nếu danh sách chỉ có 1 node thì xóa chính node đó. if (head == NULL || head -> next == NULL) { del_front(); return; } Node* p = head; while (p -> next -> next != NULL) p = p -> next; p -> next = NULL; } int value_at_index(int x) { int k = 1; Node* p = head; while (p -> next != NULL && k != x) { p = p -> next; ++k; } return p -> value; } int get_size() { int _size = 0; for (Node* p = head; p != NULL; p = p -> next) ++_size; return _size; }
}; int main()
{ // Tạo một con trỏ đại diện cho Danh sách liên kết. LinkedList* ptr_list1 = new LinkedList(); int q; cin >> q; while (q--) { int type, x; cin >> type; switch (type) { case 1: cin >> x; ptr_list1 -> add_to_front(x); break; case 2: cin >> x; ptr_list1 -> add_to_last(x); break; case 3: ptr_list1 -> del_front(); break; case 4: ptr_list1 -> del_last(); break; case 5: cin >> x; if (ptr_list1 -> get_size() < x) cout << "Can't find the kth element\n"; else cout << ptr_list1 -> value_at_index(x) << '\n'; break; } } return 0;
}

2. Super list

Đề bài

Cho $n$ danh sách liên kết, danh sách thứ $i$ được gọi là $S_i$ và có độ dài $a_i$. Bạn có một danh sách $T$ ban đầu rỗng và cần làm $n$ thao tác sau: Thao tác thứ $i$ được gán bằng $c_i;$ nếu $c_i = 0$ bạn cần chèn $S_i$ vào đầu của $T,$ ngược lại nếu $c_i = 1$ bạn cần chèn $S_i$ vào cuối của $T$.

Yêu cầu: Hãy in ra $T$ sau $n$ thao tác trên?

Input:

• Dòng đầu tiên chứa một số nguyên dương $n$ miêu tả số danh sách liên kết.
• Từ dòng thứ hai tới dòng thứ $2n+1$ có dạng:
  • Dòng thứ $2i$ miêu tả $a_i$.
  • Dòng thứ $2i+1$ gồm $a_i$ số nguyên dương miêu tả $S_i$.
• Dòng tiếp theo gồm $n$ số $c_i$ miêu tả thao tác.

Ràng buộc:

• Các số trong $S_i$ đều là số nguyên trong khoảng $[0,10^9]$.
• $1 \le n \le 100$.
• $1 \le a_i \le 200; \forall i: 1 \le i \le n$.

Output:

• Dòng đầu tiên in ra số lượng phần tử của $T$.
• Dòng thứ hai in ra các phần tử của $T$.

Sample Input:

4
3
1 4 2
2
1 5
3 5 2 1
2
2 6
1 0 0 1

Sample Output:

10
5 2 1 1 5 1 4 2 2 6

Ý tưởng

Ta có thể chèn $S_i$ vào $T$ rất nhanh chỉ bằng vài thao tác. Tuy nhiên, để thuận tiện hơn thì ta sẽ biến đổi danh sách liên kết, lưu thêm một con trỏ $last$ để trỏ vào phần tử cuối cùng của danh sách. Như vậy, ta sẽ biến đổi thao tác add_to_last() đi một chút (do bài này chỉ cần sử dụng thao tác này trong việc thêm phần tử vào danh sách):

void add_to_last(int value)
{ Node* new_node = new Node(); new_node -> create_node(value); // Danh sách rỗng thì gán luôn head và last bằng node mới. if (head == NULL) head = new_node, last = new_node; else { // Ngược lại, tạo một node p để duyệt tới phần tử cuối của danh sách. Node* p = new Node(); p = head; while (p -> next != NULL) p = p -> next; // Cho next của phần tử cuối trỏ tới node mới. // Node cuối cùng của danh sách sẽ là node mới. p -> next = new_node; last = new_node; }
}

Để thuận tiện trong việc quản lý các danh sách $S_i,$ ta dùng một mảng các con trỏ là $\text{ptr\_s}$ - với $\text{ptr\_s}[i]$ là con trỏ kiểm soát danh sách liên kết $S[i]$. Ngoài ra, ta sử dụng con trỏ $\text{ptr\_t}$ để kiểm soát danh sách $T$.

Nếu cần chèn $S_i$ vào đầu $T,$ ta sẽ nối phần tử cuối cùng của $S_i$ với phần tử đầu tiên của $T$. Tức là ta sẽ cho node $last$ của danh sách $S_i$ trỏ tới node $head$ của danh sách $T$ (nhưng nếu $T$ đang rỗng thì gán trực tiếp $T = S_i$), sau đó cập nhật lại node $head$ của $T$ thành node $last$ của $S_i$.

Ngược lại nếu cần chèn $S_i$ vào cuối $T,$ ta nối phần tử cuối cùng của $T$ với phần tử đầu tiên của $S_i$. Tức là ta sẽ cho node $last$ của $T$ trỏ tới node $head$ của $S_i$ (nhưng nếu $T$ đang rỗng thì gán trực tiếp $T = S_i$), sau đó cập nhật lại node $last$ của $T$ thành node $last$ của $S_i$.

Phép nối được thực hiện thông qua các con trỏ kiểm soát các $S_i$ và danh sách $T$.

Code mẫu

#include <bits/stdc++.h> using namespace std; // Struct thể hiện một node trên danh sách liên kết.
struct Node
{ int value; struct Node* next; Node() { value = 0; next = NULL; } void create_node(int _value) { value = _value; next = NULL; }
}; // Struct thể hiện 1 danh sách liên kết, với head là node đầu tiên và last là node cuối cùng.
struct LinkedList
{ Node* head = new Node(); Node* last = new Node(); LinkedList() { head = NULL; last = NULL; } void add_to_last(int value) { Node* new_node = new Node(); new_node -> create_node(value); // Danh sách rỗng thì gán luôn head bằng node mới. if (head == NULL) head = new_node, last = new_node; else { // Ngược lại, tạo một node p để duyệt tới phần tử cuối của danh sách. Node* p = new Node(); p = head; while (p -> next != NULL) p = p -> next; // Cho next của phần tử cuối trỏ tới node mới. // Node cuối cùng của danh sách sẽ là node mới. p -> next = new_node; last = new_node; } } void print_list() { for (Node* p = head; p != NULL; p = p -> next) cout << p -> value << ' '; } int get_size() { int _size = 0; for (Node* p = head; p != NULL; p = p -> next) ++_size; return _size; } void input_linked_list(int n) { for (int i = 0; i < n; ++i) { int value; cin >> value; add_to_last(value); } }
}; // Tạo một mảng con trỏ đại diện cho các danh sách S.
LinkedList* ptr_s[101]; int main()
{ int n; cin >> n; for (int i = 1; i <= n; ++i) { int a; cin >> a; ptr_s[i] = new LinkedList(); // Cấp phát bộ nhớ cho danh sách S[i]. ptr_s[i] -> input_linked_list(a); } LinkedList* ptr_t = new LinkedList(); for (int i = 1; i <= n; ++i) { int c; cin >> c; if (c == 0) { if (ptr_t -> head == NULL) ptr_t = ptr_s[i]; else { ptr_s[i] -> last -> next = ptr_t -> head; ptr_t -> head = ptr_s[i] -> head; } } else { if (ptr_t -> head == NULL) ptr_t = ptr_s[i]; else { ptr_t -> last -> next = ptr_s[i] -> head; ptr_t -> last = ptr_s[i] -> last; } } } cout << ptr_t -> get_size() << endl; ptr_t -> print_list(); return 0;
}

V. Tài liệu tham khảo

• https://nguyenvanhieu.vn/danh-sach-lien-ket-don/
• https://vnoi.info/wiki/algo/data-structures/array-vs-linked-lists.md
• https://viblo.asia/p/linked-list-1Je5E43YlnL

©️ Tác giả: Vũ Quế Lâm từ Viblo