Viết chương trình con tìm kiếm và xóa một phần tử trong danh sách liên kết có thứ tự.

Trong danh sách liên kết đơn, để xóa một phần tử (hay một Node) trong danh sách sẽ có 4 trường hợp sảy rả ra:

Xóa phần tử ở đầu danh sách liên kết đơn
Xóa phần tử ở cuối danh sách liên kết đơn
Xóa phần tử có khóa k trong danh sách liên kết đơn
Hủy toàn bộ danh sách liên kết đơn

1.Xóa phần tử ở đầu danh sách liên kết đơn

Danh sách đơn ban đầu của tôi bao gồm các phần tử (hay các node) bên dưới:

Để thực hiện xóa phần tử đầu tiên của danh sách trên ta chỉ cần thực hiện 3 bước:

Bước thứ nhất: Tạo một node p và gán bằng pHead hiện tại của danh sách: p = ds.pHead
Bước thứ hai: Đặt lại phần tử pHead của danh sách bằng phần tử kế sau pHead hiện tại của danh sách: ds.pHead = ds.pHead->next
Bước thứ ba: Gán node p được gán bằng pHead ở bước thứ nhất trỏ đến NULL: p->next = NULLL
Bước thứ tư: Xóa đi node p được gán bằng pHead ở bước thứ nhất: delete p

Để hiểu rõ hơn các bước trên, hãy xem hình dưới đây:

Hàm void XoaDau(LIST &ds) dưới đây thực hiện xóa phần tử (hay node) đầu tiên trong danh sách:

void XoaDau(LIST &ds){ //tao node p NODE *p = new NODE; //gan p bang node pHead dau tien cua danh sach p = ds.pHead; //thay doi lai pHead cua danh sach ds.pHead = ds.pHead->next; //gan node p ban dau tro den NULL p->next = NULL; //xoa node p delete p; }

2.Xóa phần tử ở cuối danh sách liên kết đơn

Để xóa phần tử ở cuối danh sách liên kết đơn, ta cần thực hiện 4 bước sau:

Bước đầu tiên: Tạo một node k và thực hiện duyệt toàn bộ phần tử có trong danh sách liên kết đơn
Bước thứ hai: Kiểm tra duyệt, nếu thực hiện duyệt đến phần tử cuối của danh sách nghĩa là k == ds.pTail thì thực hiện xóa phần tử đó: delete ds.pTail;
Bước thứ ba: Trỏ phần tử đứng trước pTail bằng NULL: k->next = NULL;
Bước thứ tư: Thay đổi lại pTail của danh sách bằng node k

Xem hình dưới đây để hiểu rõ hơn các bước trên:

Hàm void XoaCuoi(LIST &ds) dưới đây thực hiện xóa phần tử (hay node) đầu tiên trong danh sách:

void XoaCuoi(LIST &ds) { //duyet cac phan tu co trong danh sach for(NODE *k = ds.pHead; k != NULL; k = k ->next) { //neu duyet den phan tu pTail cuoi trong danh sach if(k->next == ds.pTail) { //xoa phan tu cuoi delete ds.pTail; //tro phan tu truoc phan tu cuoi ve NULL k->next = NULL; //thay doi lai phan tu cuoi pTail cua danh sach ds.pTail = k; } } }

3.Xóa phần tử có khóa k trong danh sách liên kết đơn

Ở phần 1 và phần 2 ta đã biết cách xóa đi phần tử đầu (pHead) hoặc phần tử cuối (pTail) trong danh sách liên kết đơn. Trong một số trường hợp ta sẽ cần xóa đi một node có một khóa bất kỳ trong danh sách (khóa ở đây ta có thể hiểu là một data nào đó của một node trong danh sách liên kết đơn)

Để xóa một phần tử (hay một node) theo khóa k trong danh sách liên kết đơn, ta sẽ cần thực hiện 3 bước sau:

Bước đầu tiên: Nhập một khóa k (hay có thể hiểu là data) vào để kiếm tra, tạo một node p và một node k: NODE *p, *k;
Bước thứ hai: Duyệt toàn bộ danh sách từ đầu đến cuối danh sách thông qua node k
Bước thứ ba: Nếu khóa k (hay data) nhập vào ở bước 1 trùng với data của node đang duyệt thì gán: p->next = k->next có thể hiểu bước này là gán con trỏ next của node trước khóa k bằng con trỏ next của khóa k. Sau đó thực hiện xóa đi node k: delete k;
Bước thứ tư: Gán lại node p bằng node k: p = k;

Chú ý:

Nếu k (hay data) nhập vào bằng với ds.pHead->data thì gọi hàm xóa đầu void XoaDau(ds), nếu k (hay data) nhập vào bằng với ds.pTail->data thì gọi hàm xóa cuối void XoaCuoi(ds)

Xem hình dưới đây để hiểu rõ hơn các bước trên:

Hàm void XoaKhoaK(LIST &ds, int k) dưới đây thực hiện xóa phần tử có khóa k trong danh sách liên kết đơn. Hàm này cần truyền tham chiếu vào LIST &ds và int data chính là dữ liệu nhập vào để xóa đi node có khóa k trùng với data đó:

void XoaKhoaK(LIST &ds, int data){ //tao node p de luu tru phan tu truoc node k can xoa NODE *p = new NODE; //neu data dau vao bang voi pHead->data thi xoa dau if(ds.pHead->data == data){ //goi ham xoa dau XoaDau(ds); //ket thuc ham return; } //neu data bang voi pTail->data thi xoa cuoi if(ds.pTail->data == data){ //goi ham xoa cuoi XoaCuoi(ds); //ket thuc ham return; } //duyet qua cac phan tu co trong danh sach for(NODE *k = ds.pHead; k != NULL; k=k->next){ //neu tim thay data trung voi k->data dang duyet if(k->data == data){ //gan con tro next cua node p bang con tro next cua node k p->next = k->next; //xoa di node k delete k; //ket thuc ham return; } //gan node p bang node k de node p luon la node dung truoc node k p = k; } }

4.Hủy toàn bộ danh sách liên kết đơn

Với 3 cách xóa ở trên, ta chỉ xóa đi một phần tử trong một lần chạy chương trình. Giả sử ta không cần sử dụng danh sách liên kết đơn nữa và ta cần xóa đi tất cả các node trong danh sách ta sẽ thực hiện hủy từng node có trong danh sách liên kết đơn đó.

Để thực hiện việc hủy danh sách, ta cần thực hiện 3 bước:

Bước đầu tiên: Duyệt toàn bộ danh sách từ đầu đến cuối danh sách
Bước thứ hai: Tạo một node p và gán bằng node đầu danh (pHead) sách: p = ds.pHead;
Bước thứ ba: gán phần tử đầu danh sách bằng node p trỏ đến next: ds.pHead = p->next
Bước thứ tư: Xóa đi node p ở bước 2: delete p; và gán phần tử cuối danh sách bằng NULL: ds.pTail = NULL;

Hàm void HuyDS(LIST &ds) dưới đây thực hiện việc xóa toàn bộ các node có trong danh sách liên kết đơn.

void HuyDS(LIST &ds){ //duyet toan bo danh sach for(NODE *k = ds.pHead; k != NULL; k = k ->next) { //tao node p gan bang phan tu dau danh sach Node *p = ds.pHead; //gan phan tu dau danh sach bang p->next ds.pHead = p->next; //xoa di node p delete p; } //gan phan tu cuoi danh sach ve NULL ds.pTail = NULL; }

Danh sách liên kết đơn | Khiêm Lê

Danh sách liên kết đơn (Single Linked List) là một cấu trúc dữ liệu động, nó là một danh sách mà mỗi phần tử đều liên kết với phần tử đúng sau nó trong danh sách. Mỗi phần tử (được gọi là một node hay nút) trong danh sách liên kết đơn là một cấu trúc có hai thành phần:

Thành phần dữ liệu: lưu thông tin về bản thân phần tử đó.
Thành phần liên kết: lưu địa chỉ phần tử đứng sau trong danh sách, nếu phần tử đó là phần tử cuối cùng thì thành phần này bằng NULL.

Minh họa danh sách liên kết đơn

Đặc điểm của danh sách liên kết đơn

Do danh sách liên kết đơn là một cấu trúc dữ liệu động, được tạo nên nhờ việc cấp phát động nên nó có một số đặc điểm sau đây:

Được cấp phát bộ nhớ khi chạy chương trình
Có thể thay đổi kích thước qua việc thêm, xóa phần tử
Kích thước tối đa phụ thuộc vào bộ nhớ khả dụng của RAM
Các phần tử được lưu trữ ngẫu nhiên (không liên tiếp) trong RAM

Và do tính liên kết của phần tử đầu và phần tử đứng sau nó trong danh sách liên kết đơn, nó có các đặc điểm sau:

Chỉ cần nắm được phần tử đầu và cuối là có thể quản lý được danh sách
Truy cập tới phần tử ngẫu nhiên phải duyệt từ đầu đến vị trí đó
Chỉ có thể tìm kiếm tuyến tính một phần tử

Cài đặt danh sách liên kết đơn

Trước khi đi vào cài đặt danh sách liên kết đơn, hãy chắc chắn rằng bạn đã nắm vững phần con trỏ và cấp phát động trong C++. Do danh sách liên kết đơn là một cấu trúc dữ liệu động, nếu bạn không nắm vững con trỏ và cấp phát động sẽ rất khó để bạn hiểu được bài viết này. Nếu bạn cảm thấy chưa tự tin, hãy dành ít thời gian để xem bài viết này của mình. Còn bây giờ thì bắt đầu thôi!

Tạo node

Danh sách liên kết đơn được tạo thành từ nhiều node, do đó, chúng ta sẽ cùng đi từ node trước. Một node gồm hai thành phần là thành phần dữ liệu và thành phần liên kết. Thành phần dữ liệu có thể là kiểu dữ liệu có sẵn hoặc bạn tự định nghĩa (struct hay class…), trong bài viết này để đơn giản mình sẽ sử dụng kiểu int cho phần dữ liệu. Thành phần liên kết là địa chỉ đương nhiên sẽ là con trỏ, con trỏ này trỏ đến node tiếp theo, do đó, con trỏ này là con trỏ trỏ vào một node.

struct Node { int data; Node* next; };

Để tạo một node mới, ta thực hiện cấp phát động cho node mới, khởi tạo giá trị ban đầu và trả về địa chỉ của node mới được cấp phát.

Node* CreateNode(int init_data) { Node* node = new Node; node->data = init_data; node->next = NULL; // node vừa tạo chưa thêm vào danh sách nên chưa liên kết với phần tử nào cả nên phần liên kết gán bằng NULL return node; }

Tạo danh sách liên kết đơn

Ta đã có được thành phần tạo nên danh sách liên kết đơn là node, tiếp theo chúng ta cần quản lý chúng bằng cách biết được phần tử đầu và cuối. Vì mỗi phần tử đều liên kết với phần tử kế vậy nên tả chỉ cần biết phần tử đầu và cuối là có thể quản lý được danh sách này. Vậy đơn giản ta cần tạo một cấu trúc lưu trữ địa chỉ phần tử đầu (head) và phần tử cuối (hay phần tử đuôi tail).

struct LinkedList { Node* head; Node* tail; };

Khi mới tạo danh sách, danh sách sẽ không có phần tử nào, do đó head và tail không trỏ vào đâu cả, ta sẽ gán chúng bằng NULL. Ta xây dựng hàm tạo danh sách như sau:

void CreateList(LinkedList& l) { l.head = NULL; l.tail = NULL; }

Bây giờ để tạo một danh sách, ta làm như sau:

LinkedList list; CreateList(list); // Gán head và tail bằng NULL

Thêm phần tử vào danh sách

Thêm vào đầu

Để thêm node vào đầu danh sách, đầu tiên ta cần kiếm tra xem danh sách đó có rỗng hay không, nếu danh sách rỗng, ta chỉ cần gán head và tail của danh sách bằng node đó. Ngược lại nếu danh sách không rỗng, ta thực hiện trỏ thành phần liên kết vào head, sau đó gán lại head bằng node mới.

void AddHead(LinkedList& l, Node* node) { if (l.head == NULL) { l.head = node; l.tail = node; } else { node->next = l.head; l.head = node; } }

Thêm phần tử vào đầu danh sách liên kết đơn

Như trong hình trên, chúng ta thêm node có data bằng 0 vào danh sách. Ta thực hiện trỏ next của node đó vào head của danh sách (chính là node đầu tiên của danh sách có data bằng 1), sau đó ta trỏ head vào node có data 0 vừa được thêm. Vậy là phần tử đó đã nằm ở đầu danh sách rồi.

Thêm vào cuối

Tương tự, để thêm node vào cuối danh sách, đầu tiên ta kiểm tra xem danh sách rỗng hay không, rỗng thì gán head và tail đều bằng node mới. Nếu không rỗng, ta thực hiện trỏ tail->next vào node mới, sau đó gán lại tail bằng node mới (vì bây giờ node mới thêm chính là tail).

void AddTail(LinkedList& l, Node* node) { if (l.head == NULL) { l.head = node; l.tail = node; } else { l.tail->next = node; l.tail = node; } }

Thêm phần tử vào cuối danh sách liên kết đơn

Trong hình trên, chúng ta thực hiện thêm node có data bằng 6 vào danh sách. Tail hiện tại là node có data 5, thực hiện gán tail->next bằng node mới để nối thêm nó vào đuôi danh sách, lúc này node mới trở thành phần tử cuối danh sách nên ta gán tail lại bằng node mới.

Thêm vào sau node bất kỳ

Để thêm một node p vào sau node q bất kỳ, đầu tiên ta cần kiếm tra xem node q có NULL hay không, nếu node q là NULL tức là danh sách rỗng, vậy thì ta sẽ thêm vào đầu danh sách. Nếu node q không NULL, tức là tồn tại trong danh sách, ta thực hiện trỏ p->next = q->next, sau đó q->next = p. Tiếp theo chúng ta kiểm tra xem node q trước đó có phải là node cuối hay không, nếu node q là node cuối thì thêm p vào, p sẽ thành node cuối nên ta gán lại tail = p.

void InsertAfterQ(LinkedList& l, Node* p, Node* q) { if (q != NULL) { p->next = q->next; q->next = p; if (l.tail == q) l.tail = p; } else AddHead(l, p); }

Thêm phần tử vào sau nút Q trong danh sách liên kết đơn

Trong hình trên, ta thêm node có data bằng 4 (node p) vào sau node có data bằng 3 (node q). Ta trỏ next của node p vào next của node q tức là node có data bằng 5, sau đó trỏ next của node q vào node p vậy là node p đã được thêm vào danh sách.

Xóa phần tử khỏi danh sách

Xóa ở đầu

Để xóa phần tử ở đầu danh sách, ta kiểm tra xem danh sách đó có rỗng hay không, nếu rỗng, ta không cần xóa, trả về kết quả là 0. Nếu danh sách không rỗng, ta thực hiện lưu node head lại, sau đó gán head bằng next của node head, sau đó xóa node head đi. Tiếp theo ta cần kiểm tra xem danh sách vừa bị xóa đi node head có rỗng hay không, nếu rỗng ta gán lại tail bằng NULL luôn sau đó trả về kết quả 1.

int RemoveHead(LinkedList& l, int& x) { if (l.head != NULL) { Node* node = l.head; x = node->data; // Lưu giá trị của node head lại l.head = node->next; delete node; // Hủy node head đi if (l.head == NULL) l.tail = NULL; return 1; } return 0; }

Lưu ý trước khi xóa node head đi, ta dùng biến tham chiếu x để lưu trữ lại giá trị của node bị hủy để sử dụng.

Xóa phần tử đầu danh sách liên kết đơn

Trong hình trên, mình thực hiện xóa node đầu tiên có data bằng 0. Mình trỏ head đến next của node 0 (hiện đang là head), thì head lúc này sẽ là node 1, sau đó mình hủy đi node 0 là được.

Xóa ở sau node bất kỳ

Để xóa một node p sau node q bất kỳ, ta kiểm tra xem node q có NULL hay không, nếu node q NULL thì không tồn tại trong danh sách, do đó trả về 0, không xóa. Nếu node q khác NULL nhưng next của q là NULL, tức là p bằng NULL thì không xóa, trả về 0 (do sau q không có node nào cả, q là tail). Nếu node p tồn tại, ta thực hiện kiểm tra xem node p có phải là tail hay không, nếu node p là tail thì gán lại tail là q, tức là node trước đó để xóa node p đi.

int RemoveAfterQ(LinkedList& l, Node* q, int& x) { if (q != NULL) { Node* p = q->next; if (p != NULL) { if (l.tail == p) l.tail = q; q->next = p->next; x = p->data; delete p; return 1; } return 0; } return 0; }

Xóa phần tử sau nút Q trong danh sách liên kết đơn

Trong hình trên, ta thực hiện xóa node có data 3 (node p) sau node có data 2 (node q). Ta trỏ next của node q vào next của node p tức là node có data 4, sau đó xóa node p đi là xong.

Duyệt danh sách và in

Sau khi có các thao tác thêm, xóa, chúng ta có thể in ra danh sách để kiểm tra xem có hoạt động đúng hay không. Để in danh sách, ta duyệt từ đầu đến cuối danh sách và in ra trong lúc duyệt. Ta gán một node bằng head, sau đó kiểm tra xem node đó có NULL hay không, không thì in ra data của node đó, sau đó gán tiếp node đó bằng next của chính nó tức node đó bây giờ là node tiếp theo, cứ như vậy cho đến hết.

void PrintList(LinkedList l) { if (l.head != NULL) { Node* node = l.head; while (node != NULL) { cout << node->data << ' '; node = node->next; // Chuyển sang node tiếp theo } } }

Lấy giá trị node bất kỳ

Để lấy giá trị phần tử trong danh sách, ta thực hiện duyệt tương tự như khi in phần tử. Ta sẽ tạo một biến đếm để biết vị trí hiện tại, duyệt qua các node cho đến khi node bằng NULL hoặc biến đếm bằng với vị trí node cần lấy. Kiểm tra xem nếu node khác NULL và biến đếm bằng vị trí cần lấy, ta sẽ trả về địa chỉ của node đó, ngược lại trả về NULL (danh sách rỗng hoặc là vị trí cần lấy nằm ngoài phạm vi của danh sách).

Node* GetNode(LinkedList& l, int index) { Node* node = l.head; int i = 0; while (node != NULL && i != index) { node = node->next; i++; } if (i == index && node != NULL) return node; return NULL; }

Tìm kiếm phần tử trong danh sách

Ý tưởng tìm kiếm phần tử cũng là duyệt danh sách, nếu như chưa tìm thấy thì tiếp tục duyệt. Sau khi kết thúc duyệt, ta chỉ cần kiểm tra xem node duyệt có bằng NULL hay không, nếu không tức là đã tìm thấy, ta sẽ trả về địa chỉ của node đó.

Node* Search(LinkedList l, int x) { Node* node = l.head; while (node != NULL && node->data != x) node = node->next; if (node != NULL) return node; return NULL; }

Đếm số phần tử của danh sách

Đếm số phần tử thì cũng tương tự, ta áp dụng duyệt từ đầu đếm cuối và đếm số node.

int Length(LinkedList l) { int count = 0; Node* node = l.head; while (node != NULL) { count++; node = node->next; } return count; }

Xóa danh sách

Để xóa danh sách, ta cần hủy tất cả các node tức là duyệt và hủy từng node. Ở đây mình sẽ dùng lại hàm RemoveHead. Đầu tiên, ta gán một node bằng head, kiểm tra nếu node đó khác NULL thì gọi RemoveHead và gán lại node bằng head tiếp, cứ lặp như vậy cho đến khi node đó NULL thì thôi. Sau khi xóa hết tất cả phần tử thì gán lại tail bằng NULL.

void DestroyList(LinkedList& l) { int x; Node* node = l.head; while (node != NULL) { RemoveHead(l, x); node = l.head; } l.tail = NULL; }

Tổng kết

Vậy là trong bài này, mình đã giới thiệu với các bạn về danh sách liên kết đơn và một số thao tác cơ bản trên danh sách. Các bạn không nhất thiết phải làm theo cách của mình, có rất nhiều cách để thực hiện khác nhau, chỉ cần bạn nắm vững về con trỏ và cấp phát động trong C++. Nếu thấy hay, đừng quên chia sẻ cho bạn bè. Cảm ơn các bạn đã theo dõi bài viết!

Source code

#ifndef LinkedList_hpp #define LinkedList_hpp struct Node { int data; Node* next; }; struct LinkedList { Node* head; Node* tail; }; Node* CreateNode(int init_data); void CreateList(LinkedList& l); void AddHead(LinkedList& l, Node* node); void AddTail(LinkedList& l, Node* node); void InsertAfterQ(LinkedList& l, Node* p, Node* q); int RemoveHead(LinkedList& l, int& x); int RemoveTail(LinkedList& l, int& x); int RemoveAfterQ(LinkedList& l, Node* q, int& x); Node* GetNode(LinkedList l, int index); void PrintList(LinkedList l); Node* Search(LinkedList l, int x); int Length(LinkedList l); void DestroyList(LinkedList& l); #endif #include <iostream> #include "LinkedList.hpp" using namespace std; Node* CreateNode(int init_data) { Node* node = new Node; node->data = init_data; node->next = NULL; return node; } void CreateList(LinkedList& l) { l.head = NULL; l.tail = NULL; } void AddHead(LinkedList& l, Node* node) { if (l.head == NULL) { l.head = node; l.tail = node; } else { node->next = l.head; l.head = node; } } void AddTail(LinkedList& l, Node* node) { if (l.head == NULL) { l.head = node; l.tail = node; } else { l.tail->next = node; l.tail = node; } } void InsertAfterQ(LinkedList& l, Node* p, Node* q) { if (q != NULL) { p->next = q->next; q->next = p->next; if (l.tail == q) l.tail = p; } else AddHead(l, p); } int RemoveHead(LinkedList& l, int& x) { if (l.head != NULL) { Node* node = l.head; x = node->data; l.head = node->next; delete node; if (l.head == NULL) l.tail = NULL; return 1; } return 0; } int RemoveAfterQ(LinkedList& l, Node* q, int& x) { if (q != NULL) { Node* p = q->next; if (p != NULL) { if (l.tail == p) l.tail = q; q->next = p->next; x = p->data; delete p; return 1; } return 0; } return 0; } Node* GetNode(LinkedList l, int index) { Node* node = l.head; int i = 0; while (node != NULL && i != index) { node = node->next; i++; } if (i == index && node != NULL) return node; return NULL; } void PrintList(LinkedList l) { if (l.head != NULL) { Node* node = l.head; while (node != NULL) { cout << node->data << ' '; node = node->next; } } } Node* Search(LinkedList l, int x) { Node* node = l.head; while (node != NULL && node->data != x) node = node->next; if (node != NULL) return node; return NULL; } int Length(LinkedList l) { int count = 0; Node* node = l.head; while (node != NULL) { count++; node = node->next; } return count; } void DestroyList(LinkedList& l) { int x; Node* node = l.head; while (node != NULL) { RemoveHead(l, x); node = l.head; } l.tail = NULL; } #include <iostream> #include "LinkedList.hpp" using namespace std; int main() { // Create a linked list LinkedList list; CreateList(list); // Add sample data to list Node* node; for (auto i = 1; i <= 10; i++) { // Create new node with init data is i node = CreateNode(i); // Add node to head // List that is added node by AddHead will be reversed //AddHead(list, node); // Add node to Tail AddTail(list, node); } // Print list PrintList(list); cout << endl; // Get list's length int len = Length(list); cout << "Length of list: " << len << endl; // Get node at index 7 Node* nodeAtIdx7 = GetNode(list, 7); if (nodeAtIdx7 != NULL) cout << "Data at node have idx 7: " << nodeAtIdx7->data << endl; // Search for 4 in list Node* search4InList = Search(list, 4); if (search4InList != NULL) cout << "4 was founded" << endl; else cout << "4 not Found" << endl; // Remove node after 4 in list int x; int res = RemoveAfterQ(list, search4InList, x); if (res) { cout << "Data of node has been removed: " << x << endl; cout << "List after removed: "; PrintList(list); cout << endl; } else cout << "Nothing is removed" << endl; // Insert 2409 after node 4 Node* node2409 = CreateNode(2409); InsertAfterQ(list, node2409, search4InList); cout << "List after insert 2409 after 4: "; PrintList(list); cout << endl; // Remove Head res = RemoveHead(list, x); if (res) { cout << "Data of node has been removed: " << x << endl; cout << "List after removed head: "; PrintList(list); cout << endl; } else cout << "Nothing is removed" << endl; // Destroy all node DestroyList(list); return 0; }