Xây dựng danh sách liên kết đơn với con trỏ (pointer)

1. Xây dựng một node trong danh sách liên đơn

Danh sách liên kết đơn (singly linked list) có đặc điểm là mỗi node (phần tử) chỉ liên kết với node đứng sau nó trong danh sách.

Mỗi node trong danh sách liên kết gồm 2 phần:

• • Phần dữ liệu (data) dùng để lưu nội dung của node.
  • Phần địa chỉ liên kết (address), thường ký hiệu là next, là các con trỏ có cùng kiểu với node. Các con trỏ này lưu trữ địa chỉ của node kế tiếp trong danh sách. Nếu là node cuối cùng thì con trỏ trỏ đến NULL.

Có thể sử dụng kiểu dữ liệu cấu trúc (struct) để xây dựng một node như sau:

struct node{
	<Kiểu dữ liệu> data;//nội dung của node
	node *next;//con trỏ lưu địa chỉ của node kế tiếp
};

<Kiểu dữ liệu> trong một node của danh sách liên kết đơn có thể là một kiểu bất kỳ như int, float, pointer, struct,…

2. Xây dựng danh sách liên đơn với các node

Bằng cách khai báo nhiều node và liên kết chúng lại với nhau, chúng ta có thể tạo ra một danh sách liên kết đơn. Trước hết, các bạn cần đọc lại bài Kỹ thuật cấp phát bộ nhớ động và minh họa với C++. Chúng sẽ sử dụng con trỏ và kỹ thuật cấp phát động để tạo ra danh sách liên kết đơn.

#include <iostream>
using namespace std;
struct node{
	int data;//nội dung của node
	node *next;//con trỏ lưu địa chỉ của node kế tiếp
};

void main()
{
	//Khai báo các node
	node *head;
	node *one = NULL;
	node *two = NULL;
	node *three = NULL;

	//Cấp phát động các node
	one = new node;
	two = new node;
	three = new node;

	//Gán giá trị cho các node
	one->data = 1;
	two->data = 2;
	three->data = 3;

	//Liên kết các node
	one->next = two;
	two->next = three;
	three->next = NULL;
	//Lưu địa chỉ của node đầu tiên trong head
	head = one;
	system("pause");
}

Với chương trình trên, chúng ta đã tạo ra một danh sách liên kết đơn đơn giản gồm 3 nodes như hình minh họa bên dưới.

Sử dụng struct để xây dựng một danh sách liên kết đơn

Ở chương trình trên, chúng ta khai báo nhiều node rồi liên kết chúng lại với nhau. Việc này làm cho code khá nhiều và rườm rà. Chúng ta có thể sử dụng struct để xây dựng một danh sách liên kết đơn gọn gàng hơn như sau:

struct node{
	int data;//nội dung của node
	node *next;//con trỏ lưu địa chỉ của node kế tiếp
};

struct sList{
	node *head;
	node *tail;
};

sList là danh sách đơn mà chúng ta xây dựng được. sList có node *head để lưu địa chỉ của node đầu tiên. sList có node *tail để lưu địa chỉ của node cuối cùng. Chúng ta hoàn toàn có thể thêm các node vào sau node *head và trước node *tail cho sList.

Sở dĩ chúng ta có thể xây dựng danh sách liên kết sList như trên là nhờ vào đặc điểm của danh sách liên kết. Nếu biết được địa chỉ của phần tử đầu tiên trong danh sách thì có thể dựa vào thông tin next của nó để truy xuất đến phần tử thứ 2. Rồi lại dựa vào thông tin next của phần tử  thứ 2 để truy xuất đến phần tử thứ 3,…Nghĩa là để quản lý một danh sách liên kết đơn chỉ cần biết địa chỉ phần tử đầu tiên (node *head).

Nhưng trong nhiều trường hợp, chúng ta cần làm việc với phần tử cuối danh sách liên kết đơn. Nên để tránh phải duyệt từ đầu danh sách, ta sử dụng thêm một node *tail để lưu trữ địa chỉ của phần tử cuối danh sách.

3. Một số ví dụ về danh sách liên kết đơn

Ví dụ 1. Định nghĩa danh sách liên kết đơn lưu trữ một dãy số nguyên.

struct node{
	int info;//lưu kiểu số nguyên
	node *next;
};
struct so_nguyen_list{
	node *head;
	node *tail;
};

Ví dụ 2. Định nghĩa danh sách liên kết đơn lưu trữ hồ sơ sinh viên.

struct SinhVien{
	char Ten[30];
	int MaSV;
};

struct SinhVienNode{
	SinhVien info;//lưu sinh viên
	SinhVienNode *next;
}

struct sinh_vien_list{
	SinhVienNode *head;
	SinhVienNode *tail;
};

Kiểu dữ liệu lưu thông tin của một node trong danh sách liên kết đơn ở trên là một struct SinhVien được lập trình viên tự định nghĩa.