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:
- 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.
- 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
- 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
).
- 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ỏ đếncurrent_node2
("D")
prev_node2.next ("C")
sẽ trỏ đếncurrent_node1 ("A")
- 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. SauA
(current_node1.next
) sẽ làNone
(current_node2.next
) và sauD
(current_node2.next
) sẽ làB
(current_node1.next
)
- 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ỏ đếnNone
.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
trongnext_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ànhcurrent
vàcurrent
thànhnext_node
để tiếp tục duyệt danh sách.
- Ta lưu trữ node tiếp theo của
- 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
- 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.
- 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).
- 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.
- 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.
- 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
- 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.
- 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ủaprev
.
- 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ặcN <= 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.
All Rights Reserved