Danh sách liên kết (Linked List) là một trong những cấu trúc dữ liệu quan trọng trong lập trình, cho phép lưu trữ và quản lý dữ liệu một cách linh hoạt. Trên Python, một ngôn ngữ lập trình mạnh mẽ và đa năng, triển khai danh sách liên kết trở nên dễ dàng và hiệu quả. Bài viết này sẽ giới thiệu về danh sách liên kết trong Python, cách hoạt động cũng như cách triển khai nó.

Khái niệm về Danh sách Liên kết

Danh sách liên kết là một cấu trúc dữ liệu mà mỗi phần tử trong đó chứa dữ liệu và một con trỏ (tham chiếu) tới phần tử tiếp theo trong danh sách. Cấu trúc này giúp lưu trữ dữ liệu một cách linh hoạt và cho phép thêm/xóa các phần tử một cách dễ dàng.

Một danh sách liên kết có thể có dạng như sau:

+---+    +---+    +---+    +---+
| 1 | -> | 2 | -> | 3 | -> | 4 |
+---+    +---+    +---+    +---+

Trong ví dụ trên, mỗi phần tử chứa một giá trị (1, 2, 3, 4) và một con trỏ đến phần tử tiếp theo trong danh sách. Phần tử cuối cùng thường có con trỏ trống, thường được ký hiệu là None, để chỉ ra cuối của danh sách.

Lợi ích của Danh sách Liên kết

Danh sách liên kết có một số ưu điểm quan trọng:

1. Linhh hoạt trong việc thêm/xóa phần tử: Thêm/xóa phần tử trong danh sách liên kết có độ phức tạp O(1), trong khi đó với mảng thông thường thì có độ phức tạp là O(n).

2. Không cần kích thước cố định: Danh sách liên kết không yêu cầu xác định kích thước trước, điều này khác biệt so với mảng.

3. Thích hợp cho dữ liệu thưa thớt: Khi dữ liệu thưa thớt (ít giá trị không null), danh sách liên kết tiết kiệm không gian bộ nhớ hơn so với mảng.

Triển khai Danh sách Liên kết trong Python

Trong Python, danh sách liên kết có thể được triển khai thông qua lớp và đối tượng. Dưới đây là một ví dụ cơ bản về cách triển khai một danh sách liên kết đơn:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_node

    def display(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

Ở đây, chúng ta định nghĩa hai lớp: Node đại diện cho một nút trong danh sách và LinkedList đại diện cho danh sách liên kết. Lớp Node chứa dữ liệu và một con trỏ đến nút tiếp theo trong danh sách. Lớp LinkedList chứa một tham chiếu đến đầu danh sách (head).

Chúng ta cũng có các phương thức append để thêm phần tử vào cuối danh sách và display để hiển thị danh sách. Dưới đây là một ví dụ sử dụng danh sách liên kết đơn:

my_list = LinkedList()
my_list.append(1)
my_list.append(2)
my_list.append(3)
my_list.display()

Kết quả sẽ là:

1 -> 2 -> 3 -> None

Các Thao tác Cơ bản trên Danh sách Liên kết

Danh sách liên kết hỗ trợ nhiều thao tác cơ bản như:

• Chèn vào đầu danh sách: Để thêm một phần tử vào đầu danh sách, chỉ cần tạo một nút mới và thiết lập nút này làm head của danh sách.

• Chèn vào cuối danh sách: Để thêm một phần tử vào cuối danh sách, bạn phải duyệt qua danh sách cho đến khi đến nút cuối cùng, sau đó thiết lập tham chiếu của nút cuối cùng đến nút mới.

• Chèn vào vị trí bất kỳ: Để chèn một phần tử vào vị trí bất kỳ trong danh sách, bạn phải cập nhật tham chiếu của nút trước và nút sau nút được chèn.

• Xóa phần tử: Để xóa một phần tử khỏi danh sách, bạn phải cập nhật tham chiếu của nút trước và nút sau nút cần xóa.

• Tìm kiếm phần tử: Để tìm kiếm một phần tử trong danh sách, bạn phải duyệt qua từng nút trong danh sách và so sánh dữ liệu của nút với giá trị cần tìm.

• **

Truy cập phần tử:** Để truy cập một phần tử ở vị trí cụ thể, bạn phải duyệt qua danh sách từ đầu cho đến vị trí cần truy cập.

Tính Linh Hoạt của Danh sách Liên kết

Danh sách liên kết cung cấp sự linh hoạt để tùy chỉnh theo nhiều cách khác nhau:

• Danh sách liên kết kép (Doubly Linked List): Trong danh sách liên kết kép, mỗi nút có tham chiếu đến cả nút trước và nút tiếp theo, cho phép di chuyển qua lại giữa các phần tử một cách hiệu quả hơn.

• Danh sách liên kết vòng (Circular Linked List): Trong danh sách liên kết vòng, nút cuối cùng trỏ lại đến nút đầu tiên, tạo thành một vòng tròn. Điều này có thể hữu ích trong các tình huống cần duyệt danh sách liên kết lặp đi lặp lại.

• Danh sách liên kết đa chiều (Multidimensional Linked List): Một danh sách liên kết đa chiều là một danh sách liên kết trong đó mỗi nút có thể chứa tham chiếu đến một danh sách liên kết khác, cho phép bạn xây dựng cấu trúc dữ liệu phức tạp hơn.

• Danh sách liên kết đối tượng (Object Linked List): Thay vì lưu trữ các giá trị nguyên thủy, bạn có thể lưu trữ các đối tượng phức tạp trong danh sách liên kết, như danh sách liên kết của đối tượng hình học.

• Danh sách liên kết ngắn gọn (Sparse Linked List): Trong trường hợp danh sách cần lưu trữ dữ liệu thưa thớt, bạn có thể sử dụng danh sách liên kết ngắn gọn để tiết kiệm bộ nhớ và tối ưu hóa hiệu suất.

Kết Luận

Trên đây Kiyoshi đã hướng dẫn bạn về cách Danh sách liên kết rồi. Danh sách liên kết là một cấu trúc dữ liệu quan trọng trong lập trình, và Python cung cấp cách dễ dàng để triển khai và làm việc với chúng. Danh sách liên kết đơn có sự linh hoạt trong việc thêm/xóa phần tử và không yêu cầu kích thước cố định, điều này làm cho chúng trở thành một lựa chọn tốt cho nhiều ứng dụng khác nhau. Bằng cách sử dụng danh sách liên kết và biết cách thao tác với nó, bạn có thể giải quyết nhiều vấn đề phức tạp trong lập trình Python một cách hiệu quả.

URL Link

https://laptrinhcanban.com/python/nhap-mon-lap-trinh-python/list-trong-python/danh-sach-lien-ket-trong-python/