Cách cài đặt danh sách liên kết đơn trong c++

Bài viết hôm này mình sẽ hướng dẫn các bạn cách cài đặt danh sách liên kết đơn sử dụng code c++.

Danh sách liên kết đơn là gì ? Danh sách liên kết đơn là một cấu trúc dữ liệu thường dùng trong các ngôn ngữ lập trình.

Các bạn có thể xem hình dưới đây biểu diễn cho một danh sách liên kết đơn

Ở mỗi khối trên ta gọi là một nút ( node ), mỗi node sẽ chứa data để lưu trữ dữ liệu và một thuộc tính next dùng để tham chiếu tới phần tử tiếp theo. Đặc biệt sẽ không có khối nào tham chiếu đến node đầu ( gọi là head ), và node cuối cùng sẽ tham chiếu đến vùng NULL.

Các hoạt động cơ bản

Một danh sách liên kết ( link list ) sẽ có các thuộc tính cơ bản sau:

• Hoạt động isEmpty(): Kiểm tra có rỗng hay không.
• Hoạt động length(): Đếm số lượng node của link list.
• Hoạt động insertFirst(): Chèn phần tử vào đầu link list.
• Hoạt động deleteFirst(): Xóa phần tử đầu tiên của link list.
• Hoạt động insert(int position, type Item): Chèn một node vào vị trí position.
• Hoạt động Delete(int position): Xóa node tại vị trí position.
• Hoạt động show(): Hiển thị tất cả dữ liệu trong link list.

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

Một danh sách liên kết đơn giản sẽ gồm hai thuộc tính:

• Data dùng để chứa dữ liệu.
• Next là con trỏ tham chiếu đến phần tử sau nó.

typedef int type;
typedef struct Node
{
	type data;
	Node *next;
} node;

Tạo một node head ( Tức là node đầu ) với giá trị NULL.

node *head = NULL; //Đầu link

Cài đặt hoạt động isEmpty()

bool isEmpty() {
	if (head == NULL)
		return true;
	return false;
}

Cài đặt hoạt động show()

void show() {
	node *ptr = head;
	cout << "Du lieu trong Linked la:" << endl;
	while (ptr != NULL)
	{
		cout << ptr->data << " ";
		ptr = ptr->next;
	}
	cout << endl;
}

Ở đây mình dùng một con trỏ ptr để duyệt các node trong link list.

Cài đặt hoạt động length()

int length() {
	int count = 0;
	node *temp = head;
	while (temp != NULL) {
		count++;
		temp = temp->next;
	}
	return count;
}

Hoạt động length() sẽ trả về một giá trị kiểu int là kích thước của link list.

Cài đặt hoạt động insertFirst()

Đầu tiên ta sẽ tạo một node để chứa data, sau đó ta sẽ cho next tham chiếu đến head. Sau khi chèn xong thì ta cũng phải thay đổi con trỏ head, giờ đây nó sẽ trỏ đến node vừa chèn.

void insertFirst(type Item) {
	node *link = new Node;
	link->data = Item;
	link->next = head;
	head = link;
}

Cài đặt hoạt động deleteFirst()

Ta đơn giản chỉ tham chiếu head đến node thứ hai mà thôi.

node* deleteFirst() {
	node *temp = head;
	head = head->next;
	return temp;
}

Hoạt động này sẽ trả về node vừa xóa.

Cài đặt hoạt động insert()

Đầu tiên ta cần duyệt đến phần tử position - 1 sau đó tiến hành tham chiếu next phần tử node cần chèn. Phần tử vừa chèn cũng tham chiếu đến phần tử node position.

void insert(int position, type Item) {
	int size = length();
	/*Cho link bắt đầu từ vị trí 1,2...*/
	if (position > size || position < 1)
		cout << "Vi tri khong hop le";
	else if (position == 1)
		insertFirst(Item);
	else {
		node *insertItem = new Node;
		node *temp;
		int count = 1;
		temp = head;
		/*Vì ta xem head có vị trí là 1 nên bắt đầu duyệt count = 1*/
		while (count != position - 1) {
			count++;
			temp = temp->next;
		}
		insertItem->data = Item;
		insertItem->next = temp->next;
		temp->next = insertItem;
	}
}

Cài đặt hoạt động Delete()

Ta sẽ duyệt đến phần tử thứ position - 1 , sau đó lấy con trỏ next tham chiếu đến phần tử thứ position + 1.

void Delete(int position) {
	int size = length();
	if (position < 0 || position > size)
		cout << "Vi tri khong hop le";
	else if (position == 1)
		deleteFirst();
	else {
		int count = 1;
		node *temp, *p;
		temp = head;
		while (count != position - 1) {
			count++;
			temp = temp->next;
		}
		p = temp->next;
		p = p->next;
		temp->next = p;
	}
}

Chạy thử link list

Ở phần dưới mình chỉ copy lại các đoạn code trong hàm main mà thôi. Các bạn có thể xem full code tại đây.

int main() {
	insertFirst(5);
	insertFirst(6);
	insertFirst(7);
	insert(1, 12);
	insert(4, 17);
	show();
	Delete(5);
	Delete(4);
	show();
}

Du lieu trong Linked la:
12 7 6 17 5
Du lieu trong Linked la:
12 7 6

Bài viết mình đến đây là kết thúc. Cám ơn các bạn đã theo dõi !