List

List là một vùng chứa tuần tự tích hợp sẵn trong C++, cho phép cấp phát bộ nhớ không liên tục. Khi nói về list, ta đang nói đến danh sách liên kết kép. Còn một loại danh sách khác gọi là forward list, nghĩa là danh sách liên kết đơn. 

Để mọi thứ rõ ràng hơn. 
Cấu trúc dữ liệu vector cho phép cấp phát bộ nhớ liên tục, nghĩa là mỗi phần tử nằm ngay sau phần tử trước đó trong bộ nhớ.
Trong khi đó, cấu trúc dữ liệu danh sách liên kết có các phần tử gồm một phần dữ liệu (giá trị thực tế) và một con trỏ chứa địa chỉ bộ nhớ của phần tử tiếp theo trong danh sách.

Có hai loại danh sách liên kết trong C++:

• danh sách liên kết kép - list
• danh sách liên kết đơn - forward list

Điểm khác biệt chính giữa danh sách liên kết kép và danh sách liên kết đơn là danh sách liên kết đơn chỉ có thể duyệt theo chiều tiến, nghĩa là mỗi phần tử có giá trị riêng và địa chỉ bộ nhớ của phần tử tiếp theo. Còn các phần tử trong danh sách liên kết kép lưu thông tin để xác định vị trí của phần tử tiếp theo và phần tử trước đó trong danh sách.

Ta sử dụng list (danh sách liên kết kép) và forward list (danh sách liên kết đơn) bằng cách đưa chúng vào tệp bằng các lệnh sau:

#include <list>
#include <forward_list>

Hoặc ta chỉ cần đưa tệp tiêu đề bits/stdc++.h vào.

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

Trước tiên, ta sẽ tìm hiểu về forward list. Có nhiều phương thức dùng với forward list, ta sẽ tìm hiểu những phương thức hữu ích nhất.
Ta khai báo một forward list giống hệt như khi khai báo vector và deque.

forward_list<int> flist = {1, 2, 3};

Ta có thể thêm phần tử bằng phương thức push_front() và xóa phần tử ở đầu bằng pop_front().

flist.push_front(5);
for (int &x : flist) // Chúng ta in ra các phần tử bằng con trỏ có giá trị tăng sau mỗi lần lặp (iteration)
	cout << x << " ";
cout << endl;

flist.pop_front();
for (int &x : flist)
	cout << x << " ";

Output:
5 1 2 3
1 2 3

Các phương thức của forward list

Danh sách liên kết kép

Tiếp theo là list. Cấu trúc dữ liệu list cũng có nhiều phương thức, nhưng bạn sẽ tìm hiểu những phương thức hữu ích nhất. 
Trước tiên, bạn sẽ học cách khai báo một list sau khi thêm thư viện này ở đầu tệp .cpp. 

list<int> list1 = {1, 2, 3};

Ta có thể thêm phần tử vào danh sách bằng phương thức push_front() hoặc push_back().
Tương tự, ta có thể xóa phần tử đầu tiên và cuối cùng bằng phương thức pop_front() và pop_back(), theo thứ tự đó.

list1.push_back(4);
list1.push_front(0);
for (int &x : list1)
	cout << x << " ";
cout << endl;

list1.pop_front();
list1.pop_back();
for (int &x : list1)
	cout << x << " ";

Output:
0 1 2 3 4
1 2 3

Các phương thức của list