Login

Danh sách liên kết (linked list) là gì và khác mảng ở điểm nào?

  • author-image

    Nguyễn Đình Cường

  • blog-tag
  • blog-comment 0 comment
  • created-date 09 Nov, 2026
blog-thumbnail

Mảng rất tiện, nhưng chèn một phần tử vào giữa thì phải dời cả dãy phía sau. Danh sách liên kết ra đời với cách tổ chức hoàn toàn khác: mỗi phần tử tự biết phần tử kế tiếp nằm ở đâu, giống một chuỗi mắt xích.

Cấu tạo của danh sách liên kết

Một danh sách liên kết gồm nhiều nút (node). Mỗi nút chứa hai thứ: dữ liệu và một tham chiếu (con trỏ) đến nút tiếp theo. Nút cuối trỏ tới "không có gì" (null hay None). Ta chỉ cần giữ nút đầu tiên, gọi là head, là có thể đi qua cả danh sách.

class Node:
    def __init__(self, gia_tri):
        self.gia_tri = gia_tri
        self.tiep = None

class DanhSach:
    def __init__(self):
        self.head = None

    def them_dau(self, gia_tri):
        nut = Node(gia_tri)
        nut.tiep = self.head
        self.head = nut

    def them_cuoi(self, gia_tri):
        nut = Node(gia_tri)
        if self.head is None:
            self.head = nut
            return
        hien_tai = self.head
        while hien_tai.tiep:
            hien_tai = hien_tai.tiep
        hien_tai.tiep = nut

    def in_ra(self):
        hien_tai = self.head
        while hien_tai:
            print(hien_tai.gia_tri, end=" -> ")
            hien_tai = hien_tai.tiep
        print("None")

ds = DanhSach()
ds.them_dau(2)
ds.them_dau(1)
ds.them_cuoi(3)
ds.in_ra()   # 1 -> 2 -> 3 -> None

Cách hoạt động khi thêm và xóa

Điểm mạnh của danh sách liên kết nằm ở thao tác chèn và xóa. Giả sử cần chèn nút X vào giữa A và B. Bạn chỉ cần sửa hai tham chiếu: A trỏ tới X, X trỏ tới B. Không có phần tử nào phải dời đi. Với xóa cũng tương tự: cho nút đứng trước bỏ qua nút cần xóa và trỏ thẳng đến nút sau nó.

def xoa(self, gia_tri):
    if self.head is None:
        return
    if self.head.gia_tri == gia_tri:
        self.head = self.head.tiep
        return
    hien_tai = self.head
    while hien_tai.tiep and hien_tai.tiep.gia_tri != gia_tri:
        hien_tai = hien_tai.tiep
    if hien_tai.tiep:
        hien_tai.tiep = hien_tai.tiep.tiep

Hàm trên là một phương thức bạn thêm vào lớp DanhSach. Lưu ý phải xử lý riêng trường hợp xóa nút đầu và trường hợp không tìm thấy.

Mảng so với danh sách liên kết

Tiêu chíMảngLinked list
Truy cập phần tử thứ kRất nhanhPhải đi từ đầu, chậm
Chèn hoặc xóa ở đầuChậm (dời phần tử)Nhanh
Chèn hoặc xóa khi đã có vị tríChậmNhanh
Bộ nhớLiền khối, gọnMỗi nút tốn thêm chỗ cho con trỏ
Hiệu năng bộ nhớ đệm CPUThường tốt hơnThường kém hơn

Trên thực tế, với dữ liệu thông thường, mảng thường thắng nhờ tính liền khối thân thiện với CPU. Danh sách liên kết hữu ích khi cần chèn xóa liên tục ở các vị trí đã biết, hoặc khi bạn xây các cấu trúc khác bên trên nó.

Các biến thể

  • Danh sách liên kết đôi: mỗi nút có cả con trỏ đến nút trước, đi được hai chiều.
  • Danh sách liên kết vòng: nút cuối trỏ về nút đầu.

Câu hỏi hay gặp khi phỏng vấn

Danh sách liên kết rất hay xuất hiện trong bài kiểm tra kỹ thuật: đảo ngược danh sách, tìm nút giữa, phát hiện vòng lặp, gộp hai danh sách đã sắp xếp. Mẹo dùng được cho nhiều bài là kỹ thuật hai con trỏ, một con đi nhanh và một con đi chậm. Trước khi code, hãy vẽ các nút và mũi tên ra giấy, rất nhiều lỗi được tránh nhờ bước này.

Lỗi thường gặp với danh sách liên kết

  1. Mất đầu danh sách. Nếu gán head trước khi nối nút cũ vào, bạn đánh mất các nút phía sau. Hãy nối nút mới vào trước rồi mới cập nhật head.
  2. Quên trường hợp danh sách rỗng khi thêm hoặc xóa.
  3. Truy cập thuộc tính của None. Viết hien_tai.tiep.gia_tri khi tiep là None gây lỗi. Kiểm tra trước.
  4. Tạo vòng lặp vô tình khiến việc duyệt không bao giờ kết thúc.

Bài tập hay nhất để luyện là đảo ngược danh sách liên kết:

def dao_nguoc(head):
    truoc = None
    hien_tai = head
    while hien_tai:
        ke = hien_tai.tiep
        hien_tai.tiep = truoc
        truoc = hien_tai
        hien_tai = ke
    return truoc

Ba con trỏ truoc, hien_tai, ke lần lượt đảo chiều từng mũi tên. Hãy vẽ ba nút ra giấy và mô phỏng từng bước để thấy rõ cơ chế.

Kết luận

Danh sách liên kết cho bạn hiểu rõ hơn về tham chiếu và cách dữ liệu nằm trong bộ nhớ. Dù ít khi bạn phải tự viết trong công việc hằng ngày, đây là nền tảng để học cây, đồ thị và hiểu các thư viện hoạt động thế nào bên trong.

Muốn học bài bản và có người hướng dẫn? Hãy xem các khóa học trên codebem.com để đi từ nền tảng đến dự án thực tế.

author_photo
Nguyễn Đình Cường

0 comment