Bạn Hiểu Gì Về Danh Sách Liên Kết Đơn Trong C++

Posted on by mtoplistChuyên mục:Top List

Bạn đã biết gì về danh sách liên kết đơn trong C++? Nó có gì giống và khác với mảng? Hãy cùng tìm hiểu trong bài viết này nhé!

1. Danh sách liên kết đơn là gì?

Về cơ bản, danh sách liên kết đơn (Singly linked list) có chức năng giống với mảng (array) như thêm, xóa phần tử,…Tuy nhiên danh sách liên kết là một cấu trúc dữ liệu đệ quy. Một danh sách liên kết sẽ bao gồm các “node”. Mỗi “node” gồm 2 thành phần là dữ liệu (data) và con trỏ để trỏ tới “node” tiếp theo nhằm tạo mối liên kết. Nếu số lượng mối liên kết của mỗi “node” là một thì danh sách trên được gọi là danh dách liên kết đơn.

2. Danh sách liên kết đơn và mảng

Một số ưu điểm của danh sách liên đơn so với mảng:

  • Sử dụng được tối ưu bộ nhớ

Thử tưởng tượng bạn là một nhân viên bán vé xe. Xe của bạn hiện đang còn trống các chỗ như hình minh họa. Giả sử có 1 gia đình 16 người đến đặt vé và yêu cầu đặt ra là vị trí ngồi của họ phải liên tiếp nhau. Sẽ chẳng có cách nào cho bạn đế đáp ứng yêu cầu đó mặc dù số lượng chỗ trống của bạn là đủ bởi yêu cầu các vị trí phải liên tiếp nhau. Lúc này nếu không tìm được khách hàng thích hợp thì chuyến xe của bạn vẫn sẽ khởi hành và lãng phí 16 ghế trống đó. Nhưng nếu như đó là 16 vị khách ngẫu nhiên và không phải ràng buộc bởi điều kiện vị trí ngồi liên tiếp nhau thì bạn có thể dễ dàng bố trí các hành khách này vào các vị trí trống để lấp đầy xe.

Yêu cầu các vị trí liên tiếp nhau cũng chính là đặc điểm của mảng. Như vậy sau một thời gian thực hiện các thao tác xin cấp phát và giải phóng hiện trạng bộ nhớ của bạn có thể bị phân mảnh. Lúc này, nếu chương trình xin cấp phát một vùng nhớ có kích thước m bytes nhưng không có vùng nhớ liên tục nào có kích thước lớn hơn hoặc bằng m bytes(cho dù tổng vùng nhớ còn trống thì đủ) thì hệ thống cũng không thể cấp phát được. Danh sách liên kết đơn có thể giải quyết được vấn đề này bởi lẽ kích thước của một “node” thường khá nhỏ cộng với việc vùng nhớ của các “node” có thể nằm rải rác trong heap.

  • Thêm và xóa phần tử dễ dàng với chi phí hằng số

Thử nhớ lại để xóa một phần tử của mảng gồm n phần tử tại vi trí thứ i bạn phải làm gì? Bạn phải gán đè các giá trị từ j + 1 vào j (với j chạy từ i đến n – 1) sau đó giảm n xuống 1 đơn vị. Với mảng tĩnh thực chất việc xóa phần tử chỉ là việc bạn dồn các phần tử khác lên một đơn vị đè lên vị trí muốn xóa, phần tử cuối cùng vẫn tồn tại ở đó và chiếm dụng bộ nhớ.

Với mảng động, bạn có thể khắc phục được tình trạng phần tử cuối cùng vẫn tồn tại bằng cách xin cấp phát lại một vùng nhớ mới có kích thước của n – 1 phần tử, chuyển n – 1 phần tử ở vùng nhớ hiện tại sang vùng nhớ mới sau đó giải phóng vùng nhớ cũ. Tuy nhiên, với cả mảng động và mảng tĩnh chúng ta đều phải dời tất cả phần tử (kể từ vị trí cần xóa + 1) sang trái 1 đơn vị. Xét về khía cạnh độ phức tạp của giải thuật thì trong trường hợp này, thao tác gán đè có chi phí rất cao(chi phí tuyến tính) bởi chương trình phải chuyển dời một dãy phần tử. Với việc thêm một phần tử vào mảng chúng ta cũng phải thực hiện những bước tương tự như trên.

Với danh sách liên kết đơn việc thêm hay chèn này được thực hiện khá dễ dàng, đó chỉ đơn giản là bạn phải thay đổi các mối liên kết (giải phóng vùng nhớ với của phần tử bị xóa với việc xóa phần tử). Về cơ bản thì những thao tác này chỉ có chi phí hằng số. 

Vậy rốt cuộc danh sách liên kết đơn có nhược điểm nào không? Câu trả lời là có, bởi nếu không thì mảng đã không tồn tại. Chính những ưu điểm của mảng lại là nhược điểm của danh sách liên kết đơn:

  • Truy xuất tuần tự: với mảng bạn có thể truy xuất đến phần tử bất kì một cách dễ dàng bằng toán tử móc vuông ([ ]), với danh sách liên kết đơn thì không đơn giản như vậy, để đến được 1 phần tử trong danh sách liên kết đơn, bạn bắt buộc phải đi từ phần tử đầu tiên, lần theo các mối liên kết để đến được phần tử cần truy xuất. Chi phí để thực hiện công việc này là tuyến tính.
  • Thao tác phức tạp: Không giống với mảng, để xây dựng danh sách liên kết đơn bạn phải va chạm nhiều với con trỏ và công việc này đòi hỏi bạn phải có một sự cẩn trọng nhất định để những lỗi không mong muốn không xảy ra. 

3. Xây dựng và một số thao tác trên danh sách liên kết đơn:

Một “node” của danh sách liên kết đơn được xây dựng như sau (ở đây để đơn giản mình sẽ để data có kiểu dữ liệu int).

 typedef struct node* point; // typedef lại để code được rõ ràng và gọn gàng hơn
 struct node{
 	int data;
	point next; 
 };

Để thuận tiện cho việc xây dựng các hàm thêm và xóa  mình sẽ xây dựng hàm getNode, hàm này nhằm mục đích tạo ra 1 “node” có phần dữ liệu là x, giá trị hàm trả về là địa chỉ “node” đó.

point getNode(int x)
{
 	point p;
	p = (point)malloc(sizeof(node));
	if(p != NULL)
	{
		p->data = x;
		p->next = NULL;
	} 
	return p; 
}

Để quản lí danh sách liên kết đơn, người ta thường dùng 1 con trỏ trỏ vào “node” đầu tiên của danh sách (ở đây mình đặt tên là head), bên cạnh đó để tiện cho việc quản lí có thể dùng thêm 1 con trỏ trỏ vào “node” cuối cùng của danh sách (tail). Yêu cầu phải được đảm bảo là trong suốt quá trình thực hiện chương trình head luôn trỏ đến “node” đầu tiên, tail luôn trỏ tới “node” cuối cùng của danh sách. Nếu không đảm bảo được điều này, danh sách liên kết có thể dẫn đến những sự cố không mong muốn. Khi khai báo 

point head = NULL, tail = NULL;

cho ta biết rằng danh sách này là danh sách rỗng.

Thêm 1 phần tử vào đầu danh sách

void addFirst(point &head, point &tail, int x)
{
 	point r = getNode(x);
	if(head == NULL)
	  	head = tail = r;
	else
	{
		r->next = head;
		head = r; 
	} 	 
}

Thêm 1 phần tử vào cuối danh sách

void addLast(point &head,point &tail, int x)
{
 	point r = getNode(x);
	if(head == NULL)
	  	head = tail = r;
	else
	{
		tail->next = r;
		tail = r; 
	} 	 
}

Thêm 1 phần tử có giá trị x vào sau “node” p

void addAfter(point p, int x)
{
	point q = getNode(x);
	q->next = p->next; 
	p->next = q;
}

Xóa 1 phần tử ở đầu danh sách

void deleteFirst(point &head)
{
	if(head == tail)
	{
		free(head);
		head = tail = NULL; 
	}
	else
	{
		point temp = head->next; 
		free(head);
		head = temp; 
	}
}

Xóa 1 phần tử ở cuối danh sách

void deleteLast(point &head, point &tail)
{
	if(head == tail)
	{
		free(head);
		head = tail = NULL; 
	}
	else
	{
		point p = head;
		while(p->next != NULL)
			p = p->next;
		free(tail); 
		tail = p;
		p->next = NULL; 
	}
}

Hủy danh sách liên kết đơn

void delList(point &head)
{
	point temp = NULL;
	while(head)
	{
		temp = head;
		head = head->next;
		free(temp);	
	} 
}

4.Tạm kết

Trên đây là những trình bày sơ lược của mình về danh sách liên kết đơn. Hi vọng những chia sẻ của mình có thể đem đến cho các bạn một cái nhìn tổng quan về danh sách liên kết đơn. Chúc các bạn học tốt!

mtoplist