Các thao tác cơ bản trên danh sách liên kết đơn (Singly Linked List)

Đây là bài 12/18 bài của series môn học Cấu trúc dữ liệu và giải thuật

Có nhiều thao tác trên danh sách liên kết đơn như thêm node, hủy node, tìm kiếm node trong danh sách, sắp xếp danh sách,…

1. Định nghĩa danh sách liên kết đơn

Giả sử, chúng ta tạo một danh sách liên kết đơn lưu trữ một dãy số nguyên như sau:

struct node{
	 int info;
	 node *next;
};
struct sList{
	node *head;
 	node *tail;
};

2. Khởi tạo một danh sách liên kết đơn rỗng         

Xây dựng hàm createList() để gán các con trỏ headtail trỏ về NULL.

void createsList(sList &l){
	l.head = NULL;
	l.tail = NULL;
}

3. Tạo một node và gán giá trị cho node

Xây dựng hàm createNode() có tham số là giá trị của node muốn tạo. Hàm createNode() có kiểu trả về là con trỏ node.

node* createNode(int x){
	node *p;
	p = new  node;
	if(p==NULL){
		cout<<"Khong du bo nho!";
		exit(1);
	}
	p->info = x;
	p->next = NULL;
	return p;
}

4. Thêm một node vào danh sách

Thêm một node vào đầu danh sách

Trường hợp 1: Nếu danh sách liên kết đơn rỗng thì node mới được xem là node đầu tiên và cũng là node cuối cùng.

Trường hợp 2: Nếu danh sách liên kết đơn không rỗng thì:

    • Cho con trỏ liên kết (next) của node mới trỏ vào node đầu tiên trong danh sách hiện tại.
    • Cho con trỏ đầu của danh sách liên kết đơn (*head) trỏ vào node mới.
void insertHead(sList &l, int x){
	node *p;
	p = createNode(x);
	if(p==NULL){
		cout<<"Khong tao duoc node!";
		exit(1);
	}
	if(l.head==NULL){//trường hợp danh sách rỗng
		l.head = l.tail = p;
	}else{//trường hợp danh sách không rỗng
		p->next = l.head;
		l.head = p;
	}
}

Thêm một node vào cuối danh sách

Trường hợp 1: Nếu danh sách liên kết đơn rỗng thì node mới được xem là node đầu tiên và cũng là node cuối cùng.

Trường hợp 2: Nếu danh sách liên kết đơn không rỗng thì:

    • Cho con trỏ liên kết (next) của node cuối danh sách hiện tại trỏ đến đến node mới.
    • Cho con trỏ cuối của danh sách liên kết đơn (*tail) trỏ vào node mới.
void insertTail(sList &l, int x){
	node *p = createNode(x);
	if(p==NULL){
		cout<<"Khong tao duoc nut moi!";
		exit(1);
	}
	if (l.head==NULL){//trường hợp danh sách rỗng
		l.head =  l.tail = p ;
	}else{//trường hợp danh sách không rỗng
		l.tail->next = p;
		l.tail = p;
	}
}

Thêm một node p vào sau một node q trong danh sách

Cho con trỏ liên kết (next) của node p chỉ vào node sau của q.

Cho con trỏ liên kết của q chỉ vào node p.

Nếu q là nút cuối thì gán lại p là nút cuối.

Minh họa thêm node vào danh sách liên kết đơn
void insertAfter(sList &l, node *p, node *q){
	p->next = q->next;
	q->next = p;
	if (q == l.tail){
		l.tail = p;
	}
}

5. Duyệt các phần tử trong danh sách

Duyệt toàn bộ danh sách

void processList(sList &l){
	node *p;
	p = l.head;
	while (p!= NULL){
		cout<<p->info<<endl;//xuất giá trị trong node
		p = p->next;
	}
}

Tìm kiếm node có giá trị k trong danh sách

Hàm searchList() có kiểu trả về là con trỏ node. Nếu tìm thấy x thì node được trả về khác NULL, ngược lại node được trả về là NULL.

node* searchList(sList l, int k){	
	node *p;
	p = l.head;
	while((p!= NULL)&&(p->info != k)){
		p = p->next;
	}
	return p;
}

Hủy toàn bộ danh sách

Sử dụng lệnh delete để giải phóng bộ nhớ lưu trữ các node trong danh sách.

void deleteList(sList &l){
	node *p;
	while (l.head!= NULL){
		p = l.head;
		l.head = p->next;
		delete p;
	}
	l.tail = NULL;
}

6. Sắp xếp các node trong danh sách

Có thể sử dụng thuật toán sắp xếp chọn trực tiếp (Selection Sort) để sắp xếp danh sách liên kết đơn.

void List_Selection_Sort(sList &l){
	node *min;
	node *p, *q;
	p = l.head;
	while(p != l.tail){
		min = p; q = p->next;
		while(q != NULL){
			if(q->info < min->info){
				min = q;
			}
			q= q->next;
    	}
		swap(min->info, p->info);
		p = p->next; 
	}
}

7. Bài tập

Bên dưới là hình minh họa một danh sách liên kết đơn.

Ví dụ một danh sách liên kết đơn

Hãy viết chương trình với C++ để thao tác với danh sách liên kết đơn ở trên:

a. Tạo danh sách liên kết đơn như hình minh họa.

b. Thêm một node có giá trị là 9 vào đầu danh sách.

c. Xuất giá trị và địa chỉ của các node trong danh sách lên màn hình.

d. Sắp xếp danh sách theo thứ tự tăng dần các giá trị của các node.

e. Giải phóng bộ nhớ cho toàn bộ danh sách.

Mời bạn đánh giá bài viết
Bài trước và bài sau trong môn học<< Xây dựng danh sách liên kết đơn với con trỏ (pointer)Xây dựng danh sách liên kết kép (Doubly Linked List) với con trỏ (pointer) >>
Chia sẻ trên mạng xã hội:

Tác giả Vinh Lê

Vinh Lê hiện đang là biên tập viên tại Góc Học IT.

Bài viết của Vinh Lê

Trả lời

Lưu ý:

1) Vui lòng bình luận bằng tiếng Việt có dấu.

2) Khuyến khích sử dụng tên thật và địa chỉ email chính xác.

3) Mọi bình luận trái quy định sẽ bị xóa bỏ.