Xây dựng danh sách liên kết kép (Doubly Linked List) với con trỏ (pointer)

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

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

Danh sách liên kết kép (doubly linked list) có đặc điểm là mỗi phần tử liên kết với phần tử đứng trước và đứng sau nó trong danh sách.

Doubly linked list

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

struct dNode{
	int info;
	struct dNode *pre;
	struct dNode *next;
};

struct dList{
	dNode *head;
	dNode *tail;
};

Mỗi node có thêm một con trỏ *pre để lưu trữ địa chỉ của node đứng trước nó. Đó là sự khác biệt lớn nhất của danh sách liên kết kếp so với danh sách liên kết đơn.

2. Các thao tác cơ bản trên danh sách liên kết kép

Cũng giống như danh sách liên kết đơn, danh sách liên kết kép cũng có những thao tác cơ bản như là thêm node, hủy node, duyệt danh sách, sắp xếp node,…

Tạo một danh sách liên kết kép rỗng

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

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

dNode* createdNode(int x){
	dNode *p;
	p = new dNode;
	if(p==NULL){
		cout<<"khong con du bo nho";
		exit(1);
	}else{
		p->info=x;
		p->next=NULL;
		p->pre=NULL;
		return p;
	}
}

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

void insertHead(dList &l, int x){
	dNode *p;
	p = createdNode(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 = p;
		l.tail = l.head;
	}else{//trường hợp danh sách không rỗng
		p->next = l.head;
		l.head->pre = p;
		l.head = p;
	}
}

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

void insertTail(dList &l, int x){
	dNode *p = createdNode(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 = p;
		l.tail = l.head;
	}else{//trường hợp danh sách không rỗng
		p->pre=l.tail;
		l.tail->next=p;
		l.tail=p;
	}
}

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

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

Hủy node đầu tiên trong danh sách

void DeleteFirst(dList &l){
	dNode *p;
	if(l.head!=NULL){
		p=l.head;
		l.head=l.head->next;
		l.head->pre=NULL;
		delete p;
		if(l.head==NULL){
			l.tail=NULL;
		}
	}
}

Hủy node cuối cùng trong danh sách

void DeleteEnd(dList &l ){
	dNode *p;
	if(l.head!=NULL){
		p=l.tail;
		l.tail=l.tail->pre;
		l.tail->next=NULL;
		delete p;
		if(l.tail==NULL){
			l.head=NULL;
		}
	}
}

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

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

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

void List_Interchange_Sort(dList &l){
	dNode *p,*q;
	p=l.head;
	while(p!=l.tail){
		q=p->next;
		while(q!=NULL){
			if(p->info>q->info){
				swap(p->info, q->info);
			}
			q=q->next;
		}
		p=p->next;
	}
}

3. Bài tập

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

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

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

a. Tạo danh sách liên kết kép 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<< Các thao tác cơ bản trên danh sách liên kết đơn (Singly Linked List)Ngăn xếp (stack) là gì? Cách xây dựng ngăn xếp >>
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ỏ.