Tìm hiều về danh sách liên kết đơn trong C++
Danh sách liên kết đơn trong C++ là gì?
Singly Linked List, tạm dịch là danh sách liên kết đơn, là một dạng cấu trúc dữ liệu động – dữ liệu đệ quy, mỗi phần từ trong danh sách đều có liên kết với phần từ đứng sau. Mỗi phần tử hay còn gọi là node (nút) là một cấu trúc có 2 thành phần chính như sau:
- Dữ liệu: là nơi lưu trữ các thông tin của node đó.
- Con trỏ: là nơi lưu trữ địa chỉ phần tử đứng sau phần tử đó trong danh sách và phần tử cuối cùng sẽ có giá trị bằng null.
Đặc điểm của danh sách liên kết đơn trong C++
Tính liên kết của các phần tử trong danh sách
Trong thành phần của mỗi node, sẽ có liên kết giữa phần tử đứng trước và phần tử đứng sau. Vì thế, người dùng có thể dễ dàng quản lý được danh sách khi nắm được thông tin node đầu và node cuối của danh sách.
Tuy nhiên, người dùng chỉ có thể tìm kiếm node ngẫu nhiên trong danh sách một cách tuyến tính. Do danh sách liên kết đơn trong C++ chỉ có thể duyệt tuyến tính từ phần tử đầu tiên đến phần tử cuối cùng.
Tính cấp phát dữ liệu động
Trong quá trình chạy chương trình, danh sách liên kết đơn trong C++ sẽ được cấp phát bộ nhớ. Các phần tử sẽ được lưu trữ một cách ngẫu nhiên trong RAM, khi bạn thực hiện các thao tác thêm, bớt phần tử; kích thước của danh sách sẽ bị thay đổi.
Kích thước của danh sách liên kết đơn trong C++ sẽ phụ thuộc vào bộ nhớ đang khả dụng của RAM.
So sánh danh sách liên kết đơn và mảng trong C++
Ưu điểm của danh sách liên kết đơn so với mảng trong C++
Sử dụng bộ nhớ tối ưu hơn mảng
Hãy tưởng tượng, bạn là một quản lý trong rạp phim. Phòng chiếu của bạn đang có những vị trí ghế ngồi như trong ảnh.
Một nhóm bạn 16 người yêu cầu phải ngồi gần nhau. Nếu không, họ sẽ không xem phim. Bạn không thể xếp tất cả họ thỏa theo điều kiện ban đầu. Vì thế, bạn sẽ vẫn buộc phải chiếu phim và mất toàn bộ 16 vé đó. Đây là một trường hợp điển hình của mảng – yêu cầu sự liên tiếp với nhau.
Trong trường hợp, những người xem phim có 2 cặp đôi, 2 người đi 1 mình và một nhóm 10 người hoặc tất cả bọn họ đều không yêu cầu đặc biệt về chỗ ngồi. Bạn sẽ có thể sắp xếp cho tất cả bọn họ có thể thưởng thức bộ phim bom tấn yêu thích. Đặc điểm động và mỗi node thường khá nhỏ sẽ giúp danh sách liên kết giải quyết vấn đề về chèn dữ liệu trên.
Dễ dàng thay đổi các phần tử trong danh sách
Quá trình xóa một phần tử trong mảng sẽ diễn ra như sau:
Bạn gán giá trị của J chạy từ i đến n – 1. Sau đó, bạn dồn các phần tử từ vị trí n xuống thành n – 1 để lấp đầy các khoảng trống bị xóa bỏ. Một cách nói khác là bạn sẽ thực hiện cách dồn các phần tử từ vị trí n xuống 1 đơn vị và đè lên vị trí yêu cầu xóa. Tuy nhiên, tại vị trí n vẫn sẽ chiếm dụng bộ nhớ tại đó.
Đối với danh sách liên kết đơn, bạn chỉ cần thay đổi các mối liên kết, giải phóng vùng nhớ của các phần tử bị xóa và bạn chỉ hao tổng chi phí hằng số.
Tuy nhiên, cả mảng lẫn danh sách liên kết đơn, bạn đều sẽ phải hao tổn rất nhiều chi phí do chương trình đều phải dời cả một dãy phần tử từ vị trí chèn/ xóa sáng vị trí +1 hoặc -1.
Nhược điểm của danh sách liên kết đơn so với mảng trong C++
Tùy vào trường hợp, bạn có thể chọn sử dụng mảng hoặc danh sách liên kết vì chúng đều có ưu điểm và nhược điểm riêng. Trong trường hợp này, ưu điểm của mảng lại trở thành nhược điểm rất lớn của danh sách liên kết.
Truy xuất tuyến tính
Mảng sẽ truy xuất tuyến tính, rất đơn giản và dễ dàng bằng các toán tử ngoặc vuông [].
Tuy nhiên, chính đặc điểm của danh sách liên kết lại biến thành một trong những nhược điểm rất lớn của danh sách liên kết.
Để truy xuất 1 một phần tử trong danh sách, bạn chỉ có một lựa chọn duy nhất là duyệt tuyến tính từ đầu đến cuối danh sách và chi phí phải bỏ ra là rất lớn.
Thao tác phức tạp
Để làm việc được với danh sách liên kết đơn, bạn sẽ phải làm việc với con trỏ và phải cực kỳ cẩn thận để tạo ra một danh sách liên kết. Nếu bạn không muốn phải debug thâu đêm, bạn sẽ buộc phải cẩn thận ngay từ đầu để lỗi không thể xảy ra.
Trong khi đó, làm việc với mảng sẽ “dễ chịu” hơn nhiều do không phải “va chạm” với con trỏ C++.
Code mẫu danh sách liên kết đơn trong C++
Trong phần này, Trang thủ thuật sẽ tổng hợp danh sách liên kết đơn trong C++ phổ biến được sử dụng thực tế trong các bài tập, một số công việc đơn giản. Bạn có thể tham khảo và áp dụng vào bài tập nhé!
Thêm node vào đầu/ cuối danh sách
Thêm node vào đầu danh sách
Để thêm một node vào đầu danh sách, bạn chỉ cần kiểm tra danh sách có rỗng hay không:
- Nếu có: dùng head và tail của danh sách bằng node cần chèn
- Nếu không: trỏ node vào liên kết head => gán head bằng 1 node mới.
Code mẫu:
void addFirst(point &head, point &tail, int x)
{
point r = getNode(x);
if(head == NULL)
head = tail = r;
else
{
r->next = head;
head = r;
}
}Thêm node vào cuối danh sách
Tương tự như trên, chúng ta sẽ có code như sau:
void addLast(point &head,point &tail, int x)
{
point r = getNode(x);
if(head == NULL)
head = tail = r;
else
{
tail->next = r;
tail = r;
}
}Thêm node vào sau 1 node
Ví dụ, bạn muốn thêm 1 phần tử có giá trị x vào sau node p, bạn sẽ có code như sau:
void addAfter(point p, int x)
{
point q = getNode(x);
q->next = p->next;
p->next = q;
}Xóa node ở đầu/ cuối danh sách
Xóa node ở đầu danh sách
Để xóa node ở đầu danh sách, ta sẽ kiểm tra xem danh sách có rỗng hay không.
- Nếu danh sách rỗng: trả kết quả = 0, không thực hiện xóa
- Nếu danh sach không rỗng: lưu head lại, gán head bằng next của node head => xóa node head đi.
Code mẫu:
void deleteFirst(point &head)
{
if(head == tail)
{
free(head);
head = tail = NULL;
}
else
{
point temp = head->next;
free(head);
head = temp;
}
}Xóa node ở cuối danh sách
Để xóa node ở cuối danh sách, bạn cũng chỉ cần thực hiện tương tự như với phần đầu
void deleteLast(point &head, point &tail)
{
if(head == tail)
{
free(head);
head = tail = NULL;
}
else
{
point p = head;
while(p->next != NULL)
p = p->next;
free(tail);
tail = p;
p->next = NULL;
}
}Đến đây, Trang thủ thuật đã giúp bạn tìm hiểu về danh sách liên kết đơn trong C++ là gì, ưu điểm và nhược điểm của danh sách liên kết đơn so với mảng trong C++ cũng như một số code mẫu về danh sách liên kết đơn trong C++. Trang thủ thuật hi vọng rằng, những kiến thức này sẽ giúp bạn có thể học tập lập trình tốt hơn!
Bài viết có tham khảo từ: TeKy, TopDev, CodeLearn, Programiz, Learn C,…