Data Structures - Danh sách liên kết đơn (Linked List)

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.

Data Structures - Danh sách liên kết đơn (Linked List)

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.

 

Data Structures - Danh sách liên kết đơn (Linked List)

 

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.
 
Linked List được cấu thành từ những phần tử (element) và được liên kết (linked) lại với nhau tạo thành một danh sách. Mỗi phần tử trong Linked List gọi là một Node. Mỗi Node được cấu thành từ hai thành phần cơ bản như sau:
  • 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.
Đối với danh sách liên kết đôi (Doubly Linked List) còn có thêm con trỏ prev để lưu trữ địa chỉ của Node trước đó. Trong khuôn khổ bài viết này, mình sẽ trình bày danh sách liên kết đơn (Singly Linked List) nên chỉ cần hai thành phần như trên là đủ.
Ở ví dụ này, mình sẽ viết code mẫu cho xây dựng danh sách liên kết đơn cơ bản với các thành phần như sau:
  • 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
 
Các bạn soi code nhé !
 
Đầu tiên, mình sẽ định nghĩa cấu trúc dữ liệu cho một Node như sau:

Data Structures - Danh sách liên kết đơn (Linked List)

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 headtail nhằm quản lý việc thêm, xóa phần tử trong danh sách.

Data Structures - Danh sách liên kết đơn (Linked List)

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.

Data Structures - Danh sách liên kết đơn (Linked List)

Ở 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:

Data Structures - Danh sách liên kết đơn (Linked List)

Data Structures - Danh sách liên kết đơn (Linked List)

Hàm xóa một Node khỏi danh sách:

Data Structures - Danh sách liên kết đơn (Linked List)

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.

Data Structures - Danh sách liên kết đơn (Linked List)

Chạy thử code nhé !

Data Structures - Danh sách liên kết đơn (Linked List)

Kết quả:

Data Structures - Danh sách liên kết đơn (Linked List)

 

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ề:

 
 

Bình luận