Khái niệm cơ bản về danh sách liên kết

Gửi bởi: Phạm Thọ Thái Dương 13 tháng 2 2020 lúc 10:19:39

Mục lục

* * * * *

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 liên kết có chứa các mục. Mỗi liên kết 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 điều khoản quan trọng để hiểu khái niệm Danh sách liên kết.

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ử.
Tiếp theo - 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à Tiếp theo.
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.

Đại 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 chỉ đến nút tiếp theo.

Theo minh họa ở trên, sau đây là những điểm quan trọng cần được xem xét.

Danh sách liên kết chứa một yếu tố liên kết được gọi đầu tiên.
Mỗi liên kết mang (các) trường dữ liệu và trường liên kết được gọi tiếp theo.
Mỗi liên kết được liên kết với liên kết tiếp theo bằng liên kết tiếp theo.
Liên kết cuối cùng mang một liên kết là null để đánh dấu sự kết thúc 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 giản - Điều hướng mục chỉ được chuyển tiếp.
Danh sách liên kết đôi - Các mục có thể được điều hướng tiến và lùi.
Danh sách liên kết tròn - Mục cuối chứa liên kết của phần tử đầu tiên là tiếp theo và phần tử đầu tiên có liên kết đến phần tử cuối cùng như trước.

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 chèn nó vào cuối, 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.

Vận hành ngược

Hoạt động này là một kỹ lưỡng. Chúng ta cần làm cho nút cuối cùng được chỉ bởi nút đầu và đảo ngược toàn bộ danh sách được liên kết.

Đầu tiên, chúng tôi đi qua cuối 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 bị mất. 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 người tiền nhiệm của chúng, làm cho chúng trở thành người kế thừa mới. Nút đầu tiên sẽ trỏ đến NULL.