Danh sách được liên kết là một trong những cấu trúc dữ liệu cơ bản nhất đại diện cho một chuỗi các nút. Phần tử đầu tiên của dãy được gọi là phần đầu của Danh sách liên kết trong khi phần tử cuối cùng tương ứng với phần đuôi
Mỗi nút trong chuỗi có một con trỏ tới phần tử tiếp theo và tùy chọn một con trỏ tới phần tử trước đó. Trong Danh sách được liên kết đơn lẻ, mỗi nút chỉ trỏ đến nút tiếp theo
Danh sách liên kết đơn — Nguồn. Tác giả
Mặt khác, trong Danh sách liên kết kép, mỗi nút trỏ đến nút tiếp theo cũng như nút trước đó
Danh sách liên kết kép — Nguồn. Tác giả
Danh sách được liên kết cực kỳ hữu ích trong các tình huống khác nhau. Chúng thường được ưu tiên hơn các mảng tiêu chuẩn khi
- bạn cần một khoảng thời gian cố định khi thêm hoặc xóa các phần tử khỏi chuỗi
- quản lý bộ nhớ hiệu quả hơn, đặc biệt là khi số lượng phần tử không xác định [nếu là mảng, bạn có thể phải liên tục thu nhỏ hoặc tăng chúng. Lưu ý rằng các mảng được điền thường chiếm ít bộ nhớ hơn so với Danh sách được liên kết
- bạn muốn chèn các mục vào điểm giữa hiệu quả hơn
Không giống như các ngôn ngữ có mục đích chung khác, Python không có triển khai Danh sách được liên kết tích hợp sẵn trong thư viện chuẩn của nó. Trong bài viết hôm nay, chúng ta sẽ khám phá cách triển khai lớp Danh sách liên kết do người dùng định nghĩa bằng Python
Triển khai lớp liên kết do người dùng xác định trong Python
Trước tiên, hãy tạo một lớp do người dùng định nghĩa cho các nút riêng lẻ trong Danh sách được liên kết. Lớp này sẽ phù hợp cho cả Danh sách liên kết đơn hoặc kép. Do đó, các thể hiện của lớp này phải có khả năng lưu trữ giá trị của nút, nút tiếp theo cũng như nút trước đó
class Node:
def __init__[self, value, next_node=None, prev_node=None]:
self.value = value
self.next = next_node
self.prev = prev_node
def __str__[self]:
return str[self.value]Lưu ý rằng khi một phiên bản của
class LinkedList:2 có
def __init__[self, values=None]:
self.head = None
self.tail = None if values is not None:
self.add_multiple_nodes[values]
class LinkedList:3 được đặt thành
def __init__[self, values=None]:
self.head = None
self.tail = None if values is not None:
self.add_multiple_nodes[values]
class LinkedList:4 thì điều đó có nghĩa là nó thực chất là phần đuôi của Danh sách được liên kết [Đơn lẻ hoặc kép]. Tương tự, trong Danh sách liên kết kép, khi một nút có
def __init__[self, values=None]:
self.head = None
self.tail = None if values is not None:
self.add_multiple_nodes[values]
class LinkedList:5 được đặt thành
def __init__[self, values=None]:
self.head = None
self.tail = None if values is not None:
self.add_multiple_nodes[values]
class LinkedList:4 thì điều này cho biết nút đó là đầu của Danh sách được liên kết
def __init__[self, values=None]:
self.head = None
self.tail = None if values is not None:
self.add_multiple_nodes[values]
Bây giờ chúng ta đã tạo một lớp cho các Nút, bây giờ chúng ta có thể tạo lớp cho chính Danh sách được liên kết. Như đã đề cập, Danh sách được liên kết có một
class LinkedList:7, một
def __init__[self, values=None]:
self.head = None
self.tail = None if values is not None:
self.add_multiple_nodes[values]
class LinkedList:8 và các nút trỏ đến nhau
def __init__[self, values=None]:
self.head = None
self.tail = None if values is not None:
self.add_multiple_nodes[values]
class LinkedList:
def __init__[self, values=None]:
self.head = None
self.tail = None if values is not None:
self.add_multiple_nodes[values]
Bây giờ để thêm các giá trị được cung cấp trong hàm tạo dưới dạng các nút trong Danh sách được liên kết, chúng ta cần xác định một số phương thức bổ sung
Phương thức đầu tiên có tên là
class LinkedList:9 được sử dụng để thêm một nút vào Danh sách được liên kết
def __init__[self, values=None]:
self.head = None
self.tail = None if values is not None:
self.add_multiple_nodes[values]
class LinkedList:0
def __init__[self, values=None]:
self.head = None
self.tail = None if values is not None:
self.add_multiple_nodes[values]
Bây giờ chúng ta hãy nhanh chóng đi qua logic của phương pháp. Nếu Danh sách liên kết không có phần đầu, thì có nghĩa là nó rỗng và do đó nút được thêm vào sẽ vừa là phần đầu vừa là phần cuối của Danh sách được liên kết. Nếu phần đầu không trống thì ta thêm phần tử
class LinkedList:2 vừa tạo làm phần tử
def __init__[self, values=None]:
self.head = None
self.tail = None if values is not None:
self.add_multiple_nodes[values]
class LinkedList:3 của phần tử
def __init__[self, values=None]:
self.head = None
self.tail = None if values is not None:
self.add_multiple_nodes[values]
class LinkedList:8 hiện tại và cuối cùng di chuyển phần đuôi để trỏ đến phần tử
def __init__[self, values=None]:
self.head = None
self.tail = None if values is not None:
self.add_multiple_nodes[values]
class LinkedList:2 mới tạo
def __init__[self, values=None]:
self.head = None
self.tail = None if values is not None:
self.add_multiple_nodes[values]
Phương thức thứ hai được gọi là
class LinkedList:04, được gọi trong hàm tạo và chỉ đơn giản là gọi phương thức
def __init__[self, values=None]:
self.head = None
self.tail = None if values is not None:
self.add_multiple_nodes[values]
class LinkedList:05 mà chúng ta đã xác định trước đó để thêm nhiều giá trị dưới dạng các nút trong thể hiện Danh sách được liên kết
def __init__[self, values=None]:
self.head = None
self.tail = None if values is not None:
self.add_multiple_nodes[values]
class LinkedList:7
def __init__[self, values=None]:
self.head = None
self.tail = None if values is not None:
self.add_multiple_nodes[values]
Cho đến nay, lớp Danh sách liên kết của chúng tôi trông giống như bên dưới
class LinkedList:8
def __init__[self, values=None]:
self.head = None
self.tail = None if values is not None:
self.add_multiple_nodes[values]
Bây giờ, hãy tạo một phương thức bổ sung có thể chèn một phần tử mới nhưng lần này là ở phần đầu của Danh sách được liên kết, tôi. e. như một cái đầu
class LinkedList:9
def __init__[self, values=None]:
self.head = None
self.tail = None if values is not None:
self.add_multiple_nodes[values]
Bây giờ, hãy ghi đè một số phương thức đặc biệt trong lớp của chúng ta có khả năng hữu ích. Đầu tiên, hãy triển khai phương thức
class LinkedList:06 để biểu diễn chuỗi của đối tượng Danh sách được liên kết có thể đọc được bằng con người. Ví dụ: khi in ra Danh sách được liên kết với các nút
def __init__[self, values=None]:
self.head = None
self.tail = None if values is not None:
self.add_multiple_nodes[values]
class LinkedList:07, đầu ra sẽ là ____108
def __init__[self, values=None]:
self.head = None
self.tail = None if values is not None:
self.add_multiple_nodes[values]
class LinkedList:3
def __init__[self, values=None]:
self.head = None
self.tail = None if values is not None:
self.add_multiple_nodes[values]
Thứ hai, hãy triển khai phương thức
class LinkedList:09 sẽ trả về độ dài của lớp do người dùng định nghĩa, về cơ bản là số lượng nút có trong chuỗi. Tất cả những gì chúng ta cần làm là lặp qua mọi nút của chuỗi cho đến khi chúng ta đến phần cuối của Danh sách được liên kết
def __init__[self, values=None]:
self.head = None
self.tail = None if values is not None:
self.add_multiple_nodes[values]
class LinkedList:5
def __init__[self, values=None]:
self.head = None
self.tail = None if values is not None:
self.add_multiple_nodes[values]
Cuối cùng, hãy đảm bảo rằng lớp
class LinkedList:70 có thể lặp lại bằng cách triển khai phương thức
def __init__[self, values=None]:
self.head = None
self.tail = None if values is not None:
self.add_multiple_nodes[values]
class LinkedList:71
def __init__[self, values=None]:
self.head = None
self.tail = None if values is not None:
self.add_multiple_nodes[values]
class LinkedList:8
def __init__[self, values=None]:
self.head = None
self.tail = None if values is not None:
self.add_multiple_nodes[values]
Ngoài ra, chúng tôi cũng có thể tạo một thuộc tính có tên là
class LinkedList:72 để chúng tôi có thể truy cập các giá trị của tất cả các nút có trong chuỗi
def __init__[self, values=None]:
self.head = None
self.tail = None if values is not None:
self.add_multiple_nodes[values]
class LinkedList:0
def __init__[self, values=None]:
self.head = None
self.tail = None if values is not None:
self.add_multiple_nodes[values]
Lớp cuối cùng trông như dưới đây
class LinkedList:0
def __init__[self, values=None]:
self.head = None
self.tail = None if values is not None:
self.add_multiple_nodes[values]
Giờ đây, ngay cả lớp
class LinkedList:2 của chúng ta cũng có thể đại diện cho các nút được bao gồm trong Danh sách liên kết đơn hoặc kép, lớp
def __init__[self, values=None]:
self.head = None
self.tail = None if values is not None:
self.add_multiple_nodes[values]
class LinkedList:70 mà chúng ta đã xác định chỉ có thể hỗ trợ Danh sách liên kết đơn. Điều này là do khi thêm các nút, chúng tôi không chỉ định nút trước đó
def __init__[self, values=None]:
self.head = None
self.tail = None if values is not None:
self.add_multiple_nodes[values]
Để đối phó với Danh sách liên kết đôi, chúng ta chỉ cần tạo một lớp bổ sung kế thừa từ lớp
class LinkedList:70 và ghi đè các phương thức
def __init__[self, values=None]:
self.head = None
self.tail = None if values is not None:
self.add_multiple_nodes[values]
class LinkedList:05 và
def __init__[self, values=None]:
self.head = None
self.tail = None if values is not None:
self.add_multiple_nodes[values]
class LinkedList:77
def __init__[self, values=None]:
self.head = None
self.tail = None if values is not None:
self.add_multiple_nodes[values]
class LinkedList:1
def __init__[self, values=None]:
self.head = None
self.tail = None if values is not None:
self.add_multiple_nodes[values]
Mã đầy đủ cho danh sách liên kết do người dùng xác định trong Python
Mã đầy đủ chứa ba lớp mà chúng tôi đã tạo như một phần của hướng dẫn hôm nay được cung cấp bên dưới dưới dạng Gist GitHub
Mã đầy đủ chứa các lớp Python Node, LinkedList và DoublyLinkedList — Nguồn. Tác giảSuy nghĩ cuối cùng
Trong hướng dẫn hôm nay, chúng ta đã thảo luận về một trong những cấu trúc dữ liệu cơ bản nhất, đó là Danh sách được liên kết. Do thư viện chuẩn của Python không chứa bất kỳ triển khai nào của cấu trúc dữ liệu cụ thể này, chúng tôi đã khám phá cách một người có thể triển khai lớp Danh sách liên kết do người dùng xác định từ đầu
Trở thành thành viên và đọc mọi câu chuyện trên Medium. Phí thành viên của bạn hỗ trợ trực tiếp cho tôi và các nhà văn khác mà bạn đọc. Bạn cũng sẽ có toàn quyền truy cập vào mọi câu chuyện trên Phương tiện