Chào ace, bài này chúng ta sẽ tìm hiểu về Chèn thêm node mới vào danh sách liên kết đơn dạng vòng trong series tự học về cấu trúc dữ liệu[CTDL] và giải thuật, sau đây cafedev sẽ giới thiệu và chia sẻ chi tiết[khái niệm, độ phức tạp, ứng dụng của nó, code ví dụ…] về nó thông qua các phần sau.
Tại sao lại là “vòng”? Trong một danh sách liên kết đơn bình thường, để truy cập tới bất kỳ node nào của danh sách liên kết, chúng ta đều phải bắt đầu duyệt từ node đầu tiên. Và nếu chúng ta đang đứng tại bất cứ node nào nằm ở giữa danh sách, thì ta sẽ không thể truy cập đến các nodes nằm trước nốt hiện tại. Vấn đề này có thể được giải quyết bằng cách thay đổi một chút cấu trúc của danh sách liên kết đơn. Trong một danh sách liên kết đơn, con trỏ next [con trỏ trỏ đến node tiếp theo] là NULL, nếu chúng ta tận dụng liên kết này để trỏ đến node đầu tiên, thì ta sẽ có thể đi đến các nodes trước đó.
Cấu trúc của danh sách liên kết đơn dạng vòng sẽ giống như sau:
Trong bài này, chúng ta sẽ tìm hiểu về cách cài đặt một danh sách liên kết vòng bằng
danh sách liên kết đơn, và cách chèn thêm một node vào trong danh sách liên kết vòng.
1. Cài đặt danh sách liên kết vòng
Để cài đặt một danh sách liên kết đơn dạng vòng, chúng ta lấy một con trỏ bên ngoài, trỏ
đến node cuối cùng của danh sách. Nếu chúng ta có một con trỏ last, trỏ đến node cuối cùng, thì last -> next sẽ trỏ đến node đầu tiên.
Ta thấy rằng con trỏ last trỏ đến node Z và last -> next sẽ trỏ đến node P.
2. Tại sao cần lấy được một con trỏ trỏ đến node last thay vì trỏ đến node first?
Để chèn thêm node mới vào đầu danh sách, chúng ta cần duyệt qua toàn bộ danh sách.
Và khi muốn chèn thêm node mới vào cuối danh sách thì toàn bộ danh sách cũng phải được duyệt qua. Thay vì sử dụng một con trỏ khởi đầu [start pointer], chúng ta sử dụng một con trỏ khác trỏ đến node last [node cuối cùng của danh sách], làm như vậy thì trong cả hai trường hợp chèn thêm node, chúng ta sẽ không cần phải duyệt qua toàn bộ danh sách nữa. Nhờ vậy, việc chèn thêm node vào đầu hay cuối danh sách đều sẽ chỉ tốn cùng một khoảng thời gian, bất kể danh sách có độ dài thế nào.
3. Chèn thêm node vào danh sách liên kết đơn dạng vòng
Một node mới có thể được chèn vào danh sách liên kết đơn dạng vòng theo các cách sau:
1. Chèn node mới vào một danh sách trống
2. Chèn node mới vào phần đầu danh sách
3. Chèn node mới vào phần cuối danh sách
4. Chèn node mới vào giữa các nodes nào đó.
3.1. Chèn node mới vào một danh sách trống
Lúc đầu, khi danh sách đang trống [empty], con trỏ last sẽ là NULL
Sau khi chèn một node T mới vào:
Sau khi được chèn vào, T sẽ là node cuối cùng của danh sách, nên con trỏ last sẽ trỏ đến T. Lúc này node T vừa là node đầu tiên và vừa là node cuối cùng của danh sách, vì vậy T sẽ trỏ đến chính nó. Dưới đây là đoạn code của hàm có chức năng chèn thêm node mới vào một danh sách liên kết đơn dạng vòng đang trống.
C++
struct Node *addToEmpty[struct Node *last, int data] { // This function is only for empty list if [last != NULL] return last; // Creating a node dynamically. struct Node *last = [struct Node*]malloc[sizeof[struct Node]]; // Assigning the data. last -> data = data; // Note : list was empty. We link single node // to itself. last -> next = last; return last; }3.2. Chèn node mới vào phần đầu danh sách
Để chèn một node mới vào phần đâu của danh sách liên kết đơn dạng vòng, ta cần làm các bước sau:
– Tạo ra một node mới, gọi là node T
– Làm cho T -> next = last -> next
– Cuối cùng, last -> next = T
Sau khi node mới T đã được chèn vào phần đầu danh sách:
Sau đây là đoạn code của hàm có chức năng chèn thêm node mới vào phần đầu của danh sách liên kết đơn dạng vòng:
C++
struct Node *addBegin[struct Node *last, int data] { if [last == NULL] return addToEmpty[last, data]; // Creating a node dynamically. struct Node *temp = [struct Node *]malloc[sizeof[struct Node]]; // Assigning the data. temp -> data = data; // Adjusting the links. temp -> next = last -> next; last -> next = temp; return last; }3.3. Chèn node mới vào phần cuối danh sách
Để chèn một node mới vào phần cuối của danh sách liên kết đơn dạng vòng, ta cần làm các bước sau:
– Tạo ra một node mới, gọi là node T
– Làm cho T -> next = last -> next
– last -> next = T545
– Cuối cùng, last = T
Sau khi node mới T đã được chèn vào phần cuối danh sách:
Sau đây là đoạn code của hàm có chức năng chèn thêm node mới vào phần cuối của danh sách liên kết đơn dạng vòng:
C++
edit play_arrow brightness_4 struct Node *addEnd[struct Node *last, int data] { if [last == NULL] return addToEmpty[last, data]; // Creating a node dynamically. struct Node *temp = [struct Node *]malloc[sizeof[struct Node]]; // Assigning the data. temp -> data = data; // Adjusting the links. temp -> next = last -> next; last -> next = temp; last = temp; return last; }3.4. Chèn thêm node mới vào giữa các nodes nào đó
Để chèn một node mới vào giữa các nodes nào đó, ta cần làm các bước sau:
– Tạo ra một node mới, gọi là node T
– Tìm tới node P mà node T sẽ được chèn vào phía sau node P đó
– Làm cho T -> next = P -> next
– Cuối cùng, P -> next = T
Trong ví dụ dưới đây, giả sử 12 cần được chèn vào giữa 8 và 10:
Sau khi tìm kiếm và thực hiện chèn node:
Dưới đây là đoạn code của hàm có chức năng chèn thêm node mới vào giữa hai nodes nào đó của danh sách liên kết đơn dạng vòng:
C++
struct Node *addAfter[struct Node *last, int data, int item] { if [last == NULL] return NULL; struct Node *temp, *p; p = last -> next; // Searching the item. do { if [p ->data == item] { // Creating a node dynamically. temp = [struct Node *]malloc[sizeof[struct Node]]; // Assigning the data. temp -> data = data; // Adjusting the links. temp -> next = p -> next; // Adding newly allocated node after p. p -> next = temp; // Checking for the last node. if [p == last] last = temp; return last; } p = p -> next; } while [p != last -> next]; cout data = data; temp -> next = last -> next; last -> next = temp; return last; } struct Node *addEnd[struct Node *last, int data] { if [last == NULL] return addToEmpty[last, data]; struct Node *temp = [struct Node *]malloc[sizeof[struct Node]]; temp -> data = data; temp -> next = last -> next; last -> next = temp; last = temp; return last; } struct Node *addAfter[struct Node *last, int data, int item] { if [last == NULL] return NULL; struct Node *temp, *p; p = last -> next; do { if [p ->data == item] { temp = [struct Node *]malloc[sizeof[struct Node]]; temp -> data = data; temp -> next = p -> next; p -> next = temp; if [p == last] last = temp; return last; } p = p -> next; } while[p != last -> next]; cout