Danh sách liên kết đơn (linked list) là một trong những cấu trúc dữ liệu cơ bản trong lập trình, thường được sử dụng để lưu trữ và quản lý dữ liệu theo cách linh hoạt. Trong Python, một ngôn ngữ lập trình mạnh mẽ và phổ biến, bạn có thể triển khai danh sách liên kết đơn một cách dễ dàng và hiệu quả. Trong bài viết này, chúng ta sẽ tìm hiểu về danh sách liên kết đơn trong Python, cách chúng hoạt động, và cách triển khai chúng.

Khái niệm về danh sách liên kết đơn

Một danh sách liên kết đơn (linked list) là một cấu trúc dữ liệu tập hợp các phần tử gọi là nút (node). Mỗi nút chứa một giá trị (hoặc dữ liệu) và một tham chiếu (reference) đến nút tiếp theo trong danh sách. Dưới đây là một biểu đồ minh họa về danh sách liên kết đơn:

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

Trong ví dụ trên, mỗi nút chứa một giá trị (1, 2, 3, 4) và một tham chiếu đến nút tiếp theo trong danh sách. Nút cuối cùng thường có tham chiếu trống (None), để chỉ ra cuối danh sách.

Danh sách liên kết đơn bao gồm một chuỗi các nút, trong đó mỗi nút chứa dữ liệu và một liên kết đến nút tiếp theo trong danh sách. Cấu trúc này cho phép bạn lưu trữ một dãy dữ liệu mà không cần phải liên kết chúng vật lý như trong mảng.

Mỗi nút trong danh sách liên kết đơn bao gồm hai phần chính:

• Dữ liệu (data): Thông tin mà nút chứa, ví dụ: một số nguyên, chuỗi, hoặc đối tượng phức tạp.
• Liên kết (next): Tham chiếu đến nút tiếp theo trong danh sách.

Lợi ích của danh sách liên kết đơn

Danh sách liên kết đơn có một số lợi ích quan trọng:

• Cấu trúc linh hoạt: Bạn có thể dễ dàng thêm, xóa hoặc di chuyển các phần tử trong danh sách mà không cần sao chép hoặc di chuyển toàn bộ danh sách.

• Không cần xác định kích thước tĩnh: Danh sách liên kết đơn có thể thay đổi kích thước mà không cần xác định trước. Điều này khác với các mảng (array) có kích thước cố định.

• Hiệu suất chèn và xóa: Danh sách liên kết đơn có thể chèn và xóa phần tử ở bất kỳ vị trí nào với độ phức tạp O(1), trong khi mảng thông thường có độ phức tạp O(n) cho thao tác này.

Triển khai danh sách liên kết đơn trong Python

Trong Python, bạn có thể triển khai danh sách liên kết đơn bằng cách sử dụng các lớp và đối tượng. Dưới đây là một ví dụ về cách triển khai một danh sách liên kết đơn đơn giả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")

Trong ví dụ trên, 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 đơn. Lớp Node chứa dữ liệu và một tham chiếu đến nút tiếp theo trong danh sách. Lớp LinkedList chứa một con trỏ đến đầu danh sách (head).

Chúng ta 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. 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

Tạo Danh Sách Liên Kết Đơn

Để tạo danh sách liên kết đơn trong Python, bạn cần định nghĩa một lớp (class) cho nút và một lớp cho danh sách liên kết đơn. Dưới đây là một ví dụ về cách tạo một danh sách liên kết đơn đơn giản:

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

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

Trong ví dụ trên, chúng ta đã định nghĩa lớp Node để biểu diễn một nút trong danh sách liên kết đơn, và lớp SinglyLinkedList để biểu diễn danh sách liên kết đơn chứa các nút.

Thêm Phần Tử vào Danh Sách Liên Kết Đơn

Để thêm một phần tử vào danh sách liên kết đơn, chúng ta có thể thực hiện các bước sau:

1. Tạo một nút mới với dữ liệu cần thêm.
2. Liên kết nút mới này đến nút cuối cùng của danh sách hoặc đặt nút mới làm đầu của danh sách.

Dưới đây là một ví dụ về cách thêm một nút mới vào danh sách liên kết đơn:

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

Trong ví dụ này, phương thức append thêm một nút mới chứa dữ liệu data vào danh sách liên kết đơn.

Xóa Phần Tử khỏi Danh Sách Liên Kết Đơn

Để xóa một phần tử từ danh sách liên kết đơn, chúng ta có thể thực hiện các bước sau:

1. Tìm nút chứa dữ liệu cần xóa.
2. Cập nhật liên kết của nút trước nút cần xóa để bỏ qua nút cần xóa.

Dưới đây là một ví dụ về cách xóa một nút từ danh sách liên kết đơn:

class SinglyLinkedList:
    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 remove(self, data):
        if not self.head:
            return
        if self.head.data == data:
            self.head = self.head.next
            return
        current = self.head
        while current.next:
            if current.next.data == data:
                current.next = current.next.next
                return
            current = current.next

Trong ví dụ này, phương thức remove xóa nút chứa dữ liệu data khỏi danh sách liên kết đơn.

Tìm Kiếm Trong Danh Sách Liên Kết Đơn

Để tìm kiếm một phần tử trong danh sách liên kết đơn, chúng ta có thể thực hiện các bước sau:

1. 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ị tìm kiếm.
2. Nếu tìm thấy nút chứa giá trị tìm kiếm, trả về nút đó; nếu không, trả về `None

` để thể hiện không tìm thấy.

Dưới đây là một ví dụ về cách tìm kiếm trong danh sách liên kết đơn:

class SinglyLinkedList:
    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 remove(self, data):
        if not self.head:
            return
        if self.head.data == data:
            self.head = self.head.next
            return
        current = self.head
        while current.next:
            if current.next.data == data:
                current.next = current.next.next
                return
            current = current.next
    
    def find(self, data):
        current = self.head
        while current:
            if current.data == data:
                return current
            current = current.next
        return None

Phương thức find trong ví dụ trên trả về nút chứa dữ liệu data nếu nó tồn tại trong danh sách liên kết đơn, ngược lại trả về None.

Duyệt Qua Danh Sách Liên Kết Đơn

Để Duyệt qua danh sách liên kết đơn, chúng ta có thể sử dụng vòng lặp và điều hướng từ nút này đến nút khác trong danh sách.

Dưới đây là một ví dụ về cách Duyệt qua danh sách liên kết đơn và xuất tất cả các phần tử:

class SinglyLinkedList:
    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 remove(self, data):
        if not self.head:
            return
        if self.head.data == data:
            self.head = self.head.next
            return
        current = self.head
        while current.next:
            if current.next.data == data:
                current.next = current.next.next
                return
            current = current.next
    
    def find(self, data):
        current = self.head
        while current:
            if current.data == data:
                return current
            current = current.next
        return None
    
    def traverse(self):
        current = self.head
        while current:
            print(current.data)
            current = current.next

Phương thức traverse trong ví dụ trên Duyệt qua danh sách liên kết đơn và xuất tất cả các phần tử.

Các thao tác cơ bản trên danh sách liên kết đơn

Danh sách liên kết đơn hỗ trợ nhiều thao tác cơ bản, bao gồm:

• Chèn vào đầu danh sách: Để thêm một phần tử vào đầu danh sách, bạn chỉ cần tạo một nút mới và thiết lập nút mới 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 đi từ đầu danh sách đến nút cuối cùng và 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.

5. Tính linh hoạt của danh sách liên kết đơn

Danh sách liên kết đơn rất linh hoạt và có thể được tùy chỉnh cho nhiều mục đích khác nhau. Dưới đây là một số biến thể và ứng dụng của danh sách liên kết đơn:

• Danh sách liên kết kép (Doubly Linked List): Trong một 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 một 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 tạo cấu trúc dữ liệu phức tạp hơn.

• Danh sách liên kết đôi chiều (Doubly Linked List): Trong một danh sách liên kết đôi chiều, 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 một 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 tạo 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ăng 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 đơn rồi. Danh sách liên kết đơn là một cấu trúc dữ liệu quan trọng và linh hoạt trong lập trình Python. Chúng cho phép bạn lưu trữ và quản lý dữ liệu một cách hiệu quả, đồng thời cung cấp tính linh hoạt trong việc thêm, xóa, và di chuyển các phần tử trong danh sách. Bằng cách sử dụng danh sách liên kết đơn và một số biến thể của nó, bạn có thể giải quyết nhiều vấn đề khác nhau trong lập trình.

Nếu bạn muốn làm việc với danh sách liên kết đơn trong Python, bạn nên hiểu cách triển khai, thao tác và ứng dụng của chúng. Việc sử dụng danh sách liên kết đơn một cách thông minh có thể giúp bạn xây dựng các ứng dụng phức tạp và giải quyết các vấn đề phức tạp trong lập trình.

URL Link

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