Danh sách liên kết và một số thao tác trên danh sách liên kết

Danh sách liên kết là gì?

Danh sách liên kết là một cấu trúc dữ liệu bao gồm một tập, trong đó mỗi phần tử là một phần của một nút có chứa một liên kết tới một nút.

Để khai báo danh sách liên kết trong C, ta có thể dùng cấu trúc con trỏ.

Ví dụ khai báo một danh sách liên kết mà mỗi nút là một phần tử số nguyên:

struct Node
{
	int Info;
	Node* Next;
};

Đầu tiên ta khai báo cấu trúc Node bao gồm 2 thành phần:

• Biến chứa dữ liệu
• Con trỏ chứa dữ liệu nút kế tiếp.

Tiếp theo ta định nghĩa một kiểu dữ liệu con trỏ tới nút có tên là listnode.

Đối với danh sách liên kết có kiểu dữ liệu phức tạp hơn, ta khái báo cấu trúc của phần tử này trước (xstruct), sau đó đưa kiểu cấu trúc đó vào kiểu phần tử trong cấu trúc node.

struct Node
{
	Data Info;
	Node* Next;
};

Các thao tác cơ bản trên danh sách liên kết

1.Tạo và cấp phát bộ nhớ cho một nút

Node* GetNode(int x)
{
	Node *p = new Node;

	p->Info = x;
	p->Next = NULL;

	return p;
}

2. Chèn 1 nút vào đầu danh sách liên kết

• Tạo và cấp phát bộ nhớ cho nút mới
• Sau khi gán giá trị thích hợp cho phần tử của nút mới, cho con trỏ của nút mới trỏ đến nút đầu tiên của danh sách.
• Cuối cùng, để p vẫn trỏ đến nút đầu danh sách, ta cần cho p trỏ đến nút mới tạo.

Chú ý: Cần phải làm đúng trình tự, nếu không sẽ dẫn đến mất dữ liệu. Chẳng hạn, nếu ta cho con trỏ p trỏ đến nút mới tạo trước, thì khi đó nút mới tạo sẽ không trỏ được tới đầu danh sách liên kết cũ, vì không còn biến nào lưu trữ vị trí này.

Ta tạo ra cấu trúc của 1 List như sau, việc này sẽ dễ dàng hơn cho các thao tác.

struct List
{
	Node* Head;
	Node* Tail;

	List(){}
	List(Node* Head, Node* Tail)
	{
		this->Head = Head;
		this->Tail = Tail;
	}
};

void InsertHead(List &list, Node* node)
{
	if (!list.Head) //xét danh sách rỗng
		list.Head = list.Tail = node;
	else
	{
		node->Next = list.Head; //sửa lk node cần thêm
		list.Head = node; //chỉnh lại con trỏ của danh sách
	}
}

3. Chèn một nút vào cuối danh sách

• Tạo và cấp phát bộ nhớ cho 1 nút mới
• Dịch chuyển con trỏ đến cuối danh sách
• Cho con trỏ của nút cuối trỏ đến nút vừa tạo, và con trỏ nút vừa tạo trỏ đến null.

void InsertTail(List &list, Node* node)
{
	if (!list.Head)
		list.Head = list.Tail = node;
	else
	{
		list.Tail->Next = node;
		list.Tail = node;
	}
}

Trên đây là định nghĩa về danh sách liên kết và một số thao tác cơ bản, còn rất nhiều thao tác trên danh sách liên kết sẽ được gửi đến các bạn trong các bài viết tiếp theo. Chúc các bạn thành công!