Bỏ qua đến nội dung chính
Mục lục

Danh sách liên kết (linked list) trong Python

AIDev Team · duyệt: Nguyễn Việt Chung

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

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.

python
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.tiep

KẾT QUẢ

Ga Huế
Đại Nội
Chợ Đông Ba

Duyệ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.

python
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 A02

Node(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ó.

python
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.tiep

KẾ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:

python
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ữ dau

Lấy phần tử thứ i

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

  1. 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òng nut = ga, vòng while in ra mấy trạm?

    • 3
    • 4
    • 1
  2. Trong khung bẫy đi tới nút cuối của danh sách rỗng, Python báo lỗi gì?

    • AttributeError
    • IndexError
    • TypeError
  3. 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
  4. Trong khung bẫy quên trường hợp nút đầu, dòng print(dau.gia_tri) in ra gì?

    • Đại Nội
    • Ga Huế
    • None
Đúng hết lần đầu +15 XP

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ột Node mớ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 mang gia_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.

python
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):
        pass

Tóm tắt

  • Danh sách liên kết nối các nút: mỗi Node giữ gia_tri và tiep, nút cuối có tiep là None.

  • Duyệt là đi từ nút đầu theo tiep cho tới khi gặp None.

  • Thêm hay xóa ở đầu là O(1), lấy phần tử thứ i hay đ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 .tiep của None khi danh sách rỗng báo AttributeError.

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ủ đề

linked list

Bài này có hữu ích?

Hỏi đáp

Đang tải câu hỏi…

Tham vấn chuyên môn

Nguyễn Việt Chung

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.
Biên soạn: AIDev Team · Rà soát · Quy trình biên tập