Trong phần này, chúng ta sẽ tìm hiểu về danh sách tổng quát. Danh sách tổng quát có thể được định nghĩa như sau:
Một danh sách tổng quát L là một dãy hữu hạn gồm n phần tử (n ≥ 0). Phần tử ei là một nguyên tử (phần tử đơn lẻ) hoặc một danh sách tổng quát khác. Các phần tử ei không phải là nguyên tử sẽ là các danh sách con của L. Giả sử L là ((A, B, C), ((D, E), F), G). Tại đây, L có ba phần tử: danh sách con (A, B, C), danh sách con ((D, E), F) và nguyên tử G. Lại nữa, danh sách con ((D, E), F) có hai phần tử: một danh sách con (D, E) và nguyên tử F.
Trong C++, ta có thể định nghĩa cấu trúc danh sách tổng quát như sau:
class GeneralizedListNode {
private:
GeneralizedListNode *next;
bool tag;
union {
char data;
GeneralizedListNode *down;
};
};Nếu tag là true, phần tử được biểu diễn bởi nút là một danh sách con. Con trỏ down trỏ đến nút đầu tiên trong danh sách con. Nếu tag là false, phần tử là nguyên tử. Con trỏ next trỏ đến phần tử tiếp theo trong danh sách. Cấu trúc danh sách sẽ trông như sau:
