Bài viết nằm trong chuỗi hướng dẫn về Cấu trúc Dữ liệu và Thuật toán trong Python

Danh Sách Liên Kết Đơn (Singly Linked List)

Giới thiệu

Danh sách liên kết đơn là một cấu trúc dữ liệu bao gồm nhiều node. Mỗi node chứa hai thành phần chính:

1. Dữ liệu (Data)
   Node trong danh sách liên kết đơn có khả năng lưu trữ nhiều loại dữ liệu khác nhau như chuỗi, ký tự, số hoặc bất kỳ kiểu dữ liệu nào khác.

2. Con trỏ (Next)
   Con trỏ là một biến trỏ từ node hiện tại đến node tiếp theo trong danh sách. Con trỏ next này tạo ra mối quan hệ liên kết giữa các node.

Head là điểm bắt đầu của danh sách. Nó không phải là một node mà là một con trỏ chỉ đến node đầu tiên. Khi cần duyệt qua danh sách hoặc truy cập một phần tử, chúng ta sẽ bắt đầu từ head và di chuyển theo các node tiếp theo thông qua con trỏ next. Phần tử cuối cùng trong danh sách liên kết đơn được đánh dấu bằng giá trị None, chỉ ra rằng không còn node nào khác.

class Node:
    def __init__(self, data):
        self.data = data  # Dữ liệu mà node lưu trữ
        self.next = None  # Con trỏ trỏ đến node tiếp theo (ban đầu là None)

class SinglyLinkedList:
    def __init__(self):
        self.head = None  # Khởi tạo danh sách với head là None (danh sách trống)

Hàm hiển thị (display)

Chúng ta sẽ bắt đầu từ con trỏ head và in ra dữ liệu của từng node cho đến khi gặp giá trị None. Quy trình này sử dụng vòng lặp để đảm bảo không bỏ sót node nào.

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

Thao tác Chèn (Insertion)

Thêm vào cuối (Append)

Phương thức append sẽ chèn một phần tử vào cuối danh sách liên kết đơn.

Khi danh sách rỗng

Nếu danh sách rỗng (tức là head bằng None), node mới sẽ trở thành head của danh sách.

def append(self, data):
    new_node = Node(data)
    if not self.head:
        self.head = new_node
        return

Khi danh sách không rỗng

Chúng ta cần duyệt đến node cuối cùng và chèn node mới vào đó.

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

Ví dụ sử dụng Append

sll = SinglyLinkedList()
sll.append(1)
sll.append(2)
sll.append(3)
sll.display()  # Kết quả: 1 -> 2 -> 3 -> None

Thêm vào đầu (Prepend)

Phương thức prepend sẽ chèn một phần tử vào đầu danh sách. Chúng ta chỉ cần cập nhật head để trỏ đến node mới.

def prepend(self, data):
    new_node = Node(data)
    new_node.next = self.head
    self.head = new_node

Ví dụ sử dụng Prepend

sll = SinglyLinkedList()
sll.prepend("C")
sll.prepend("B")
sll.prepend("A")
sll.prepend("D")
sll.display()  # Kết quả: D -> A -> B -> C -> None

Chèn sau một node cụ thể (Insert After Node)

Phương thức insert_after_node cho phép chúng ta chèn một node mới sau một node đã có trong danh sách.

def insert_after_node(self, prev_node_data, data):
    current_node = self.head
    while current_node:
        if current_node.data == prev_node_data:
            new_node = Node(data)
            new_node.next = current_node.next
            current_node.next = new_node
            return
        current_node = current_node.next
    print(f"Node với giá trị {prev_node_data} không tồn tại trong danh sách.")

Thao tác Xóa (Deletion)

Xóa theo giá trị

Chúng ta sẽ xử lý hai trường hợp: node đầu tiên và node không phải đầu tiên.

Nếu node cần xóa là node đầu tiên

Chúng ta cập nhật head để trỏ đến node tiếp theo.

def delete_node(self, key):
    if self.head and self.head.data == key:
        self.head = self.head.next
        return

Nếu node cần xóa không phải là node đầu tiên

Chúng ta sẽ duyệt để tìm node trước node cần xóa và cập nhật liên kết.

def delete_node(self, key):
    current_node = self.head
    if current_node and current_node.data == key:
        self.head = current_node.next
        current_node = None
        return
    prev_node = None
    while current_node and current_node.data != key:
        prev_node = current_node
        current_node = current_node.next
    if current_node is None:
        print(f"Node với giá trị {key} không tồn tại trong danh sách.")
        return
    prev_node.next = current_node.next
    current_node = None

Kết Luận

Danh sách liên kết đơn (Singly Linked List) là một cấu trúc dữ liệu cơ bản nhưng cực kỳ quan trọng trong lập trình. Việc hiểu cách hoạt động và thao tác với nó là nền tảng cần thiết để phát triển và áp dụng các giải pháp trong nhiều bài toán thực tế. Qua bài viết này, hy vọng bạn đã nắm rõ cách cài đặt cũng như các thao tác quan trọng liên quan tới danh sách liên kết đơn trong Python.
source: viblo