Thêm node vào danh sách liên kết

Nội dung chính Show

Thêm node vào đầu danh sách liên kết
Thêm node vào cuối danh sách liên kết
Thêm node vào vị trí bất kỳ trong danh sách liên kết
1. Cài đặt danh sách liên kết vòng
2. Tại sao cần lấy được một con trỏ trỏ đến node last thay vì trỏ đến node first?
3. Chèn thêm node vào danh sách liên kết đơn dạng vòng
3.1. Chèn node mới vào một danh sách trống
3.2. Chèn node mới vào phần đầu danh sách
3.3. Chèn node mới vào phần cuối danh sách
3.4. Chèn thêm node mới vào giữa các nodes nào đó

Chúng ta đã tìm hiểu về Linked list ở bài biết trước. Chúng ta đã biết cấu trúc của một danh sách kết như thế nào rồi. Bây giờ, chúng ta sẽ đi tìm hiểu cách thêm một phần tử vào danh sách sẽ như thế nào nha.

Mình sẽ hướng dẫn 3 cách thêm chính trong danh sách liên kết

Thêm vào đầu danh sách liên kết
Thêm vào cuối danh sách liên kết
Thêm vào vị trí bất kỳ trong danh sách liên kết

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

Để thêm một node vào đầu danh sách liên kết, ta có 3 bước chính.

B1: Khởi tạo new_nodeB2: Lấy con trỏ của new_node trỏ đến phần tử đầu tiên trong danh sách liên kết

B3: Gán head = new_node

/** * Insert to head of Linked list * @Param: T data */ public void addFirst(T data) { Node<T> newNode = new Node<>(data); newNode.setNext(this.head); this.head = newNode; }

Thêm node vào cuối danh sách liên kết

Để thêm một node mới vào cuối danh sách liên kết, ta có 3 bước chính

B1: Khởi tạo new_nodeB2: Lấy con trỏ của phần tử cuối cùng trong mảng trỏ đến new_node

B3: Lấy con trỏ của new_node trỏ đến null

/** * Insert to end of Linked list * @Param: T data */ public void addEnd(T data) { Node<T> newNode = new Node<>(data); // If the Linked list is empty, newNode will be head node if (this.head == null) { this.head = newNode; return; } // Go to the last node Node<T> last = this.head; while (last.getNext() != null) { last = last.getNext(); } // Append newNode to end the linked list last.setNext(newNode); }

Thêm node vào vị trí bất kỳ trong danh sách liên kết

Để thêm một node vào một vị trí bất kỳ, điều kiện đầu tiên là 0 <= pos < size, với size là tổng số lượng phần tử trong danh sách liên kết.

Trường hợp pos = 0, thì chúng ta sẽ quay về lại trường hợp thêm node vào đầu danh sách liên kết.

Chúng ta có các bước làm chính như sau

B1: Khởi tạo new_nodeB2: Lấy con trỏ tại vị trí prefix tại vị trí pos – 1 trỏ đến new_node

B3: Lấy con trỏ của new_node trỏ đến prefix -> next

/** * Insert newNode to a posotion in linked list * @Param: T data, int pos */ public void addPos(T data, int pos) { if (pos < 0) { return; } // If pos is zero, It's add to first if (pos == 0) { this.addFirst(data); return; } int i = 0; Node<T> cur = this.head; while (i < pos - 1 && cur != null) { i++; cur = cur.getNext(); } // pos is outIndex of linked list if (i != pos - 1) { return; } // insert newNode to pos Node<T> newNode = new Node<>(data); newNode.setNext(cur.getNext()); cur.setNext(newNode); }

Link full source code linked list: LinkedList

Would love your thoughts, please comment.x

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<bits/stdc++.h> 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()

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: