“Danh sách liên kết đơn trong C++” hay “Danh sách liên kết đơn” trong các ngôn ngữ lập trình khác là một trong những khái niệm vô cùng quan trọng trong lập trình. Vì thế, trong bài viết này, Tino Group sẽ cùng bạn tìm hiểu về danh sách liên kết đơn trong C++ nhé!
Tóm Tắt
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ó link giữa thành phần đứng trước và thành phần đứng sau. Vì thế, người dùng hoàn toàn có thể thuận tiện quản trị được list khi nắm được thông tin node đầu và node cuối của list .
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.
Bạn đang đọc: Toàn tập danh sách liên kết đơn trong C++
Tính cấp phát dữ liệu động
Trong quy trình chạy chương trình, list link đơn trong C + + sẽ được cấp phép bộ nhớ. Các thành phần sẽ được tàng trữ một cách ngẫu nhiên trong RAM, khi bạn triển khai những thao tác thêm, bớt thành phần ; kích cỡ của list sẽ bị đổi khác .
Kích thước của list link đơn trong C + + sẽ phụ thuộc vào 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 trị 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 những thành phần từ vị trí n xuống thành n – 1 để lấp đầy những khoảng trống bị xóa bỏ. Một cách nói khác là bạn sẽ thực thi cách dồn những thành phần từ vị trí n xuống 1 đơn vị chức năng và đè lên vị trí nhu yếu xóa. Tuy nhiên, tại vị trí n vẫn sẽ chiếm hữu 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 list link đơn, bạn đều sẽ phải hao tổn rất nhiều ngân sách do chương trình đều phải dời cả một dãy thành phần 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 hoàn toàn có thể chọn sử dụng mảng hoặc list link vì chúng đều có ưu điểm và điểm yếu kém riêng. Trong trường hợp này, ưu điểm của mảng lại trở thành điểm yếu kém rất lớn của list link .
Truy xuất tuyến tính
Mảng sẽ truy xuất tuyến tính, rất đơn thuần và thuận tiện bằng những toán tử ngoặc vuông [ ] .
Tuy nhiên, chính đặc thù của list link lại biến thành một trong những điểm yếu kém rất lớn của list link .
Để truy xuất 1 một thành phần trong list, 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 list và ngân sách phải bỏ ra là rất lớn .
Thao tác phức tạp
Để thao tác được với list link đơn, bạn sẽ phải thao tác với con trỏ và phải cực kỳ cẩn trọng để tạo ra một list link. Nếu bạn không muốn phải debug thâu đêm, bạn sẽ buộc phải cẩn trọng ngay từ đầu để lỗi không hề xảy ra .
Trong khi đó, thao tác với mảng sẽ “ dễ chịu và thoải mái ” 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, Tino Group sẽ tổng hợp list link đơn trong C + + phổ cập được sử dụng thực tiễn trong những bài tập, 1 số ít việc làm đơn thuần. Bạn hoàn toàn có thể tìm hiểu thêm và vận 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 list, bạn chỉ cần kiểm tra list 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, tất cả 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 list, ta sẽ kiểm tra xem list 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 list, bạn cũng chỉ cần triển khai tựa như 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, Tino Group đã giúp bạn tìm hiểu và khám phá về list link đơn trong C + + là gì, ưu điểm và điểm yếu kém của list link đơn so với mảng trong C + + cũng như một số ít code mẫu về list link đơn trong C + +. Tino Group hy vọng rằng, những kiến thức và kỹ năng này sẽ giúp bạn hoàn toàn có thể học tập lập trình tốt hơn !
Bài viết có tìm hiểu thêm từ : TeKy, TopDev, CodeLearn, Programiz, Learn C, …
FAQs về danh sách liên kết đơn trong C++
Làm sao để tìm hiểu thêm về danh sách liên kết đơn trong C++?
Nếu tiếng anh của bạn tốt, bạn có thể tra từ khóa Singly Linked list C++ trên Google và tìm hiểu thêm tại các trang lớn chuyên dạy ngôn ngữ lập trình khác nhé!
Vì sao nên học ngôn ngữ C++?
C / C + + là một ngôn từ lập trình nền tảng, khi bạn học thành thạo ngôn từ C / C + +, bạn sẽ hoàn toàn có thể thuận tiện học những ngôn từ lập trình mới được tăng trưởng gần đây .
C / C + + có hiệu suất cùng tính linh động rất cao vì ngôn từ C / C + + thao tác gần với ngôn từ máy hơn những ngôn từ lập trình bậc cao khác .
Học C++ để làm gì?
Nếu bạn yêu dấu việc lập trình nhúng, bạn muốn tăng trưởng những mạng lưới hệ thống, ứng dụng hay game, ngôn từ C / C + + sẽ là ngôn từ lập trình tốt nhất bạn nên học đấy !
Học ngôn ngữ lập trình C++ ở đâu?
Để học ngôn từ lập trình C + + hay bất kể ngôn từ lập trình nào khác, bạn chỉ cần một chiếc máy tính liên kết internet là bạn đã hoàn toàn có thể học trực tuyến trải qua Youtube, những website như : Learn C, Programiz, … Thậm chí có rất nhiều ứng dụng học ngôn từ C / C + + ngay trên thiết bị di động đấy !
CÔNG TY CỔ PHẦN TẬP ĐOÀN TINO
- Trụ sở chính: L17-11, Tầng 17, Tòa nhà Vincom Center, Số 72 Lê Thánh Tôn, Phường Bến Nghé, Quận 1, Thành phố Hồ Chí Minh
Văn phòng đại diện: 42 Trần Phú, Phường 4, Quận 5, Thành phố Hồ Chí Minh - Điện thoại: 0364 333 333
Tổng đài miễn phí: 1800 6734 - Email: [email protected]
- Website: www.tino.org
Source: https://final-blade.com
Category: Kiến thức Internet
