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.
Nội dung chính
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()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 12Nguồn và Tài liệu tiếng anh tham khảo:
Tài liệu từ cafedev:
- Full series tự học Cấu trúc dữ liệu và giải thuật từ cơ bản tới nâng cao tại đây nha.
- Ebook về Cấu trúc dữ liệu và giải thuật tại đây.
- Các series tự học lập trình khác
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:
Chào thân ái và quyết thắng!
 và giải thuật){kind=link}