Danh sách liên kết (linked list) trong Python
Bài 5/20 · Chương 23
Cấu trúc dữ liệu và giải thuật
- 7 phút
- Trung cấp
- Python 3.14
- Cập nhật
Trong bài này · 11
Danh sách liên kết (linked list) là một dãy giá trị mà mỗi phần tử nằm trong một nút, và mỗi nút giữ đường tới nút ngay sau nó. Bạn dùng nó khi cần thêm hay bớt phần tử ở đầu dãy thật nhanh, hoặc chèn một trạm vào giữa tuyến xe mà không phải dời các trạm còn lại.
Cần biết trước: None, vòng lặp while và __init__ và self.
Nút và đường tới nút sau
Tuyến xe là một chuỗi trạm: đứng ở trạm nào, bạn chỉ cần biết trạm kế tiếp. Mỗi nút (node) giữ hai thuộc tính: gia_tri là dữ liệu, tiep trỏ tới nút sau. Nút cuối có tiep là None, tức là hết đường.
class Node:
def __init__(self, gia_tri, tiep=None):
self.gia_tri = gia_tri
self.tiep = tiep
ga = Node("Ga Huế")
dai_noi = Node("Đại Nội")
cho = Node("Chợ Đông Ba")
ga.tiep = dai_noi
dai_noi.tiep = cho
nut = ga
while nut is not None:
print(nut.gia_tri)
nut = nut.tiepKẾT QUẢ
Ga Huế
Đại Nội
Chợ Đông BaDuyệt danh sách là đi từ nút đầu, theo tiep từng bước, tới khi gặp None. Python không cất các nút liền nhau như list: mỗi nút là một object riêng, và chỉ có thuộc tính tiep nối chúng thành dãy, giống các toa tàu móc vào nhau. Đổi ga.tiep = dai_noi thành ga.tiep = cho rồi chạy lại: chỉ còn hai dòng, dòng hai in Chợ Đông Ba, vì Đại Nội không còn nút nào trỏ tới.
Class LinkedList và thêm vào đầu
Class LinkedList chỉ cần giữ nút đầu trong self.dau. Thêm vào đầu là ba bước: tạo nút mới, cho nó trỏ tới nút đầu cũ, rồi đặt nó làm nút đầu.
class Node:
def __init__(self, gia_tri, tiep=None):
self.gia_tri = gia_tri
self.tiep = tiep
class LinkedList:
def __init__(self):
self.dau = None
def them_dau(self, gia_tri):
self.dau = Node(gia_tri, self.dau)
hang = LinkedList()
for ma in ["A01", "A02", "A03"]:
hang.them_dau(ma)
print(hang.dau.gia_tri, hang.dau.tiep.gia_tri)KẾT QUẢ
A03 A02Node(gia_tri, self.dau) làm cả hai bước đầu trong một dòng. Dù danh sách dài một triệu nút, them_dau() vẫn chỉ làm đúng việc đó: O(1). Thêm vào cuối thì khác: phải đi từ nút đầu qua mọi nút mới tới được nút cuối, nên là O(n), trừ khi class giữ thêm một thuộc tính trỏ thẳng tới nút cuối.
Xóa một nút bằng cách nối vòng qua nó
Xóa một trạm là cho nút đứng trước nó trỏ thẳng tới nút đứng sau. Nút bị bỏ qua không còn ai trỏ tới, Python tự thu dọn nó.
class Node:
def __init__(self, gia_tri, tiep=None):
self.gia_tri = gia_tri
self.tiep = tiep
cuoi = Node("Chợ Đông Ba", Node("Thiên Mụ"))
dau = Node("Ga Huế", Node("Đại Nội", cuoi))
truoc = dau
while truoc.tiep.gia_tri != "Chợ Đông Ba":
truoc = truoc.tiep
truoc.tiep = truoc.tiep.tiep
nut = dau
while nut is not None:
print(nut.gia_tri)
nut = nut.tiepKẾT QUẢ
Ga Huế
Đại Nội
Thiên MụDòng truoc.tiep = truoc.tiep.tiep là cả việc xóa: không nút nào phải dời chỗ. Phần tốn công là đi tìm nút đứng trước, O(n) ở trường hợp xấu nhất.
Duyệt bằng for và so sánh với list
Bài iterator và next() cho biết for gọi __iter__ rồi __next__ tới khi gặp StopIteration. Một iterator đi theo tiep là đủ để for và list() đọc được chuỗi nút:
class Node:
def __init__(self, gia_tri, tiep=None):
self.gia_tri, self.tiep = gia_tri, tiep
class DuyetNut:
def __init__(self, nut):
self.nut = nut
def __iter__(self):
return self
def __next__(self):
if self.nut is None:
raise StopIteration
gia_tri, self.nut = self.nut.gia_tri, self.nut.tiep
return gia_tri
dau = Node("Ga Huế", Node("Đại Nội", Node("Chợ Đông Ba")))
print(list(DuyetNut(dau)))KẾT QUẢ
['Ga Huế', 'Đại Nội', 'Chợ Đông Ba']List của Python cất các phần tử liền nhau, nên lấy theo chỉ số nhanh mà thêm ở đầu chậm. Danh sách liên kết thì ngược lại:
Thao tác | list | Danh sách liên kết giữ |
|---|---|---|
Lấy phần tử thứ | O(1) | O(n), phải đi từ đầu |
Thêm, bớt ở đầu | O(n), dời mọi phần tử | O(1) |
Thêm ở cuối | O(1) | O(n), trừ khi giữ thêm nút cuối |
Xóa khi đã đứng ở nút trước | O(n), dời phần còn lại | O(1) |
Mỗi nút còn tốn thêm chỗ cho thuộc tính tiep. Trong code thật bạn ít khi tự viết danh sách liên kết: deque của Python đã dựng sẵn trên các khối nối với nhau (cách CPython cài), bài deque dùng nó.
Kiểm tra nhanh
Trong ví dụ ba trạm nối tay, nếu thêm dòng
cho.tiep = Node("Thiên Mụ")ngay trước dòngnut = ga, vòng while in ra mấy trạm?- 3
- 4
- 1
Trong khung bẫy đi tới nút cuối của danh sách rỗng, Python báo lỗi gì?
AttributeErrorIndexErrorTypeError
Với danh sách liên kết chỉ giữ nút đầu
dau, những thao tác nào là O(1)?- Thêm một nút vào đầu
- Thêm một nút vào cuối
- Lấy giá trị ở vị trí thứ
i - Xóa nút đầu bằng
dau = dau.tiep
Trong khung bẫy quên trường hợp nút đầu, dòng
print(dau.gia_tri)in ra gì?Đại NộiGa HuếNone
Bài tập
Viết danh sách liên kết cho các trạm của tuyến
Tuyến xe giữ các trạm trong một danh sách liên kết: self.dau là nút đầu, mỗi Node có gia_tri và tiep. Viết thân ba phương thức của LinkedList, không cất trạm vào list nào khác:
them_cuoi(gia_tri): nối mộtNodemới vào sau nút cuối. Danh sách rỗng thì nút mới là nút đầu.xoa(gia_tri): xóa nút đầu tiên manggia_tri, trả vềTrue. Không có nút đó thì trả vềFalse.danh_sach(): các giá trị từ nút đầu tới nút cuối.
Trả về: xoa() một bool, danh_sach() một list.
class Node:
def __init__(self, gia_tri, tiep=None):
self.gia_tri = gia_tri
self.tiep = tiep
class LinkedList:
def __init__(self):
self.dau = None
def them_cuoi(self, gia_tri):
pass # Viết thân các phương thức thay cho các dòng pass
def xoa(self, gia_tri):
pass
def danh_sach(self):
passTóm tắt
Danh sách liên kết nối các nút: mỗi
Nodegiữgia_trivàtiep, nút cuối cótieplàNone.Duyệt là đi từ nút đầu theo
tiepcho tới khi gặpNone.Thêm hay xóa ở đầu là O(1), lấy phần tử thứ
ihay đi tới cuối là O(n).Xóa một nút là nối nút đứng trước sang nút đứng sau, và phải xét riêng nút đầu.
Đọc
.tiepcủaNonekhi danh sách rỗng báoAttributeError.
Câu hỏi thường gặp
Linked list là gì, khác list của Python ở đâu?
Linked list là chuỗi nút nối nhau bằng tham chiếu, list của Python là một khối ô liền nhau. Vì vậy list lấy theo chỉ số trong một bước, còn linked list phải đi từ đầu. Đổi lại, linked list thêm và bớt ở đầu không phải dời phần tử nào, như bảng so sánh của bài.
Python có sẵn kiểu linked list không?
Không có kiểu tên linked list. collections.deque là thứ gần nhất: trong CPython nó cất phần tử trong các khối nối hai chiều, nên thêm bớt ở hai đầu đều nhanh. Bài deque dạy kiểu này, và bạn nên dùng nó thay cho tự viết trong chương trình thật.
Danh sách liên kết đôi là gì?
Mỗi nút giữ thêm một thuộc tính trỏ về nút đứng trước, nên đi được cả hai chiều và xóa một nút khi đang đứng ngay ở nó mà không cần tìm nút trước. Cái giá là mỗi lần nối hay xóa phải sửa hai tham chiếu thay vì một. Cây nhị phân dùng cùng ý đó với hai con, bài cây nhị phân ngay sau bài này.
Chủ đề
Bài này có hữu ích?
Hỏi đáp
Tham vấn chuyên môn
Nhà sáng lập AIDev và VietPlatform · Thạc sĩ AI MSE
- Tốt nghiệp thủ khoa xuất sắc Thạc sĩ AI MSE.
- Đồng sáng lập, CTO E-University, SVOnline: số hóa 10+ đại học, 40.000+ sinh viên.
- Xây hệ thống AI cho doanh nghiệp tại VietPlatform.