Ứng dụng danh sách liên kết đơn

Danh sách liên kết đơn

Danh sách liên kết là một cấu trúc tài liệu gồm những node và những liên kết giữa những node đó. Mỗi node được liên kết với một node khác [ trong trường hợp danh sách liên kết đơn ] hoặc hai node [ trong trường hợp danh sách liên kết kép ] bằng con trỏ .
Các node gồm hai phần chính là phần tài liệu và phần liên kết [ những con trỏ để trỏ tới node khác ], và phần bộ nhớ dánh cho chúng hoàn toàn có thể được cấp phép bằng phương pháp cấp phát động .

Trong thực tế chúng ta không nhất thiết phải dùng cấp phát động để xây dựng danh sách liên kết, còn có một cách khác nữa đó là dùng mảng. Nhưng cách dùng cấp phát động hay được sử dụng hơn và có nhiều ưu điểm hơn.

Bạn đang đọc: Chi tiết bài học Danh sách liên kết đơn

Một node trong danh sách liên kết đơn được cấu thành từ hai thành phần là tài liệu và phần liên kết .

Xây dựng danh sách liên kết bởi liên kết những node với nhau .

Các điểm mạnh và điểm yếu của danh sách liên kết so với mảng:

Cả danh sách liên kết và mảng đều hoàn toàn có thể được sử dụng để chứa những tài liệu cùng kiểu. Nhưng chúng lại có những đặc thù riêng, và ưu điểm của cái này lại là điểm yếu kém của cái còn lại .

Điểm mạnh :

Danh sách liên kết có kích cỡ động, hoàn toàn có thể lan rộng ra hay thu hẹp rất dễ ràng .
Việc chèn hay xóa một thành phần trong danh sách liên kết là rất thuận tiện, ta chỉ cần biến hóa vị trí trỏ của những con trỏ thay vì phải dịch hàng loạt phần tài liệu còn lại. Xem ví dụ sau khi ta muốn chèn node C vào giữa node A và B :

Trước khi chèn :

Sau khi chèn :

Điểm yếu :

Danh sách liên kết mang yếu điểm của cấp phát động về hiệu năng. Điều này cũng dễ hiểu vì mảng có vị trí bộ đệm tốt hơn [ là những khối những ô nhớ liên tục ] so với danh sách liên kết .
Ta không hề truy vấn ngẫu nhiên một thành phần trong danh sách liên kết ngay lập tức, mà phải thực thi duyệt từ đầu danh sách cho tới khi gặp thành phần đó. Do vậy ta không hề thực thi tìm kiếm nhị phân với những danh sách liên kết .
Cần thêm khoảng trống bộ nhớ cho con trỏ trong mỗi thành phần của danh sách liên kết .

Xây dựng danh sách liên kết đơn với C / C + +

Để kiến thiết xây dựng một danh sách sách liên kết trước hết ta cần biết được danh sách liên kết cần gồm có những thành phần nào và những thao tác mà ta hoàn toàn có thể triển khai với danh sách liên kết :
Các thành phần của danh sách liên kết đơn gồm có :

Các node : Mỗi node gồm có hai thành phần : phần tài liệu và phần liên kết là một con trỏ để trỏ tới vị trí của node tiếp theo, nói cách khác, con trỏ này có giá trị là địa chỉ của node tiếp theo. Node ở đầu cuối của danh sách liên kết sẽ trỏ tới NULL, tức là không trỏ tới đâu cả .
struct node { int data; /* Phần dữ liệu của một node*/ struct node* next; /* Con trỏ tới node kế tiếp */ };
Con trỏ head để trỏ tới vị trí tiên phong của danh sách liên kết .

struct node * head; /* Con trỏ tới head node */

Các thao tác chính với danh sách liên kết đơn:

Tạo một node mới và trả về con trỏ tới node đó .

Xem thêm: Ứng dụng học tiếng Anh chính phủ Mỹ khuyên dùng

/* Tạo một node mới và trả về con trỏ tới node đó. */ struct node* NewNode[int x] { struct node* new_node = [struct node*]malloc[sizeof[struct node]]; /* Cấp phát bộ nhớ cho node */ new_node->data = x; new_node->next = NULL; return new_node; }
Chèn một thành phần vào danh sách . /* Chèn node vào vị trí cuối của danh sách liên kết */ void InsertAtTail[int x] { struct node* temp = head; /* Tạo ra một con trỏ tạm, tránh trực tiếp làm thay đổi vị trí trỏ của con trỏ head */ struct node* new_node = NewNode[x]; /* Tạo ra một node mới với phần dữ liệu là tham số được truyền vào */ if[head == NULL] { /* Nếu danh sách rỗng, con trỏ head sẽ trỏ tới node được chèn vào danh sách */ head = new_node; return; } while[temp->next != NULL] temp = temp->next; /* Đi tới vị trí cuối cùng của danh sách */ temp->next = new_node; /* Chèn node mới vào cuối danh sách */ }
Xóa một thành phần khỏi danh sách . struct node* Delete[struct node *head, int position] { struct node *prev = NULL; /* Con trỏ lưu node ngay trước node cần xóa */ struct node *ptr = head; /* Tạo ra bản sao của con trỏ head, tránh làm thay đổi vị trí trỏ của con trỏ head khi duyệt danh sách*/ int pos = 0; /* Biến lưu vị trí các phần tử trong danh sách */ if[position==0] /* Trường hợp xóa phần tử ở đầu danh sách */ { head=head->next; /* Trả về vị trí của phần tử tiếp theo, vị trí trỏ của head thay đổi */ free[ptr]; /* Thu hồi bộ nhớ của phần tử cần được xóa */ } else { while[position!=pos] /*Duyệt danh sách, lặp cho tới khi tìm thấy vị trí cần xóa */ { ++pos; prev=ptr; ptr=ptr->next; } /* Sau vòng lặp tìm được node cần xóa là ptr, địa chỉ node ngay trước node cần xóa được lưu trữ trong prev */ if[ptr!=NULL] /* Nếu tìm tháy node cần xóa trong danh sách, thực hiện xóa */ { prev->next=ptr->next; free[ptr]; } } return head; }
Hiển thị tổng thể những node trong danh sách . void Display[] { struct node* temp = head; while[temp != NULL] { printf["%d ",temp->data]; temp = temp->next; } printf["\n"]; }

Ứng dụng của danh sách liên kết đơn trong thực tế:

Danh sách liên kết đơn hầu hết được dùng để thiết kế xây dựng những loại cấu trúc tài liệu khác như ngăn xếp hoặc hàng đợi hoặc đồ thị …
Đôi khi ta cần biết node ở vị trí trước. Nhưng với danh sách liên kết đơn thì không làm được. Để biết được vị trí của cả những node trước và sau node hiện tại, ta phải lưu cả vị trí của node trước và node sau. Lúc này cấu trúc của một node sẽ có dạng như sau .

struct node { int data; struct node* next; struct node* prev; };

Cấu trúc trên chính là cấu trúc của danh sách liên kết kép . Để hiểu hơn về danh sách liên kết kép mời bạn đọc bài tiếp theo .

Bạn cũng hoàn toàn có thể đọc thêm những bài toán về danh sách liên kết đơn tại những đường dẫn sau :

Danh sách liên kết đơn

Điểm mạnh :

Điểm yếu :

Xây dựng danh sách liên kết đơn với C / C + +

Video liên quan

Bài Viết Liên Quan

Toplist mới

Bài mới nhất

Chủ Đề