Danh sách liên kết đơn [Single Linked List] là một cấu trúc dữ liệu động, nó là một danh sách mà mỗi phần tử đều liên kết với phần tử đúng sau nó trong danh sách. Mỗi phần tử [được gọi là một nút hoặc nút] trong danh sách liên kết đơn là một cấu trúc có hai thành phần
- Data section. lưu thông tin về bản thân phần tử đó
- Thành phần liên kết. lưu địa chỉ phần tử đứng sau trong danh sách, nếu phần tử đó là phần tử cuối cùng thì thành phần này bằng NULL
Tham khảo thêm. công việc lập trình c++ lương cao tại Topdev
Minh họa danh sách liên kết đơn
Đặc điểm của danh sách liên kết đơn
Do danh sách liên kết đơn là một cấu trúc dữ liệu động, được tạo nên nhờ vào việc cấp phát động nên nó có một số đặc điểm sau đây
- Được cấp phát bộ nhớ khi chạy chương trình
- There can change the size through the more, delete the death section
- Kích thước tối đa phụ thuộc vào khả năng sử dụng bộ nhớ của RAM
- Các phần tử được lưu trữ ngẫu nhiên [không liên tiếp] trong RAM
Và tính liên kết của phần tử đầu và phần tử đứng sau nó trong danh sách liên kết đơn, nó có các đặc điểm sau
- Chỉ cần nắm lấy phần đầu và cuối phần tử là có thể quản lý được danh sách
- Truy cập ngẫu nhiên phần tử phải duyệt từ đầu đến vị trí đó
- Chỉ có thể tìm kiếm tuyến tính một phần tử
1001 Mẹo. Con trỏ và hàm [Con trỏ & Hàm] trong C++
Mã game săn mồi trên bảng điều khiển bằng C++
Cài đặt danh sách liên kết đơn
Trước khi vào cài đặt danh sách liên kết đơn, hãy đảm bảo rằng bạn đã nắm giữ phần con trỏ và cấp phát động trong C++. Do danh sách liên kết đơn là một cấu trúc dữ liệu động, nếu bạn không ôm con trỏ và cấp phát động sẽ rất khó để bạn hiểu được bài viết này. Nếu bạn cảm thấy chưa tự tin, hãy dành ít thời gian để xem bài viết này của mình. Còn bây giờ thì bắt đầu thôi
Tạo nút
Danh sách liên kết đơn được tạo thành từ nhiều nút, do đó, chúng ta sẽ cùng đi từ nút trước. Một nút bao gồm hai thành phần là thành phần dữ liệu và thành phần liên kết. Thành phần dữ liệu có thể là kiểu dữ liệu có sẵn hoặc bạn tự định nghĩa [struct hay class…], trong bài viết này để đơn giản mình sẽ sử dụng kiểu int cho phần dữ liệu. Thành phần liên kết là địa chỉ đương nhiên sẽ là con trỏ, con trỏ này trỏ đến nút tiếp theo, do đó, con trỏ này là con trỏ vào một nút
struct Node
{
int data;
Node* next;
};Để tạo một nút mới, ta thực hiện cấp phát động cho nút mới, khởi tạo giá trị ban đầu và trả về địa chỉ của nút mới được cấp phát
Node* CreateNode[int init_data]
{
Node* node = new Node;
node->data = init_data;
node->next = NULL; // node vừa tạo chưa thêm vào danh sách nên chưa liên kết với phần tử nào cả nên phần liên kết gán bằng NULL
return node;
}Tạo danh sách liên kết đơn
Ta đã thành phần tạo nên danh sách liên kết đơn là nút, tiếp theo chúng ta cần quản lý chúng bằng cách biết phần tử đầu và phần cuối. Vì mỗi phần tử đều liên kết với phần tử kế tiếp nên chỉ cần giải thích phần tử đầu và phần cuối là có thể quản lý được danh sách này. This đơn giản ta cần tạo một cấu trúc lưu trữ địa chỉ phần tử đầu [phần đầu] và phần tử cuối [hoặc phần tử đuôi]
struct LinkedList
{
Node* head;
Node* tail;
};Khi mới tạo danh sách, danh sách sẽ không có phần tử nào, đầu và đuôi không trỏ vào đâu cả, ta sẽ gán chúng bằng NULL. Ta build a function to list as after
void CreateList[LinkedList& l]
{
l.head = NULL;
l.tail = NULL;
}Bây giờ để tạo một danh sách, ta làm như sau
LinkedList list;
CreateList[list]; // Gán head và tail bằng NULLThêm phần tử vào danh sách
Thêm vào đầu
Để thêm nút vào đầu danh sách, đầu tiên ta cần tra cứu xem danh sách đó có trống hay không, nếu danh sách trống, ta chỉ cần gán đầu và đuôi của danh sách bằng nút đó. Đảo ngược nếu danh sách không trống, ta thực hiện con trỏ thành phần liên kết vào đầu, sau đó gán lại đầu bằng nút mới
void AddHead[LinkedList& l, Node* node]
{
if [l.head == NULL]
{
l.head = node;
l.tail = node;
}
else
{
node->next = l.head;
l.head = node;
}
}Thêm phần tử vào đầu danh sách liên kết đơn
Như trong hình trên, chúng ta thêm nút có dữ liệu bằng 0 vào danh sách. Ta thực hiện con trỏ tiếp theo của nút đó vào đầu của danh sách [chính là nút đầu tiên của danh sách có dữ liệu bằng 1], sau đó ta trỏ đầu vào nút có dữ liệu 0 vừa được thêm vào. Do đó, phần tử đó đã nằm ở đầu danh sách rồi
Add to end
Tương tự, để thêm nút vào cuối danh sách, đầu tiên ta kiểm tra xem danh sách trống hay không, trống thì gán đầu và đuôi đều bằng nút mới. Nếu không trống, ta thực hiện đuôi trỏ->next vào nút mới, sau đó gán lại đuôi cho nút mới [vì bây giờ nút mới thêm chính là đuôi]
void AddTail[LinkedList& l, Node* node]
{
if [l.head == NULL]
{
l.head = node;
l.tail = node;
}
else
{
l.tail->next = node;
l.tail = node;
}
}Thêm phần tử vào cuối danh sách liên kết đơn
Trong hình trên, chúng ta thực hiện thêm nút có dữ liệu bằng 6 vào danh sách. Tail hiện tại là nút có dữ liệu 5, thực hiện gán tail->next bằng nút mới để nối thêm nó vào đuôi danh sách, lúc này nút mới trở thành phần tử cuối danh sách nên ta gán đuôi lại bằng nút mới
Add to after node any
Để thêm một nút p vào sau nút q bất kỳ, đầu tiên ta cần tra cứu xem nút q có NULL hay không, nếu nút q là NULL tức là danh sách rỗng, vậy thì ta sẽ thêm vào đầu danh sách. If node q not NULL, tức là tồn tại trong danh sách, ta thực hiện cursor p->next = q->next, sau đó q->next = p. Tiếp theo chúng ta kiểm tra xem nút q trước đó có phải là nút cuối hay không, nếu nút q là nút cuối thì thêm p vào, p sẽ thành nút cuối nên ta gán lại đuôi = p
void InsertAfterQ[LinkedList& l, Node* p, Node* q]
{
if [q != NULL]
{
p->next = q->next;
q->next = p;
if [l.tail == q]
l.tail = p;
}
else
AddHead[l, p];
}Thêm phần tử vào sau nút Q trong danh sách liên kết đơn
Trong cấu hình trên, ta thêm nút có dữ liệu bằng 4 [nút p] vào sau nút có dữ liệu bằng 3 [nút q]. Ta trỏ next của node p vào next của node q tức là node có dữ liệu bằng 5, sau đó trỏ next của node q vào node p vậy là node p đã được thêm vào danh sách
Delete the death section from the list
Delete at the head
Để xóa phần tử ở đầu danh sách, ta kiểm tra xem danh sách đó có trống hay không, nếu trống, ta không cần xóa, kết quả trả về là 0. Nếu danh sách không trống, ta thực hiện lưu lại đầu nút, sau đó gán đầu bằng phần tiếp theo của đầu nút, sau đó xóa đầu nút đi. Tiếp theo ta cần kiểm tra xem danh sách vừa bị xóa đi nút đầu có trống hay không, nếu trống ta gán lại đuôi bằng NULL luôn sau đó trả về kết quả 1
Lưu ý trước khi xóa đầu nút đi, ta sử dụng biến tham chiếu x để lưu trữ lại giá trị của nút bị hủy để sử dụng
Xoá phần tử đầu danh sách liên kết đơn
Trong hình trên, mình thực hiện xóa nút đầu tiên có dữ liệu bằng 0. Mình trỏ head đến next của node 0 [hiện đang là head], thì lúc này head sẽ là node 1, sau đó mình hủy đi node 0 là được
Delete at after node any
Để xóa một nút p sau nút q bất kỳ, ta kiểm tra xem nút q có NULL hay không, nếu nút q NULL thì không tồn tại trong danh sách, trả về 0, không xóa. If node q other NULL but next of q is NULL, tức là p bằng NULL, thì không xóa, trả về 0 [do sau q không có nút nào cả, q là đuôi]. Nếu nút p tồn tại, ta thực hiện kiểm tra xem nút p có phải là đuôi hay không, nếu nút p là đuôi thì gán lại đuôi là q, tức là nút trước đó để xóa nút p đi
int RemoveAfterQ[LinkedList& l, Node* q, int& x]
{
if [q != NULL]
{
Node* p = q->next;
if [p != NULL]
{
if [l.tail == p]
l.tail = q;
q->next = p->next;
x = p->data;
delete p;
return 1;
}
return 0;
}
return 0;
}Trong hình trên, ta thực hiện xóa nút có dữ liệu 3 [nút p] sau nút có dữ liệu 2 [nút q]. Ta trỏ next của node q vào next của node p tức là node có dữ liệu 4, sau đó xóa node p đi là xong
Browse the list and in
Sau khi có các thao tác thêm, xóa, chúng ta có thể vào danh sách để kiểm tra xem hoạt động có đúng hay không. To in the list, ta watching from the header to the end list and in time. Ta gán một nút bằng đầu, sau đó kiểm tra xem nút đó có NULL hay không, không thì trong dữ liệu ra của nút đó, sau đó gán tiếp nút đó bằng nút tiếp theo của chính nó tức nút đó bây giờ là nút tiếp theo, cứ
Node* CreateNode[int init_data]
{
Node* node = new Node;
node->data = init_data;
node->next = NULL; // node vừa tạo chưa thêm vào danh sách nên chưa liên kết với phần tử nào cả nên phần liên kết gán bằng NULL
return node;
}Get value node any
Để lấy giá trị của phần tử trong danh sách, ta thực hiện duyệt tương tự như trong phần tử. Ta sẽ tạo một biến đếm để biết vị trí hiện tại, duyệt qua các nút cho đến khi nút bằng NULL hoặc biến đếm bằng với nút vị trí cần lấy. Kiểm tra xem nếu nút khác NULL và biến số đếm bằng vị trí cần lấy, ta sẽ trả về địa chỉ của nút đó, ngược lại trả về NULL [danh sách trống hoặc vị trí cần lấy nằm ngoài phạm vi của danh sách]
Node* CreateNode[int init_data]
{
Node* node = new Node;
node->data = init_data;
node->next = NULL; // node vừa tạo chưa thêm vào danh sách nên chưa liên kết với phần tử nào cả nên phần liên kết gán bằng NULL
return node;
}Tìm kiếm phần tử trong danh sách
Ý tưởng tìm kiếm phần tử cũng là duyệt danh sách, nếu như chưa tìm thấy thì tiếp tục duyệt. Sau khi kết thúc duyệt, ta chỉ cần kiểm tra xem nút duyệt có bằng NULL hay không, nếu không tức là đã tìm thấy, ta sẽ trả về địa chỉ của nút đó
Node* CreateNode[int init_data]
{
Node* node = new Node;
node->data = init_data;
node->next = NULL; // node vừa tạo chưa thêm vào danh sách nên chưa liên kết với phần tử nào cả nên phần liên kết gán bằng NULL
return node;
}Dem number of the list list
Đếm số phần tử thì cũng tương tự, ta áp dụng duyệt từ đầu đếm cuối và nút đếm số
Node* CreateNode[int init_data]
{
Node* node = new Node;
node->data = init_data;
node->next = NULL; // node vừa tạo chưa thêm vào danh sách nên chưa liên kết với phần tử nào cả nên phần liên kết gán bằng NULL
return node;
}Delete the list
Để xóa danh sách, ta cần hủy tất cả các nút tức thời đang duyệt và hủy từng nút. Ở đây mình sẽ dùng lại hàm RemoveHead. Đầu tiên, ta gán node bằng head, kiểm tra xem node đó khác NULL thì gọi RemoveHead và gán lại node bằng head tiếp, cứ lặp như vậy cho đến khi node đó NULL thì thôi. Sau khi xóa hết tất cả các phần tử thì gán lại đuôi bằng NULL
Node* CreateNode[int init_data]
{
Node* node = new Node;
node->data = init_data;
node->next = NULL; // node vừa tạo chưa thêm vào danh sách nên chưa liên kết với phần tử nào cả nên phần liên kết gán bằng NULL
return node;
}Tổng kết
Vì trong bài viết này, mình đã giới thiệu với các bạn về danh sách liên kết đơn và một số thao tác cơ bản trên danh sách. Các bạn không nhất thiết phải làm theo cách của mình, có rất nhiều cách để thực hiện khác nhau, chỉ cần bạn nắm bắt về con trỏ và cấp phát động trong C++. Nếu thấy hay đừng quên Share cho bạn bè nhé. Cảm ơn các bạn đã theo dõi bài viết