Single Linked List C++ (Danh sách liên kết đơn).

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

Danh sách đơn liên kết (Danh sách liên kết đơn) là một dữ liệu cấu trúc, nó là một danh sách mà mỗi phần tử đều liên kết với phần tử đúng sau nó trong danh sách. Mỗi phần tử (được gọi là một nút hoặc nút) trong đơn liên kết danh sách là một cấu trúc có hai thành phần:

Thành phần dữ liệu: lưu thông tin về phần tử thân máy đó.
Liên kết thành phần: lưu trữ phần tử địa chỉ sau trong danh sách, nếu phần tử đó là phần tử cuối cùng thì phần tử này thành phần bằng NULL.

Tham khảo thêm: việc làm lập trình viên c++ lương cao tại Topdev

Minh họa danh sách liên kết

Đặc điểm của đơn liên kết danh sách

Do danh sách liên kết là một dữ liệu cấu trúc, được tạo nên nhờ công việc phát hiện nên nó có một số đặc điểm sau đây:

Được cấp bộ nhớ khi chạy chương trình
Có thể thay đổi kích thước bổ sung, xóa phần tử
Tối đa kích thước phụ thuộc vào khả năng nhớ của RAM
Các phần tử được lưu trữ ngẫu nhiên (không liên tiếp) trong RAM

Và do tính chất liên kết của phần đầu và phần tử đứng sau nó trong đơn liên kết danh sách, không có các đặc điểm sau:

Chỉ cần nhận được phần đầu và phần tử cuối cùng là có thể quản lý danh sách
Truy cập vào phần tử ngẫu nhiên phải duyệt từ vị trí đầu tiên
Chỉ có thể tìm kiếm một phần tử tính tuyến tuyến

1001 Tips: Con trỏ và hàm (Con trỏ & Hàm) trong C++

Code game săn bắn trên console bằng C++

Cài đặt menu liên kết danh sách

Trước khi cài đặt danh sách liên kết đơn, hãy chắc chắn rằng bạn đã nắm chắc phần con trỏ và cấp độ phát hiện trong C++. Do danh sách liên kết là một cấu trúc dữ liệu, nếu bạn không nắm bắt được con trỏ và cấp độ phát hiện sẽ rất khó để bạn hiểu được bài viết này. Nếu bạn cảm thấy chưa tự tin, hãy dành ít thời gian để xem bài viết này của mình. Còn bây giờ thì bắt đầu thôi!

Tạo nút

Danh sách đơn liên kết được tạo thành từ nhiều nút, do đó, chúng ta sẽ cùng đi từ nút trước. Một nút bao gồm hai thành phần là dữ liệu thành phần và liên kết thành phần. Thành phần dữ liệu có thể có sẵn kiểu dữ liệu hoặc bạn tự định nghĩa (struct hay class…), trong bài viết này để đơn giản mình sẽ sử dụng kiểu int cho phần dữ liệu. Thành phần liên kết là địa chỉ đương nhiên sẽ là con trỏ, con trỏ này đến nút tiếp theo, do đó, con trỏ này là con trỏ vào một nút.

struct Node
{
	int data;
	Node* next;
};

Để tạo một nút mới, hãy thực hiện phát hiện cấp độ cho nút mới, khởi động ban đầu giá trị và trả về địa chỉ của nút mới được phát hiện.

Node* CreateNode(int init_data)
{
	Node* node = new Node;
	node->data = init_data;
	node->next = NULL;      // node vừa tạo chưa thêm vào danh sách nên chưa liên kết với phần tử nào cả nên phần liên kết gán bằng NULL
	return node;
}

Xem tiếp…

Tạo menu liên kết danh sách

Ta đã được tạo thành công nên danh sách liên kết đơn là nút, tiếp theo chúng ta cần quản lý chúng bằng cách biết được phần tử đầu và cuối. Vì mỗi phần tử đều liên kết với kế hoạch phần tử nên cần phải mô tả cụ thể đầu và cuối phần tử tử có thể quản lý danh sách này. Vì vậy, ta đơn giản cần tạo một cấu trúc lưu trữ địa chỉ phần tử đầu (head) và phần tử cuối cùng (hay phần tử đuôi đuôi).

struct LinkedList
{
	Node* head;
	Node* tail;
};

Khi mới tạo danh sách, danh sách sẽ không có phần tử nào, head và tail không trỏ vào đâu cả, ta sẽ phân bổ chúng bằng NULL. Xây dựng chức năng tạo danh sách như sau:

void CreateList(LinkedList& l)
{
	l.head = NULL;
	l.tail = NULL;
}

Bây giờ để tạo một danh sách, ta làm như sau:

LinkedList list;
CreateList(list); // Gán head và tail bằng NULL

Add phần tử vào danh sách

Add to the first

Để thêm nút vào đầu danh sách, ta đầu tiên cần tìm kiếm danh sách trống hoặc không, nếu danh sách trống, ta chỉ cần gán phần đầu và đuôi của danh sách bằng nút đó. Ngược lại, nếu danh sách không trống, hãy thực hiện con trỏ liên kết thành phần vào đầu, sau đó gán lại đầu bằng nút mới.

void AddHead(LinkedList& l, Node* node)
{
	if (l.head == NULL)
	{
		l.head = node;
		l.tail = node;
	}
	else
	{
		node->next = l.head;
		l.head = node;
	}
}

Xem tiếp…

Add Elements vào menu liên kết đầu danh sách

Như trong hình trên, chúng tôi thêm nút có dữ liệu bằng 0 vào danh sách. Ta thực thi con trỏ tiếp theo của nút đó vào phần đầu của danh sách (chính là nút đầu tiên của danh sách có dữ liệu bằng 1), sau đó ta đưa đầu con trỏ vào nút có dữ liệu 0 vừa được thêm vào. Sau đó, phần tử đó đã nằm ở đầu danh sách.

Add to the end

Tương tự, để thêm nút vào danh sách cuối cùng, kiểm tra đầu tiên xem danh sách trống hay không, trống thì phân bổ đầu và đuôi đều bằng nút mới. Nếu không trống, hãy thực hiện đuôi con trỏ->tiếp theo vào mới nút, sau đó phân bổ lại đuôi bằng nút mới (vì bây giờ nút mới thêm chính là đuôi).

void AddTail(LinkedList& l, Node* node)
{
	if (l.head == NULL)
	{
		l.head = node;
		l.tail = node;
	}
	else
	{
		l.tail->next = node;
		l.tail = node;
	}
}

Xem tiếp…

Add element element vào menu liên kết cuối cùng của danh sách

Trong hình trên, chúng tôi thực hiện thêm nút có dữ liệu bằng 6 vào danh sách. Hiện tại đuôi là nút có dữ liệu 5, thực hiện phân bổ đuôi->tiếp theo bằng nút mới để kết nối thêm nó vào đuôi danh sách, lúc này nút mới trở thành danh sách thành phần tử cuối cùng nên ta phân bổ lại đuôi bằng mới nút.

Thêm vào sau nút bất kỳ

Để thêm một nút p vào sau nút q bất kỳ lúc nào, đầu tiên ta cần tìm kiếm nút xem q có NULL hay không, nếu nút q là NULL nội dung là danh sách trống thì ta sẽ thêm vào danh sách đầu tiên. Nếu nút q không NULL, nội dung tồn tại trong danh sách, ta thực hiện con trỏ p->next = q->next, sau đó q->next = p. Tiếp theo chúng ta kiểm tra xem nút q trước đó phải là nút cuối hay không, nếu nút q là nút cuối thì thêm p vào, p sẽ thành nút cuối nên ta gán lại tail = p.

void InsertAfterQ(LinkedList& l, Node* p, Node* q)
{
	if (q != NULL)
	{
		p->next = q->next;
		q->next = p;
		if (l.tail == q)
			l.tail = p;
	}
	else
		AddHead(l, p);
}

Xem tiếp…

Thêm phần tử vào sau nút Q trong đơn liên kết danh sách

Trong hình trên, ta thêm nút có dữ liệu bằng 4 (nút p) vào sau nút có dữ liệu bằng 3 (nút q). Ta con trỏ tiếp theo của nút p vào nút tiếp theo của nút q tức là nút có dữ liệu bằng 5, sau đó con trỏ tiếp theo của nút q vào nút p vậy là nút p đã được thêm vào danh sách.

Xóa phần tử khỏi danh sách

Xóa ở đầu

Để xóa phần tử ở đầu danh sách, ta kiểm tra xem danh sách có trống hay không, nếu trống, ta không cần xóa, trả về kết quả là 0. Nếu danh sách không trống, ta thực hiện lưu lại đầu nút, sau đó chỉ định đầu nút tiếp theo của đầu nút, sau đó xóa đầu nút đi. Tiếp theo ta cần kiểm tra xem danh sách vừa bị xóa đi nút đầu có trống hay không, nếu trống ta phân bổ lại đuôi bằng NULL thì luôn trả về kết quả 1.

int RemoveHead(LinkedList& l, int& x)
{
	if (l.head != NULL)
	{
		Node* node = l.head;
		x = node->data;      // Lưu giá trị của node head lại
		l.head = node->next;
		delete node;         // Hủy node head đi
		if (l.head == NULL)
			l.tail = NULL;
		return 1;
	}
	return 0;
}

Xem tiếp…

Lưu ý trước khi xóa phần đầu nút, ta sử dụng biến tham chiếu x để lưu lại giá trị của nút bị hủy bỏ để sử dụng.

Xóa đơn liên kết đầu danh sách phần tử

Trong hình trên, mình thực hiện xóa nút đầu tiên có dữ liệu bằng 0. Mình trỏ đầu đến nút tiếp theo của nút 0 (hiện đang là đầu), thì đầu lúc này sẽ là nút 1, sau đó mình ade đi nút 0 được.

Xóa ở sau nút bất kỳ

Để xóa một nút p sau nút q bất kỳ, ta kiểm tra xem nút q có NULL hay không, nếu nút q NULL thì không tồn tại trong danh sách, do đó trả về 0, không xóa. Nếu nút q khác NULL nhưng tiếp theo của q là NULL, tức là p bằng NULL thì không xóa, trả về 0 (do sau q không có nút nào cả, q là tail). Nếu nút p tồn tại, ta thực hiện kiểm tra xem nút p có phải là đuôi hay không, nếu nút p là đuôi thì gán lại đuôi là q, tức là nút trước đó để xóa nút p đi.

int RemoveAfterQ(LinkedList& l, Node* q, int& x)
{
	if (q != NULL)
	{
		Node* p = q->next;
		if (p != NULL)
		{
			if (l.tail == p)
				l.tail = q;
			q->next = p->next;
			x = p->data;
			delete p;
			return 1;
		}
		return 0;
	}
	return 0;
}

Xem tiếp…

Trong hình trên, ta thực hiện xóa nút có dữ liệu 3 (nút p) sau nút có dữ liệu 2 (nút q). Ta trỏ nút tiếp theo của nút q vào nút tiếp theo của p tức là nút có dữ liệu 4, sau đó xóa nút p đi là xong.

Duyệt danh sách và trong

Sau khi có các thao tác bổ sung, hãy xóa, chúng tôi có thể ra danh sách để kiểm tra xem hoạt động có đúng hay không. Để trong danh sách, hãy duyệt từ đầu đến cuối danh sách và ra trong lúc duyệt. Ta chỉ định một nút bằng đầu, sau đó kiểm tra xem nút đó có NULL hay không, không thì ra dữ liệu của nút đó, sau đó chỉ định nút tiếp theo đó bằng nút tiếp theo của nút chính hiện tại bây giờ là nút tiếp theo, cứ như vậy cho đến hết.

void PrintList(LinkedList l)
{
	if (l.head != NULL)
	{
		Node* node = l.head;
		while (node != NULL)
		{
			cout << node->data << ' ';
			node = node->next; // Chuyển sang node tiếp theo
		}
	}
}

Xem tiếp…

Nhận nút giá trị bất kỳ lúc nào

Để lấy phần tử giá trị trong danh sách, hãy thực hiện trình duyệt tương tự như khi trong phần tử. Ta sẽ tạo một biến đếm để biết hiện tại vị trí, duyệt qua các nút để đến khi nút bằng NULL hoặc biến số bằng nút vị trí cần lấy. Kiểm tra xem nếu nút khác NULL và vị trí đếm biến cần lấy, ta sẽ trả về địa chỉ của nút đó, ngược lại trả về NULL (danh sách trống hoặc vị trí cần lấy nằm ngoài phạm vi của danh sách).

Node* GetNode(LinkedList& l, int index)
{
	Node* node = l.head;
	int i = 0;
	while (node != NULL && i != index)
	{
		node = node->next;
		i++;
	}
	if (i == index && node != NULL)
		return node;
	return NULL;
}

Xem tiếp…

Search phần tử trong danh sách

Ý tưởng tìm kiếm phần tử cũng là trình duyệt danh sách, nếu chưa tìm thấy thì hãy tiếp tục duyệt. Sau khi kết thúc trình duyệt, ta chỉ cần kiểm tra xem nút trình duyệt có bằng NULL hay không, nếu không tìm thấy tức thời, ta sẽ trả về địa chỉ của nút đó.

Node* Search(LinkedList l, int x)
{
	Node* node = l.head;
	while (node != NULL && node->data != x)
		node = node->next;
	if (node != NULL)
		return node;
	return NULL;
}

Xem tiếp…

Đếm số phần tử của danh sách

Đếm số phần tử cũng tương tự, ta áp dụng trình duyệt từ nút đếm đầu và cuối.

int Length(LinkedList l)
{
	int count = 0;
	Node* node = l.head;
	while (node != NULL)
	{
		count++;
		node = node->next;
	}
	return count;
}

Xem tiếp…

Remove list

Để xóa danh sách, ta cần hủy bỏ tất cả các nút tức thời là trình duyệt và hủy bỏ từng nút. Ở đây mình sẽ sử dụng lại hàm RemoveHead. Đầu tiên, ta chỉ định một nút bằng phần đầu, kiểm tra nếu nút khác NULL thì gọi RemoveHead và phân bổ lại nút bằng phần đầu tiếp theo, cứ lặp như vậy cho đến khi nút đó NULL thì thôi. Sau khi xóa tất cả các phần tử thì phân bổ lại đuôi bằng NULL.

void DestroyList(LinkedList& l)
{
	int x;
	Node* node = l.head;
	while (node != NULL)
	{
		RemoveHead(l, x);
		node = l.head;
	}
	l.tail = NULL;
}

Xem tiếp…

Tổng kết

Vì vậy, trong bài viết này, tôi đã giới thiệu cho các bạn về danh sách liên kết đơn và một số thao tác cơ bản trên danh sách. Các bạn không nhất thiết phải làm theo cách của mình, có rất nhiều cách để thực hiện khác nhau, chỉ cần bạn nắm vững về con trỏ và cấp độ phát hiện trong C++. Nếu thấy hay đừng quên chia sẻ cho bạn nhé. Cảm ơn các bạn đã theo dõi bài viết!

Mã nguồn

LinkedList.hpp

#ifndef LinkedList_hpp
#define LinkedList_hpp

struct Node
{
	int data;
	Node* next;
};

struct LinkedList
{
	Node* head;
	Node* tail;
};

Node* CreateNode(int init_data);
void CreateList(LinkedList& l);
void AddHead(LinkedList& l, Node* node);
void AddTail(LinkedList& l, Node* node);
void InsertAfterQ(LinkedList& l, Node* p, Node* q);
int RemoveHead(LinkedList& l, int& x);
int RemoveTail(LinkedList& l, int& x);
int RemoveAfterQ(LinkedList& l, Node* q, int& x);
Node* GetNode(LinkedList l, int index);
void PrintList(LinkedList l);
Node* Search(LinkedList l, int x);
int Length(LinkedList l);
void DestroyList(LinkedList& l);

#endif

Xem tiếp…LinkedList.cpp

#include <iostream>
#include "LinkedList.hpp"
using namespace std;

Node* CreateNode(int init_data)
{
	Node* node = new Node;
	node->data = init_data;
	node->next = NULL;
	return node;
}

void CreateList(LinkedList& l)
{
	l.head = NULL;
	l.tail = NULL;
}

void AddHead(LinkedList& l, Node* node)
{
	if (l.head == NULL)
	{
		l.head = node;
		l.tail = node;
	}
	else
	{
		node->next = l.head;
		l.head = node;
	}
}

void AddTail(LinkedList& l, Node* node)
{
	if (l.head == NULL)
	{
		l.head = node;
		l.tail = node;
	}
	else
	{
		l.tail->next = node;
		l.tail = node;
	}
}

void InsertAfterQ(LinkedList& l, Node* p, Node* q)
{
	if (q != NULL)
	{
		p->next = q->next;
		q->next = p->next;
		if (l.tail == q)
			l.tail = p;
	}
	else
		AddHead(l, p);
}

int RemoveHead(LinkedList& l, int& x)
{
	if (l.head != NULL)
	{
		Node* node = l.head;
		x = node->data;
		l.head = node->next;
		delete node;
		if (l.head == NULL)
			l.tail = NULL;
		return 1;
	}
	return 0;
}

int RemoveAfterQ(LinkedList& l, Node* q, int& x)
{
	if (q != NULL)
	{
		Node* p = q->next;
		if (p != NULL)
		{
			if (l.tail == p)
				l.tail = q;
			q->next = p->next;
			x = p->data;
			delete p;
			return 1;
		}
		return 0;
	}
	return 0;
}

Node* GetNode(LinkedList l, int index)
{
	Node* node = l.head;
	int i = 0;
	while (node != NULL && i != index)
	{
		node = node->next;
		i++;
	}
	if (i == index && node != NULL)
		return node;
	return NULL;
}

void PrintList(LinkedList l)
{
	if (l.head != NULL)
	{
		Node* node = l.head;
		while (node != NULL)
		{
			cout << node->data << ' ';
			node = node->next;
		}
	}
}

Node* Search(LinkedList l, int x)
{
	Node* node = l.head;
	while (node != NULL && node->data != x)
		node = node->next;
	if (node != NULL)
		return node;
	return NULL;
}

int Length(LinkedList l)
{
	int count = 0;
	Node* node = l.head;
	while (node != NULL)
	{
		count++;
		node = node->next;
	}
	return count;
}

void DestroyList(LinkedList& l)
{
	int x;
	Node* node = l.head;
	while (node != NULL)
	{
		RemoveHead(l, x);
		node = l.head;
	}
	l.tail = NULL;
}

Xem tiếp…chính.cpp

#include <iostream>
#include "LinkedList.hpp"
using namespace std;

int main()
{

Mr4 Java Developer

Đi lên từ nền tảng vững chắc!

Single Linked List C++ (Danh sách liên kết đơn).

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

Đặc điểm của đơn liên kết danh sách

Cài đặt menu liên kết danh sách

Tạo nút

Tạo menu liên kết danh sách

Add phần tử vào danh sách

Add to the first

Add to the end

Thêm vào sau nút bất kỳ

Xóa phần tử khỏi danh sách

Xóa ở đầu

Xóa ở sau nút bất kỳ

Duyệt danh sách và trong

Nhận nút giá trị bất kỳ lúc nào

Search phần tử trong danh sách

Đếm số phần tử của danh sách

Remove list

Tổng kết

Mã nguồn

Hãy bình luận đầu tiên

Để lại một phản hồi Hủy