vi
new
+1
Avatar
thavrith @thavrith
329 8 11
Đã đăng vào thg 9 6, 8:46 SA 13 phút đọc
80

Singly Linked List trong Python

Bài viết nằm trong series Data Structures và Algorithms trong Python

Singly Linked List

Giới thiệu

Mỗi Singly Linked List bao gồm nhiều nodes, và mỗi node chứa hai thành phần chính:

  1. Data
  • Component data cho phép mỗi node trong singly linked list lưu trữ một phần tử dữ liệu. Phần tử này có thể là string, character, number, hoặc bất kỳ kiểu dữ liệu nào khác.
  1. Next (con trỏ)
  • Component thứ hai, là một con trỏ (pointer) trỏ từ node hiện tại đến node tiếp theo trong danh sách liên kết. Component next này giúp kết nối các node lại với nhau, tạo thành chuỗi liên kết.

Head là điểm bắt đầu của linked list. Head không phải là một node mà là một con trỏ trỏ đến node đầu tiên trong danh sách. Khi cần duyệt qua linked list hoặc truy cập một phần tử, chúng ta sẽ bắt đầu từ head và di chuyển theo hướng của các node tiếp theo bằng cách sử dụng con trỏ next.

Component cuối cùng của singly linked list là null. Trong Python là None, biểu thị rằng đây là node cuối cùng và không có node nào tiếp theo nữa.

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)

display()

Chúng ta sẽ bắt đầu từ con trỏ head và in ra dữ liệu của từng node, sau đó di chuyển đến node tiếp theo. Ta sẽ tiếp tục kiểm tra node tiếp theo để đảm bảo rằng nó không phải là None. Nếu không phải, ta sẽ tiếp tục di chuyển đến node kế tiếp. Quy trình này sẽ lặp lại cho đến khi chạm tới node cuối cùng, nơi con trỏ next là None.

def display(self):
    current_node = self.head
    while current_node:  # Duyệt qua danh sách cho đến khi gặp None
        print(current_node.data, end=" -> ")
        current_node = current_node.next
    print("None")

Insertion

Append

Phương thức append sẽ chèn một phần tử vào cuối linked list.

Trường hợp Linked List rỗng

Khi triển khai phương thức append cho linked list, chúng ta cần xử lý trường hợp đặc biệt nếu linked list rỗng. Trong trường hợp list rỗng (tức là head bằng None), node mới sẽ trở thành head của danh sách. Dưới đây là cách triển khai phương thức append bao gồm xử lý cho trường hợp list rỗng:


# Phương thức append: Chèn một phần tử mới vào cuối danh sách
def append(self, data):
    new_node = Node(data)
    # Nếu danh sách rỗng, node mới sẽ là head
    if not self.head:
        self.head = new_node
        return

Trường hợp Linked List không rỗng

Trong trường hợp linked list không rỗng, chúng ta cần duyệt qua linked list để tìm node cuối cùng và thêm node mới vào cuối danh sách.


# Phương thức append: Chèn một phần tử mới vào cuối danh sách
def append(self, data):
    new_node = Node(data)
    # Nếu danh sách rỗng, node mới sẽ là head
    if not self.head:
        self.head = new_node
        return
    # Nếu danh sách không rỗng, tìm node cuối và gắn node mới vào cuối
    last_node = self.head
    while last_node.next:
        last_node = last_node.next
    last_node.next = new_node

Sử dụng append

# Sử dụng danh sách liên kết
sll = SinglyLinkedList()

# Thêm các phần tử vào danh sách
sll.append(1)
sll.append(2)
sll.append(3)

# Hiển thị danh sách
sll.display() # Output: 1 -> 2 -> 3 -> None

Prepend

Phương thức prepend sẽ chèn một phần tử vào đầu linked list. Khi thêm một node mới vào đầu danh sách, chúng ta chỉ cần thay đổi con trỏ head để trỏ đến node mới, và con trỏ của node mới sẽ trỏ đến node cũ mà head trỏ đến trước đó.

def prepend(self, data):
    new_node = Node(data)  # Tạo node mới
    new_node.next = self.head  # Con trỏ của node mới trỏ đến node đầu hiện tại
    self.head = new_node  # Cập nhật head để trỏ đến node mới

Sử dụng

# Sử dụng danh sách liên kết
sll = SinglyLinkedList()

# Thêm các phần tử vào danh sách
sll.prepend("C")  # Danh sách: C
sll.prepend("B")  # Danh sách: B -> C
sll.prepend("A")  # Danh sách: A -> B -> C

# Thêm phần tử D vào đầu danh sách
sll.prepend("D")  # Danh sách: D -> A -> B -> C

# Hiển thị danh sách
sll.display() # Output: D -> A -> B -> C -> None

Insert After Node

Phương thức insert_after_node sẽ chèn một node mới sau một node cụ thể đã có trong linked list. Để triển khai phương thức này, ta cần tìm node đích và sau đó thêm node mới ngay sau nó. Điều này yêu cầu cập nhật các con trỏ để đảm bảo rằng danh sách liên kết vẫn duy trì cấu trúc chính xác.

def insert_after_node(self, prev_node_data, data):
    current_node = self.head
    while current_node:  # Duyệt qua danh sách
        if current_node.data == prev_node_data:  # Tìm node đích
            new_node = Node(data)  # Tạo node mới
            new_node.next = current_node.next  # Con trỏ của node mới trỏ đến node tiếp theo của node đích
            current_node.next = new_node  # Cập nhật con trỏ của node đích trỏ đến node mới
            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 liên kết.")

Sử dụng:

# Sử dụng danh sách liên kết
sll = SinglyLinkedList()

# Thêm các phần tử vào danh sách
sll.append("A")
sll.append("B")
sll.append("C")

# Chèn phần tử sau node "B"
sll.insert_after_node("B", "D")

# Hiển thị danh sách
sll.display() # Output: A -> B -> D -> C -> None

# Chèn phần tử sau node "F"
sll.insert_after_node("F", "D") # Output: Node với giá trị F không tồn tại trong danh sách liên kết.

Insert a node at a specific position in a linked list

Để chèn một phần tử vào vị trí cụ thể trong singly linked list, ta cần xử lý hai trường hợp chính:

  • Chèn tại vị trí 0: ta chỉ cần cập nhật con trỏ next của node mới để trỏ đến head hiện tại, sau đó cập nhật head trỏ đến node mới.
  • Chèn tại vị trí bất kỳ khác: Nếu position lớn hơn 0, ta sẽ duyệt qua danh sách để tìm node trước (prev_node) vị trí cần chèn. Sau đó, ta chèn node mới giữa node trước và node tại vị trí đó.
def insert_at_position(self, position, data):
    new_node = Node(data)

    # Trường hợp vị trí là 0 (chèn vào đầu danh sách)
    if position == 0:
        new_node.next = self.head
        self.head = new_node
        return

    # Trường hợp chèn vào vị trí bất kỳ khác
    current_node = self.head
    count = 0
    prev_node = None

    # Duyệt qua danh sách để tìm vị trí cần chèn
    while current_node and count < position:
        prev_node = current_node
        current_node = current_node.next
        count += 1

    # Nếu vị trí vượt quá kích thước của danh sách
    if count != position:
        print(f"Vị trí {position} vượt quá kích thước của danh sách.")
        return

    # Chèn node mới vào vị trí đã tìm thấy
    new_node.next = current_node
    prev_node.next = new_node

Sử dụng

# Sử dụng danh sách liên kết
llist = SinglyLinkedList()

# Thêm các phần tử vào danh sách
llist.append("A")
llist.append("B")
llist.append("C")

# Hiển thị danh sách ban đầu
print("Danh sách ban đầu:")
llist.display()

# Chèn node tại vị trí 0 (đầu danh sách)
llist.insert_at_position(0, "D")

# Hiển thị danh sách sau khi chèn tại vị trí 0
print("\nDanh sách sau khi chèn tại vị trí 0:")
llist.display()

# Chèn node tại vị trí 2
llist.insert_at_position(2, "E")

# Hiển thị danh sách sau khi chèn tại vị trí 2
print("\nDanh sách sau khi chèn tại vị trí 2:")
llist.display()

Output

Danh sách ban đầu:

A -> B -> C -> None

Danh sách sau khi chèn tại vị trí 0:
D -> A -> B -> C -> None

Danh sách sau khi chèn tại vị trí 2:
D -> A -> E -> B -> C -> None

Deletion

Xóa bởi giá trị

Chúng ta có 2 trường hợp:

  • Node cần xóa là node đầu tiên (head).
  • Node cần xóa không phải là node đầu tiên (head).

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

Nếu node cần xóa là head, ta chỉ cần cập nhật con trỏ head để trỏ đến node tiếp theo của head. Điều này sẽ xóa đi liên kết của head hiện tại, và danh sách liên kết vẫn sẽ được duy trì.

def delete_node(self, key):
    # Trường hợp node cần xóa là head
    if self.head and self.head.data == key:
        self.head = self.head.next
        return

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

Nếu node cần xóa không phải là head, ta sẽ duyệt qua danh sách để tìm node trước node cần xóa. Sau khi tìm thấy, ta sẽ cập nhật con trỏ next của node trước này để trỏ đến node tiếp theo của node cần xóa, và điều này sẽ xóa bỏ node cần xóa ra khỏi danh sách.

def delete_node(self, key):
    current_node = self.head

    # Trường hợp node cần xóa là head
    if current_node and current_node.data == key:
        self.head = current_node.next
        current_node = None
        return

    # Trường hợp node cần xóa không phải là head
    prev_node = None
    while current_node and current_node.data != key:
        prev_node = current_node
        current_node = current_node.next

    # Nếu node cần xóa không tồn tại trong danh sách
    if current_node is None:
        print(f"Node với giá trị {key} không tồn tại trong danh sách liên kết.")
        return

    # Cập nhật con trỏ của node trước trỏ đến node tiếp theo của node bị xóa
    prev_node.next = current_node.next
    current_node = None

Sử dụng

    # Sử dụng danh sách liên kết

llist = SinglyLinkedList()

# Thêm các phần tử vào danh sách

llist.append("A")
llist.append("B")
llist.append("C")
llist.append("D")

# Hiển thị danh sách ban đầu

print("Danh sách ban đầu:")
llist.display()

# Xóa node "B" (không phải head)

llist.delete_node("B")

# Hiển thị danh sách sau khi xóa

print("\nDanh sách sau khi xóa B:")
llist.display()

# Xóa node "A" (là head)

llist.delete_node("A")

# Hiển thị danh sách sau khi xóa

print("\nDanh sách sau khi xóa A (head):")
llist.display()

Output

Danh sách ban đầu:
A -> B -> C -> D -> None

Danh sách sau khi xóa B:
A -> C -> D -> None

Danh sách sau khi xóa A (head):
C -> D -> None

Xóa bởi vị trí

Để xóa một node theo vị trí cụ thể trong singly linked list (danh sách liên kết đơn), ta sẽ xử lý hai trường hợp:

  • Node cần xóa ở vị trí 0 (node đầu tiên - head): Đây là trường hợp đặc biệt khi node cần xóa là head, ta chỉ cần cập nhật con trỏ head để trỏ đến node tiếp theo.

  • Node cần xóa không ở vị trí 0: Trong trường hợp này, ta cần duyệt qua danh sách đến vị trí cần xóa, tìm node trước vị trí đó và cập nhật con trỏ của node trước để bỏ qua node cần xóa.

Xóa node ở vị trí 0

def delete_at_position(self, position):
    if self.head is None:
        print("Danh sách trống.")
        return

    current_node = self.head

    # Trường hợp node cần xóa ở vị trí 0 (node đầu tiên)
    if position == 0:
        self.head = current_node.next  # Cập nhật head để trỏ đến node tiếp theo
        current_node = None
        return

Xóa node ở các vị trí khác

def delete_at_position(self, position):
    if self.head is None:
        print("Danh sách trống.")
        return

    current_node = self.head

    # Trường hợp node cần xóa ở vị trí 0 (node đầu tiên)
    if position == 0:
        self.head = current_node.next  # Cập nhật head để trỏ đến node tiếp theo
        current_node = None
        return

    # Trường hợp node cần xóa không phải ở vị trí 0
    prev_node = None
    count = 0

    # Duyệt qua danh sách đến vị trí cần xóa
    while current_node and count != position:
        prev_node = current_node
        current_node = current_node.next
        count += 1

    # Nếu vị trí không tồn tại trong danh sách
    if current_node is None:
        print(f"Vị trí {position} vượt quá kích thước của danh sách.")
        return

    # Cập nhật con trỏ của node trước trỏ đến node tiếp theo của node bị xóa
    prev_node.next = current_node.next
    current_node = None

Sử dụng:


# Sử dụng danh sách liên kết
llist = SinglyLinkedList()

# Thêm các phần tử vào danh sách

llist.append("A")
llist.append("B")
llist.append("C")
llist.append("D")
llist.append("E")

# Hiển thị danh sách ban đầu

print("Danh sách ban đầu:")
llist.display()

# Xóa node tại vị trí 0 (head)

llist.delete_at_position(0)

# Hiển thị danh sách sau khi xóa node tại vị trí 0

print("\nDanh sách sau khi xóa vị trí 0 (head):")
llist.display()

# Xóa node tại vị trí 2

llist.delete_at_position(2)

# Hiển thị danh sách sau khi xóa node tại vị trí 2

print("\nDanh sách sau khi xóa vị trí 2:")
llist.display()

Output

Danh sách ban đầu:

A -> B -> C -> D -> E -> None

Danh sách sau khi xóa vị trí 0 (head):
B -> C -> D -> E -> None

Danh sách sau khi xóa vị trí 2:
B -> C -> E -> None

File code singly-linked-list cho tới lúc này

Length

Iterative

def get_length_iterative(self):
    count = 0
    current_node = self.head
    while current_node:  # Duyệt qua danh sách cho đến khi gặp None
        count += 1
        current_node = current_node.next
    return count

Recursive

def get_length_recursive(self, node):
    # Nếu node là None, tức là danh sách rỗng
    if not node:
        return 0
    # Tính độ dài đệ quy cho các node tiếp theo
    return 1 + self.get_length_recursive(node.next)

Node Swap

Trường hợp cần xử lý khi swap 2 nodes:

  • Node 1 và Node 2 không phải là head.
  • Một trong hai node là head.
  • Hai node cần hoán đổi là giống nhau (không cần thực hiện gì).

Các bước để thực hiện swap 2 nodes:

  • Tìm vị trí của hai node cần hoán đổi.
  • Nếu một trong hai node là head, cập nhật con trỏ head để trỏ đến node kia.
  • Cập nhật các con trỏ của các node trước hai node cần hoán đổi để giữ liên kết giữa các node trong danh sách.
    def swap_nodes(self, key1, key2):
        # Nếu hai node giống nhau, không cần hoán đổi
        if key1 == key2:
            return

        # Tìm vị trí của key1
        prev_node1 = None
        current_node1 = self.head
        while current_node1 and current_node1.data != key1:
            prev_node1 = current_node1
            current_node1 = current_node1.next

        # Tìm vị trí của key2
        prev_node2 = None
        current_node2 = self.head
        while current_node2 and current_node2.data != key2:
            prev_node2 = current_node2
            current_node2 = current_node2.next

        # Nếu không tìm thấy một trong hai node (None), dừng lại
        if not current_node1 or not current_node2:
            print("Một hoặc cả hai node không tồn tại.")
            return
        # Nếu key1 không phải là head, cập nhật con trỏ của prev_node1
        if prev_node1:
            prev_node1.next = current_node2
        else:  # Nếu key1 là head
            self.head = current_node2

        # Nếu key2 không phải là head, cập nhật con trỏ của prev_node2
        if prev_node2:
            prev_node2.next = current_node1
        else:  # Nếu key2 là head
            self.head = current_node1
        # Hoán đổi con trỏ next của hai node
        current_node1.next, current_node2.next = current_node2.next, current_node1.next

Sử dụng:

llist = SinglyLinkedList()

print("------------------------------")

llist.append("A")
llist.append("B")
llist.append("C")
llist.append("D")
# Hiển thị danh sách ban đầu
print("Danh sách ban đầu:")
llist.display()

# Hoán đổi hai node
llist.swap_nodes("A", "D")

# Hiển thị danh sách sau khi hoán đổi
print("\nDanh sách sau khi hoán đổi A và D:")
llist.display()

Output

------------------------------
Danh sách ban đầu:
A -> B -> C -> D -> None

Danh sách sau khi hoán đổi A và D:
D -> B -> C -> A -> None

Giải thích

  1. Tìm hai node cần hoán đổi:
  • Ta duyệt qua danh sách liên kết để tìm prev_node và current_node cho cả hai node cần hoán đổi (key1 và key2).
  1. Cập nhật liên kết:
  • Nếu một trong hai node là head, ta cập nhật head trỏ đến node kia.
  • Sau đó, ta cập nhật con trỏ của node trước để nó trỏ đến node còn lại.

Ví dụ key1 là "A": head, key2 là "D" thì

  • self.head sẽ trỏ đến current_node2 ("D")
  • prev_node2.next ("C") sẽ trỏ đến current_node1 ("A")
  1. Hoán đổi các con trỏ next:
  • Cuối cùng, ta hoán đổi con trỏ next của hai node hiện tại (current_node1.next và current_node2.next) để hoàn tất việc hoán đổi các node trong danh sách liên kết. Sau A (current_node1.next) sẽ là None (current_node2.next) và sau D (current_node2.next) sẽ là B (current_node1.next)
  1. Trường hợp không tìm thấy node:
  • Nếu không tìm thấy một trong hai node, chương trình sẽ thông báo và dừng lại.

Minh họa

File code singly-linked-list cho tới lúc này

Reverse

Iterative

def reverse_iterative(self):
    prev = None
    current = self.head
    while current:
        next_node = current.next  # Lưu trữ node tiếp theo
        current.next = prev  # Đảo ngược liên kết
        prev = current  # Di chuyển prev lên
        current = next_node  # Di chuyển current lên node tiếp theo
    self.head = prev  # Cập nhật head để trỏ đến node cuối cùng (bây giờ là node đầu tiên)
  • prev bắt đầu là None vì node cuối cùng của danh sách liên kết đảo ngược sẽ trỏ đến None.
  • current là head, ta se duyệt qua từng node trong danh sách liên kết. Tại mỗi bước:
    • Ta lưu trữ node tiếp theo của current trong next_node.
    • Đảo ngược liên kết của node hiện tại (current.next) để trỏ về node trước (prev).
    • Cập nhật prev thành current và current thành next_node để tiếp tục duyệt danh sách.
  • Cuối cùng, head được cập nhật để trỏ đến node cuối cùng, là node đầu tiên trong danh sách đảo ngược.

Merge Two Sorted Linked Lists

Ý tưởng cơ bản là so sánh các phần tử từ hai danh sách liên kết và xây dựng một danh sách mới bằng cách liên kết các node theo thứ tự.

    def merge_sorted_lists(self, other_list):

        head1 = self.head  # con trỏ tới đầu danh sách 1
        head2 = other_list.head  # con trỏ tới đầu danh sách 2
        tail = None  # theo dõi phần cuối của merged list

        # Kiểm tra nếu danh sách đầu tiên rỗng
        if not head1:
            return head2
        # Kiểm tra nếu danh sách thứ hai rỗng
        if not head2:
            return head1

        # Bắt đầu so sánh giá trị của hai danh sách
        if head1 and head2:
            if head1.data <= head2.data:
                tail = head1
                head1 = tail.next
            else:
                tail = head2
                head2 = tail.next
            new_head = tail  # new_head là con trỏ tới đầu merged list

        # Duyệt qua hai danh sách và tiếp tục so sánh các phần tử
        while head1 and head2:
            if head1.data <= head2.data:
                tail.next = head1  # Kết nối node nhỏ hơn từ head1
                tail = head1
                head1 = tail.next
            else:
                tail.next = head2  # Kết nối node nhỏ hơn từ head2
                tail = head2
                head2 = tail.next

        # Nếu head1 hết node, nối phần còn lại của head2
        if not head1:
            tail.next = head2
        # Nếu head2 hết node, nối phần còn lại của head1
        if not head2:
            tail.next = head1

        self.head = new_head  # Cập nhật lại head của merged list
        return self.head
  1. Kiểm tra danh sách rỗng:
  • Nếu một trong hai danh sách rỗng, trả về danh sách còn lại.
  1. Xác định node đầu tiên của merged list
  • So sánh giá trị của node đầu tiên từ cả hai danh sách, chọn node có giá trị nhỏ hơn làm new_head (node đầu tiên của merged list).
  1. Merge hai danh sách:
  • Duyệt qua hai danh sách bằng cách so sánh từng node. Node nào nhỏ hơn sẽ được thêm vào merged list trước.
  1. Nối phần còn lại:
  • Khi một trong hai danh sách hết node, nối tất cả các node còn lại của danh sách kia vào.
  1. Cập nhật self.head:
  • Cập nhật self.head để trỏ đến node đầu tiên của merged list và trả về nếu có cần sử dụng cho mục đích khác.

Sử dụng

# Sử dụng danh sách liên kết
llist1 = SinglyLinkedList()
llist2 = SinglyLinkedList()

# Thêm các phần tử vào danh sách liên kết 1 (đã sắp xếp)
llist1.append(1)
llist1.append(3)
llist1.append(5)

# Thêm các phần tử vào danh sách liên kết 2 (đã sắp xếp)
llist2.append(2)
llist2.append(4)
llist2.append(6)

print("Danh sách liên kết 1:")
llist1.display()

print("Danh sách liên kết 2:")
llist2.display()

# Gộp hai danh sách liên kết đã sắp xếp
llist1.merge_sorted_lists(llist2)

print("\nDanh sách liên kết sau khi gộp:")
llist1.display()

Output

Danh sách liên kết 1:

1 -> 3 -> 5 -> None
Danh sách liên kết 2:
2 -> 4 -> 6 -> None

Danh sách liên kết sau khi gộp:
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> None

Remove Duplicates

  • Duyệt qua danh sách liên kết, sử dụng set để lưu các giá trị đã gặp.
  • Mỗi khi gặp một giá trị mới, thêm nó vào set.
  • Nếu gặp một giá trị đã tồn tại trong set, ta xóa node đó khỏi danh sách.
    # Xóa các phần tử trùng lặp trong danh sách
    def remove_duplicates(self):
        if not self.head:
            return

        current = self.head
        prev = None
        seen_data = set()  # Tập hợp để lưu các giá trị đã gặp

        while current:
            if current.data in seen_data:  # Nếu giá trị đã gặp
                prev.next = current.next  # Bỏ qua node hiện tại (current)
            else:
                seen_data.add(current.data)  # Thêm giá trị vào tập hợp
                prev = current  # Cập nhật con trỏ prev
            current = current.next  # Di chuyển đến node tiếp theo
  1. Duyệt qua danh sách:
  • Sử dụng con trỏ current để duyệt qua từng node của danh sách.
  • Con trỏ prev để theo dõi node trước đó, giúp ta cập nhật liên kết khi xóa một node trùng lặp.
  1. Kiểm tra giá trị trùng lặp:
  • Sử dụng set (seen_data) để lưu trữ các giá trị đã gặp.
  • Mỗi khi gặp một giá trị mới, ta thêm nó vào tập hợp.
  • Nếu giá trị đã tồn tại trong tập hợp, ta xóa node hiện tại bằng cách thay đổi con trỏ next của prev.
  1. Cập nhật liên kết:
  • Nếu phát hiện trùng lặp, ta bỏ qua node đó bằng cách thay đổi liên kết giữa prev và current.next.

Sử dụng

# Sử dụng danh sách liên kết
llist = SinglyLinkedList()

# Thêm các phần tử vào danh sách
llist.append(1)
llist.append(2)
llist.append(2)
llist.append(3)
llist.append(4)
llist.append(4)
llist.append(5)

print("Danh sách ban đầu:")
llist.display()

# Xóa các phần tử trùng lặp
llist.remove_duplicates()

print("Danh sách sau khi xóa các phần tử trùng lặp:")
llist.display()

Output

Danh sách ban đầu:
1 -> 2 -> 2 -> 3 -> 4 -> 4 -> 5 -> None
Danh sách sau khi xóa các phần tử trùng lặp:
1 -> 2 -> 3 -> 4 -> 5 -> None

Nth-to-Last Node

  • Tính độ dài của danh sách
  • Xác định vị trí của node thứ N từ cuối target_index = length - N
  • Duyệt qua danh sách từ đầu đến vị trí target_index.
  • Trả về node tại vị trí đó nếu tìm thấy, nếu N không hợp lệ (lớn hơn độ dài của danh sách hoặc N <= 0), trả về None.
    def nth_to_last_node(self, N):
        length = self.get_length_iterative()  # Tính độ dài của danh sách
        if N > length or N <= 0:  # Kiểm tra xem N có hợp lệ không
            return None

        target_index = length - N  # Vị trí tương đương từ đầu danh sách
        current = self.head
        count = 0

        while current:
            if count == target_index:
                return current  # Trả về node thứ N từ cuối
            count += 1
            current = current.next
        return None

Count Occurrences

Hàm count_occurrences sẽ duyệt qua từng node của danh sách, kiểm tra giá trị của từng node và đếm số lần giá trị mà ta muốn kiểm tra xuất hiện trong danh sách.

# Phương thức đếm số lần xuất hiện của một giá trị
    def count_occurrences(self, value):
        count = 0
        current = self.head
        while current:
            if current.data == value:
                count += 1
            current = current.next
        return count

Is Palindrome

Để kiểm tra xem một Singly Linked List có phải là palindrome hay không, chúng ta có thể sử dụng nhiều phương pháp khác nhau.

Sử dụng List

    def is_palindrome(self):
        values = []
        current = self.head

        # Lưu các giá trị của danh sách liên kết vào một list
        while current:
            values.append(current.data)
            current = current.next

        # Kiểm tra xem list có phải là palindrome không
        return values == values[::-1]

Kết bài

Singly Linked List là một trong những cấu trúc dữ liệu cơ bản và quan trọng trong lập trình. Nó cung cấp một cách hiệu quả để lưu trữ và quản lý dữ liệu động, với các thao tác CRUD mà không cần cấp phát lại bộ nhớ như mảng. Tuy nhiên, điểm hạn chế của Singly Linked List là khó truy cập ngẫu nhiên đến các phần tử so với cấu trúc dữ liệu như mảng, do phải duyệt tuần tự qua từng node.

Việc nắm vững các thao tác trong Singly Linked List sẽ giúp ta áp dụng chúng một cách hiệu quả trong các bài toán lập trình. Hơn nữa, hiểu rõ các thuật toán liên quan đến danh sách liên kết đơn như reverse, kiểm tra palindrome, hay merge sorted list sẽ nâng cao kỹ năng xử lý dữ liệu của ta trong những tình huống thực tế.

Dù là một cấu trúc dữ liệu đơn giản, Singly Linked List vẫn là nền tảng quan trọng để hiểu sâu hơn về các cấu trúc dữ liệu phức tạp hơn, và sẽ trở thành công cụ mạnh mẽ khi bạn giải quyết những bài toán cần sự linh hoạt trong quản lý dữ liệu.

linked list singly linked list swap nodes linked list in python

All rights reserved

Mục lục


Viblo
Hãy đăng ký một tài khoản Viblo để nhận được nhiều bài viết thú vị hơn.
Đăng kí