Header Ads

[DSA] Danh sách liên kết đơn (Singly Linked List)

tháng 2 24, 2023 0

1. Định nghĩa:

Danh sách liên kết đơn (Singly Linked List) là một cấu trúc dữ liệu được tạo thành từ một chuỗi các nút (node) liên kết với nhau theo một thứ tự nhất định. Mỗi nút chứa một giá trị dữ liệu và một tham chiếu (con trỏ - pointer) đến nút tiếp theo trong danh sách.

Cấu trúc của một nút trong danh sách liên kết đơn bao gồm hai trường dữ liệu chính:

  • Dữ liệu (Data): Chứa giá trị dữ liệu mà nút này đang lưu trữ.
  • Tham chiếu (Pointer): Lưu trữ địa chỉ của nút kế tiếp trong danh sách liên kết.

2. Một số thao tác phổ biến trên danh sách liên kết đơn bao gồm:

  • Thêm phần tử vào đầu danh sách (Insertion at the beginning): Để thêm một phần tử vào đầu danh sách, ta cần tạo ra một nút mới và đặt giá trị dữ liệu của nó là giá trị cần chèn. Sau đó, ta gán tham chiếu của nút mới này bằng địa chỉ của nút hiện tại đang ở đầu danh sách. Cuối cùng, ta cập nhật tham chiếu của đầu danh sách để trỏ đến nút mới này.
  • Thêm phần tử vào cuối danh sách (Insertion at the end): Để thêm một phần tử vào cuối danh sách, ta cần tìm đến nút cuối cùng trong danh sách và cập nhật tham chiếu của nút đó để trỏ đến nút mới. Nút mới này được tạo ra với giá trị dữ liệu cần chèn và tham chiếu của nó được gán bằng giá trị NULL.
  • Xóa phần tử khỏi danh sách (Deletion): Để xóa một phần tử khỏi danh sách, ta cần tìm đến nút chứa giá trị dữ liệu cần xóa và cập nhật tham chiếu của nút trước nó để trỏ đến nút tiếp theo. Nếu nút cần xóa đang ở đầu danh sách, ta chỉ cần cập nhật tham chiếu của đầu danh sách để trỏ đến nút tiếp theo.

3. Hiện thực các phép toán:

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
int data;
struct Node* next;
} Node;

// Khởi tạo một danh sách liên kết rỗng
Node* createLinkedList() {
return NULL;
}

// Thêm một phần tử vào đầu danh sách liên kết
Node* insertAtBeginning(Node* head, int data) {
Node* newNode = (Node*) malloc(sizeof(Node));
newNode->data = data;
newNode->next = head;
return newNode;
}

// Thêm một phần tử vào cuối danh sách liên kết
Node* insertAtEnd(Node* head, int data) {
Node* newNode = (Node*) malloc(sizeof(Node));
newNode->data = data;
newNode->next = NULL;
if (head == NULL) {
return newNode;
}
Node* current = head;
while (current->next != NULL) {
current = current->next;
}
current->next = newNode;
return head;
}

// In ra tất cả các phần tử trong danh sách liên kết
void printLinkedList(Node* head) {
printf("Linked List: ");
if (head == NULL) {
printf("Empty");
}
while (head != NULL) {
printf("%d ", head->data);
head = head->next;
}
printf("\n");
}

// Tìm kiếm một phần tử trong danh sách liên kết và trả về vị trí của nó
int findElement(Node* head, int data) {
int pos = 1;
while (head != NULL) {
if (head->data == data) {
return pos;
}
head = head->next;
pos++;
}
return -1;
}

// Xóa một phần tử khỏi danh sách liên kết
Node* deleteElement(Node* head, int data) {
Node* current = head;
Node* previous = NULL;
while (current != NULL) {
if (current->data == data) {
if (previous == NULL) {
head = current->next;
} else {
previous->next = current->next;
}
free(current);
return head;
}
previous = current;
current = current->next;
}
return head;
}

int main() {
Node* head = createLinkedList();

// Thêm các phần tử vào danh sách liên kết
head = insertAtBeginning(head, 5);
head = insertAtBeginning(head, 3);
head = insertAtEnd(head, 7);

// In ra danh sách liên kết
printLinkedList(head);

// Tìm kiếm phần tử trong danh sách liên kết
int pos = findElement(head, 3);
if (pos != -1) {
printf("The element 3 is found at position %d\n", pos);
} else {
printf("The element 3 is not found\n");
}

// Xóa một phần tử khỏi danh sách liên kết
head = deleteElement(head, 5);

// In ra danh sách
printLinkedList(head);
}


4. Ví dụ về việc dùng danh sách liên kết đơn:

Một ví dụ về việc sử dụng danh sách liên kết đơn trong ngôn ngữ lập trình C là để lưu trữ và quản lý một danh sách sinh viên trong một lớp học. Trong đó, mỗi sinh viên sẽ được lưu trữ dưới dạng một nút trong danh sách liên kết đơn, với các trường thông tin như tên, mã sinh viên, ngày sinh, điểm trung bình, v.v...


#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//định nghĩa cấu trúc Student
typedef struct student {
char name[50];
int id;
char dob[20];
float gpa;
struct student *next;
} Student;
//. 0. Tạo sinh viên
Student * createStudent(char name[], int id, char dob[], float gpa)
{
Student *newStudent = (Student*)malloc(sizeof(Student));
strcpy(newStudent->name, name);
newStudent->id = id;
strcpy(newStudent->dob, dob);
newStudent->gpa = gpa;
return newStudent;
}
//1. Tạo danh sách rỗng:
Student* createList() {
return NULL;
}
//2. Kiểm tra danh sách rỗng:
int isEmpty(Student *head) {
return head == NULL;
}
//3. Thêm sinh viên vào đầu danh sách:
Student* insertAtBeginning(Student *head, Student *newStudent) {
newStudent->next = head;
head = newStudent;
return head;
}
//4. Thêm sinh viên vào cuối danh sách:

Student* insertAtEnd(Student *head, Student *newStudent) {
newStudent->next = NULL;
if (head == NULL) {
head = newStudent;
}
else {
Student *temp = head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newStudent;
}
return head;
}
//5. In ra danh sách sinh viên:

void printList(Student *head) {
if (isEmpty(head)) {
printf("Danh sach rong!");
return;
}
Student *temp = head;
while (temp != NULL) {
printf("*************\n");
printf("Ten: %s\n", temp->name);
printf("Ma sinh vien: %d\n", temp->id);
printf("Ngay sinh: %s\n", temp->dob);
printf("Diem trung binh: %f\n", temp->gpa);
temp = temp->next;
}
}
//7. Tìm kiếm sinh viên theo mã số sinh viên:

Student* searchStudent(Student *head, int id) {
if (isEmpty(head)) {
printf("Danh sach rong!");
return NULL;
}
Student *temp = head;
while (temp != NULL) {
if (temp->id == id) {
return temp;
}
temp = temp->next;
}
printf("Khong tim thay sinh vien co ma so %d!", id);
return NULL;
}

//8. Xóa một sinh viên theo mã sinh viên
Student* deleteStudent(Student *head, int id) {
if (head == NULL) {
return NULL;
}
if (head->id == id) {
Student *temp = head;
head = head->next;
free(temp);
return head;
}
Student *prev = head;
Student *current = head->next;
while (current != NULL) {
if (current->id == id) {
prev->next = current->next;
free(current);
return head;
}
prev = current;
current = current->next;
}
return head;
}
// main function to test the list of students
int main() {
// create an empty list
Student *head = NULL;

// thêm sinh viên vào đầu danh sách
Student *s1 = createStudent("Nguyen Van A", 1001, "01/01/2000", 3.6);
Student *s2 = createStudent("Tran Thi B", 1002, "02/02/2000", 3.7);
head = insertAtBeginning(head, s1);
head = insertAtBeginning(head, s2);

Student *s3 = createStudent("Pham Van C", 1003, "03/03/2000", 3.8);
Student *s4 = createStudent("Le Thi D", 1004, "04/04/2000", 3.9);
// thêm sinh viên vào cuối danh sách
head = insertAtEnd(head, s3);
head = insertAtEnd(head, s4);

// in ra danh sách sinh viên
printf("Danh sach sinh vien:\n");
printList(head);

// tìm kiếm sinh viên theo mã sinh viên
int id = 1003;
Student *foundStudent = searchStudent(head, id);
printf("=========== TIM KIEM:===========\n");
if (foundStudent != NULL) {
printf("Sinh vien co ma so %d la: %s\n", id, foundStudent->name);
} else {
printf("Khong tim thay sinh vien co ma so %d.\n", id);
}

// xóa sinh viên theo mã sinh viên
id = 1002;
head = deleteStudent(head, id);
printf("=================\nDanh sach sinh vien sau khi xoa sinh vien co ma so %d:\n", id);
printList(head);
}

5. Ưu điểm và nhược điểm của danh sách liên kết đơn:

5.1. Ưu điểm

  • Cấp phát động: danh sách liên kết đơn cho phép cấp phát động bộ nhớ tùy thuộc vào số lượng phần tử cần lưu trữ, giúp tiết kiệm bộ nhớ so với cách cấp phát tĩnh.
  • Thao tác chèn/xóa phần tử nhanh: khi cần chèn/xóa một phần tử vào danh sách liên kết đơn, chỉ cần thay đổi liên kết của 2 phần tử liền kề, không cần di chuyển phần tử khác trong danh sách, giúp tăng tốc độ thao tác chèn/xóa.
  • Khả năng mở rộng: danh sách liên kết đơn có thể mở rộng một cách dễ dàng bằng cách thêm các phần tử mới vào cuối danh sách.

5.2. Nhược điểm:

  • Truy cập ngẫu nhiên chậm: truy cập một phần tử bất kỳ trong danh sách liên kết đơn cần phải duyệt qua tất cả các phần tử từ đầu đến phần tử cần truy cập, do đó việc truy cập ngẫu nhiên sẽ chậm hơn so với mảng.
  • Dùng nhiều bộ nhớ hơn: mỗi phần tử trong danh sách liên kết đơn bao gồm một trường lưu trữ dữ liệu và một trường lưu trữ liên kết, do đó danh sách liên kết đơn sẽ dùng nhiều bộ nhớ hơn so với mảng khi lưu trữ cùng số lượng phần tử.
  • Khó khăn trong việc tìm kiếm: do truy cập ngẫu nhiên chậm, việc tìm kiếm một phần tử trong danh sách liên kết đơn cũng sẽ chậm hơn so với mảng.

Nguồn: chatGPT

Tags:

Không có nhận xét nào

Đăng ký: Đăng Nhận xét ( Atom )
Được tạo bởi Blogger.