Toàn tập danh sách liên kết đơn trong C++
“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 cực kỳ quan trọng trong lập trình. Do đó, trong bài viết này, thuthuatkiemtien.com sẽ cùng các bạn tìm hiểu về danh sách liên kết đơn trong C ++ nhé!
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ì?
Danh sách liên kết Singly, tạm dịch là danh sách liên kết đơn lẻ, là một kiểu cấu trúc dữ liệu động - dữ liệu đệ quy, mỗi từ trong danh sách có một liên kết với từ theo sau. Mỗi phần tử còn được gọi là nút (nút thắt) là một cấu trúc gồm 2 thành phần chính như sau:
- Dữ liệu: là nơi lưu trữ thông tin của nút đó.
- Con trỏ: là nơi lưu địa chỉ của 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 vô giá trị.
Các tính năng của danh sách liên kết đơn trong C ++
Liên kết của các phần tử trong một danh sách
Trong thành phần của mỗi nút sẽ có sự liên kết giữa phần tử trước và phần tử sau. Do đó, người dùng có thể dễ dàng quản lý danh sách khi biết được nút đầu tiên và nút cuối cùng của danh sách.
Tuy nhiên, người dùng chỉ có thể tìm kiếm một cách tuyến tính một nút ngẫu nhiên trong danh sách. Bởi vì một danh sách được liên kết đơn lẻ trong C ++ chỉ có thể truyền tuyến tính từ phần tử đầu tiên đến phần tử cuối cùng.
Phân bổ dữ liệu động
Trong quá trình thực thi chương trình, một 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ữ ngẫu nhiên trong RAM, khi bạn thực hiện các thao tác thêm bớt các phần tử; kích thước của danh sách sẽ được thay đổi.
Kích thước của một danh sách được liên kết đơn lẻ trong C ++ sẽ phụ thuộc vào bộ nhớ 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 trên mảng trong C ++
Sử dụng bộ nhớ tối ưu trên các mảng
Hãy tưởng tượng, bạn là quản lý trong một rạp chiếu phim. Phòng chiếu của bạn có các vị trí ngồi như trong ảnh.
Một nhóm gồm 16 người bạn được yêu cầu ngồi gần nhau. Nếu không, họ sẽ không xem phim. Bạn không thể sắp xếp tất cả chúng theo điều kiện ban đầu. Do đó, bạn vẫn sẽ buộc phải chiếu phim và mất hết 16 vé đó. Đây là một trường hợp điển hình của mảng - yêu cầu tính liên tục.
Trong trường hợp khán giả đi xem phim với 2 cặp đôi, 2 khách lẻ và nhóm 10 người hoặc tất cả, sẽ không có yêu cầu đặc biệt về chỗ ngồi. Bạn sẽ có thể sắp xếp cho tất cả họ để có thể thưởng thức bộ phim bom tấn yêu thích của họ. Đặc tính di chuyển và mỗi nút thường khá nhỏ, điều này giúp danh sách liên kết giải quyết được vấn đề chèn dữ liệu.
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ột 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 xếp chồng các phần tử từ vị trí n xuống đến n - 1 để lấp đầy những khoảng trống đã loại bỏ. Nói cách khác, bạn sẽ thực hiện cách đẩy các phần tử từ vị trí n lên 1 đơn vị và ghi đè lên vị trí yêu cầu xóa. Tuy nhiên, tại vị trí n sẽ vẫn chiếm bộ nhớ ở đó.
Đối với danh sách liên kết duy nhất, bạn chỉ cần thay đổi các liên kết, giải phóng bộ nhớ của các phần tử đã bị xóa và bạn chỉ có chi phí không đổi.
Tuy nhiên, cả mảng và danh sách liên kết đơn, bạn sẽ phải tốn rất nhiều chi phí vì chương trình phải di chuyển cả một mảng phần tử từ vị trí chèn / xóa sang 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 từng 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 nhược điểm riêng. Trong trường hợp này, ưu điểm của mảng 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ẽ được truy cập tuyến tính, rất đơn giản và dễ dàng bằng cách sử dụng các toán tử dấu ngoặc vuông [].
Tuy nhiên, chính đặc điểm của danh sách liên kết lại trở 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 cập một phần tử trong danh sách, bạn chỉ có một lựa chọn, đó là đi tuyến tính từ đầu đến cuối danh sách và chi phí rất lớn.
Hoạt động phức tạp
Để làm việc với các danh sách được liên kết đơn lẻ, bạn sẽ phải làm việc với các con trỏ và cực kỳ cẩn thận để tạo một danh sách được liên kết. Nếu bạn không muốn phải gỡ lỗi cả đêm, bạn sẽ phải cẩn thận ngay từ đầu để lỗi không xảy ra.
Trong khi đó, làm việc với mảng sẽ “dễ chịu” hơn rất nhiều vì không phải “va chạm” với con trỏ C ++.
Mã mẫu cho danh sách liên kết đơn trong C ++
Trong phần này, thuthuatkiemtien.com sẽ tổng hợp danh sách liên kết đơn phổ biến trong C ++ được sử dụng thực tế trong một số bài tập và nhiệm vụ đơn giản. Các bạn có thể tham khảo và áp dụng vào các bài tập của mình nhé!
Thêm nút vào đầu / cuối danh sách
Thêm nút vào đầu danh sách
Để thêm một nút vào đầu danh sách, bạn chỉ cần kiểm tra xem danh sách có trống hay không:
- Nếu có: sử dụng cái đầu và đuôi của danh sách bằng nút cần phải chèn
- Nếu không: trỏ nút tới liên kết đầu => gán đầu bằng một nút mới.
Mã 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 nút vào cuối danh sách
Tương tự như trên, chúng ta sẽ có đoạn mã 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 nút sau 1 nút
Ví dụ: bạn muốn thêm một phần tử có giá trị x sau nút P, bạn sẽ có mã sau:
void addAfter(point p, int x)
point q = getNode(x);
q->next = p->next;
p->next = q;
Xóa nút ở đầu / cuối danh sách
Xóa nút ở đầu danh sách
Để loại bỏ nút ở đầu danh sách, chúng ta sẽ kiểm tra xem danh sách có trống hay không.
- Nếu danh sách trống: trả về kết quả = 0, không thực hiện xóa
- Nếu danh sách không trống: lưu đầu, gán đầu cho đầu tiếp theo của nút đầu => xóa nút đầu.
Mã 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 nút ở cuối danh sách
Để loại bỏ nút ở cuối danh sách, bạn 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;
Trên đây, thuthuatkiemtien.com đã giúp bạn tìm hiểu về danh sách liên kết đơn trong C ++ là gì, ưu 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ố đoạn mã mẫu về danh sách liên kết đơn trong C ++. thuthuatkiemtien.com mong rằng những kiến thức này sẽ giúp bạn học lập trình tốt hơn!
Bài viết có tham khảo từ: TeKy, TopDev, CodeLearn, Programiz, Learn C,…
Câu hỏi thường gặp về danh sách được liên kết đơn lẻ trong C ++
Làm thế nào để 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 cứu từ khóa Singly Danh sách liên kết C ++ trên Google và tìm hiểu thêm tại các trang web tuyệt vời dạy các ngôn ngữ lập trình khác!
Tại sao phải học ngôn ngữ C ++?
C / C ++ là một ngôn ngữ lập trình nền tảng, một khi bạn thành thạo C / C ++, bạn sẽ có thể dễ dàng học các ngôn ngữ lập trình được phát triển gần đây.
C / C ++ có hiệu suất và tính linh hoạt rất cao vì ngôn ngữ C / C ++ hoạt động gần với ngôn ngữ máy hơn các ngôn ngữ lập trình cấp cao khác.
Học C ++ để làm gì?
Nếu bạn yêu thích lập trình nhúng, bạn muốn phát triển hệ thống, phần mềm hay game thì ngôn ngữ C / C ++ sẽ là ngôn ngữ lập trình tốt nhất mà bạn nên học!
Học ngôn ngữ lập trình C ++ ở đâu?
Để học C ++ hay bất kỳ ngôn ngữ lập trình nào khác, bạn chỉ cần có máy tính kết nối internet, có thể học trực tuyến qua Youtube, các trang web như: Học C, Programiz, ... Thậm chí có rất nhiều ứng dụng học ngôn ngữ C / C ++. trên thiết bị di động!
CÔNG TY CỔ PHẦN TẬP ĐOÀN TINO
- Trụ sở chính: L17-11, Lầu 17, Tòa nhà Vincom Center, Số 72 Lê Thánh Tôn, P. Bến Nghé, Q.1, TP.
VPĐD: 42 Trần Phú, P.4, Q.5, TP.HCM - Điện thoại: 0364 333 333
Tổng đài miễn cước: 1800 6734 - Email: sales@tino.org
- Trang web: www.tino.org
Nguồn: Toàn tập danh sách liên kết đơn trong C++Xem thêm nhiều bài viết về : Kiến Thức Cơ Bản
Nhận xét
Đăng nhận xét