Danh sách liên kết là 1 cấu trúc dữ liệu cơ bản, được sử dụng để khắc phục hạn chế của mảng (cố định về kích thước). C++ nói chung và cụ thể là thư viện STL đã cung cấp sẵn một kiểu dữ liệu List. Tuy nhiên tôi vẫn muốn chia sẻ bài viết này để nêu rõ về bản chất của danh sách liên kết và một số thao tác cơ bản trên nó. Show
Tổ chức danh sách liên kết đơnCũng giống như mảng, danh sách liên kết bao gồm các phần tử, có mối liên hệ với nhau, mỗi phần tử đó là một Node, mỗi Node sẽ lưu trữ 2 thông tin:
 Một cách tổng quát ta có: struct Node { Data info; Node* next; };
Mỗi phần tử trong trong danh sách liên kết đơn là một biến được cấp phát động, danh sách liên kết đơn chính là sự liên kết các biến này với nhau do đó ta hoàn toàn chủ động về số lượng các phần tử. Giả sử Data là int, Node của danh sách liên kết sẽ được định nghĩa như sau: struct Node { int value; Node* next; };Một số thao tác cơ bản trên danh sách liên kết đơnTrong danh sách liên kết đơn, các Node sẽ không được lưu liên tiếp nhau trên bộ nhớ, Node trước sẽ mang thông tin địa chỉ của Node sau, như vậy nếu bạn xử lý lỗi một Node sẽ dẫn đến tình huống xấu là mất thông tin truy cập các Node phía sau. Code cơ bản khi hình thành 1 danh sách liên kết như bên dưới: struct Node { int data; Node* next; Node (int _data) { data = _data; next = nullptr; } }; struct List { Node* head; Node* tail; List() { head = nullptr; tail = nullptr; } };Nếu biết được địa chỉ đầu tiên trong danh sách liên kết ta có thể dựa vào thông tin next để truy xuất đến các phần tử còn lại, do đó ta sẽ dùng một con trỏ head để lưu lại địa chỉ Node đầu tiên của danh sách. tail là 1 trường hợp tối ưu việc truy cập nhanh nhất vào cuối danh sách, do đó bạn không cần thiết phải có tail khi không có nhu cầu, nếu có tail thì bạn phải lưu ý cập nhật lại tail mỗi lần thêm hoặc xóa phần tử ở cuối danh sách. Chèn vào đầu danh sáchNhư đã trình bày ở trên, khi thao tác với mỗi Node trên danh sách liên kết cần thực hiện cẩn thận, đúng thứ tự để tránh mất thông tin của các Node phía sau.
Chèn vào cuối danh sáchChèn vào cuối danh sách chúng ta chỉ cần cập nhập lại con trỏ tail.
Chèn vào danh sách sau một Node q trong danh sáchChèn vào danh sách sau một phần tử q nào đó, chèn vào giữa danh sách không cần cập nhập lại hai con trỏ pHead và pTail tuy nhiên chúng ta cần hết sức cần thận để tránh mất dữ liệu phía sau.
Xóa một phần tử đầu danh sáchXóa 1 phần tử ở đầu danh sách không chỉ đơn giản là cập nhập lại biến con trỏ head, mà ta phải giải phóng được vùng nhớ của Node cần xóa.
Xóa một Node đứng sau Node qĐể xóa một phần tử đứng sau phần tử q, ta thực hiện các bước sau:
Duyệt danh sáchKhi có được giá trị của head ta có thể dựa và thông tin next để duyệt lần lượt các phần tử của danh sách. Node* p; p = list.head; while (p != NULL) { // Process Node p = p->next; }Lời kếtSource code được viết theo hướng cấu trúc để các bạn chưa có khái niệm về hướng đối tượng có thể tiếp cận một cách dễ dàng. Có thể thấy được, danh sách liên kết đã khắc phục được nhược điểm của mảng - đó là kích thước cố định. #include using namespace std; struct Node { int data; Node* next; Node (int _data) { data = _data; next = nullptr; } }; struct List { Node* head; Node* tail; List() { head = nullptr; tail = nullptr; } insertToHead(Node* node) { node->next = head; head = node; } insertToTail(Node* node) { if (tail != nullptr) tail->next = node; else { head = node; tail = node; } } insertAfter(Node* node, Node* q) { if (q != tail) { node->next = q->next; q->next = node; } else { insertToTail(node); } } removeAtHead() { if (head == nullptr) return; Node* temp = head; head = head->next; delete temp; } removeAfter(Node* q) { Node* temp = q->next; q->next = temp->next; delete temp; } iterate() { Node* p; p = head; while (p != NULL) { // TODO: cout << p->value << endl; p = p->next; } } Node* find(int _value) { Node* p; p = head; while (p != NULL) { if (p->value == _value) return p; p = p->next; } return nullptr; } }; // Test int main() { List li; li.insertToHead(3); li.insertToHead(2); li.insertToTail(4); Node* q = li.find(3); li.insertAfter(new Node(9), q); return 0; }
“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++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:
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. 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ảngHã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áchQuá trình xóa một phần tử trong mảng sẽ diễn ra như sau:
QUẢNG CÁO 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ínhMả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++. 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áchThê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:
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áchTươ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 nodeVí 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áchXó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.
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++
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é!
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.
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++ 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! CÔNG TY CỔ PHẦN TẬP ĐOÀN TINO
|
