Nội dung bài viết
Đăng ký học lập trình C++
Tại STDIO bạn được dạy nền tảng lập trình tốt nhất.
Đăng ký học
Cơ bản về danh sách liên kết trong C/C++, bao gồm mô tả, giải thuật và code mẫu. Danh sách liên kết là 1 cấu trúc dữ liệu cơ bản, được sử dụng để khắc phục hạn chế của mảng (cố định về kích thước). C++ nói chung và cụ thể là thư viện STL đã cung cấp sẵn một kiểu dữ liệu List. Tuy nhiên tôi vẫn muốn chia sẻ bài viết này để nêu rõ về bản chất của danh sách liên kết và một số thao tác cơ bản trên nó.

Giới thiệu

Danh sách liên kết là 1 cấu trúc dữ liệu cơ bản, được sử dụng để khắc phục hạn chế của mảng (cố định về kích thước). C++ nói chung và cụ thể là thư viện STL đã cung cấp sẵn một kiểu dữ liệu List. Tuy nhiên tôi vẫn muốn chia sẻ bài viết này để nêu rõ về bản chất của danh sách liên kết và một số thao tác cơ bản trên nó.

Tiền đề bài viết

Trong quá trình nghiên cứu tôi nhận thấy danh sách liên kết đơn là một cấu trúc dữ liệu khá thú vị,  và nhờ nó tôi hình dung rõ hơn về chức năng lưu trữ địa chỉ của con trỏ. Do đó, tôi muốn chia sẻ với mọi người một số kiến thức cơ bản về danh sách liên kết (linked-list).

Đối tượng hướng đến

Bài viết dành cho các bạn lập trình viên đã có kiến thức cơ bản về struct và pointer trong ngôn ngữ C++, có nhu cầu tìm hiểu về cấu trúc dữ liệu danh sách liên kết (linked list).

Toàn bộ code trong các ví dụ minh họa bên dưới được tôi thực hiện với Visual Studio Propressional 2013 trên môi trường Windows 8.1.

Tổ chức danh sách liên kết đơn

Cũng giống như mảng, danh sách liên kết cũng bao gồm các phần tử, có mối liên hệ với nhau. Tôi gọi mỗi phần tử đó là một Node. Node được xem là trái tim của danh sách liên kết, mỗi Node sẽ lưu trữ 2 thông tin:

  • Thông tin dữ liệu: Lưu trữ các thông tìn về chính Node đó.
  • Thông tin liên kết: Lưu trữ địa chỉ của phần tử kế tiếp trong danh sách, hoặc lưu trữ giá trị NULL nếu phần tử đó nằm cuối danh sách. 

ss_1

Một cách tổng quát ta có:

struct SNode
{
	Data Info;
	SNode* pNext;
};

Mỗi phần tử trong trong danh sách liên kết đơn là một biến động sẽ được yêu cầu cấp phát khi cần thiết, danh sách liên kết đơn chính là sự liên kết các biến này với nhau do đó ta hoàn toàn chủ động về số lượng các phần tử.

Để đơn giản, trong bài viết này tôi sẽ lấy ví dụ danh sách liên kết đơn lưu trữ các số nguyên.

Node của danh sách liên kết sẽ được định nghĩa như sau:

struct SNode
{
	int Data;
	SNode* pNext;
};

Tôi sử dụng một phương thức GetNode để cấp phát động một Node khi cần thiết:

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

	p->Data = x;
	p->pNext = NULL;

	return p;
}

Bây giờ chúng ta bắt đầu tìm hiểu một số phương thức đơn giản tạo nên sự liên kết các Node để tạo ra một danh sách liên kết đơn hoàn chỉnh.

Một số thao tác cơ bản trên danh sách liên kết đơn

Trong danh sách liên kết đơn, các Node sẽ không được lưu liên tiếp nhau trên bộ nhớ, Node trước sẽ mang thông tin địa chỉ của Node sau, như vậy nếu bạn xử lý lỗi một Node sẽ dẫn đến tính huống xấu nhất, ta sẽ mất toàn bộ thông tin của các Node phía sau.

Chúng ta sẽ bắt đầu làm việc với các thao tác cơ bản trên một danh sách liên kết đơn. Giả sử tôi có định nghĩa sau:

struct SNode
{
	int Data;
	SNode* pNext;
};

struct SList
{
	SNode* pHead;
	SNode* pTail;

	SList(){}
	SList(SNode* Head, SNode* Tail)
	{
		this->pHead = Head;
		this->pTail = Tail;
	}
};

Nếu biết được địa chỉ đầu tiên trong danh sách liên kết ta có thể dựa vào thông tin pNext để truy xuất đến các phần tử còn lại, do đó ta sẽ dùng một con trỏ pHead để lưu lại địa chỉ Node đầu tiên của danh sách. Trong một số trường hợp ta cũng cần thao tác trên phần tử cuối cùng của danh sách, nên tôi dùng thêm một con trỏ pTail để lưu trữ địa chỉ của Node cuối cùng trong danh sách.

Chèn vào đầu danh sách

Như đã trình bày ở trên, khi thao tác với mỗi Node trên danh sách liên kết ta cần thực hiện cẩn thận, đúng thứ tự để tránh mất thông tin của các Node phía sau. Dưới đây là thứ tự các bước chèn một phần tử vào đầu mảng.

Bước 1: cấp phát một Node mới (new_element).

Bước 2: gán pNext của Node mới trỏ đến Node đầu (cũ).

new_element->pNext = pHead;

Bước 3: cập nhập lại giá trị pHead

pHead = new_element;

Lưu đồ bên dưới thể hiện từng bước để thêm vào một Node mới ở đầu danh sách

ss_2

Chèn vào cuối danh sách

Tương tự với thao tác chèn vào đầu danh sách, chèn vào cuối danh sách chúng ta chỉ cần cập nhập lại con trỏ pTail.

Bước 1: cấp phát một Node mới (new_element).

Bước 2: gán lại pNext của Node cuối cùng (cũ) sẽ trỏ đến Node mới. 

pTail->pNext = new_element;

Bước 3: cập nhập lại giá trị pTail, bây giờ Node cuối của danh sách là Node chúng ta vừa thêm.

pTail = new_element;

Đây là lưu đồ thứ tự thực hiên các bước ở trên

ss_3

Chèn vào danh sách sau một phần tử q

Chèn vào danh sách sau một phần tử q nào đó, chèn vào giữa danh sách không cần cập nhập lại hai con trỏ pHead pTail tuy nhiên chúng ta cần hết sức cần thận để tránh mất dữ liệu phía sau.

Bước 1: cấp phát một Node mới - new_element.

Bước 2: gán pNext của Node mới bằng địa chỉ của Node sau q.

new_element ->pNext = q-> pNext;

Bước 3: cập nhập lại pNext của Node q trỏ đến Node mới.

q-> pNext = new_element;

ss_4

Xóa một phần tử đầu danh sách

Xóa 1 phần tử ở đầu danh sách không chỉ đơn giản là cập nhập lại biến con trỏ pHead, mà ta phải giải phóng được vùng nhớ của Node cần xóa.

Bước 1: Khai báo một con trỏ p để lưu lại địa chỉ của Node đầu tiên.

SNode* p = pHead;

Bước 2: cập nhập lại giá trị của pHead.

pHead = pHead->pNext;

Bước 3: giải phóng vùng nhớ của Node cần xóa.

delete p;

ss_5

Xóa một phần tử đứng sau phần tử q

Tương tự như thao tác xóa phần tử đầu danh sách, để xóa một phần tử đứng sau phần tử q, ta thực hiện các bước sau:

Bước 1: Khai báo một con trỏ p để lưu lại địa chỉ của Node đầu tiên.

SNode* p = q->pNext;

Bước 2: cập nhập lại giá trị pNext của Node q.

q->pNext = p->pNext;

Bước 3: giải phóng vùng nhớ của Node cần xóa.

delete p;

ss_6

Duyệt danh sách

Khi có được giá trị của pHead ta có thể dựa và thông tin pNext để duyệt lần lượt các phần tử của danh sách.

SNode* p;

p = list.pHead;
while (p != NULL)
{
	// Process Node
	p = p->pNext;
}

Lời kết

Source code được viết theo hướng cấu trúc để các bạn chưa có khái niệm về hướng đối tượng có thể tiếp cận một cách dễ dàng.

Có thể thấy được, danh sách liên kết đã khắc phục được nhược điểm của mảng - đó là kích thước cố định.Với bài viết này, hy vọng các bạn đã có cái nhìn tổng quát hơn về danh sách liên kết và các thao tác liên quan như: thêm phần tử, xóa phần tử ... và có thể ứng dụng được vào các dự án của mình.

THẢO LUẬN