Danh sách trăn __init__
Danh sách liên kết là một trong những cấu trúc dữ liệu phổ biến nhất được sử dụng trong khoa học máy tính. Nó cũng là một trong những cấu trúc đơn giản nhất và cũng là cấu trúc cơ bản cho các cấu trúc cấp cao hơn như ngăn xếp, bộ đệm vòng tròn và hàng đợi Show Nội dung chính Hiển thị
Nội dung chính
Nói chung, danh sách là tập hợp các thành phần dữ liệu đơn lẻ được kết nối thông qua các tham chiếu. Các lập trình viên C biết đây là con trỏ. Ví dụ: một phần tử dữ liệu có thể bao gồm dữ liệu địa chỉ, dữ liệu địa lý, dữ liệu hình học, thông tin định tuyến hoặc chi tiết giao dịch. Thông thường, mỗi phần tử của danh sách liên kết có cùng một kiểu dữ liệu đặc trưng cho danh sách Một phần tử danh sách duy nhất được gọi là một nút. Các nút không giống như các mảng được lưu trữ tuần tự trong bộ nhớ. Thay vào đó, có khả năng tìm thấy chúng ở các phân đoạn bộ nhớ khác nhau mà bạn có thể tìm thấy bằng cách lần theo các con trỏ từ nút này sang nút tiếp theo. Người ta thường đánh dấu phần cuối của danh sách bằng phần tử NIL, được biểu thị bằng mã Python tương đương 9Hình 1. Danh sách liên kết đơn Có hai loại danh sách - danh sách liên kết đơn và danh sách liên kết kép. Một nút trong danh sách liên kết đơn chỉ trỏ đến phần tử tiếp theo trong danh sách, trong khi một nút trong danh sách liên kết kép cũng trỏ đến nút trước đó. Cấu trúc dữ liệu chiếm nhiều không gian hơn vì bạn sẽ cần một biến bổ sung để lưu trữ tham chiếu tiếp theo Hình 2. danh sách liên kết đôi Một danh sách liên kết đơn có thể được duyệt từ đầu đến đuôi trong khi duyệt ngược lại không dễ dàng như vậy. Ngược lại, danh sách liên kết kép cho phép duyệt qua các nút theo cả hai hướng với cùng một chi phí, bất kể bạn bắt đầu với nút nào. Ngoài ra, việc thêm và xóa các nút cũng như chia tách danh sách liên kết đơn được thực hiện không quá hai bước. Trong danh sách liên kết kép, bốn con trỏ phải được thay đổi Ngôn ngữ Python không chứa kiểu dữ liệu được xác định trước cho danh sách được liên kết. Để đối phó với tình huống này, chúng ta phải tạo kiểu dữ liệu của riêng mình hoặc phải sử dụng các mô-đun Python bổ sung cung cấp triển khai kiểu dữ liệu đó Trong bài viết này, chúng ta sẽ thực hiện các bước để tạo cấu trúc dữ liệu danh sách được liên kết của riêng mình. Đầu tiên chúng ta tạo một cấu trúc dữ liệu tương ứng cho nút. Thứ hai, bạn sẽ học cách triển khai và sử dụng cả danh sách liên kết đơn và cuối cùng là danh sách liên kết đôi Bước 1. Nút như một cấu trúc dữ liệuĐể có cấu trúc dữ liệu mà chúng ta có thể làm việc với, chúng ta xác định một nút. Một nút được triển khai dưới dạng một lớp có tên 0. Lớp chứa định nghĩa để tạo một thể hiện đối tượng, trong trường hợp này, với hai biến - 1 để giữ giá trị nút và 2 để lưu tham chiếu đến nút tiếp theo trong danh sách. Hơn nữa, một nút có các phương thức và thuộc tính sau
Các phương pháp này đảm bảo rằng chúng tôi có thể khởi tạo một nút đúng cách với dữ liệu của mình ( 7) và bao gồm cả việc trích xuất và lưu trữ dữ liệu (thông qua thuộc tính 4) cũng như nhận được tham chiếu đến nút được kết nối (thông qua thuộc tính 5). Phương thức 6 cho phép chúng ta so sánh giá trị nút với giá trị của một nút khácLiệt kê 1. Lớp ListNode 2Tạo một nút đơn giản như vậy và khởi tạo một đối tượng của lớp 0Liệt kê 2. Khởi tạo các nút
Sau khi hoàn thành việc đó, chúng tôi có sẵn ba phiên bản của lớp 0. Các trường hợp này đại diện cho ba nút độc lập chứa các giá trị 15 (số nguyên), 8. 2 (thả nổi) và "Berlin" (chuỗi)Bước 2. Tạo lớp cho danh sách liên kết đơnỞ bước thứ hai, chúng tôi xác định một lớp có tên 63 bao gồm các phương thức cần thiết để quản lý các nút danh sách của chúng tôi. Nó chứa các phương thức này
Chúng ta sẽ từng bước thực hiện từng phương pháp này Phương thức 7 định nghĩa hai biến lớp bên trong có tên là 41 và 42. Chúng đại diện cho các nút đầu và cuối của danh sách. Ban đầu, cả 41 và 42 đều có giá trị 9 miễn là danh sách trốngLiệt kê 3. Lớp SingleLinkedList (phần một)
Bước 3. Thêm nútViệc thêm các mục vào danh sách được thực hiện thông qua 67. Phương thức này yêu cầu một nút làm tham số bổ sung. Để đảm bảo rằng đó là một nút thích hợp (một thể hiện của lớp 0), trước tiên, tham số được xác minh bằng cách sử dụng hàm Python tích hợp sẵn 48. Nếu thành công, nút sẽ được thêm vào cuối danh sách. Nếu 49 không phải là một 0, thì một cái sẽ được tạoTrong trường hợp danh sách (vẫn) trống, nút mới sẽ trở thành phần đầu của danh sách. Nếu một nút đã có trong danh sách, thì giá trị của đuôi sẽ được điều chỉnh tương ứng Liệt kê 4. Lớp SingleLinkedList (phần hai) 6Phương thức 65 đếm các nút và trả về độ dài của danh sách. Để chuyển từ nút này sang nút tiếp theo trong danh sách, thuộc tính nút 5 phát huy tác dụng và trả về liên kết đến nút tiếp theo. Việc đếm các nút được thực hiện trong vòng lặp while miễn là chúng ta chưa đến cuối danh sách, được biểu thị bằng liên kết 9 tới nút tiếp theoLiệt kê 5. Lớp SingleLinkedList (phần ba) 4Phương thức 66 xuất các giá trị nút bằng thuộc tính nút 1. Một lần nữa, để đi từ nút này sang nút tiếp theo, liên kết được sử dụng được cung cấp qua thuộc tính 2Liệt kê 6. Lớp SingleLinkedList (phần bốn) 3Dựa trên lớp 63, chúng ta có thể tạo một danh sách thích hợp có tên là 38 và sử dụng các phương thức của nó như đã được mô tả ở trên trong Liệt kê 3-6. Do đó, chúng tôi tạo bốn nút danh sách, đánh giá chúng trong vòng lặp 39 và xuất nội dung danh sách. Liệt kê 7 chỉ cho bạn cách lập trình điều đó và Liệt kê 8 hiển thị kết quảLiệt kê 7. Tạo các nút và đầu ra danh sách 7Đầu ra như sau và cho biết danh sách phát triển như thế nào Hãy xem hướng dẫn thực hành, thực tế của chúng tôi để học Git, với các phương pháp hay nhất, tiêu chuẩn được ngành chấp nhận và bao gồm bảng gian lận. Dừng các lệnh Git trên Google và thực sự tìm hiểu nó Liệt kê 8. Thêm các nút vào danh sách 8Bước 4. Tìm kiếm danh sáchTìm kiếm toàn bộ danh sách được thực hiện bằng phương pháp 68. Nó yêu cầu một tham số bổ sung cho giá trị được tìm kiếm. Người đứng đầu danh sách là điểm bắt đầuTrong khi tìm kiếm, chúng tôi đếm các nút. Để chỉ ra một trận đấu, chúng tôi sử dụng số nút tương ứng. Phương thức 68 trả về một danh sách các số nút đại diện cho các kết quả khớp. Ví dụ, cả nút thứ nhất và nút thứ tư đều chứa giá trị 15. Việc tìm kiếm 15 kết quả trong một danh sách có hai yếu tố. 72Liệt kê 9. Phương thức tìm kiếm unordered_search() 2Bước 5. Xóa một mục khỏi danh sáchViệc xóa một nút khỏi danh sách chỉ yêu cầu điều chỉnh một tham chiếu - tham chiếu trỏ đến nút cần xóa bây giờ phải trỏ đến nút tiếp theo. Tham chiếu này được giữ bởi nút bị xóa và phải được thay thế. Trong nền, trình thu gom rác của Python xử lý các đối tượng không được ước tính và dọn dẹp Phương pháp sau đây được đặt tên là 69. Là một tham số, nó đề cập đến số nút tương tự với giá trị được trả về bởi 68Liệt kê 10. Xóa một nút theo số nút 5Bước 6. Tạo danh sách liên kết képĐể tạo một danh sách liên kết kép, bạn chỉ cần mở rộng lớp 0 bằng cách tạo một tham chiếu bổ sung cho nút trước đó. Điều này ảnh hưởng đến các phương pháp thêm, xóa và sắp xếp các nút. Như trong Liệt kê 11, một thuộc tính mới có tên là 76 đã được thêm vào để lưu trữ con trỏ tham chiếu tới nút trước đó trong danh sách. Chúng tôi cũng sẽ thay đổi các phương pháp của mình để sử dụng thuộc tính này cho việc theo dõi và duyệt qua các nútLiệt kê 11. Lớp nút danh sách mở rộng 0Bây giờ chúng ta có thể định nghĩa một danh sách liên kết kép như sau Liệt kê 12. Một lớp DoubleLinkedList 1Như đã mô tả trước đó, việc thêm các nút yêu cầu thêm một chút thao tác. Liệt kê 13 cho thấy cách thực hiện điều đó Liệt kê 13. Thêm nút trong danh sách liên kết đôi 2Loại bỏ một mặt hàng khỏi danh sách chi phí tương tự phải được tính đến. Liệt kê 14 cho thấy cách thực hiện điều đó Liệt kê 14. Xóa một mục khỏi danh sách liên kết đôi 3Liệt kê 15 cho thấy cách sử dụng lớp trong chương trình Python Liệt kê 15. Xây dựng danh sách liên kết đôi 4Như bạn có thể thấy, chúng ta có thể sử dụng lớp chính xác như trước khi nó chỉ là một danh sách liên kết đơn. Thay đổi duy nhất là cấu trúc dữ liệu bên trong Bước 7. Tạo danh sách liên kết đôi với dequeVì các kỹ sư khác cũng gặp phải vấn đề tương tự nên chúng tôi có thể đơn giản hóa mọi thứ cho chính mình và sử dụng một trong số ít triển khai hiện có sẵn. Trong Python, chúng ta có thể sử dụng đối tượng deque từ mô-đun 77. Theo tài liệu mô-đun
Ví dụ: đối tượng này chứa các phương thức sau
Cấu trúc dữ liệu cơ bản của 88 là một danh sách Python được liên kết kép. Nút danh sách đầu tiên có chỉ số 0. Sử dụng 88 dẫn đến sự đơn giản hóa đáng kể của lớp 0. Điều duy nhất chúng tôi giữ lại là biến lớp 1 để lưu trữ giá trị nút. Liệt kê 16 như sauLiệt kê 16. Lớp ListNode với deque (đơn giản hóa) 5Định nghĩa của các nút không thay đổi và tương tự như Liệt kê 2. Với kiến thức này, chúng tôi tạo một danh sách các nút như sau Liệt kê 17. Tạo một danh sách với deque 6Việc thêm một mục vào đầu danh sách hoạt động với phương pháp 79 như Liệt kê 18 cho thấyLiệt kê 18. Thêm phần tử vào đầu danh sách 7Tương tự, 78 thêm một nút vào cuối danh sách như Liệt kê 19 cho thấyLiệt kê 19. Thêm phần tử vào cuối danh sách 8Phần kết luậnDanh sách được liên kết dưới dạng cấu trúc dữ liệu dễ triển khai và mang lại sự linh hoạt trong sử dụng. Nó được thực hiện với một vài dòng mã. Để cải thiện, bạn có thể thêm bộ đếm nút - một biến lớp chỉ chứa số lượng nút trong danh sách. Điều này làm giảm việc xác định độ dài danh sách thành một thao tác đơn lẻ với O(1) và bạn không phải duyệt qua toàn bộ danh sách Để đọc thêm và triển khai thay thế, bạn có thể xem tại đây
Sự nhìn nhậnTác giả xin cảm ơn Gerold Rupprecht và Mandy Neumeyer đã hỗ trợ và đóng góp ý kiến khi viết bài này |