Chào ace, bài này chúng ta sẽ tìm hiểu về Thao tác xóa node trong danh sách liên kết 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.
Trong các bài trước, chúng ta đã tìm hiểu về danh sách liên kết vòng và cách duyệt qua danh sách liên kết vòng. Trong bài hôm nay, chúng ta sẽ học cách xóa một node khỏi danh sách liên kết vòng. Xét danh sách liên kết vòng như hình vẽ sau:
Giả sử, chúng ta được cho trước một node, và nhiệm vụ cần làm là xóa node đó khỏi danh sách liên kết vòng.
Ví dụ:
Input: 2->5->7->8->10->(head node)
data = 5
Output : 2->7->8->10->(head node)
Input : 2->5->7->8->10->(head node)
data = 7
Output : 2->5->8->10->2(head node)
Thuật toán
1. Trường hợp 1: Danh sách liên kết vòng đang trống
– Nếu danh sách đang trống, chúng ta chỉ cần return.
2. Trường hợp 2: Danh sách liên kết vòng không trống
– Nếu danh sách không trống, chúng ta sẽ khai báo hai con trỏ là curr và prev, rồi khởi tạo con trỏ curr với node head.
– Sử dụng con trỏ curr để duyệt qua danh sách liên kết vòng để tìm thấy node muốn xóa, và bạn cần nhớ là, trước khi di chuyển con trỏ curr tới node tiếp theo, luôn luôn phải thiết lập prev = curr.
– Nếu tìm thấy được node muốn xóa, kiểm tra xem liệu rằng nó có phải node duy nhất trong danh sách mang giá trị mà chúng ta muốn xóa hay không. Nếu nó là node duy nhất mang giá trị mà chúng ta đang muốn xóa, hãy thiết lập cho head = NULL và giải phóng con trỏ curr free(curr).
– Nếu trong danh sách liên kết vòng có nhiều hơn một node mang giá trị mà chúng ta muốn xóa, kiểm tra xem liệu rằng nó có phải là node đầu tiên trong danh sách không, câu lệnh để kiểm tra điều này là (curr == head). Nếu câu lệnh trên là TRUE, chúng ta sẽ di chuyển con trỏ prev cho đến khi đi tới node cuối cùng của danh sách. Sau khi con trỏ prev đã đi tới node cuối cùng của danh sách, chúng ta cần thiết lập head = head -> next và prev -> next = head. Cuối cùng là xóa đi node curr bằng câu lệnh free(curr).
– Nếu curr không phải là node đầu tiên, chúng ta sẽ kiểm tra xem liệu rằng nó có phải node cuối cùng trong danh sách không. Câu lệnh để kiểm tra điều này là (curr -> next == head).
– Nếu curr là node cuối cùng trong danh sách liên kết vòng. Hãy thiết lập prev -> next = head và sau đó xóa đi node curr bằng câu lệnh free(curr).
– Nếu node muốn xóa không phải là node đầu và cũng không phải là node cuối trong danh sách liên kết vòng, vậy thì hãy thiết lập prev -> next = temp -> next và sau đó xóa đi node curr bằng câu lệnh free(curr).
Sau đây là đoạn chương trình hoàn thiện minh họa thao tác xóa node khỏi danh sách liên kết vòng:
ĐOẠN CODE VÍ DỤ ĐƯỢC VIẾT BẰNG NHIỀU NGÔN NGỮ KHÁC NHAU
C
// C program to delete a given key from
// linked list.
#include <stdio.h>
#include <stdlib.h>
/* structure for a node */
struct Node {
int data;
struct Node* next;
};
/* Function to insert a node at the beginning of
a Circular linked list */
void push(struct Node** head_ref, int data)
{
// Create a new node and make head as next
// of it.
struct Node* ptr1 = (struct Node*)malloc(sizeof(struct Node));
ptr1->data = data;
ptr1->next = *head_ref;
/* If linked list is not NULL then set the
next of last node */
if (*head_ref != NULL) {
// Find the node before head and update
// next of it.
struct Node* temp = *head_ref;
while (temp->next != *head_ref)
temp = temp->next;
temp->next = ptr1;
}
else
ptr1->next = ptr1; /*For the first node */
*head_ref = ptr1;
}
/* Function to print nodes in a given
circular linked list */
void printList(struct Node* head)
{
struct Node* temp = head;
if (head != NULL) {
do {
printf("%d ", temp->data);
temp = temp->next;
} while (temp != head);
}
printf("\n");
}
/* Function to delete a given node from the list */
void deleteNode(struct Node* head, int key)
{
if (head == NULL)
return;
// Find the required node
struct Node *curr = head, *prev;
while (curr->data != key) {
if (curr->next == head) {
printf("\nGiven node is not found"
" in the list!!!");
break;
}
prev = curr;
curr = curr->next;
}
// Check if node is only node
if (curr->next == head) {
head = NULL;
free(curr);
return;
}
// If more than one node, check if
// it is first node
if (curr == head) {
prev = head;
while (prev->next != head)
prev = prev->next;
head = curr->next;
prev->next = head;
free(curr);
}
// check if node is last node
else if (curr->next == head) {
prev->next = head;
free(curr);
}
else {
prev->next = curr->next;
free(curr);
}
}
/* Driver program to test above functions */
int main()
{
/* Initialize lists as empty */
struct Node* head = NULL;
/* Created linked list will be 2->5->7->8->10 */
push(&head, 2);
push(&head, 5);
push(&head, 7);
push(&head, 8);
push(&head, 10);
printf("List Before Deletion: ");
printList(head);
deleteNode(head, 7);
printf("List After Deletion: ");
printList(head);
return 0;
}
C++
// C++ program to delete a given key from
// linked list.
#include <bits/stdc++.h>
using namespace std;
/* structure for a node */
class Node {
public:
int data;
Node* next;
};
/* Function to insert a node at the beginning of
a Circular linked list */
void push(Node** head_ref, int data)
{
// Create a new node and make head as next
// of it.
Node* ptr1 = new Node();
ptr1->data = data;
ptr1->next = *head_ref;
/* If linked list is not NULL then set the
next of last node */
if (*head_ref != NULL) {
// Find the node before head and update
// next of it.
Node* temp = *head_ref;
while (temp->next != *head_ref)
temp = temp->next;
temp->next = ptr1;
}
else
ptr1->next = ptr1; /*For the first node */
*head_ref = ptr1;
}
/* Function to print nodes in a given
circular linked list */
void printList(Node* head)
{
Node* temp = head;
if (head != NULL) {
do {
cout << temp->data << " ";
temp = temp->next;
} while (temp != head);
}
cout << endl;
}
/* Function to delete a given node from the list */
void deleteNode(Node** head, int key)
{
// If linked list is empty
if (*head == NULL)
return;
// If the list contains only a single node
if((*head)->data==key && (*head)->next==*head)
{
free(*head);
*head=NULL;
return;
}
Node *last=*head,*d;
// If head is to be deleted
if((*head)->data==key) {
// Find the last node of the list
while(last->next!=*head)
last=last->next;
// Point last node to the next of head i.e.
// the second node of the list
last->next=(*head)->next;
free(*head);
*head=last->next;
}
// Either the node to be deleted is not found
// or the end of list is not reached
while(last->next!=*head&&last->next->data!=key) {
last=last->next;
}
// If node to be deleted was found
if(last->next->data==key) {
d=last->next;
last->next=d->next;
free(d);
}
else
cout<<"no such keyfound";
}
/* Driver program to test above functions */
int main()
{
/* Initialize lists as empty */
Node* head = NULL;
/* Created linked list will be 2->5->7->8->10 */
push(&head, 2);
push(&head, 5);
push(&head, 7);
push(&head, 8);
push(&head, 10);
cout << "List Before Deletion: ";
printList(head);
deleteNode(&head, 7);
cout << "List After Deletion: ";
printList(head);
return 0;
} Java
// Java program to delete a given key from
// linked list.
class GFG {
/* ure for a node */
static class Node {
int data;
Node next;
};
/* Function to insert a node at the beginning of
a Circular linked list */
static Node push(Node head_ref, int data)
{
// Create a new node and make head as next
// of it.
Node ptr1 = new Node();
ptr1.data = data;
ptr1.next = head_ref;
/* If linked list is not null then set the
next of last node */
if (head_ref != null) {
// Find the node before head and update
// next of it.
Node temp = head_ref;
while (temp.next != head_ref)
temp = temp.next;
temp.next = ptr1;
}
else
ptr1.next = ptr1; /*For the first node */
head_ref = ptr1;
return head_ref;
}
/* Function to print nodes in a given
circular linked list */
static void printList(Node head)
{
Node temp = head;
if (head != null) {
do {
System.out.printf("%d ", temp.data);
temp = temp.next;
} while (temp != head);
}
System.out.printf("\n");
}
/* Function to delete a given node from the list */
static Node deleteNode(Node head, int key)
{
if (head == null)
return null;
// Find the required node
Node curr = head, prev = new Node();
while (curr.data != key) {
if (curr.next == head) {
System.out.printf("\nGiven node is not found"
+ " in the list!!!");
break;
}
prev = curr;
curr = curr.next;
}
// Check if node is only node
if (curr.next == head) {
head = null;
return head;
}
// If more than one node, check if
// it is first node
if (curr == head) {
prev = head;
while (prev.next != head)
prev = prev.next;
head = curr.next;
prev.next = head;
}
// check if node is last node
else if (curr.next == head) {
prev.next = head;
}
else {
prev.next = curr.next;
}
return head;
}
/* Driver program to test above functions */
public static void main(String args[])
{
/* Initialize lists as empty */
Node head = null;
/* Created linked list will be 2.5.7.8.10 */
head = push(head, 2);
head = push(head, 5);
head = push(head, 7);
head = push(head, 8);
head = push(head, 10);
System.out.printf("List Before Deletion: ");
printList(head);
head = deleteNode(head, 7);
System.out.printf("List After Deletion: ");
printList(head);
}
} Python
# Python program to delete a given key from
# linked list.
# Node of a doubly linked list
class Node:
def __init__(self, next = None, data = None):
self.next = next
self.data = data
# Function to insert a node at the beginning of
# a Circular linked list
def push(head_ref, data):
# Create a new node and make head as next
# of it.
ptr1 = Node()
ptr1.data = data
ptr1.next = head_ref
# If linked list is not None then set the
# next of last node
if (head_ref != None) :
# Find the node before head and update
# next of it.
temp = head_ref
while (temp.next != head_ref):
temp = temp.next
temp.next = ptr1
else:
ptr1.next = ptr1 # For the first node
head_ref = ptr1
return head_ref
# Function to print nodes in a given
# circular linked list
def printList( head):
temp = head
if (head != None) :
while(True) :
print( temp.data, end = " ")
temp = temp.next
if (temp == head):
break
print()
# Function to delete a given node from the list
def deleteNode( head, key) :
# If linked list is empty
if (head == None):
return
# If the list contains only a single node
if((head).data == key and (head).next == head):
head = None
last = head
d = None
# If head is to be deleted
if((head).data == key) :
# Find the last node of the list
while(last.next != head):
last = last.next
# Point last node to the next of head i.e.
# the second node of the list
last.next = (head).next
head = last.next
# Either the node to be deleted is not found
# or the end of list is not reached
while(last.next != head and last.next.data != key) :
last = last.next
# If node to be deleted was found
if(last.next.data == key) :
d = last.next
last.next = d.next
else:
print("no such keyfound")
return head
# Driver program to test above functions
# Initialize lists as empty
head = None
# Created linked list will be 2.5.7.8.10
head = push(head, 2)
head = push(head, 5)
head = push(head, 7)
head = push(head, 8)
head = push(head, 10)
print("List Before Deletion: ")
printList(head)
head = deleteNode(head, 7)
print( "List After Deletion: ")
printList(head) C#
// C# program to delete a given key from
// linked list.
using System;
class GFG {
/* structure for a node */
public class Node {
public int data;
public Node next;
};
/* Function to insert a node at the beginning of
a Circular linked list */
static Node push(Node head_ref, int data)
{
// Create a new node and make head as next
// of it.
Node ptr1 = new Node();
ptr1.data = data;
ptr1.next = head_ref;
/* If linked list is not null then set the
next of last node */
if (head_ref != null) {
// Find the node before head and update
// next of it.
Node temp = head_ref;
while (temp.next != head_ref)
temp = temp.next;
temp.next = ptr1;
}
else
ptr1.next = ptr1; /*For the first node */
head_ref = ptr1;
return head_ref;
}
/* Function to print nodes in a given
circular linked list */
static void printList(Node head)
{
Node temp = head;
if (head != null) {
do {
Console.Write("{0} ", temp.data);
temp = temp.next;
} while (temp != head);
}
Console.Write("\n");
}
/* Function to delete a given node from the list */
static Node deleteNode(Node head, int key)
{
if (head == null)
return null;
// Find the required node
Node curr = head, prev = new Node();
while (curr.data != key) {
if (curr.next == head) {
Console.Write("\nGiven node is not found"
+ " in the list!!!");
break;
}
prev = curr;
curr = curr.next;
}
// Check if node is only node
if (curr.next == head) {
head = null;
return head;
}
// If more than one node, check if
// it is first node
if (curr == head) {
prev = head;
while (prev.next != head)
prev = prev.next;
head = curr.next;
prev.next = head;
}
// check if node is last node
else if (curr.next == head) {
prev.next = head;
}
else {
prev.next = curr.next;
}
return head;
}
/* Driver code */
public static void Main(String[] args)
{
/* Initialize lists as empty */
Node head = null;
/* Created linked list will be 2.5.7.8.10 */
head = push(head, 2);
head = push(head, 5);
head = push(head, 7);
head = push(head, 8);
head = push(head, 10);
Console.Write("List Before Deletion: ");
printList(head);
head = deleteNode(head, 7);
Console.Write("List After Deletion: ");
printList(head);
}
} Kết quả in ra là:
List Before Deletion: 10 8 7 5 2
List After Deletion: 10 8 5 2Nguồ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}