fbpx
close

Toàn tập danh sách liên kết đơn trong C++

Tác giả: TinoHost Ngày cập nhật: 11/10/2021 Chuyên mục: Webmasters
Disclosure
Website Wiki.tino.org được cung cấp bởi Tino Group. Truy cập và sử dụng website đồng nghĩa với việc bạn đồng ý với các điều khoản và điều kiện trong chính sách bảo mật - điều khoản sử dụng nội dung. Wiki.tino.org có thể thay đổi điều khoản sử dụng bất cứ lúc nào. Việc bạn tiếp tục sử dụng Wiki.tino.org sau khi thay đổi có nghĩa là bạn chấp nhận những thay đổi đó.
Why Trust Us
Các bài viết với hàm lượng tri thức cao tại wiki.tino.org được tạo ra bởi các chuyên viên Marketing vững chuyên môn và được kiểm duyệt nghiêm túc theo chính sách biên tập bởi đội ngũ biên tập viên dày dặn kinh nghiệm. Mọi nỗ lực của chúng tôi đều hướng đến mong muốn mang đến cho cộng đồng nguồn thông tin chất lượng, chính xác, khách quan, đồng thời tuân thủ các tiêu chuẩn cao nhất trong báo cáo và xuất bản.

“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 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.
danh-sach-lien-ket-don-trong-c++

Đặ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.

danh-sach-lien-ket-don-trong-c++

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.

danh-sach-lien-ket-don-trong-c++

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ố.

danh-sach-lien-ket-don-trong-c++

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++.

danh-sach-lien-ket-don-trong-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 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 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.
danh-sach-lien-ket-don-trong-c++

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.
Toàn tập danh sách liên kết đơn trong C++ 1

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, Tino Group đã 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++. Tino Group 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,…

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 ngữ lập trình nền tảng, khi bạn học thành thạo ngôn ngữ C/C++, bạn sẽ có thể dễ dàng học những ngôn ngữ lập trình mới được phát triển gần đây.

C/C++ có hiệu suất cùng tính linh hoạt rất cao vì ngôn ngữ C/C++ làm việc gần với ngôn ngữ máy hơn những ngôn ngữ lập trình bậc cao khác.

Học C++ để làm gì?

Nếu bạn yêu thích việc lập trình nhúng, bạn muốn phát triển các hệ thống, phần mềm hay game, ngôn ngữ C/C++ sẽ là ngôn ngữ 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 ngữ lập trình C++ hay bất cứ ngôn ngữ lập trình nào khác, bạn chỉ cần một chiếc máy tính kết nối internet là bạn đã có thể học online thông qua Youtube, các trang web như: Learn C, Programiz, … Thậm chí có rất nhiều ứng dụng học ngôn ngữ C/C++ ngay trên thiết bị di động đấy!

Chia sẻ một chút thông tin về bạn. Những thông tin này có thể được công khai.

Xem thêm bài viết

Bài viết liên quan

Mục lục

Xem nhiều

giá tốt, chất lượng cao mình rất hài lòng
chất lượng dịch vụ tốt lắm...á
chất lượng dịch vụ rất tốt.
giá tốt, chất lượng cao mình rất hài lòng
Dịch vụ chăm sóc khách hàng tốt
Dùng rất oke nha mọi người
Dịch vụ chăm sóc khách hàng tốt, mình rất hài lòng về dịch vụ của TINOHOST
Đã mua rất nhiều tên miền tại Tinohost. Chất lượng tốt
dịch vụ và chăm sóc khách hàng rất tốt , mình rất thích tinohost , mình đã sử dụng nhiều dịch vụ của tinohost rồi
tuyệt vời chăm sóc khách hàng quá tốt
dịch vụ và chăm sóc khách hàng rất tốt , mình rất thích tinohost , mình đã sử dụng nhiều dịch vụ của tinohost rồi
Quá tốt - Quá xuất sắc và tuyệt
Hỗ trợ nhiệt tình. dịch vụ chất lượng
Đội ngũ support rất nhiệt tình.
Sử dụng dịch vụ của bạn Tinohost 2 3 năm nay chưa khi nào phải thất vọng.
host dùng chất lượng, miền giá rẻ
dịch vụ hỗ trợ rất nhanh, tốc độ hosting tốt
Hộ trợ tốt, nhanh. Tuyệt vời 🥰
tuyệt vời, dịch vụ cực tốt và hỗ trợ siêu nhanh
Làm việc nhanh chóng, giá thành hợp lí.
Hosting rẻ và nhanh thích hợp cho học sinh sinh viên như mình
dịch vu tốt ! Sẽ sử dụng thưởng xuyên !
Mỗi lần cần gì, nhắn Tino là được hỗ trợ ngay. Nên một đứa không biết gì về web như mình cũng tạo được blog. Cơ bản mình chỉ lo viết, mọi thứ có anh IT của Tino lo hết.
Nhìn chung thì Tino xứng đáng là một trong những nhà cung cấp host giá rẻ #1 tại VN. Bên này support khá nhanh và nhiệt tình nên quá trình sử dụng diễn ra tương đối trơn tru.
Chất lượng quá ok so với mức giá. Các SME có thể tham khảo để dựng web nhé.
uy tín chất lượng chuẩn cho 5 sao
Dịch vụ nhanh chóng thanh toán tiện lợi
Dịch vụ nhanh chóng, giá cả hợp lý
Chất lượng phục vụ ok, support khá nhanh chóng và chất lượng gói lớn tốt, gói nhỏ cần tốt hơn.
Dịch vụ tốt, giá cả hợp lý👍
Rất hay, rất tốt, rất hữu ích
Hỗ trợ rất nhanh và nhiệt tình
Chất lượng phục vụ ok, support khá nhanh chóng và chất lượng gói lớn tốt, gói nhỏ cần tốt hơn.
dịch vụ tốt, thanh toán nhanh chống
Hài lòng dịch vụ của tinohost
Sau khi sử dụng dịch vụ của TinoHost. Mình thấy website load nhanh hơn hẳn so với sử dụng ở nhà cung cấp cũ. Giá cả do mình đc mua với giá sale 99% của TinoHost nên rất là rẻ. Gói mình mua là gòi Hosting Bussiness 20GB. Thông số cấu hình cao nên web load khá mượt
Chúc TinoHost phát triển!
domain rẻ, có nhiều gói hữu ích thích hợp cho sinh viên
Hài lòng về dịch vụ và tư vấn
Dịch vụ tốt . Support nhiệt tình
Chất lượng OK
Nhanh chóng
dịch vụ rất tốt
Nhân viên support nhanh, hỗ trợ nhiệt tình, giao dịch tự động nên khá tiện
Đã dùng nhiều dịch vụ tại Tinohost, chất lượng tốt, rất hài lòng ...😀
Sự dụng rất hài lòng với các dịch vụ của tinohost
Dịch vụ tốt, uy tín chất lượng
Tino dịch vụ quá tuyệt vời
Giá rẻ, dịch vụ tốt, hỗ trợ nhanh chóng
dịch vụ rất tốt rất tuyệt vời
Giá hợp lý cho người mới dùng
Mình thấy Tinohost có giao diện thân thiện, dễ đăng ký sử dụng cho người mới tập tành làm web như mình. Hosting hỗ trợ có nhiều lựa chọn về dung lượng và giá cả! Thanh toán qua momo thuận tiện. Recommended!
wed quá ok làm việc nhanh ngọn
Dịch vụ tốt. Khá hài lòng vì support nhiệt tình
Dịch vụ quá tuyệt vời danh cho các bạn
Xin cảm ơn đội ngủ kỹ thuật. Các bạn rất chuyên nghiệp và thân thiện. Tôi sẽ giới thiệu các bạn cho bạn bè của mình.
Dịch vụ hỗ trợ tốt, ổn định, thanh toán dễ dàng.
Mình từng dùng VPS bên Vietel IDC, hay gặp lỗi vặt và bảo trì liên tục. Nhưng Tino thì rất ok
dùng tốt, nhanh, dễ sử dụng
Giao diện đẹp mắt, dễ sử dụng
Đề nghị xem lại vấn đề phục vụ khách hàng (livchat)!
Good. Tốc độ cao. Tùy chỉnh nhiều trên shared hosting.
hosting ngon, giá luôn rẻ, tôi làm code nhưng rất thích sài host tino
Tino cung cấp host rất chuyên nghiệp. Đội ngũ kỹ thuật hỗ trợ rất tận tâm và nhiệt tình. Mình sẽ tiếp tục ủng hộ Tino 🥰.
Rất tuyệt vời🙆🙆🙆🙆🙆🙆🙆🙆🙆
Xét về tầm giá thì TinoHost rất đáng để mua và sử dụng lâu dài.
Dịch vụ chất lượng, ủng hộ 1 năm nay rồi
tuyệt vời quá đi,tuyệt vời quá đi
Tốc độ ổn định, tư vấn nhiệt tình
mới tham gia, mong mọi người hỗ trợ thêm
Tốc độ khá tốt với gói rẻ nhất 9k
Giao dịch nhanh,support nhanh và tận tình,chuyển miền nhanh,Hosting Ok
mua sản phẩm dịch vụ tinhot rất tốt tặng ad 5tr ** luon nè🥰🥰🥰
tinohost
một truong những nơi bán hosting rẻ, chất lượng dành cho anh em nào cần để làm web
mua tại : tinohost.com
mình đã mua 2 tên miền + hosting của Tino Host . quả nhiên hiệu quả SEO cải thiện đáng kể và chứng chỉ bảo mật HTTPS miễn phí của Tino Host cũng ko kém phần quang trọng cho việc SEO website của mình
Tino host là một trong nhà cung cấp tốt nhất mình từng sử dụng. Với ưu đãi khuyến mại nhiều, giá thành rẻ kèm theo đó là sự support tuyệt vời của các admin. Nếu ai chưa lựa chọn được nhà cung cấp cho bản thân mình thì Tinohost sẽ là câu trả lời tốt nhất.
dịch vụ tốt, đội ngũ support nhiệt tình, cảm ơn #tinohost
Uy tín, chất lượng, nhân viên hỗ trợ nhiệt tình
mua 2 domain tại tinohost dùng rất chất lượng
Đã mua 02 domain và hosting tại TinoHost, hài lòng cách tư vấn và chăm sóc khách hàng của TinoHost :)
Giá rẻ cấu hình mạnh, black friday là sự bùng nổ của Tino
Hay web bán tài nguyên rất ngon
dịch vụ tốt, mua luôn host chất lượng cao của công ty nhân dịp blackfriday, cảm ơn #tinohost
Dịch vụ rất tốt, nhân viên tận tình.
Hỗ trợ nhiệt tình nhất trong các nhà cung cấp mih từng dùng. Không những server mạnh, ưu đãi có 1 không 2 mà còn nhiều plugin pro bản quyền đính kèm nữa. Quyết định gắn bó "Lifetime" với tino 😁
Dịch vụ tốt hỗ trợ nhanh chóng
Thích cách tư vấn tận tình và nhanh gọn của Tino mỗi khi có vấn đề trục trặc. Hosting ổn định, giá rẻ tốt lắm nhé mọi người
mình có mua 2 tên msiền của tino, mình rât thích cách tư vấn và chăm sóc khách hàng tại đây. Ngoài ra giá domain khá rẻ, phù hợp cho mọi người. 5 sao
Dịch vụ tốt, support nhiệt tình
tinohost tuyệt vời giá cả hợp lý
domain mua rất rẻ :))))
tốt, chất lượng, hostingok
Hosting tốt, giá cả cạnh tranh
Tuyệt vời , Hosting quá ổn
Chất lượng lắm ạ. Domain mua rẻ nhất thị trường
Dịch vụ tốt và chất lượng
Chất lượng lắm ạ. Domain mua rẻ nhất thị trường
Tino Host dùng quá ngon đi !💥💥💥💥💥
Tôi đã mua domain và hosting của các nhà cung cấp khác rồi, nhưng thực sự thấy không tốt bằng Tino, ngoài ra còn hỗ trợ rất tốt. Cảm ơn tino nhiều!
Next Reviews
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é, Q. 1, TP. Hồ Chí Minh

Văn phòng kinh doanh: Số 42 Trần Phú, Phường 4, Quận 5, TP HCM
GPKD số 0315679836 do Sở KH và ĐT TP Hồ Chí Minh cấp
Hotline: 0364 333 333
Góp ý/Phản ánh dịch vụ: 0933 000 886