programming python

Có danh sách liên kết trong python không?

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 thể hiện của một

class LinkedList:
    def __init__[self, values=None]:
        self.head = None
        self.tail = None        if values is not None:
            self.add_multiple_nodes[values]

2 có ____1_______3 được đặt thành ____1_______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ó ____1_______5 được đặt thành ____1_______4 thì điều này cho biết nút đó là đầu của Danh sách được liên kết

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, một Danh sách Liên kết có một

class LinkedList:
    def __init__[self, values=None]:
        self.head = None
        self.tail = None        if values is not None:
            self.add_multiple_nodes[values]

7, một

class LinkedList:
    def __init__[self, values=None]:
        self.head = None
        self.tail = None        if values is not None:
            self.add_multiple_nodes[values]

8 và các nút trỏ tới nhau

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:
    def __init__[self, values=None]:
        self.head = None
        self.tail = None        if values is not None:
            self.add_multiple_nodes[values]

9 được sử dụng để thêm một nút vào Danh sách được liên kết

def add_node[self, value]:
    if self.head is None:
        self.tail = self.head = Node[value]
    else:
        self.tail.next = Node[value]
        self.tail = self.tail.next
    return self.tail

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 được 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:
    def __init__[self, values=None]:
        self.head = None
        self.tail = None        if values is not None:
            self.add_multiple_nodes[values]

2 vừa tạo vào thành phần tử

class LinkedList:
    def __init__[self, values=None]:
        self.head = None
        self.tail = None        if values is not None:
            self.add_multiple_nodes[values]

3 của phần tử hiện tại

class LinkedList:
    def __init__[self, values=None]:
        self.head = None
        self.tail = None        if values is not None:
            self.add_multiple_nodes[values]

8 và cuối cùng di chuyển phần đuôi để trỏ đến phần tử

class LinkedList:
    def __init__[self, values=None]:
        self.head = None
        self.tail = None        if values is not None:
            self.add_multiple_nodes[values]

2 mới tạo

Phương thức thứ hai được gọi là

def add_node[self, value]:
    if self.head is None:
        self.tail = self.head = Node[value]
    else:
        self.tail.next = Node[value]
        self.tail = self.tail.next
    return self.tail

4 được gọi trong hàm tạo và chỉ đơn giản là gọi phương thức

def add_node[self, value]:
    if self.head is None:
        self.tail = self.head = Node[value]
    else:
        self.tail.next = Node[value]
        self.tail = self.tail.next
    return self.tail

5 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 add_multiple_nodes[self, values]:
    for value in values:
        self.add_node[value]

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:
    def __init__[self, values=None]:
        self.head = None
        self.tail = None        if values is not None:
            self.add_multiple_nodes[values]    def add_node[self, value]:
        if self.head is None:
            self.tail = self.head = Node[value]
        else:
            self.tail.next = Node[value]
            self.tail = self.tail.next
        return self.tail    def add_multiple_nodes[self, values]:
        for value in values:
            self.add_node[value]

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

def add_node_as_head[self, value]:
    if self.head is None:
        self.tail = self.head = Node[value]
    else:
        self.head = Node[value, self.head]
    return self.head

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

def add_node[self, value]:
    if self.head is None:
        self.tail = self.head = Node[value]
    else:
        self.tail.next = Node[value]
        self.tail = self.tail.next
    return self.tail

6 để 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 add_node[self, value]:
    if self.head is None:
        self.tail = self.head = Node[value]
    else:
        self.tail.next = Node[value]
        self.tail = self.tail.next
    return self.tail

7, đầu ra sẽ là

def add_node[self, value]:
    if self.head is None:
        self.tail = self.head = Node[value]
    else:
        self.tail.next = Node[value]
        self.tail = self.tail.next
    return self.tail

def __str__[self]:
    return ' -> '.join[[str[node] for node in self]]

Thứ hai, hãy triển khai phương thức

def add_node[self, value]:
    if self.head is None:
        self.tail = self.head = Node[value]
    else:
        self.tail.next = Node[value]
        self.tail = self.tail.next
    return self.tail

9 sẽ trả về độ dài của lớp do người dùng định nghĩa, về cơ bản là số 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 __len__[self]:
    count = 0
    node = self.head
    while node:
        count += 1
        node = node.next
    return count

Cuối cùng, hãy đảm bảo rằng lớp

def add_multiple_nodes[self, values]:
    for value in values:
        self.add_node[value]

0 có thể lặp lại bằng cách triển khai phương thức

def add_multiple_nodes[self, values]:
    for value in values:
        self.add_node[value]

def __iter__[self]:
    current = self.head
    while current:
        yield current
        current = current.next

Ngoài ra, chúng tôi cũng có thể tạo một thuộc tính có tên là

def add_multiple_nodes[self, values]:
    for value in values:
        self.add_node[value]

2 để 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

@property
def values[self]:
    return [node.value for node in self]

Lớp cuối cùng trông như dưới đây

class LinkedList:
    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:
    def __init__[self, values=None]:
        self.head = None
        self.tail = None        if values is not None:
            self.add_multiple_nodes[values]

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 add_multiple_nodes[self, values]:
    for value in values:
        self.add_node[value]

0 mà chúng tôi đã 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 đó

Để đối phó với Danh sách liên kết kép, chúng ta chỉ cần tạo một lớp bổ sung kế thừa từ lớp

def add_multiple_nodes[self, values]:
    for value in values:
        self.add_node[value]

0 và ghi đè các phương thức

def add_node[self, value]:
    if self.head is None:
        self.tail = self.head = Node[value]
    else:
        self.tail.next = Node[value]
        self.tail = self.tail.next
    return self.tail

5 và

def add_multiple_nodes[self, values]:
    for value in values:
        self.add_node[value]

class LinkedList:
    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

Là danh sách trong mảng Python hoặc danh sách được liên kết?

Trong hầu hết các ngôn ngữ lập trình, có sự khác biệt rõ ràng trong cách thức lưu trữ danh sách liên kết và mảng trong bộ nhớ. Tuy nhiên, trong Python, danh sách là mảng động .

Các danh sách Python có được lưu trữ dưới dạng danh sách được liên kết không?

Danh sách của Python thực sự là mảng có độ dài thay đổi, không phải danh sách liên kết kiểu Lisp .

Triển khai lớp liên kết do người dùng xác định trong Python

Mã đầy đủ cho danh sách liên kết do người dùng xác định trong Python

Suy nghĩ cuối cùng

Là danh sách trong mảng Python hoặc danh sách được liên kết?

Các danh sách Python có được lưu trữ dưới dạng danh sách được liên kết không?

Bài Viết Liên Quan

Toplist mới

Bài mới nhất

Chủ Đề