[DSA] Danh sách liên kết đôi - Doubly Linked List
1. Danh sách liên kết đôi là gì?
Danh sách liên kết đôi (double linked list) là một kiểu dữ liệu trừu tượng trong lập trình, nó bao gồm một tập hợp các nút (node) được liên kết với nhau bởi các con trỏ, trong đó mỗi nút lưu trữ thông tin về phần tử của danh sách và hai con trỏ, một trỏ đến phần tử tiếp theo và một trỏ đến phần tử trước đó.
Khác với danh sách liên kết đơn, danh sách liên kết đôi cho phép ta truy cập phần tử từ cả hai phía của danh sách. Do đó, các thao tác trên danh sách liên kết đôi được thực hiện dễ dàng hơn so với danh sách liên kết đơn. Tuy nhiên, danh sách liên kết đôi cũng tốn nhiều bộ nhớ hơn và phức tạp hơn khi thêm hoặc xóa phần tử so với danh sách liên kết đơn.
2. Danh sách liên kết đôi để làm gì?
Danh sách liên kết đôi (double linked list) được sử dụng để lưu trữ và quản lý một tập hợp các phần tử mà ta muốn truy cập và thực hiện các thao tác trên danh sách từ cả hai phía.
Các thao tác cơ bản trên danh sách liên kết đôi bao gồm:
- Chèn một phần tử vào đầu hoặc cuối danh sách.
- Chèn một phần tử vào vị trí bất kỳ trong danh sách.
- Xóa một phần tử khỏi danh sách.
- Tìm kiếm một phần tử trong danh sách.
- Đảo ngược thứ tự các phần tử trong danh sách.
- Sắp xếp các phần tử trong danh sách.
Danh sách liên kết đôi được sử dụng rộng rãi trong các ứng dụng như hệ thống quản lý tệp tin, trình duyệt web, các trình đọc PDF, các ứng dụng quản lý tài khoản ngân hàng, trò chơi máy tính, v.v. Ta có thể sử dụng danh sách liên kết đôi để giải quyết các bài toán về cấu trúc dữ liệu và giải thuật.
3. Hiện thực các phép toán:
#include <stdio.h>
#include <stdlib.h>
// Define a structure for a doubly linked list node
struct Node {
int data;
struct Node *prev;
struct Node *next;
};
// Function to insert a new node at the beginning of the doubly linked list
void insertAtBeginning(struct Node **head, int data) {
// Create a new node
struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->prev = NULL;
newNode->next = (*head);
// If the list is not empty, set the previous pointer of the current head to the new node
if ((*head) != NULL) {
(*head)->prev = newNode;
}
// Set the new node as the head of the list
(*head) = newNode;
}
// Function to insert a new node at the end of the doubly linked list
void insertAtEnd(struct Node **head, int data) {
// Create a new node
struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->prev = NULL;
newNode->next = NULL;
// If the list is empty, set the new node as the head of the list
if ((*head) == NULL) {
(*head) = newNode;
return;
}
// Traverse the list to find the last node
struct Node *last = (*head);
while (last->next != NULL) {
last = last->next;
}
// Set the next pointer of the last node to the new node, and the previous pointer of the new node to the last node
last->next = newNode;
newNode->prev = last;
}
// Function to delete a node from the doubly linked list
void deleteNode(struct Node **head, struct Node *node) {
// If the node to be deleted is the head of the list, set the next node as the new head
if ((*head) == node) {
(*head) = node->next;
}
// If the node to be deleted is not the last node, set the previous pointer of the next node to the previous node of the current node
if (node->next != NULL) {
node->next->prev = node->prev;
}
// If the node to be deleted is not the first node, set the next pointer of the previous node to the next node of the current node
if (node->prev != NULL) {
node->prev->next = node->next;
}
// Free the memory used by the node
free(node);
}
// Function to print the elements of the doubly linked list
void printList(struct Node *head) {
// Traverse the list and print each element
while (head != NULL) {
printf("%d ", head->data);
head = head->next;
}
printf("\n");
}
// Deletion operations
void deleteAtBeginning(struct Node **head_ref)
{
// kiểm tra nếu danh sách rỗng
if (*head_ref == NULL)
return;
// nếu danh sách có phần tử, ta lưu trữ địa chỉ của phần tử thứ 2
struct Node *temp = *head_ref;
*head_ref = (*head_ref)->next;
// kiểm tra nếu danh sách không chỉ có 1 phần tử
if (*head_ref != NULL)
(*head_ref)->prev = NULL;
// giải phóng phần tử đầu tiên
free(temp);
}
void deleteAtEnd(struct Node **head_ref)
{
// kiểm tra nếu danh sách rỗng
if (*head_ref == NULL)
return;
// tìm phần tử cuối cùng
struct Node *temp = *head_ref;
while (temp->next != NULL)
temp = temp->next;
// kiểm tra nếu danh sách chỉ có 1 phần tử
if (temp == *head_ref)
*head_ref = NULL;
else
temp->prev->next = NULL;
// giải phóng phần tử cuối cùng
free(temp);
}
//Function to reverse the elements of the doubly linked list
void reverseList(struct Node **head_ref)
{
// kiểm tra nếu danh sách rỗng hoặc chỉ có 1 phần tử
if (*head_ref == NULL || (*head_ref)->next == NULL)
return;
struct Node *current = *head_ref;
struct Node *temp = NULL;
// đảo ngược con trỏ next và prev của từng nút trong danh sách
while (current != NULL)
{
temp = current->prev;
current->prev = current->next;
current->next = temp;
current = current->prev;
}
// kiểm tra nếu danh sách không rỗng, cập nhật lại con trỏ đầu danh sách
if (temp != NULL)
*head_ref = temp->prev;
}
// Function to search for a given element in a doubly linked list
// Returns the node containing the element if found, otherwise returns NULL
struct Node* search(struct Node* head, int key) {
// Traverse the list from the head
struct Node* current = head;
while (current != NULL) {
// If the current node contains the key, return it
if (current->data == key) {
return current;
}
// Move to the next node
current = current->next;
}
// If the key is not found in the list, return NULL
return NULL;
}
// Test the doubly linked list operations
int main() {
struct Node *head = NULL;
// Insert elements at the beginning of the list
insertAtBeginning(&head, 5);
insertAtBeginning(&head, 10);
insertAtBeginning(&head, 15);
// Print the list
printf("List after inserting elements at the beginning: ");
printList(head);
// Insert elements at the end of the list
insertAtEnd(&head, 20);
insertAtEnd(&head, 25);
insertAtEnd(&head, 30);
printf("1. List after inserting elements at the end of the list: ");
printList(head);
deleteAtBeginning(&head);
printf("2. List after delete element at the BEGINING of the list: ");
printList(head);
// Test the search function
// key is not found
printf("3. Test SEACH function: \n");
int key = 300;
struct Node* result = search(head, key);
if (result != NULL) {
printf("\t- Found key %d at node with data %d\n", key, result->data);
} else {
printf("\t- Key %d not found in the list\n", key);
}
//key is found
key = 25;
result = search(head, key);
if (result != NULL) {
printf("\t- Found key %d at node with data %d\n", key, result->data);
} else {
printf("\t- Key %d not found in the list\n", key);
}
insertAtBeginning(&head, 5000);
printf("4. List after inserting element 5000 at the beginning: ");
printList(head);
reverseList(&head);
printf("5. List after reversing: ");
printList(head);
}
Không có nhận xét nào