Cách in danh sách liên kết trong python
Bài viết này sẽ thảo luận về một cấu trúc dữ liệu tùy chỉnh được gọi là Danh sách được liên kết. Chúng tôi cũng sẽ triển khai danh sách được liên kết trong Python và thực hiện các thao tác khác nhau trên danh sách được liên kết Show
Danh sách liên kết trong Python là gìNhư tên gợi ý, danh sách liên kết là cấu trúc dữ liệu chứa các phần tử được kết nối bằng liên kết Một danh sách được liên kết được tạo bằng cách sử dụng các đối tượng được gọi là các nút. Mỗi nút chứa hai thuộc tính - một để lưu trữ dữ liệu và một để kết nối với nút tiếp theo trong danh sách được liên kết Bạn có thể hiểu cấu trúc của một nút bằng hình sau Nơi đây,
Như trong hình dưới đây, chúng ta có thể kết nối nhiều nút khác nhau để tạo danh sách liên kết Nơi đây,
Bây giờ chúng ta đã hiểu cấu trúc cơ bản của danh sách liên kết. Hãy để chúng tôi thực hiện một danh sách được liên kết trong Python Cách tạo danh sách liên kết trong PythonVì các nút là các khối xây dựng của một danh sách được liên kết, trước tiên chúng ta sẽ tạo một nút. Đối với điều này, chúng ta sẽ định nghĩa một lớp 9 với các thuộc tính 0 và 1 như hình bên dưới 7đầu ra 8Trong ví dụ trên, bạn có thể quan sát thấy rằng thuộc tính 1 của 9 đề cập đến 8 theo mặc định. Khi chúng ta chèn nó vào danh sách liên kết, chúng ta gán thuộc tính 1 cho các nút trong danh sách liên kết, như chúng ta sẽ thảo luận trướcTa phải tạo đối tượng có thuộc tính 4 để tạo danh sách liên kết. Chúng ta có thể định nghĩa lớp 41 như hình bên dưới
đầu ra
Trong ví dụ trên, chúng ta đã tạo một danh sách liên kết Sau đó, chúng tôi tạo các nút theo cách thủ công bằng cách sử dụng dữ liệu đã cho, thêm từng nút một vào danh sách được liên kết và in chúng. Sau này, chúng ta sẽ học cách chèn các phần tử vào danh sách liên kết bằng cách sử dụng vòng lặp 42 của PythonBây giờ chúng ta hãy thảo luận về cách chúng ta có thể in tất cả các phần tử của danh sách được liên kết mà không cần truy cập tất cả các nút theo cách thủ công In tất cả các phần tử của danh sách được liên kết bằng PythonChúng tôi sẽ sử dụng vòng lặp 42 để in tất cả các phần tử danh sách được liên kếtBắt đầu từ con trỏ 4, đầu tiên chúng ta sẽ in dữ liệu trong nút hiện tại bằng thuộc tính 0 của nút. Sau đó, chúng ta sẽ di chuyển đến nút tiếp theo bằng cách sử dụng con trỏ 1Chúng tôi sẽ làm theo quy trình này cho đến khi chúng tôi đến cuối danh sách được liên kết (i. e. , thuộc tính 1 của một nút được tìm thấy là 8). Như được hiển thị bên dưới, bạn có thể triển khai toàn bộ logic trong phương thức 49 5đầu ra 4Chèn phần tử vào danh sách liên kết trong PythonCó 4 tình huống xảy ra khi chèn phần tử vào danh sách liên kết
Hãy để chúng tôi thảo luận về cách chèn một phần tử vào danh sách được liên kết trong mọi tình huống Chèn một phần tử vào danh sách liên kết rỗngĐể chèn một phần tử vào một danh sách liên kết trống, chúng ta sẽ định nghĩa một phương thức 70 chấp nhận phần tử đó làm đối số đầu vào và thêm một nút chứa phần tử đầu vào vào danh sách được liên kếtĐối với điều này, chúng tôi sẽ tạo một nút trong 70 với phần tử đầu vào là 0. Sau khi tạo nút ta sẽ gán cho nút thuộc tính 4Bằng cách này, nút mới sẽ trở thành nút đầu tiên của danh sách liên kết. Phương pháp có thể được thực hiện như sau 7đầu ra 2Chèn phần tử vào đầu danh sách liên kếtĐể chèn một phần tử vào đầu danh sách không trống, chúng ta sẽ định nghĩa một phương thức 74 lấy một phần tử làm đầu vào và thêm nó vào đầu danh sách được liên kết. Trong phương thức 74, đầu tiên chúng ta sẽ tạo một nút với phần tử đầu vào là dữ liệuSau đó, ta sẽ trỏ thuộc tính 1 của nút vừa tạo tới nút mà thuộc tính 4 của danh sách liên kết trỏ đến. Tiếp theo, chúng ta sẽ gán cho nút vừa tạo thuộc tính 4Bằng cách này, nút mới sẽ được chèn vào đầu danh sách liên kết 8đầu ra 9Như hình bên dưới, chúng ta có thể kết hợp các phương thức trên để tạo một phương thức duy nhất để chèn một phần tử vào đầu danh sách liên kết 80đầu ra 9Chúng tôi đã hợp nhất phương thức 70 vào phương thức 74 vì việc chèn vào danh sách liên kết trống về cơ bản có nghĩa là chúng tôi đang chèn một phần tử vào đầu danh sách được liên kếtChèn một phần tử vào cuối danh sách liên kếtChèn phần tử vào cuối danh sách rỗng cũng giống như chèn phần tử vào đầu danh sách liên kết Để chèn một phần tử vào cuối danh sách liên kết, trước tiên chúng ta sẽ kiểm tra xem danh sách liên kết có trống không. Nếu danh sách được liên kết được tìm thấy trống, chúng ta có thể chỉ cần gán một nút chứa phần tử mới cho thuộc tính 4 như chúng ta đã làm trong phương thức 74Nếu không, chúng tôi sẽ duyệt qua danh sách được liên kết cho đến khi kết thúc bằng cách sử dụng vòng lặp 42. Chúng tôi sẽ bắt đầu với 4 và tiếp tục di chuyển đến nút tiếp theo bằng cách sử dụng thuộc tính 1 của các nút cho đến khi chúng tôi thấy rằng thuộc tính 1 của nút trỏ đến 8Khi chúng tôi đến một nút có thuộc tính 1 trỏ đến 8, chúng tôi đang ở nút cuối cùng. Bây giờ, chúng ta sẽ tạo một nút mới bằng cách sử dụng dữ liệu đầu vào và gán nút này cho thuộc tính tiếp theo của nút cuối cùng của danh sách liên kếtBằng cách này, phần tử mới sẽ được chèn vào cuối danh sách liên kết. Bạn có thể triển khai toàn bộ logic này trong phương thức 80 như sau 82đầu ra 83Chèn một phần tử vào một vị trí nhất định trong danh sách được liên kếtChúng ta sẽ sử dụng một biến đếm và một vòng lặp 42 để chèn một phần tử vào một vị trí nhất định trong danh sách liên kếtChúng ta sẽ bắt đầu từ con trỏ Head và tiếp tục di chuyển đến nút tiếp theo bằng vòng lặp 42. Trong mỗi lần lặp, chúng ta cũng sẽ tăng biến đếmKhi chúng tôi đến nút trước vị trí đã cho, chúng tôi thoát khỏi vòng lặp 42. Ngoài ra, chúng tôi sẽ thoát khỏi vòng lặp nếu chúng tôi đến cuối danh sách được liên kết. Nếu không, chương trình sẽ gặp lỗiSau đó, nếu chúng ta vẫn ở 4, chúng ta phải thêm phần tử vào vị trí đầu tiên của danh sách được liên kết; . Tiếp theo, chúng tôi sẽ gán nút của phần tử mới cho danh sách được liên kết của 4Nếu không phải chèn phần tử vào vị trí thứ nhất, chúng ta sẽ gán nút tại vị trí đã cho cho con trỏ 1 của nút chứa phần tử mới. Tiếp theo, chúng ta sẽ gán nút mới cho thuộc tính 1 của nút tại 89Bằng cách này, phần tử mới sẽ được chèn vào vị trí đã cho. Như được hiển thị bên dưới, bạn có thể triển khai toàn bộ logic trong phương thức 90 84đầu ra 85Xóa phần tử khỏi danh sách liên kết trong PythonCó thể xảy ra ba tình huống khi chúng ta cố gắng xóa một phần tử khỏi danh sách liên kết
Hãy để chúng tôi thảo luận về tất cả các trường hợp này từng cái một Xóa phần tử đầu tiên của danh sách liên kếtĐể xóa phần tử đầu tiên của danh sách liên kết, trước tiên chúng ta sẽ kiểm tra xem danh sách liên kết có trống hay không Đối với điều này, chúng tôi sẽ kiểm tra xem 4 của danh sách được liên kết có trỏ đến 8 không. Nếu có, chúng tôi sẽ thông báo cho người dùng rằng danh sách được liên kết trống và chúng tôi không có phần tử nào để xóaNếu không, chúng tôi sẽ gán nút đầu tiên cho một biến tạm thời. Sau đó, chúng ta sẽ gán nút thứ hai của danh sách liên kết cho thuộc tính 4Sau đó, chúng tôi sẽ xóa nút đầu tiên được lưu trữ trong biến tạm thời bằng cách sử dụng câu lệnh 94. Như được hiển thị bên dưới, bạn có thể triển khai toàn bộ logic trong phương thức 95 86đầu ra 87Xóa phần tử cuối cùng của danh sách liên kếtĐể xóa phần tử cuối cùng của danh sách liên kết, trước tiên chúng ta sẽ kiểm tra xem danh sách liên kết có trống hay không Đối với điều này, chúng tôi sẽ kiểm tra xem 4 của danh sách được liên kết có trỏ đến 8 không. Nếu có, chúng tôi sẽ thông báo cho người dùng rằng danh sách được liên kết trống và chúng tôi không có phần tử nào để xóaNếu có các phần tử có mặt trong danh sách, chúng tôi sẽ thực hiện theo quy trình sau
Chúng ta có thể xóa phần tử cuối cùng của danh sách liên kết bằng cách thực hiện các bước trên. Như được hiển thị bên dưới, bạn có thể triển khai toàn bộ logic trong phương thức 813 88đầu ra 89Xóa phần tử tại vị trí bất kỳ trong danh sách liên kếtĐể xóa một phần tử tại một vị trí bất kỳ trong danh sách liên kết, trước tiên chúng ta sẽ kiểm tra xem danh sách liên kết có trống hay không Đối với điều này, chúng tôi sẽ kiểm tra xem 4 của danh sách được liên kết có trỏ đến 8 không. Nếu có, chúng tôi sẽ thông báo cho người dùng rằng danh sách được liên kết trống và chúng tôi không có phần tử nào để xóaNếu trong danh sách liên kết có phần tử mà ta phải xóa phần tử ở vị trí khác ta thực hiện theo các bước sau
Chúng ta có thể thực hiện logic trên trong phương thức 834 được thảo luận bên dưới 0đầu ra 1Đếm số phần tử trong danh sách liên kết trong PythonĐể đếm số phần tử trong danh sách liên kết, chúng ta chỉ cần khởi tạo biến 819 thành 0Sau đó, chúng tôi sẽ bắt đầu từ 4 và di chuyển đến nút tiếp theo bằng vòng lặp 42 cho đến khi chúng tôi đến cuối danh sách được liên kết. Trong mỗi lần lặp của vòng lặp 42, chúng tôi sẽ tăng 819 lên 1Sau khi thực hiện vòng lặp 42 ta sẽ có số phần tử của danh sách liên kết trong biến 819. Bạn có thể triển khai logic này như được hiển thị trong phương pháp 842 bên dưới 2đầu ra 3Có thể xảy ra hai tình huống để cập nhật giá trị tại một nút trong danh sách liên kết
Thay thế một giá trị trong danh sách được liên kếtĐể thay thế một giá trị trong danh sách được liên kết, chúng tôi sẽ bắt đầu từ nút đầu tiên và duyệt qua danh sách được liên kết bằng vòng lặp 42Chúng tôi sẽ kiểm tra xem nút 98 có chứa giá trị được thay thế tại mỗi nút không. Nếu có, chúng tôi sẽ thay thế giá trị trong nút hiện tại bằng giá trị mớiBằng cách này, chúng ta có thể cập nhật lần xuất hiện đầu tiên của bất kỳ phần tử nào trong danh sách được liên kết như trong phương thức 845 4đầu ra 5Để cập nhật phần tử tại một vị trí nhất định trong danh sách liên kết, trước tiên chúng ta sẽ kiểm tra xem danh sách liên kết có trống không. Nếu có, có thể có hai tình huống Nếu danh sách được liên kết trống và chúng tôi phải cập nhật một phần tử khác với vị trí đầu tiên, chúng tôi sẽ thông báo cho người dùng rằng điều đó không thể thực hiện được Nếu danh sách liên kết trống và chúng ta phải cập nhật phần tử ở vị trí đầu tiên, chúng ta sẽ tạo một nút mới với phần tử đã cho và gán nút vào 4 của danh sách liên kết. Nếu không, chúng ta sẽ khởi tạo biến 847 thành 1Sau đó, chúng tôi sẽ duyệt qua danh sách được liên kết bằng vòng lặp 42. Trong mỗi lần lặp của vòng lặp 42, chúng ta sẽ di chuyển đến nút tiếp theo trong danh sách liên kết, tăng biến 847 lên 1 và kiểm tra xem đã đến vị trí phần tử cần cập nhật chưaNếu đến vị trí cần cập nhật, chúng tôi sẽ cập nhật giá trị tại nút hiện tại của danh sách liên kết và thông báo cho người dùng Nếu chúng ta không đến được vị trí cần cập nhật và vòng lặp 42 kết thúc, chúng ta sẽ thông báo cho người dùng rằng không đủ phần tử và chúng ta không thể cập nhật giá trị. Logic này có thể được thực hiện như hình bên dưới trong phương pháp 852 6đầu ra 7Tại sao nên sử dụng Danh sách được liên kết trong Python
Danh sách liên kết triển khai đầy đủ trong PythonSau đây là mã chạy đầy đủ để triển khai danh sách được liên kết trong Python với tất cả các phương thức được thảo luận trong bài viết này 8Sự kết luậnTrong bài viết này, chúng ta đã thảo luận về cấu trúc dữ liệu danh sách được liên kết và cách triển khai nó trong Python. Chúng tôi cũng đã triển khai các phương thức cho các hoạt động khác nhau trong danh sách được liên kết Trong bài viết này, chúng tôi đã thực hiện tất cả các hoạt động bằng cách sử dụng các phương pháp. Bạn cũng có thể triển khai từng thao tác bằng cách sử dụng các hàm lấy đầu vào là _____14 của danh sách được liên kết và trả về phần đầu sau khi thực hiện các thao tác được yêu cầu Tuy nhiên, điều này sẽ yêu cầu nhiều tài nguyên hơn trong quá trình thực thi. Vì vậy, tôi khuyên bạn nên sử dụng phương pháp được sử dụng trong bài viết này |