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
Nội dung chính Hiển thị
- Bước 1. Nút như một cấu trúc dữ liệu
- Bước 2. Tạo lớp cho danh sách liên kết đơn
- Bước 3. Thêm nút
- Bước 4. Tìm kiếm danh sách
- Bước 5. Xóa một mục khỏi danh sách
- Bước 6. Tạo danh sách liên kết kép
- Bước 7. Tạo danh sách liên kết đôi với deque
- Sự nhìn nhận
Nội dung chính
- Bước 1. Nút như một cấu trúc dữ liệu
- Bước 2. Tạo lớp cho danh sách liên kết đơn
- Bước 3. Thêm nút
- Bước 4. Tìm kiếm danh sách
- Bước 5. Xóa một mục khỏi danh sách
- Bước 6. Tạo danh sách liên kết kép
- Bước 7. Tạo danh sách liên kết đôi với deque
- Sự nhìn nhận
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
node1 = ListNode[15]
node2 = ListNode[8.2]
node3 = ListNode["Berlin"]
Hì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
class SingleLinkedList:
def __init__[self]:
"constructor to initiate this object"
self.head = None
self.tail = None
return
class SingleLinkedList:
def __init__[self]:
"constructor to initiate this object"
self.head = None
self.tail = None
return
class SingleLinkedList:
def __init__[self]:
"constructor to initiate this object"
self.head = None
self.tail = None
return
3. khởi tạo nút với dữ liệuclass SingleLinkedList: def __init__[self]: "constructor to initiate this object" self.head = None self.tail = None return
4. giá trị được lưu trữ trong nútclass SingleLinkedList: def __init__[self]: "constructor to initiate this object" self.head = None self.tail = None return
5. con trỏ tham chiếu đến nút tiếp theoclass SingleLinkedList: def __init__[self]: "constructor to initiate this object" self.head = None self.tail = None return
6. so sánh một giá trị với giá trị nútclass SingleLinkedList: def __init__[self]: "constructor to initiate this object" self.head = None self.tail = None return
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 [
class SingleLinkedList:
def __init__[self]:
"constructor to initiate this object"
self.head = None
self.tail = None
return
class SingleLinkedList:
def __init__[self]:
"constructor to initiate this object"
self.head = None
self.tail = None
return
class SingleLinkedList:
def __init__[self]:
"constructor to initiate this object"
self.head = None
self.tail = None
return
class SingleLinkedList:
def __init__[self]:
"constructor to initiate this object"
self.head = None
self.tail = None
return
Liệt kê 1. Lớp ListNode
class SingleLinkedList:
def __init__[self]:
"constructor to initiate this object"
self.head = None
self.tail = None
return
Tạ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
class SingleLinkedList:
def __init__[self]:
"constructor to initiate this object"
self.head = None
self.tail = None
return
Liệt kê 2. Khởi tạo các nút
node1 = ListNode[15]
node2 = ListNode[8.2]
node3 = ListNode["Berlin"]
Sau khi hoàn thành việc đó, chúng tôi có sẵn ba phiên bản của lớp
class SingleLinkedList:
def __init__[self]:
"constructor to initiate this object"
self.head = None
self.tail = None
return
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
class SingleLinkedList:
def __init__[self]:
"constructor to initiate this object"
self.head = None
self.tail = None
return
7. khởi tạo một đối tượngclass SingleLinkedList: def __init__[self]: "constructor to initiate this object" self.head = None self.tail = None return
65. trả về số nútclass SingleLinkedList: def __init__[self]: "constructor to initiate this object" self.head = None self.tail = None return
66. xuất các giá trị nútclass SingleLinkedList: def __init__[self]: "constructor to initiate this object" self.head = None self.tail = None return
67. thêm một nút vào cuối danh sáchclass SingleLinkedList: def __init__[self]: "constructor to initiate this object" self.head = None self.tail = None return
68. tìm kiếm danh sách cho các nút có giá trị được chỉ địnhclass SingleLinkedList: def __init__[self]: "constructor to initiate this object" self.head = None self.tail = None return
69. xóa nút theo id của nóclass SingleLinkedList: def __init__[self]: "constructor to initiate this object" self.head = None self.tail = None return
Chúng ta sẽ từng bước thực hiện từng phương pháp này
Phương thức
class SingleLinkedList:
def __init__[self]:
"constructor to initiate this object"
self.head = None
self.tail = None
return
class SingleLinkedList:
def __init__[self]:
"constructor to initiate this object"
self.head = None
self.tail = None
return
class SingleLinkedList:
def __init__[self]:
"constructor to initiate this object"
self.head = None
self.tail = None
return
class SingleLinkedList:
def __init__[self]:
"constructor to initiate this object"
self.head = None
self.tail = None
return
class SingleLinkedList:
def __init__[self]:
"constructor to initiate this object"
self.head = None
self.tail = None
return
node1 = ListNode[15]
node2 = ListNode[8.2]
node3 = ListNode["Berlin"]
Liệt kê 3. Lớp SingleLinkedList [phần một]
class SingleLinkedList:
def __init__[self]:
"constructor to initiate this object"
self.head = None
self.tail = None
return
Bước 3. Thêm nút
Việc thêm các mục vào danh sách được thực hiện thông qua
class SingleLinkedList:
def __init__[self]:
"constructor to initiate this object"
self.head = None
self.tail = None
return
class SingleLinkedList:
def __init__[self]:
"constructor to initiate this object"
self.head = None
self.tail = None
return
class SingleLinkedList:
def __init__[self]:
"constructor to initiate this object"
self.head = None
self.tail = None
return
class SingleLinkedList:
def __init__[self]:
"constructor to initiate this object"
self.head = None
self.tail = None
return
class SingleLinkedList:
def __init__[self]:
"constructor to initiate this object"
self.head = None
self.tail = None
return
Trong 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]
class SingleLinkedList:
def __init__[self]:
"constructor to initiate this object"
self.head = None
self.tail = None
return
Phương thức
class SingleLinkedList:
def __init__[self]:
"constructor to initiate this object"
self.head = None
self.tail = None
return
class SingleLinkedList:
def __init__[self]:
"constructor to initiate this object"
self.head = None
self.tail = None
return
node1 = ListNode[15]
node2 = ListNode[8.2]
node3 = ListNode["Berlin"]
Liệt kê 5. Lớp SingleLinkedList [phần ba]
class SingleLinkedList:
def __init__[self]:
"constructor to initiate this object"
self.head = None
self.tail = None
return
Phương thức
class SingleLinkedList:
def __init__[self]:
"constructor to initiate this object"
self.head = None
self.tail = None
return
class SingleLinkedList:
def __init__[self]:
"constructor to initiate this object"
self.head = None
self.tail = None
return
class SingleLinkedList:
def __init__[self]:
"constructor to initiate this object"
self.head = None
self.tail = None
return
Liệt kê 6. Lớp SingleLinkedList [phần bốn]
class SingleLinkedList:
def __init__[self]:
"constructor to initiate this object"
self.head = None
self.tail = None
return
Dựa trên lớp
class SingleLinkedList:
def __init__[self]:
"constructor to initiate this object"
self.head = None
self.tail = None
return
class SingleLinkedList:
def __init__[self]:
"constructor to initiate this object"
self.head = None
self.tail = None
return
class SingleLinkedList:
def __init__[self]:
"constructor to initiate this object"
self.head = None
self.tail = None
return
Liệt kê 7. Tạo các nút và đầu ra danh sách
class SingleLinkedList:
def __init__[self]:
"constructor to initiate this object"
self.head = None
self.tail = None
return
Đầ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
class SingleLinkedList:
def __init__[self]:
"constructor to initiate this object"
self.head = None
self.tail = None
return
Bước 4. Tìm kiếm danh sách
Tìm kiếm toàn bộ danh sách được thực hiện bằng phương pháp
class SingleLinkedList:
def __init__[self]:
"constructor to initiate this object"
self.head = None
self.tail = None
return
Trong 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
class SingleLinkedList:
def __init__[self]:
"constructor to initiate this object"
self.head = None
self.tail = None
return
class SingleLinkedList:
def __init__[self]:
"constructor to initiate this object"
self.head = None
self.tail = None
return
Liệt kê 9. Phương thức tìm kiếm unordered_search[]
class SingleLinkedList:
def __init__[self]:
"constructor to initiate this object"
self.head = None
self.tail = None
return
Bước 5. Xóa một mục khỏi danh sách
Việ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à
class SingleLinkedList:
def __init__[self]:
"constructor to initiate this object"
self.head = None
self.tail = None
return
class SingleLinkedList:
def __init__[self]:
"constructor to initiate this object"
self.head = None
self.tail = None
return
Liệt kê 10. Xóa một nút theo số nút
class SingleLinkedList:
def __init__[self]:
"constructor to initiate this object"
self.head = None
self.tail = None
return
Bướ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
class SingleLinkedList:
def __init__[self]:
"constructor to initiate this object"
self.head = None
self.tail = None
return
class SingleLinkedList:
def __init__[self]:
"constructor to initiate this object"
self.head = None
self.tail = None
return
Liệt kê 11. Lớp nút danh sách mở rộng
node1 = ListNode[15]
node2 = ListNode[8.2]
node3 = ListNode["Berlin"]
Bâ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
node1 = ListNode[15]
node2 = ListNode[8.2]
node3 = ListNode["Berlin"]
Như đã 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
node1 = ListNode[15]
node2 = ListNode[8.2]
node3 = ListNode["Berlin"]
Loạ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
node1 = ListNode[15]
node2 = ListNode[8.2]
node3 = ListNode["Berlin"]
Liệ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
node1 = ListNode[15]
node2 = ListNode[8.2]
node3 = ListNode["Berlin"]
Như 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 deque
Vì 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
class SingleLinkedList:
def __init__[self]:
"constructor to initiate this object"
self.head = None
self.tail = None
return
Deques là sự khái quát hóa của ngăn xếp và hàng đợi [tên được phát âm là "bộ bài" và là viết tắt của "hàng đợi hai đầu"]. Deques hỗ trợ nối thêm và bật hiệu quả bộ nhớ, an toàn cho luồng từ hai bên của deque với hiệu suất O[1] xấp xỉ như nhau theo cả hai hướng
Ví dụ: đối tượng này chứa các phương thức sau
78. thêm một mục vào phía bên phải của danh sách [kết thúc]class SingleLinkedList: def __init__[self]: "constructor to initiate this object" self.head = None self.tail = None return
79. thêm một mục vào phía bên trái của danh sách [đầu]class SingleLinkedList: def __init__[self]: "constructor to initiate this object" self.head = None self.tail = None return
80. xóa tất cả các mục khỏi danh sáchclass SingleLinkedList: def __init__[self]: "constructor to initiate this object" self.head = None self.tail = None return
81. đếm số mục có giá trị nhất địnhclass SingleLinkedList: def __init__[self]: "constructor to initiate this object" self.head = None self.tail = None return
82. tìm sự xuất hiện đầu tiên của một giá trị trong danh sáchclass SingleLinkedList: def __init__[self]: "constructor to initiate this object" self.head = None self.tail = None return
83. chèn một mục trong danh sáchclass SingleLinkedList: def __init__[self]: "constructor to initiate this object" self.head = None self.tail = None return
84. xóa một mục khỏi phía bên phải của danh sách [kết thúc]class SingleLinkedList: def __init__[self]: "constructor to initiate this object" self.head = None self.tail = None return
85. xóa một mục từ phía bên trái của danh sách [đầu]class SingleLinkedList: def __init__[self]: "constructor to initiate this object" self.head = None self.tail = None return
86. xóa một mục khỏi danh sáchclass SingleLinkedList: def __init__[self]: "constructor to initiate this object" self.head = None self.tail = None return
87. đảo ngược danh sáchclass SingleLinkedList: def __init__[self]: "constructor to initiate this object" self.head = None self.tail = None return
Cấu trúc dữ liệu cơ bản của
class SingleLinkedList:
def __init__[self]:
"constructor to initiate this object"
self.head = None
self.tail = None
return
class SingleLinkedList:
def __init__[self]:
"constructor to initiate this object"
self.head = None
self.tail = None
return
class SingleLinkedList:
def __init__[self]:
"constructor to initiate this object"
self.head = None
self.tail = None
return
class SingleLinkedList:
def __init__[self]:
"constructor to initiate this object"
self.head = None
self.tail = None
return
Liệt kê 16. Lớp ListNode với deque [đơn giản hóa]
node1 = ListNode[15]
node2 = ListNode[8.2]
node3 = ListNode["Berlin"]
Đị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
node1 = ListNode[15]
node2 = ListNode[8.2]
node3 = ListNode["Berlin"]
Việc thêm một mục vào đầu danh sách hoạt động với phương pháp
class SingleLinkedList:
def __init__[self]:
"constructor to initiate this object"
self.head = None
self.tail = None
return
Liệt kê 18. Thêm phần tử vào đầu danh sách
node1 = ListNode[15]
node2 = ListNode[8.2]
node3 = ListNode["Berlin"]
Tương tự,
class SingleLinkedList:
def __init__[self]:
"constructor to initiate this object"
self.head = None
self.tail = None
return
Liệt kê 19. Thêm phần tử vào cuối danh sách
node1 = ListNode[15]
node2 = ListNode[8.2]
node3 = ListNode["Berlin"]
Phần kết luận
Danh 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
24 - Kiểu dữ liệu danh sách được liên kết cho Python [https. //pythonhosted. tổ chức/danh sách/]class SingleLinkedList: def __init__[self]: "constructor to initiate this object" self.head = None self.tail = None return
77 - Kiểu dữ liệu vùng chứa [https. // tài liệu. con trăn. tổ chức/3. 6/thư viện/bộ sưu tập. html]class SingleLinkedList: def __init__[self]: "constructor to initiate this object" self.head = None self.tail = None return
Sự nhìn nhận
Tá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