Danh sách liên kết (Linked List) là gì? Các loại danh sách liên kết

Đây là bài 10/18 bài của series môn học Cấu trúc dữ liệu và giải thuật

Bài này sẽ giới thiệu về cấu trúc dữ liệu danh sách liên kết (Linked List). Đây là một trong những cấu trúc dữ liệu kinh điển thường được nhắc đến. Linked List có nhiều loại khác nhau. Hãy cùng nhau tìm hiểu các đặc điểm của từng loại Linked List nào nhé!

1. Danh sách liên kết (Linked List) là gì?

Một danh sách liên kết (Linked List) là một cấu trúc dữ liệu tuyến tính, bao gồm một chuỗi các node kết nối với nhau. Mỗi node có thể xem như một phần tử trong danh sách. Mỗi node sẽ lưu trữ dữ liệu (data) của node đó và địa chỉ (address) của node kế tiếp. Bên dưới là minh họa cấu trúc dữ liệu danh sách liên kết.

Singly linked list

Danh sách liên kết phải có node bắt đầu, được gọi là HEAD. Node cuối cùng được gọi là TAIL. Mỗi node có nhiều nhất 1 phần tử đứng trước cũng như có nhiều nhất 1 phần tử đứng sau.

Có nhiều trường hợp trong thực tế có thể được lưu trữ bằng cách sử dụng Linked List như:

    • Danh sách học sinh
    • Danh mục sách trong thư viện
    • Danh bạ điện thoại
    • Danh sách các nhân viên trong công ty

2. Các loại danh sách liên kết

Có nhiều loại danh sách liên kết như danh sách liên kết đơn (singly linked list), danh sách liên kết kép (doubly linked list), danh sách liên kết vòng (circular linked list).

Danh sách liên kết đơn (singly linked list)

Singly linked list

Mỗi phần tử chỉ liên kết với phần tử đứng sau nó trong danh sách.

Danh sách liên kết kép (doubly linked list)

Doubly linked list

Mỗi phần tử liên kết với phần tử đứng trước và đứng sau nó trong danh sách.

Danh sách liên kết vòng (circular linked list)

Đặc điểm của Circular Linked List là phần tử cuối danh sách liên kết với phần tử đầu danh sách. Có 2 loại danh sách liên kết vòng là:

Danh sách liên kết đơn vòng
Circular linked list
Danh sách liên kết đôi vòng
Linked list đôi vòng

Ở những bài sau, chúng ta sẽ tìm hiểu về cách xây dựng các loại danh sách liên kết cũng như những thao tác cơ bản trên chúng.

4.7/5 - (12 bình chọn)
Bài trước và bài sau trong môn học<< Thuật toán sắp xếp Quick SortXây dựng danh sách liên kết đơn với con trỏ (pointer) >>
Chia sẻ trên mạng xã hội:

Trả lời

Lưu ý:

1) Vui lòng bình luận bằng tiếng Việt có dấu.

2) Khuyến khích sử dụng tên thật và địa chỉ email chính xác.

3) Mọi bình luận trái quy định sẽ bị xóa bỏ.