Danh sách liên kết trong Python: Hướng dẫn kèm ví dụ

Danh sách liên kết (linked list) là một cấu trúc dữ liệu đóng vai trò quan trọng trong việc tổ chức và quản lý dữ liệu. Nó chứa một chuỗi các nút (node) được lưu ở các vị trí ngẫu nhiên trong bộ nhớ, cho phép quản lý bộ nhớ hiệu quả. Mỗi nút trong danh sách liên kết gồm hai thành phần chính: phần dữ liệu và tham chiếu tới nút tiếp theo trong chuỗi.

Nếu khái niệm này ban đầu có vẻ phức tạp, đừng lo!

Chúng ta sẽ tách nhỏ về các yếu tố cơ bản để giải thích danh sách liên kết là gì, vì sao ta dùng chúng, và những ưu điểm đặc thù mà chúng mang lại.

Vì sao dùng danh sách liên kết?

Danh sách liên kết được tạo ra để khắc phục nhiều hạn chế khi lưu trữ dữ liệu trong danh sách và mảng thông thường, như trình bày dưới đây:

Dễ chèn và xóa

Trong danh sách, việc chèn hoặc xóa một phần tử ở bất kỳ vị trí nào ngoài cuối danh sách đòi hỏi phải dời tất cả các phần tử theo sau sang vị trí khác. Quy trình này có độ phức tạp thời gian O(n) và có thể làm giảm hiệu năng đáng kể, đặc biệt khi kích thước danh sách tăng. Nếu bạn chưa quen với cách danh sách hoạt động hoặc cách triển khai của chúng, bạn có thể đọc hướng dẫn về danh sách trong Python của chúng tôi.

Danh sách liên kết thì hoạt động khác. Chúng lưu trữ phần tử ở nhiều vị trí bộ nhớ rời rạc và kết nối chúng qua con trỏ tới các nút kế tiếp. Cấu trúc này cho phép danh sách liên kết thêm hoặc xóa phần tử ở bất kỳ vị trí nào chỉ bằng cách sửa đổi các liên kết để chèn phần tử mới hoặc bỏ qua phần tử bị xóa.

Khi bạn đã có tham chiếu trực tiếp tới nút tại điểm chèn hoặc xóa, bản thân thao tác có độ phức tạp O(1). Tuy vậy, việc tìm vị trí đó vẫn cần duyệt O(n), vì thế lợi thế O(1) chỉ áp dụng khi bạn đã có con trỏ tới nút liên quan (chẳng hạn khi làm việc ở đầu danh sách).

Kích thước động

Danh sách trong Python là mảng động, nghĩa là chúng cung cấp sự linh hoạt để thay đổi kích thước.

Tuy nhiên, quy trình này bao gồm một loạt thao tác phức tạp, như cấp phát lại mảng sang một khối bộ nhớ mới, lớn hơn. Việc cấp phát lại như vậy kém hiệu quả vì các phần tử phải được sao chép sang khối mới, và có thể cấp phát nhiều không gian hơn mức cần thiết ngay lập tức.

Ngược lại, danh sách liên kết có thể tăng giảm kích thước một cách linh hoạt mà không cần cấp phát lại hoặc đổi kích thước. Điều này khiến chúng là lựa chọn phù hợp cho các tác vụ cần mức linh hoạt cao.

Hiệu quả bộ nhớ

Danh sách (list) cấp phát bộ nhớ cho tất cả phần tử của nó trong một khối liên tiếp. Nếu một danh sách cần tăng vượt kích thước ban đầu, nó phải cấp phát một khối bộ nhớ liên tiếp mới, lớn hơn và sau đó sao chép tất cả các phần tử hiện có sang khối mới. Quy trình này tốn thời gian và kém hiệu quả, đặc biệt với các danh sách lớn. Mặt khác, nếu ước lượng kích thước ban đầu quá cao, phần bộ nhớ không dùng đến sẽ bị lãng phí.

Ngược lại, danh sách liên kết cấp phát bộ nhớ riêng cho từng phần tử. Cấu trúc này giúp tận dụng bộ nhớ tốt hơn vì bộ nhớ cho các phần tử mới có thể được cấp phát khi chúng được thêm vào.

Khi nào bạn nên dùng danh sách liên kết?

Mặc dù danh sách liên kết mang lại một số lợi ích so với danh sách và mảng thông thường, như kích thước động và hiệu quả bộ nhớ, chúng cũng có những hạn chế. Vì cần lưu con trỏ cho mỗi phần tử để tham chiếu tới nút tiếp theo, mức sử dụng bộ nhớ trên mỗi phần tử cao hơn khi dùng danh sách liên kết. Ngoài ra, cấu trúc dữ liệu này không cho phép truy cập trực tiếp vào dữ liệu. Truy cập một phần tử đòi hỏi phải duyệt tuần tự từ đầu danh sách, dẫn đến độ phức tạp thời gian tìm kiếm O(n).

Việc lựa chọn giữa danh sách liên kết hay mảng phụ thuộc vào nhu cầu cụ thể của ứng dụng. Danh sách liên kết hữu ích nhất khi:

• Bạn cần thường xuyên chèn và xóa nhiều phần tử
• Kích thước dữ liệu khó dự đoán hoặc có khả năng thay đổi thường xuyên
• Không cần truy cập trực tiếp tới phần tử
• Tập dữ liệu chứa các phần tử hoặc cấu trúc lớn

Các loại danh sách liên kết

Có ba loại danh sách liên kết, mỗi loại mang lại lợi thế riêng cho các tình huống khác nhau. Các loại này gồm:

Danh sách liên kết đơn

Danh sách liên kết đơn

Danh sách liên kết đơn là loại đơn giản nhất, trong đó mỗi nút chứa dữ liệu và tham chiếu tới nút tiếp theo trong chuỗi. Chúng chỉ có thể được duyệt theo một hướng duy nhất - từ đầu (nút đầu tiên) đến cuối (nút cuối cùng).

Mỗi nút trong danh sách liên kết đơn thường gồm hai phần:

• Dữ liệu: Thông tin thực sự được lưu trong nút.
• Con trỏ Next: Tham chiếu tới nút tiếp theo. Con trỏ next của nút cuối thường được đặt là null.

Vì các cấu trúc dữ liệu này chỉ có thể được duyệt theo một hướng, việc truy cập một phần tử cụ thể theo giá trị hoặc chỉ số yêu cầu bắt đầu từ đầu danh sách và di chuyển tuần tự qua các nút cho đến khi tìm thấy nút mong muốn. Thao tác này có độ phức tạp O(n), khiến nó kém hiệu quả với danh sách lớn.

Chèn và xóa một nút ở đầu danh sách liên kết đơn rất hiệu quả với độ phức tạp O(1). Tuy nhiên, chèn và xóa ở giữa hoặc cuối danh sách đòi hỏi phải duyệt đến vị trí đó, dẫn đến độ phức tạp O(n).

Thiết kế của danh sách liên kết đơn khiến chúng hữu ích khi thực hiện các thao tác xảy ra ở phần đầu danh sách.

Danh sách liên kết kép

Danh sách liên kết kép

Một nhược điểm của danh sách liên kết đơn là ta chỉ có thể duyệt theo một hướng và không thể lùi lại nút trước đó khi cần. Ràng buộc này hạn chế khả năng thực hiện các thao tác cần điều hướng hai chiều.

Danh sách liên kết kép giải quyết vấn đề này bằng cách bổ sung một con trỏ trong mỗi nút, đảm bảo danh sách có thể được duyệt theo cả hai hướng. Mỗi nút trong danh sách liên kết kép chứa ba thành phần: dữ liệu, con trỏ tới nút tiếp theo và con trỏ tới nút trước đó.

Danh sách liên kết vòng

Danh sách liên kết vòng

Danh sách liên kết vòng là một dạng chuyên biệt của danh sách liên kết, trong đó nút cuối trỏ ngược về nút đầu, tạo thành cấu trúc vòng tròn. Điều này có nghĩa, không giống như các danh sách liên kết đơn và kép đã thấy, danh sách liên kết vòng không kết thúc; thay vào đó, nó lặp lại vòng tròn.

Tính chu kỳ của danh sách liên kết vòng khiến chúng lý tưởng cho các tình huống cần lặp liên tục, như trò chơi bàn cờ xoay vòng từ người chơi cuối quay lại người đầu, hoặc trong các thuật toán máy tính như lập lịch vòng tròn (round-robin).

Tóm tắt độ phức tạp thời gian

Thật hữu ích khi nhìn nhanh cách danh sách liên kết so sánh với danh sách Python:

Điểm mấu chốt: danh sách liên kết vượt trội ở thao tác chèn và xóa tại đầu (O(1)), nhưng thua ở hầu hết phần còn lại. Nếu bạn không thường xuyên thêm hoặc bớt phần tử ở đầu cấu trúc dữ liệu, một danh sách Python thông thường có lẽ là lựa chọn tốt hơn.

Cách tạo danh sách liên kết trong Python

Giờ đây chúng ta đã hiểu danh sách liên kết là gì, vì sao dùng chúng và các biến thể của chúng, hãy tiến hành triển khai các cấu trúc dữ liệu này trong Python. Notebook cho hướng dẫn này cũng có sẵn trong DataLab workbook này; nếu bạn tạo một bản sao, bạn có thể chỉnh sửa và chạy mã. Đây là một lựa chọn tuyệt vời nếu bạn gặp vấn đề khi tự chạy mã!

Khởi tạo một nút

Như đã học trước đó, một nút là phần tử trong danh sách liên kết lưu trữ dữ liệu và tham chiếu tới nút tiếp theo trong chuỗi. Dưới đây là cách bạn có thể định nghĩa một nút trong Python:

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

    def __repr__(self):
        return f"Node({self.data})"

Đoạn mã trên khởi tạo một nút bằng hai hành động chính: Thuộc tính “data” của nút được gán một giá trị biểu thị thông tin thực mà nút cần chứa. Thuộc tính “next” thể hiện địa chỉ của nút tiếp theo. Hiện tại thuộc tính này được đặt là None, cho thấy nó chưa liên kết tới bất kỳ nút nào khác trong danh sách. Khi chúng ta tiếp tục thêm các nút mới vào danh sách liên kết, thuộc tính này sẽ được cập nhật để trỏ tới nút kế tiếp.

Tạo lớp danh sách liên kết

Tiếp theo, chúng ta cần tạo lớp danh sách liên kết. Lớp này sẽ bao bọc tất cả các thao tác quản lý các nút, như chèn và xóa. Chúng ta sẽ bắt đầu bằng cách khởi tạo danh sách liên kết:

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

Bằng cách đặt self.head là None, chúng ta đang nói rằng danh sách liên kết ban đầu trống và không có nút nào để trỏ tới. Giờ chúng ta sẽ tiến hành điền dữ liệu vào danh sách bằng cách chèn các nút mới.

Chèn một nút mới ở đầu danh sách liên kết

Bên trong lớp LinkedList, chúng ta sẽ thêm một phương thức để tạo một nút mới và đặt nó ở đầu danh sách:

    def insertAtBeginning(self, new_data):
        new_node = Node(new_data)  # Create a new node 
        new_node.next = self.head  # Next for new node becomes the   current head
        self.head = new_node  # Head now points to the new node

Mỗi lần bạn gọi phương thức trên, một nút mới được tạo với dữ liệu bạn chỉ định. Con trỏ next của nút mới này được đặt trỏ tới head hiện tại của danh sách, nhờ đó đặt nút này nằm trước các nút hiện có. Cuối cùng, nút vừa tạo được gán làm head của danh sách.

Chúng ta sẽ điền danh sách liên kết này bằng một chuỗi từ để hiểu rõ hơn cách hoạt động của thao tác chèn. Để làm điều này, hãy tạo một phương thức để duyệt và in nội dung danh sách:

    def printList(self):
        temp = self.head # Start from the head of the list
        while temp:
            print(temp.data,end=' ') # Print the data in the current node
            temp = temp.next # Move to the next node
        print()  # Ensures the output is followed by a new line

Phương thức trên sẽ in nội dung của danh sách liên kết. Giờ hãy dùng các phương thức đã định nghĩa để điền danh sách của chúng ta bằng chuỗi từ: “the quick brown fox.”

if __name__ == '__main__':
    # Create a new LinkedList instance
    llist = LinkedList()

    # Insert each letter at the beginning using the method we created
    llist.insertAtBeginning('fox') 
    llist.insertAtBeginning('brown') 
    llist.insertAtBeginning('quick')  
    llist.insertAtBeginning('the')  

    # Now 'the' is the head of the list, followed by 'quick', then 'brown' and 'fox'

    # Print the list
    llist.printList()

Những dòng mã trên sẽ cho ra kết quả sau:

"the quick brown fox"

Chèn một nút mới ở cuối danh sách liên kết

Chúng ta sẽ tạo một phương thức tên là insertAtEnd trong lớp LinkedList để tạo một nút mới ở cuối danh sách. Nếu danh sách trống, nút mới sẽ trở thành head của danh sách. Ngược lại, nó sẽ được nối vào nút cuối hiện tại trong danh sách. Hãy xem cách hoạt động trên thực tế:

    def insertAtEnd(self, new_data):
        new_node = Node(new_data)
        if self.head is None:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node

Phương thức trên bắt đầu bằng cách tạo một nút mới. Sau đó kiểm tra xem danh sách có trống không, nếu có thì nút mới được gán làm head của danh sách. Nếu không, nó duyệt danh sách để tìm nút cuối và đặt con trỏ của nút này trỏ tới nút mới.

Giờ chúng ta cần thêm phương thức này vào lớp LinkedList và dùng nó để thêm một từ vào cuối danh sách. Để thực hiện, hãy sửa hàm main của bạn như sau:

if __name__ == '__main__':
    llist = LinkedList()

    # Insert words at the beginning
    llist.insertAtBeginning('fox')
    llist.insertAtBeginning('brown')
    llist.insertAtBeginning('quick')
    llist.insertAtBeginning('the')

    # Insert a word at the end
    llist.insertAtEnd('jumps')

    # Print the list
    llist.printList()

Lưu ý rằng chúng ta chỉ cần gọi phương thức insertAtEnd để in từ “jumps” ở cuối danh sách. Đoạn mã trên sẽ cho ra kết quả sau:

"the quick brown fox jumps"

Xóa một nút ở đầu danh sách liên kết

Xóa nút đầu tiên của danh sách liên kết rất đơn giản vì chỉ cần trỏ head của danh sách này tới nút thứ hai. Bằng cách đó, nút đầu tiên sẽ không còn là một phần của danh sách. Để thực hiện, hãy thêm phương thức sau vào lớp LinkedList:

def deleteFromBeginning(self):
    if self.head is None:
        return "The list is empty" # If the list is empty, return this string
    self.head = self.head.next  # Otherwise, remove the head by making the next node the new head

Xóa một nút ở cuối danh sách liên kết

Để xóa nút cuối của danh sách liên kết, chúng ta phải duyệt danh sách để tìm nút kế cuối và đổi con trỏ next của nó thành None. Bằng cách đó, nút cuối sẽ không còn là một phần của danh sách. Sao chép và dán phương thức sau vào lớp LinkedList của bạn để thực hiện:

def deleteFromEnd(self):
    if self.head is None:
        return "The list is empty" 
    if self.head.next is None:
        self.head = None  # If there's only one node, remove the head by making it None
        return
    temp = self.head
    while temp.next.next:  # Otherwise, go to the second-last node
        temp = temp.next
    temp.next = None  # Remove the last node by setting the next pointer of the second-last node to None

Phương thức trên đầu tiên kiểm tra xem danh sách liên kết có trống không, nếu trống sẽ trả về thông báo cho người dùng. Nếu danh sách chỉ có một nút, nút đó sẽ bị xóa. Với danh sách có nhiều nút, phương thức sẽ tìm nút kế cuối và cập nhật tham chiếu nút tiếp theo của nó thành None.

Giờ hãy cập nhật hàm main để xóa phần tử ở đầu và cuối danh sách liên kết:

if __name__ == '__main__':
    llist = LinkedList()

    # Insert words at the beginning
    llist.insertAtBeginning('fox')
    llist.insertAtBeginning('brown')
    llist.insertAtBeginning('quick')
    llist.insertAtBeginning('the')

    # Insert a word at the end
    llist.insertAtEnd('jumps')

    # Print the list before deletion
    print("List before deletion:")
    llist.printList()

    # Deleting nodes from the beginning and end
    llist.deleteFromBeginning()
    llist.deleteFromEnd()

    # Print the list after deletion
    print("List after deletion:")
    llist.printList()

Đoạn mã trên sẽ in danh sách trước và sau khi xóa, thể hiện cách các thao tác chèn và xóa hoạt động trong danh sách liên kết. Sau khi chạy mã, bạn sẽ thấy kết quả sau:

List before deletion:
the quick brown fox jumps 
List after deletion:
quick brown fox

Tìm kiếm một giá trị cụ thể trong danh sách liên kết

Thao tác cuối cùng chúng ta học trong chương này là truy xuất một giá trị cụ thể trong danh sách liên kết. Để làm điều này, phương thức nên bắt đầu từ head của danh sách và lặp qua từng nút, kiểm tra xem dữ liệu của nút có khớp với giá trị cần tìm không. Dưới đây là một triển khai thực tế của thao tác này:

def search(self, value):
    current = self.head  # Start with the head of the list
    position = 0  # Counter to keep track of the position
    while current: # Traverse the list
        if current.data == value: # Compare the list's data to the search value
            return f"Value '{value}' found at position {position}" # Print the value if a match is found
        current = current.next
        position += 1
    return f"Value '{value}' not found in the list" 

Để tìm các giá trị cụ thể trong danh sách liên kết mà chúng ta đã tạo, hãy cập nhật hàm main để bao gồm phương thức tìm kiếm vừa viết:

if __name__ == '__main__':
    llist = LinkedList()

    # Insert words at the beginning
    llist.insertAtBeginning('fox')
    llist.insertAtBeginning('brown')
    llist.insertAtBeginning('quick')
    llist.insertAtBeginning('the')

    # Insert a word at the end
    llist.insertAtEnd('jumps')

   # Print the list before deletion
    print("List before deletion:")
    llist.printList()

    # Deleting nodes from beginning and end
    llist.deleteFromBeginning()
    llist.deleteFromEnd()

    # Print the list after deletion
    print("List after deletion:")
    llist.printList()
    
        # Search for 'quick' and 'lazy' in the list
    print(llist.search('quick'))  # Expected to find
    print(llist.search('lazy'))   # Expected not to find

Đoạn mã trên sẽ cho ra kết quả sau:

List before deletion:
the quick brown fox jumps 
List after deletion:
quick brown fox 
Value 'quick' found at position 0
Value 'lazy' not found in the list

Từ “quick” đã được tìm thấy trong danh sách liên kết vì nó nằm ở vị trí đầu tiên của danh sách. Tuy nhiên, từ “lazy” không nằm trong danh sách, nên không được tìm thấy.

Tổng kết

Nếu bạn đã đọc đến đây, xin chúc mừng! Giờ bạn đã nắm vững các nguyên lý cơ bản của danh sách liên kết, bao gồm cấu trúc, các loại, cách thêm và xóa phần tử, và cách duyệt chúng.

Nhưng hành trình không dừng lại ở đây. Danh sách liên kết chỉ là điểm khởi đầu của thế giới cấu trúc dữ liệu và thuật toán. Dưới đây là một vài bước tiếp theo để bạn đào sâu kiến thức về chủ đề này:

Tạo dự án của riêng bạn

Khám phá các ứng dụng thực tế của danh sách liên kết bằng cách tích hợp chúng vào một dự án lập trình hoặc khoa học dữ liệu. Danh sách liên kết được dùng để phát triển hệ thống tệp, xây dựng bảng băm, và thậm chí tạo hệ thống điều hướng GPS và trò chơi bàn cờ. Để bắt đầu với các dự án của riêng bạn, hãy xem các dự án khoa học dữ liệu có hướng dẫn miễn phí của chúng tôi giúp bạn học cách giải quyết các vấn đề thực tế bằng Python, R và SQL.

Tìm hiểu về cấu trúc dữ liệu và thuật toán

Học các cấu trúc dữ liệu khác như cây, ngăn xếp (stack) và hàng đợi (queue) là bước phát triển tự nhiên sau khi hiểu danh sách liên kết. Những cấu trúc này xây dựng dựa trên các nguyên lý của danh sách liên kết, giúp bạn giải quyết hiệu quả hơn nhiều bài toán tính toán. Ví dụ, cây và cây tìm kiếm nhị phân mở rộng khái niệm danh sách liên kết theo dạng phân cấp, cho phép mỗi nút kết nối tới nhiều phần tử trong cấu trúc dữ liệu.

Nếu các khái niệm này còn xa lạ với bạn, đừng lo! Datacamp có một khóa học đầy đủ về cấu trúc dữ liệu và thuật toán trong Python, sẽ đưa bạn qua những khái niệm này chi tiết hơn. Trước hết, bạn sẽ học về các cấu trúc dữ liệu như ngăn xếp, cây, bảng băm, hàng đợi và đồ thị. Khi tiến triển qua khóa học, bạn sẽ hiểu về các thuật toán tìm kiếm và sắp xếp, giúp bạn trở thành lập trình viên và người giải quyết vấn đề hiệu quả hơn.

Khám phá các khái niệm nâng cao về danh sách liên kết

Chúng ta đã triển khai danh sách liên kết đơn trong hướng dẫn này, bao gồm các thao tác như chèn, xóa và duyệt.

Bạn có thể tiến xa hơn bằng cách học cách triển khai danh sách liên kết kép và vòng. Skip list là một phần mở rộng khác của danh sách liên kết cho phép tìm kiếm nhanh hơn nhờ khả năng truy cập các phần tử nhanh hơn.

Việc tìm hiểu các cấu trúc dữ liệu nâng cao này sẽ đưa kỹ năng kỹ thuật của bạn lên tầm cao mới và cải thiện đáng kể khả năng lập trình, chuẩn bị cho bạn đối mặt với những thử thách phức tạp hơn trong các lĩnh vực như khoa học dữ liệu, phát triển phần mềm và kỹ sư học máy.

Nếu bạn muốn một phần mở đầu thân thiện hơn với người mới trước khi tiếp cận các chủ đề nâng cao này, hãy khám phá lộ trình kỹ năng Python Programming của chúng tôi. Lộ trình cung cấp một chuỗi khóa học dạy bạn các nền tảng của ngôn ngữ.