Danh sách liên kết
Danh sách liên kết là một chuỗi các cấu trúc dữ liệu, được kết nối với nhau thông qua các liên kết.
Danh sách liên kết là một chuỗi các cấu trúc dữ liệu, bao gồm các nút(node). Mỗi liên kết (link) chứa một kết nối đến một liên kết khác. Danh sách liên kết là cấu trúc dữ liệu được sử dụng nhiều thứ hai sau mảng. Sau đây là các khái niệm cơ bản liên quan đến danh sách liên kết.
- Link(Liên kết) - Mỗi liên kết của danh sách được liên kết có thể lưu trữ dữ liệu được gọi là một phần tử.
- Next - Mỗi liên kết của danh sách được liên kết chứa một liên kết đến liên kết tiếp theo được gọi là Next.
- LinkedList - Danh sách được liên kết chứa liên kết kết nối đến liên kết đầu tiên được gọi là First.
Biểu diễn danh sách liên kết
Danh sách liên kết có thể được hình dung như một chuỗi các nút, trong đó mọi nút trỏ đến nút tiếp theo.
Dưới đây là một số điểm cần nhớ về danh sách liên kết:
- Danh sách liên kết chứa một phần tử link được gọi là first.
- Mỗi link mang một trường dữ liệu và link được gọi là next.
- Mỗi link sẽ liên kết tới link kế tiếp sử dụng link tiếp theo.
- Link cuối cùng mang một link là null để đánh dấu điểm cuối của danh sách.
Các loại danh sách liên kết
Sau đây là các loại danh sách liên kết.
- Danh sách liên kết đơn (Simple Linked List): chỉ duyệt các phần tử theo chiều về trước.
- Danh sách liên kết đôi (Doubly Linked List): các phần tử có thể được duyệt theo chiều về trước hoặc về sau.
- Danh sách liên kết vòng (Circular Linked List): phần tử cuối cùng chứa link của phần tử đầu tiên như là next và phần tử đầu tiên có link tới phần tử cuối cùng như là prev.
Hoạt động cơ bản
Sau đây là các hoạt động cơ bản được hỗ trợ bởi một danh sách.
- Chèn - Thêm một phần tử ở đầu danh sách.
- Xóa - Xóa một phần tử ở đầu danh sách.
- Hiển thị - Hiển thị danh sách đầy đủ.
- Tìm kiếm - Tìm kiếm một phần tử bằng khóa đã cho.
- Xóa - Xóa một phần tử bằng phím đã cho.
Thao tác chèn
Thêm một nút mới trong danh sách được liên kết là một hoạt động nhiều hơn một bước. Chúng ta sẽ tìm hiểu điều này với các sơ đồ ở đây. Đầu tiên, tạo một nút bằng cách sử dụng cùng một cấu trúc và tìm vị trí mà nó phải được chèn.
Hãy tưởng tượng rằng chúng ta đang chèn một nút B (NewNode), giữa A (LeftNode) và C (RightNode). Sau đó, điểm B.next đến C:
NewNode.next −> RightNode;
Nó sẽ trông như thế này:
Bây giờ, nút tiếp theo ở bên trái sẽ trỏ đến nút mới.
LeftNode.next −> NewNode;
Điều này sẽ đặt nút mới ở giữa hai. Danh sách mới sẽ trông như thế này:
Các bước tương tự nên được thực hiện nếu nút được chèn vào đầu danh sách. Trong khi đặt một nút vào vị trí cuối của danh sách, nút cuối cùng thứ hai của danh sách sẽ trỏ đến nút mới và nút mới sẽ trỏ đến NULL.
Thao tác xóa
Xóa cũng là một quá trình nhiều hơn một bước. Chúng ta sẽ học với đại diện bằng hình ảnh. Đầu tiên, xác định vị trí nút mục tiêu cần loại bỏ, bằng cách sử dụng các thuật toán tìm kiếm.
Nút bên trái (trước) của nút đích bây giờ sẽ trỏ đến nút tiếp theo của nút đích -
LeftNode.next −> TargetNode.next;
Điều này sẽ loại bỏ liên kết đã được trỏ đến nút mục tiêu. Bây giờ, bằng cách sử dụng đoạn mã sau, chúng tôi sẽ loại bỏ những gì nút đích đang chỉ vào.
TargetNode.next −> NULL;
Chúng ta cần sử dụng nút bị xóa. Chúng ta có thể giữ nó trong bộ nhớ nếu không chúng ta có thể đơn giản giải phóng bộ nhớ và xóa sạch hoàn toàn nút đích.
Đảo ngược danh sách liên kết
Với hoạt động này, bạn cần phải cẩn thận. Chúng ta cần làm cho nút đầu (head) trỏ tới nút cuối cùng và đảo ngược toàn bộ danh sách liên kết.
Đầu tiên, chúng ta đi đến phần thử cuối của danh sách. Nó nên được trỏ đến NULL. Bây giờ, chúng ta sẽ làm cho nó trỏ đến nút trước đó của nó:
Chúng ta phải đảm bảo rằng nút cuối cùng không phải là nút cuối cùng. Vì vậy, chúng ta sẽ có một số nút tạm thời, trông giống như nút đầu trỏ đến nút cuối cùng. Bây giờ, chúng ta sẽ làm cho tất cả các nút bên trái trỏ đến các nút trước đó của chúng từng cái một.
Ngoại trừ nút (nút đầu tiên) được chỉ bởi nút đầu, tất cả các nút phải trỏ đến nút trước của chúng, làm cho chúng trở thành nút kế thừa mới. Nút đầu tiên sẽ trỏ đến NULL.
Chúng ta sẽ làm cho nút đầu trỏ đến nút đầu tiên mới bằng cách sử dụng nút tạm thời.
Danh sách liên kết bây giờ được đảo ngược.
- Hiếu Kiều -
Bài viết nổi bật
Bài viết nổi bật