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 vòng được sắp xếp 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 bài học này, chúng ta sẽ tìm hiểu về cách để chèn thêm một node chứa giá trị mới vào trong một danh sách liên kết vòng được sắp xếp (sorted Circular Linked List).
Ví dụ, nếu danh sách liên kết vòng được xét và Sau khi chèn thêm node chứa giá trị 8 vào, danh sách liên kết vòng ban đầu sẽ trở thành:
Thuật toán
Chúng ta sẽ cấp phát bộ nhớ cho node mới được chèn thêm vào, và đặt dữ liệu/giá trị mong muốn vào node mới được cấp phát đó. Đặt tên con trỏ trỏ đến node mới đó là new_node. Sau khi cấp phát bộ nhớ xong, chúng ta sẽ phải xử lý một trong 3 trường hợp dưới đây:
Nội dung chính
1. Danh sách liên kết vòng đang trống
a) Bởi vì new_node là node duy nhất trong danh sách liên kết vòng hiện tại, cho nên node tiếp theo trong danh sách liên kết, chính là bản thân node new_node, ta sẽ tạo ra một liên kết vòng:
new_node->next = new_node;
b) Thay đổi con trỏ head để trỏ đến node mới được thêm vào danh sách liên kết:
*head_ref = new_node;
2. Node mới sẽ được chèn vào ngay trước node head
a) Tìm ra node cuối cùng của danh sách liên kết bằng cách sử dụng một vòng lặp.
while(current->next != *head_ref)
current = current->next;
b) Thay đổi con trỏ next (trỏ đến node tiếp theo) của node cuối cùng của danh sách liên kết.
current->next = new_node;
c) Thay đổi con trỏ next của node mới được chèn vào, để trỏ đến node head.
new_node->next = *head_ref;
d) Thay đổi con trỏ head để trỏ đến node mới được chèn vào.
*head_ref = new_node;
3. Node mới được chèn vào nơi nào đó, nằm sau node head
a) Định vị được vị trí của node mà ngay sau node đó, node mới sẽ được chèn vào.
while ( current->next!= *head_ref &&
current->next->data data)
{ current = current->next; }
b) Làm cho con trỏ next của new_node trở nên giống với con trỏ next của con trỏ vừa được định vị ở bước a)
new_node->next = current->next;
c) Thay đổi con trỏ next của con trỏ được định vị ở bước a)
current->next = new_node;
Ví dụ chèn thêm node mới vào trong danh sách liên kết vòng đã được sắp xếp được viết bằng ngôn ngữ C++:
// C++ program for sorted insert
// in circular linked list
#include <bits/stdc++.h>
using namespace std;
/* structure for a node */
class Node
{
public:
int data;
Node *next;
};
/* function to insert a new_node in a list in sorted way.
Note that this function expects a pointer to head node
as this can modify the head of the input linked list */
void sortedInsert(Node** head_ref, Node* new_node)
{
Node* current = *head_ref;
// Case 1 of the above algo
if (current == NULL)
{
new_node->next = new_node;
*head_ref = new_node;
}
// Case 2 of the above algo
else if (current->data >= new_node->data)
{
/* If value is smaller than head's value then
we need to change next of last node */
while(current->next != *head_ref)
current = current->next;
current->next = new_node;
new_node->next = *head_ref;
*head_ref = new_node;
}
// Case 3 of the above algo
else
{
/* Locate the node before the point of insertion */
while (current->next!= *head_ref &&
current->next->data < new_node->data)
current = current->next;
new_node->next = current->next;
current->next = new_node;
}
}
/* Function to print nodes in a given linked list */
void printList(Node *start)
{
Node *temp;
if(start != NULL)
{
temp = start;
do {
cout<<temp->data<<" ";
temp = temp->next;
} while(temp != start);
}
}
/* Driver code */
int main()
{
int arr[] = {12, 56, 2, 11, 1, 90};
int list_size, i;
/* start with empty linked list */
Node *start = NULL;
Node *temp;
/* Create linked list from the array arr[].
Created linked list will be 1->2->11->12->56->90 */
for (i = 0; i< 6; i++)
{
temp = new Node();
temp->data = arr[i];
sortedInsert(&start, temp);
}
printList(start);
return 0;
} Sau đây là ví dụ được viết bằng ngôn ngữ C:
#include<stdio.h>
#include<stdlib.h>
/* structure for a node */
struct Node
{
int data;
struct Node *next;
};
/* function to insert a new_node in a list in sorted way.
Note that this function expects a pointer to head node
as this can modify the head of the input linked list */
void sortedInsert(struct Node** head_ref, struct Node* new_node)
{
struct Node* current = *head_ref;
// Case 1 of the above algo
if (current == NULL)
{
new_node->next = new_node;
*head_ref = new_node;
}
// Case 2 of the above algo
else if (current->data >= new_node->data)
{
/* If value is smaller than head's value then
we need to change next of last node */
while(current->next != *head_ref)
current = current->next;
current->next = new_node;
new_node->next = *head_ref;
*head_ref = new_node;
}
// Case 3 of the above algo
else
{
/* Locate the node before the point of insertion */
while (current->next!= *head_ref &&
current->next->data < new_node->data)
current = current->next;
new_node->next = current->next;
current->next = new_node;
}
}
/* Function to print nodes in a given linked list */
void printList(struct Node *start)
{
struct Node *temp;
if(start != NULL)
{
temp = start;
printf("\n");
do {
printf("%d ", temp->data);
temp = temp->next;
} while(temp != start);
}
}
/* Driver program to test above functions */
int main()
{
int arr[] = {12, 56, 2, 11, 1, 90};
int list_size, i;
/* start with empty linked list */
struct Node *start = NULL;
struct Node *temp;
/* Create linked list from the array arr[].
Created linked list will be 1->2->11->12->56->90 */
for (i = 0; i< 6; i++)
{
temp = (struct Node *)malloc(sizeof(struct Node));
temp->data = arr[i];
sortedInsert(&start, temp);
}
printList(start);
return 0;
}
Và tiếp theo là ví dụ được minh họa bằng Java:
// Java program for sorted insert in circular linked list
class Node
{
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
class LinkedList
{
Node head;
// Constructor
LinkedList() { head = null; }
/* function to insert a new_node in a list in sorted way.
Note that this function expects a pointer to head node
as this can modify the head of the input linked list */
void sortedInsert(Node new_node)
{
Node current = head;
// Case 1 of the above algo
if (current == null)
{
new_node.next = new_node;
head = new_node;
}
// Case 2 of the above algo
else if (current.data >= new_node.data)
{
/* If value is smaller than head's value then
we need to change next of last node */
while (current.next != head)
current = current.next;
current.next = new_node;
new_node.next = head;
head = new_node;
}
// Case 3 of the above algo
else
{
/* Locate the node before the point of insertion */
while (current.next != head &&
current.next.data < new_node.data)
current = current.next;
new_node.next = current.next;
current.next = new_node;
}
}
// Utility method to print a linked list
void printList()
{
if (head != null)
{
Node temp = head;
do
{
System.out.print(temp.data + " ");
temp = temp.next;
} while (temp != head);
}
}
// Driver code to test above
public static void main(String[] args)
{
LinkedList list = new LinkedList();
// Creating the linkedlist
int arr[] = new int[] {12, 56, 2, 11, 1, 90};
/* start with empty linked list */
Node temp = null;
/* Create linked list from the array arr[].
Created linked list will be 1->2->11->12->56->90*/
for (int i = 0; i < 6; i++)
{
temp = new Node(arr[i]);
list.sortedInsert(temp);
}
list.printList();
}
} Khi sử dụng ngôn ngữ Python, chúng ta sẽ viết code như sau:
# Node class
class Node:
# Constructor to initialize the node object
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
# Function to initialize head
def __init__(self):
self.head = None
# Function to insert a new node at the beginning
def push(self, new_data):
new_node = Node(new_data)
new_node.next = self.head
self.head = new_node
# Utility function to print the linked LinkedList
def printList(self):
temp = self.head
print temp.data,
temp = temp.next
while(temp != self.head):
print temp.data,
temp = temp.next
""" function to insert a new_node in a list in sorted way.
Note that this function expects a pointer to head node
as this can modify the head of the input linked list """
def sortedInsert(self, new_node):
current = self.head
# Case 1 of the above algo
if current is None:
new_node.next = new_node
self.head = new_node
# Case 2 of the above algo
elif (current.data >= new_node.data):
# If value is smaller than head's value then we
# need to change next of last node
while current.next != self.head :
current = current.next
current.next = new_node
new_node.next = self.head
self.head = new_node
# Case 3 of the above algo
else:
# Locate the node before the point of insertion
while (current.next != self.head and
current.next.data < new_node.data):
current = current.next
new_node.next = current.next
current.next = new_node
# Driver program to test the above function
#llist = LinkedList()
arr = [12, 56, 2, 11, 1, 90]
list_size = len(arr)
# start with empty linked list
start = LinkedList()
# Create linked list from the array arr[]
# Created linked list will be 1->2->11->12->56->90
for i in range(list_size):
temp = Node(arr[i])
start.sortedInsert(temp)
start.printList() Và nếu bạn thích sử dụng C#:
// C# program for sorted insert
// in circular linked list
using System;
class LinkedList
{
public class Node
{
public int data;
public Node next;
public Node(int d)
{
data = d;
next = null;
}
}
Node head;
// Constructor
LinkedList()
{
head = null;
}
/* function to insert a new_node
in a list in sorted way. Note that
this function expects a pointer
to head node as this can modify
the head of the input linked list */
void sortedInsert(Node new_node)
{
Node current = head;
// Case 1 of the above algo
if (current == null)
{
new_node.next = new_node;
head = new_node;
}
// Case 2 of the above algo
else if (current.data >= new_node.data)
{
/* If value is smaller than
head's value then we need
to change next of last node */
while (current.next != head)
current = current.next;
current.next = new_node;
new_node.next = head;
head = new_node;
}
// Case 3 of the above algo
else
{
/* Locate the node before
the point of insertion */
while (current.next != head &&
current.next.data < new_node.data)
current = current.next;
new_node.next = current.next;
current.next = new_node;
}
}
// Utility method to print a linked list
void printList()
{
if (head != null)
{
Node temp = head;
do
{
Console.Write(temp.data + " ");
temp = temp.next;
}
while (temp != head);
}
}
// Driver code
public static void Main(String []args)
{
LinkedList list = new LinkedList();
// Creating the linkedlist
int []arr = {12, 56, 2, 11, 1, 90};
/* start with empty linked list */
Node temp = null;
/* Create linked list from the
array arr[]. Created linked list
will be 1->2->11->12->56->90*/
for (int i = 0; i < 6; i++)
{
temp = new Node(arr[i]);
list.sortedInsert(temp);
}
list.printList();
}
}
Kết quả in ra là:
1 2 11 12 56 90Độ phức tạp thuật toán: O(n) trong đó n là số lượng các nodes nằm trong danh sách liên kết được cho
Trường hợp 2 của thuật toán/đoạn code trên có thể được tối ưu. Để cài đặt sự tối ưu này, chúng ta cần thay đổi trường hợp 2 thành như sau:
// Case 2 of the above algo
else if (current->data >= new_node->data)
{
// swap the data part of head node and new node
// assuming that we have a function swap(int *, int *)
swap(&(current->data), &(new_node->data));
new_node->next = (*head_ref)->next;
(*head_ref)->next = new_node;
}
Nguồ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}