Thêm một node vào đầu danh sách

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 << item << " not present in the list." << endl; return last; }

Cuối cùng, bên dưới là đoạn chương trình hoàn thiện, sử dụng tất cả các phương thức/hàm ở  trên để tạo ra một danh sách liên kết đơn dạng vòng:

ĐOẠN CODE VÍ DỤ BẰNG NHIỀU NGÔN NGỮ

C++

#include using namespace std; struct Node { int data; struct Node *next; }; 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 *temp = (struct Node*)malloc(sizeof(struct Node)); // Assigning the data. temp -> data = data; last = temp; // Creating the link. last -> next = last; return last; } struct Node *addBegin(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; 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 << item << " not present in the list." << endl; return last; } void traverse(struct Node *last) { struct Node *p; // If list is empty, return. if (last == NULL) { cout << "List is empty." << endl; return; } // Pointing to first Node of the list. p = last -> next; // Traversing the list. do { cout << p -> data << " "; p = p -> next; } while(p != last->next); } // Driven Program int main() { struct Node *last = NULL; last = addToEmpty(last, 6); last = addBegin(last, 4); last = addBegin(last, 2); last = addEnd(last, 8); last = addEnd(last, 12); last = addAfter(last, 10, 8); traverse(last); return 0; }

Java

class GFG { static class Node { int data; Node next; }; static Node addToEmpty(Node last, int data) { // This function is only for empty list if (last != null) return last; // Creating a node dynamically. Node temp = new Node(); // Assigning the data. temp.data = data; last = temp; // Creating the link. last.next = last; return last; } static Node addBegin(Node last, int data) { if (last == null) return addToEmpty(last, data); Node temp = new Node(); temp.data = data; temp.next = last.next; last.next = temp; return last; } static Node addEnd(Node last, int data) { if (last == null) return addToEmpty(last, data); Node temp = new Node(); temp.data = data; temp.next = last.next; last.next = temp; last = temp; return last; } static Node addAfter(Node last, int data, int item) { if (last == null) return null; Node temp, p; p = last.next; do { if (p.data == item) { temp = new 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); System.out.println(item + " not present in the list."); return last; } static void traverse(Node last) { Node p; // If list is empty, return. if (last == null) { System.out.println("List is empty."); return; } // Pointing to first Node of the list. p = last.next; // Traversing the list. do { System.out.print(p.data + " "); p = p.next; } while(p != last.next); } // Driven code public static void main(String[] args) { Node last = null; last = addToEmpty(last, 6); last = addBegin(last, 4); last = addBegin(last, 2); last = addEnd(last, 8); last = addEnd(last, 12); last = addAfter(last, 10, 8); traverse(last); } }

Python3

class Node: def __init__(self, data): self.data = data self.next = None class CircularLinkedList: def __init__(self): self.last = None # This function is only for empty list def addToEmpty(self, data): if (self.last != None): return self.last # Creating the newnode temp temp = Node(data) self.last = temp # Creating the link self.last.next = self.last return self.last def addBegin(self, data): if (self.last == None): return self.addToEmpty(data) temp = Node(data) temp.next = self.last.next self.last.next = temp return self.last def addEnd(self, data): if (self.last == None): return self.addToEmpty(data) temp = Node(data) temp.next = self.last.next self.last.next = temp self.last = temp return self.last def addAfter(self, data, item): if (self.last == None): return None temp = Node(data) p = self.last.next while p: if (p.data == item): temp.next = p.next p.next = temp if (p == self.last): self.last = temp return self.last else: return self.last p = p.next if (p == self.last.next): print(item, "not present in the list") break def traverse(self): if (self.last == None): print("List is empty") return temp = self.last.next while temp: print(temp.data, end = " ") temp = temp.next if temp == self.last.next: break # Driver Code if __name__ == '__main__': llist = CircularLinkedList() last = llist.addToEmpty(6) last = llist.addBegin(4) last = llist.addBegin(2) last = llist.addEnd(8) last = llist.addEnd(12) last = llist.addAfter(10,8) llist.traverse()

C#

using System; public class GFG { public class Node { public int data; public Node next; }; static Node addToEmpty(Node last, int data) { // This function is only for empty list if (last != null) return last; // Creating a node dynamically. Node temp = new Node(); // Assigning the data. temp.data = data; last = temp; // Creating the link. last.next = last; return last; } static Node addBegin(Node last, int data) { if (last == null) return addToEmpty(last, data); Node temp = new Node(); temp.data = data; temp.next = last.next; last.next = temp; return last; } static Node addEnd(Node last, int data) { if (last == null) return addToEmpty(last, data); Node temp = new Node(); temp.data = data; temp.next = last.next; last.next = temp; last = temp; return last; } static Node addAfter(Node last, int data, int item) { if (last == null) return null; Node temp, p; p = last.next; do { if (p.data == item) { temp = new 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); Console.WriteLine(item + " not present in the list."); return last; } static void traverse(Node last) { Node p; // If list is empty, return. if (last == null) { Console.WriteLine("List is empty."); return; } // Pointing to first Node of the list. p = last.next; // Traversing the list. do { Console.Write(p.data + " "); p = p.next; } while(p != last.next); } // Driven code public static void Main(String[] args) { Node last = null; last = addToEmpty(last, 6); last = addBegin(last, 4); last = addBegin(last, 2); last = addEnd(last, 8); last = addEnd(last, 12); last = addAfter(last, 10, 8); traverse(last); } }

Kết quả in ra là:

2 4 6 8 10 12

Nguồn và Tài liệu tiếng anh tham khảo:

• w3schools
• Geeksforgeeks
• codechef
• dev.to

Tài liệu từ cafedev:

Nếu bạn thấy hay và hữu ích, bạn có thể tham gia các kênh sau của cafedev để nhận được nhiều hơn nữa:

• Group Facebook
• Fanpage
• Youtube
• Instagram
• Twitter
• Linkedin
• Pinterest
• Trang chủ

Chào thân ái và quyết thắng!