Cài đặt danh sách liên kết đơn bằng C++

Trái ngược với danh sách tuyến tính sử dụng mảng một chiều, danh sách liên kết đơn sử dụng con trỏ và địa chỉ xác định các phần tử trong danh sách. Kể từ danh sách liên kết đơn trở đi, việc hiểu và sử dụng thành thạo con trỏ gần như là điều bắt buộc đối với môn Cấu trúc dữ liệu (CTDL).

Ưu điểm của danh sách liên kết đơn đó là bộ nhớ được cấp phát động tùy theo số lượng phần tử được chèn vào danh sách.

Nhược điểm của nó là chúng ta không thể truy xuất phần tử theo vị trí như mảng một chiều mà buộc phải duyệt qua tất cả các node trong danh sách để tìm phần tử cần xử lý, và chỉ có 1 chiều di chuyển từ node đầu tới node cuối chứ không thể theo chiều ngược lại. Ngoài ra, mỗi nút của danh sách phải chứa thêm con trỏ next nên tốn thêm bộ nhớ.

Nói thêm về mảng một chiều thực nhất cũng là các ô nhớ được cấp phát trước, tuy nhiên, các ô nhớ này lại nằm liền kề nhau, tương đương với địa chỉ của node và node sau chỉ chênh nhau 1 đơn vị * sizeof(type) nên chúng ta có thể dễ dàng lấy ra một phần tử bất kỳ chỉ dựa vào vị trí của nó. Còn đối với danh sách liên kết, các ô nhớ nằm rải rác với các địa chỉ khác nhau, và cách duy nhất để kết nối chúng với nhau là dựa vào con trỏ.

Trong danh sách liên kết đơn, phần tử trước được kết nối với phần tử sau bởi một con trỏ duy nhất. Với danh sách liên kết đôi, mỗi node sẽ có 2 con trỏ để liên kết tới phần tử trước và sau nó.

Bây giờ, chúng ta sẽ thử cài đặt một cấu trúc liên kết đơn đơn giản cùng các hàm xử lý cơ bản cho nó. Cấu trúc mỗi node của chúng ta sẽ rất đơn giản, bao gồm một biến id chứa giá trị kiểu số nguyên và một con trỏ next để chứa địa chỉ của node kế tiếp.

Các bạn có thể tải về mã nguồn đầy đủ của chương trình demo từ link bên dưới. Demo được viết bằng ngôn ngữ C++, sử dụng IDE Dev-C++ 5.11.

Singly Linked List

Output của chương trình sẽ có dạng như sau:

 26 ->  NULL
 26 -> -94 ->  NULL
 26 -> -94 -> -65 ->  NULL
 26 -> -94 -> -65 ->  -7 ->  NULL
 26 -> -94 -> -65 ->  -7 ->  29 ->  NULL
-55 ->  26 -> -94 -> -65 ->  -7 ->  29 ->  NULL
-77 -> -55 ->  26 -> -94 -> -65 ->  -7 ->  29 ->  NULL
-73 -> -77 -> -55 ->  26 -> -94 -> -65 ->  -7 ->  29 ->  NULL
 33 -> -73 -> -77 -> -55 ->  26 -> -94 -> -65 ->  -7 ->  29 ->  NULL
  2 ->  33 -> -73 -> -77 -> -55 ->  26 -> -94 -> -65 ->  -7 ->  29 ->  NULL

Linked list sorted ascending:
-94 -> -77 -> -73 -> -65 -> -55 ->  -7 ->   2 ->  26 ->  29 ->  33 ->  NULL

Linked list sorted descending:
 33 ->  29 ->  26 ->   2 ->  -7 -> -55 -> -65 -> -73 -> -77 -> -94 ->  NULL

Chú thích:

- Chương trình sẽ sinh ngẫu nhiên 10 phần tử để chèn vào danh sách.

- 5 phần tử đầu tiên sẽ được chèn vào cuối danh sách nhờ hàm insert_last().

- 5 phần tử tiếp theo sẽ được chèn vào đầu danh sách nhờ hàm insert_first().

- Sau đó, sắp xếp danh sách tăng dần dựa trên thuật toán Bubble Sort.

- Và sắp sếp giảm dần cũng dựa trên Bubble Sort.

Xem thêm: Cài đặt danh sách liên kết đơn bằng C