Data Structures - Danh sách liên kết đơn (Linked List)
Khi phát triển ứng dụng, nhất là các ứng dụng trên vi điều khiển, ngoài phần code cấu hình ngoại vi (Peripheral), lập trình viên cần nắm về cấu trúc dữ liệu, các cấu trúc liên quan đến container (Vector, Linked List, cấu trúc cây,...) đặt biệt là Linked List. Để ứng dụng Linked List vào ứng dụng thực tế, các bạn cần thao tác rất nhuần nhuyễn, tự mình code Linked List, không dùng thư viện chuẩn của C, do nhiều MCU bộ nhớ bị giới hạn, khi đó sẽ không sử dụng được thư viện chuẩn C Standard Library.
Linked List được sử dụng để hiện thực thao tác bộ nhớ động heap, các hàm malloc(), free(), ruột bên trong là các thao tác Linked List, Linked List cũng là xương sống trong các hệ điều hành thời gian thực RTOS. Tóm lại, nắm được Linked List, ứng dụng của bạn sẽ rất linh hoạt.
Danh sách liên kết (Linked List) là một cấu trúc dữ liệu dạng danh sách, mảng (Array) cũng là một cấu trúc dữ liệu dạng danh sách. Để truy cập các phần tử trong Array, chúng ta sẽ thông qua index (chỉ mục) đến vị trí của phần tử trong mảng, và phải duyệt mảng. Kích thước của Array thường được chốt cố định, không thay đổi trong quá trình chạy của chương trình, nếu ứng dụng mà dùng được C++ các bạn nên sử dụng Vector thay cho Array, sẽ linh hoạt hơn nhiều.
Khác với Array, Linked list cho phép tổ chức danh sách này ở dạng động, tức là không biết trước số lượng phần tử cần thêm vào danh sách. Việc truy cập đến phần tử trong Linked list sẽ được truy cập thông qua head (vị trí đầu danh sách) hoặc tail (vị trí cuối danh sách).
Các bạn hình dung Linked List giống một sợi dây xích vậy, từng phần tử trong danh sách sẽ móc nối và tạo liên kết với nhau.
Khi mình thêm một phần tử vào danh sách, sợi dây này sẽ dài ra, khi mình lấy một phần tử ra, sợi dây này sẽ ngắn lại. Từng phần tử đều có mối liên hệ liền kề với phần tử ở cạnh nó.
Tùy nhu cầu sử dụng Linked List có thể biến thành Queue, Ring Buffer, Pool memory,.. Linked List có 2 dạng để duyệt list.
- Linked List Đơn (Singly Linked List): List chỉ duyệt từ đầu tới đuôi.
- Linked List Đôi (Doubly Linked List): List có thể duyệt từ đầu đến đuôi và ngược lại từ đuôi đến đầu.
- Dữ liệu: là thành phần lưu trữ dữ liệu của Node.
- Con trỏ next: lưu trữ địa chỉ của Node kế tiếp.
- Khởi tạo danh sách
- Thêm một phần tử vào danh sách
- Xóa một phần tử khỏi danh sách
Trong định nghĩa Node này, data chính là nơi lưu trữ dữ liệu của Node, các bạn có thể thay thế kiểu dữ liệu khác cho data này hoặc thêm các data khác nữa tùy thuộc vào ứng dụng. Con trỏ next của Node để lưu địa chỉ của Node tiếp theo khi khởi tạo danh sách.
Mình sẽ định nghĩa một danh sách liên kết đơn với head và tail nhằm quản lý việc thêm, xóa phần tử trong danh sách.
Trong cấu trúc list_t phía trên, khi được khởi tạo head sẽ trỏ đến đầu danh sách và tail sẽ trỏ đến cuối danh sách. Đối với loại Đơn các bạn không cần tail cũng được nha, không có tail thì Node nào trỏ đến NULL chính là tail.
Tiếp theo, mình sẽ tạo các hàm quản lý các phần tử trong danh sách.
Để thêm một Node mới vào danh sách, mình cần cấp phát vùng nhớ cho Node này.
Ở ví dụ này mình đang cấp phát bộ nhớ ở dạng động (dynamic). Mỗi lần khởi tạo một Node mới nó sẽ lấy dữ liệu từ vùng nhớ Heap để cấp phát cho Node. Ở bài viết kế tiếp, mình sẽ trình bày cơ chế Pool memory, ta sẽ cấp phát tĩnh một "bể" dữ liệu để thay cho việc lấy bộ nhớ từ vùng Heap này (Một dạng Linked List nằm trong 1 Array :) )
Để thêm một Node vào danh sách, mình sẽ tạo các hàm như sau:
Hàm xóa một Node khỏi danh sách:
Như vậy tương đối đã đủ các thành phần cơ bản để quản lý các thao tác trên Linked List. Mình tạo thêm một hàm để in ra các phần tử trong danh sách này để dễ quan sát.
Chạy thử code nhé !
Kết quả:
Các bạn tham khảo các chủ đề thú vị khác về Lập trình nhúng Vi điều khiển tại: AK Embedded Software
Các thắc mắc các bạn gửi về:
- Facebook: https://www.facebook.com/groups/laptrinhvidieukhiennangcao
- Zalo: 0367 939 867
- Email: contact@epcb.vn
Bình luận